Text book of design and analysis of algorithm M. Sc.(Sem-I) (Computer Science) According to new CBCS syllabus w. e. f. 2019-20
- 1st ed.
- Pune: Vision publication, 2019
- 240 p. : 21 cm
1. Basics of Algorithms • Algorithm definition and characteristics • Space complexity • Time complexity, worst case-best case-average case • complexity, asymptotic notation • Recursive and non-recursive algorithms • Sorting algorithms (insertion sort, heap sort, bubble sort) • Sorting in linear time: counting sort, the concept of the bucket and radix sort • Searching algorithms: Linear, Binary
2. Divide and conquer strategy • A general method, control abstraction • Binary search • Merge sort, Quicksort • Comparison between Traditional Method of Matrix Multiplication vs. Strassen’s Matrix Multiplication
3. Greedy Method • Knapsack problem • Job sequencing with deadlines, • Minimum-cost spanning trees: Kruskal and Prim’s algorithm • Optimal storage on tapes • Optimal merge patterns • Huffman coding • Shortest Path: Dijkstra’s Algorithm
4. Dynamic Programming • Principle of optimality • Matrix chain multiplication • 0/1 Knapsack Problem i) Merge & Purge ii) Functional Method • Bellman-Ford Algorithm • All pairs Shortest Path Floyd- Warshall Algorithm • Longest common subsequence, • String editing, Travelling Salesperson problem
5. Decrease and Conquer • Definition of Graph Representation of graph • By Constant - DFS and BFS • Topological sorting • Connected components and spanning trees • By Variable Size decrease Euclid’s algorithm • Articulation Point and Bridge edge
6. Backtracking • General method • Fixed Tuple vs. Variable Tuple Formulation • n- Queen’s problem • Graph colouring problem • Hamiltonian cycle • Sum of subsets
7. Branch and Bound • Introduction • FIFO BB Search, LIFO Search • Definitions of LCBB Search • Bounding Function, Ranking Function • Travelling Salesman problem Using Variable tuple • Formulation using LCBB • 0/1 knapsack problem using LCBB
8. Problem Classification • Nondeterministic algorithm • The class of P, NP, NP-hard and NP-Complete problems • Cook’s theorem