Page no:86
IT44 Design And Analysis of Algorithms Objective : To understand and learn advance algorithms and methods used in
computer science to create strong logic and problem solving approach in student. Sr. No. 1 Nos. of Session Reference Books
Chapter Details Introduction Algorithm, analysis, time complexity and space complexity, O-notation, Omega notation and Theta notation, Heaps and Heap sort, Sets and disjoint set, union and find algorithms. Sorting in linear time. Divide And Conquer Divide and Conquer: General Strategy, Exponentiation. Binary Search, Quick Sort and Merge Sort Greedy Method General Strategy, Knapsack problem, Job sequencing with Deadlines, Optimal merge patterns, Minimal Spanning Trees and Dijkstra’s algorithm. Dynamic Programming General Strategy, Multistage graphs, OBST, 0/1 Knapsack, Traveling Salesperson Problem, Flow Shop Scheduling Backtracking Backtracking: General Strategy, 8 Queen’s problem, Graph Coloring, Hamiltonian Cycles, 0/1 Knapsack Branch and Bound General Strategy, 0/1 Knapsack, Traveling Salesperson Problem
6
1,2
2
4
1,2
3
5
1,2
4
5
1,2
5
6
1,2
6
5
1,2
7 N NP-HARD AND NP-COMPLETE PROBLEMS Basic concepts, non-deterministics algorithms, NP-HARD and NP-COMPLETE classes, COOKS theorem
5
1,2