Unit 1 Introduction and Analysis of Algorithm

4 lecture hours

• Introduction to algorithm
• Properties of good algorithm
• Best and worst case analysis
• Asymptotic Notations (Big Oh, Big Theta
• Big Omega)
• Disjoint set operations
• Union and find algorithms

Unit 2 Analysis of Sorting Algorithms

6 lecture hours

• Comparison based sorting: Bubble sort
• Selection sort
• Insertion sort
• Heap sort
• Sorting in linear time Bucket sort
• Radix sort and Counting sort

Unit 3 Divide and Conquer

6 lecture hours

• General method
• Recurrence and different methods to solve recurrence
• Problem solving using Divide and Conquer: Binomial Coefficient
• Binary Search
• Max-Min problem
• Merge Sort
• Quick Sort
• Quick sort using median of three
• Matrix Multiplication

Unit 4 Dynamic Programming

6 lecture hours

• General method
• Elements of Dynamic Programming
• The Principle of Optimality Problem Solving using Dynamic Programming: Binomial Coefficient
• Making Change Problem
• Knapsack problem
• Matrix chain multiplication
• Longest Common Subsequence
• Shortest Common Supersequence

Unit 5 Greedy Algorithm

5 lecture hours

• General method
• Characteristics of greedy algorithms
• Elements of greedy strategy Problem solving using Greedy method: Making change problem
• Activity selection problem
• Knapsack problem (0/1 and Fractional)
• Job Scheduling Problem

Unit 6 Graph Algorithms

6 lecture hours

• Types of graph
• Representation Graph
• Traversing Graphs: Depth First Search, and Breath First Search
• Topological sort
• Strongly Connected components
• Program Name: Bachelor of Engineering Level: UG Subject Code: BE04000241 Subject Name: Analysis and Design of Algorithms Problems solving: Finding articulation point
• Minimum Spanning trees (Kruskal’s algorithm
• Prim’s algorithm) using greedy approach
• Single pair shortest path using greedy method
• All Points Shortest path using Dynamic Programming

Unit 7 Backtracking

6 lecture hours

• General method
• n-queen problem
• Sum of subset problem
• Graph coloring problem
• Hamiltonian cycle problem
• Branch and Bound: General method
• LC branch and bound
• FIFO branch and bound
• Traveling salesman problem
• Knapsack problem

Unit 8 Introduction to NP-Completeness

• The class P and NP, Polynomial reduction
• NP- Complete Problems
• NP-Hard Problems. 3 05