Deore, Y. A.
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
9789350164693
Computer algorithms
FYMSc-Sem -I
Algorithms
Computer science
005.1 / DEO
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
9789350164693
Computer algorithms
FYMSc-Sem -I
Algorithms
Computer science
005.1 / DEO