DESIGN AND ANALYSIS OF ALGORITHMS-18CS412

Unit-1 --> DIVIDE AND CONQUER TECHNIQUE

• Algorithm Analysis Framework
• Asymptotic Notations and Basic Efficiency Classes
• Analysis of Non-recursive and Recursive Algorithms
• Divide and Conquer: Merge Sort
• Quick Sort
• Strassen’s Matrix Multiplication.

Unit-2 --> DECREASE AND CONQUER TECHNIQUE

• Depth First Search and Breadth First Search
• Decrease and Conquer: Insertion sort
• Binary Search
• Selection Problem
• Transform and Conquer: Presorting
• Balanced Search Trees: AVL tree
• 2-3 Tree.

Unit-3 --> DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE

• Dynamic Programming: Knapsack Problem
• Optimal Binary Search Trees
• Warshall’s Algorithm
• Floyd’s Algorithm
• Greedy Technique: Prim’s Algorithm
• Kruskal’s Algorithm
• Dijkstra’s Algorithm
• Huffman Trees and Codes.

Unit-4 --> BACKTRACKING,BRANCH AND BOUND TECHNIQUES

• Backtracking: 8-Queens
• Hamiltonian Circuit
• Sum of Subset
• Graph Coloring
• Branch and Bound: Assignment Problem
• Knapsack Problem
• Traveling Salesman Problem

Unit-5 --> NP PROBLEMS AND APPROXIMATION ALGORITHMS

• P and NP Problems
• NP Complete Problems
• Approximation Algorithms for NP Hard Problems
• Travelling Salesman Problem: Nearest Neighbor Algorithm
• Multifragment Heuristic Algorithm
• Knapsack Problem.

↩