Syllabus Design and Analysis of Algorithms - (BC04001011) Total Credits L + T + (PR/2) Assessment Pattern and Marks Total Marks C Theory Tutorial / Practical ESE (E) PA / CA (M) PA / CA (I) ESE (V) 4 70 30 20 30 150 Unit No. Content 1 Introduction : Role of Algorithms in Computing : Algorithms, Algorithms as a technology, Insertion sort, Analyzing algorithms, Designing algorithms, Growth of Functions : Asymptotic notation, Standard notations and common functions. (Chapter - 1) 2 Algorithms using Divide-and-Conquer, Probabilistic Analysis and Randomized Algorithms : The maximum-subarray problem, Strassen’s algorithm for matrix multiplication, The substitution method for solving recurrences, The recursion-tree method for solving recurrences, The master method for solving recurrences. (Chapter - 2) 3 Dynamic Programming : Rod cutting, Matrix-chain multiplication, Elements of dynamic programming, Longest common subsequence, Optimal binary search trees. (Chapter - 3) 4 Greedy Algorithms : Example-Knapsack Problem, Job Sequencing with Deadlines, An activity-selection problem, Elements of the greedy strategy, Huffman codes. Minimum Spanning Trees and Single-Source Shortest Paths : Growing a minimum spanning tree, The algorithms of Kruskal and Prim, The Bellman-Ford algorithm, Single-source shortest paths in directed acyclic graphs, Dijkstra’s algorithm. (Chapter - 4) 5 Backtracking, Branch and Bound Algorithms : BFS, DFS, 8-Queen problem, M-Coloring problem, Hamiltonian circuits; Branch-and-Bound algorithms : Examples : Shortest path ; 16-Puzzle and 8-Puzzle, 0/1 Knapsack problem, Traveling salesman problem. (Chapter - 5)
