T M. Sc.(Sem-I) (Computer Science) According to new CBCS syllabus w. e. f. 2019-20 Deore, Y. A. creator Chaudhari, P. P. Paatil, S. text xxu Pune Vision publication 2019 1st ed. monographic eng

print

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 FYMSc-Sem -I Algorithms Computer science 005.1 DEO 9789350164693 200306 20200306132140.0