Part A
Algorithms:Analyzing algorithms, order arithmetic, Time and space complexity of an algorithm, comparing the performance of different algorithms for the same problem. Different orders of growth. Asymptotic notation. Polynomial vs. Exponential running time. Principles of Algorithm Design. Mathematical analysis of Recursive and Non-recursive algorithms. [CO1]
Basic Algorithm Design Techniques: Divide-and-conquer, Greedy approach, Randomizationand dynamic programming. [CO2] [CO4]
Example problems on Backtracking: n-Queens problem, Hamiltonian Circuit Problem, Subset – Sum Problem. Branch-and- Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem.
Part B
Sorting and searching: Insertion and selection sort, Binary search in an ordered array. Sorting algorithms such as Merge sort, Quick sort, Heap sort, Radix Sort, and Bubble sort with analysis of their running times. Lower bound on sorting. Exhaustive search and String Matching. [CO3] [CO4]
Graphs and NP-completeness: Graph traversal: Breadth-First Search(BFS) and Depth-First Search (DFS). Applications of BFS and DFS. Shortest paths in graphs: Dijkstra algorithm. Definition of class NP, P, NP-hard and NP-complete problems. [CO5]