DESIGN AND ANALYSIS OF ALGORITHMS
Subject Code:18CS42
CIE Marks:40
SEE Marks:60
Number of Contact Hours/Week:3:2:0
Total Number of Contact Hours:50
Exam Hours:3 Hrs
CREDITS –4
Course Learning Objectives: This course (18CS42) will enable students to:
• Explain various computational problem-solving techniques.• Apply appropriate methods to solve a given problem.
• Describe various methods of algorithm analysis.
Module 1
Introduction:What is an Algorithm? (T2:1.1), Algorithm Specification (T2:1.2), Analysis Framework (T1:2.1), Performance Analysis: Space complexity, Time complexity (T2:1.3). Asymptotic Notations: Big-Oh notation (O), Omega notation (?), Theta notation (?), and Little-oh notation (o), Mathematical analysis of Non-Recursive and recursive Algorithms with Examples (T1:2.2, 2.3, 2.4). Important Problem Types: Sorting, Searching, String processing, Graph Problems, Combinatorial Problems. Fundamental Data Structures: Stacks, Queues, Graphs, Trees, Sets and Dictionaries. (T1:1.3,1.4).
Click here to download Module-1
Module 2
Divide and Conquer:A general method, Binary search, Recurrence equation for divide and conquer, Finding the maximum and minimum (T2:3.1, 3.3, 3.4), Merge sort, Quicksort (T1:4.1, 4.2), Strassen’s matrix multiplication (T2:3.8), Advantages and Disadvantages of divide and conquer.
Decrease and Conquer Approach: Topological Sort. (T1:5.3).
Click here to download Module-2
Module 3
Greedy Method:General method, Coin Change Problem, Knapsack Problem, Job sequencing with deadlines (T2:4.1, 4.3, 4.5).Minimum cost spanning trees: Prim’s Algorithm, Kruskal’s Algorithm (T1:9.1, 9.2).
Single source shortest paths: Dijkstra's Algorithm (T1:9.3).
Optimal Tree problem: Huffman Trees and Codes (T1:9.4).
Transform and Conquer Approach: Heaps and Heap Sort (T1:6.4).
Click here to download Module-3
Module 4
Dynamic Programming: General method with Examples, Multistage Graphs (T2:5.1, 5.2).Transitive Closure: Warshall’s Algorithm, All Pairs Shortest Paths: Floyd's Algorithm, Optimal Binary Search Trees, Knapsack problem ((T1:8.2, 8.3, 8.4), Bellman-Ford Algorithm (T2:5.4), Travelling Sales Person problem (T2:5.9), Reliability design (T2:5.8).
Click here to download Module-4
Module 5
Backtracking: General method (T2:7.1), N-Queens problem (T1:12.1), Sum of subsets problem (T1:12.1), Graph coloring (T2:7.4), Hamiltonian cycles (T2:7.5). Branch and Bound: Assignment Problem, Travelling Sales Person problem (T1:12.2), 0/1 Knapsack problem (T2:8.2, T1:12.2): LC Branch and Bound solution (T2:8.2), FIFO Branch andBound solution (T2:8.2). NP-Complete and NP-Hard problems: Basic concepts, non-deterministic algorithms, P, NP, NP-Complete, and NP-Hard classes (T2:11.1).
Click here to download Module-5
Important Links:
Click here to download complete handwritten notes
Course Outcomes: The student will be able to :
• Describe a computational solution to well-known problems like searching, sorting, etc.• Estimate the computational complexity of different algorithms.
• Devise an algorithm using appropriate design strategies for problem-solving.
Question Paper Pattern:
• The question paper will have ten questions.• Each full Question consisting of 20 marks
• There will be 2 full questions (with a maximum of four sub-questions) from each module.
• Each full question will have sub questions covering all the topics under a module.
• The students will have to answer 5 full questions, selecting one full question from each module.
Textbooks:
1. Introduction to the Design and Analysis of Algorithms, Anany Levitin:, 2rd Edition, 2009. Pearson.2. Computer Algorithms/C++, Ellis Horowitz, Sartaj Sahni and Rajasekaran, 2nd Edition, 2014, Universities Press
Reference Books:
1. Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.2. Design and Analysis of Algorithms , S. Sridhar, Oxford (Higher Education).
0 Comments