Syllabus Analysis and Design of Algorithms - (BE04000241) Total Credits = TH / 30 Assessment Pattern and Marks Total Marks Theory Tutorial / Practical ESE (E) PA (M) PA (I) PBL (I) ESE (V) 04 70 30 20 30 50 200 Sr. No. Course Content 1. Introduction and Analysis of Algorithm : Introduction to algorithm, Properties of good algorithm, Average, Best and worst case analysis, Asymptotic Notations (Big Oh, Big Theta, Big Omega), Disjoint set operations, Union and find algorithms. (Chapter - 1) 2. Analysis of Sorting Algorithms : Comparison based sorting : Bubble sort, Selection sort, Insertion sort, Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort. (Chapter - 2) 3. Divide and Conquer : Introduction, General method, Recurrence and different methods to solve recurrence, Problem solving using Divide and Conquer : Binomial Coefficient, Binary Search, Max-Min problem, Merge Sort, Quick Sort, Quick sort using median of three, Matrix Multiplication, Exponential. (Chapter - 3) 4. Dynamic Programming : Introduction, General method, Elements of Dynamic Programming, The Principle of Optimality. Problem Solving using Dynamic Programming : Binomial Coefficient, Making Change Problem, Knapsack problem, Matrix chain multiplication, Longest Common Subsequence, Shortest Common Supersequence. (Chapter - 4) 5. Greedy Algorithm : Introduction, General method, Characteristics of greedy algorithms, Elements of greedy strategy. Problem solving using Greedy method : Making change problem, Activity selection problem, Knapsack problem (0/1 and Fractional), Job Scheduling Problem. (Chapter - 5) 6. Graph Algorithms : Introduction, Types of graph, Representation Graph, Traversing Graphs : Depth First Search, and Breath First Search, Topological sort, Strongly Connected components. Problem solving : Finding articulation point, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm) using greedy approach, Single pair shortest path using greedy method, All Points Shortest path using Dynamic Programming. (Chapter - 6) 7. Backtracking : Introduction, General method, n-queen problem, Sum of subset problem, Graph coloring problem, Hamiltonian cycle problem. Branch and Bound : General method, LC branch and bound, FIFO branch and bound, Traveling salesman problem, Knapsack problem. (Chapter - 7) 8. Introduction to NP-Completeness : The class P and NP, Polynomial reduction, NP- Complete Problems, NP-Hard Problems. (Chapter - 8)
