nam a22 7a 4500 OSt 20200306132140.0 200306b xxu||||| |||| 00| 0 eng d 9789350164693 AEF 23rd ed. 005.1 DEO Deore, Y. A. 1317 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 Computer algorithms 1327 FYMSc-Sem -I 1149 Algorithms 1328 Computer science 1329 Chaudhari, P. P. 1151 Paatil, S. 1152 ddc BK 7928 7928 0 0 ddc 0 0 AEF AEF 2020-03-03 Bill No. : 1767 dated 01-03-2020 206.25 005.15 SAR 5201 2020-03-06 1 275.00 2020-03-06 BK 0 0 ddc 0 0 AEF AEF 2020-03-03 Bill No. : 1767 dated 01-03-2020 206.25 005.15 SAR 5202 2020-03-06 2 275.00 2020-03-06 BK 0 0 ddc 0 0 AEF AEF 2020-03-03 Bill No. : 1767 dated 01-03-2020 206.25 005.15 SAR 5203 2020-03-06 3 275.00 2020-03-06 BK 0 0 ddc 0 0 AEF AEF 2020-03-03 Bill No. : 1767 dated 01-03-2020 206.25 005.15 SAR 5204 2020-03-06 4 275.00 2020-03-06 BK 0 0 ddc 0 0 AEF AEF 2020-03-03 Bill No. : 1767 dated 01-03-2020 206.25 005.15 SAR 5205 2020-03-06 5 275.00 2020-03-06 BK