CSPC-413 Design and Analysis of Algorithm
Teaching Scheme			Credit	Marks Distribution			Duration of End Semester Examination
L	T	P		Internal Assessment	End Semester Examination	Total
3	1	0	4	Maximum Marks: 40	Maximum Marks: 60	100	3 Hours
				Minimum Marks: 16	Minimum Marks: 24	40

Unit-I

Introduction: Algorithms Introduction: Algorithm Design paradigms- motivation, concept of algorithmic efficiency, run time analysis of algorithms, Asymptotic Notations.

Divide and Conquer Approach: Structure of divide-and-conquer algorithms: sets and disjoint sets: Union and Find algorithms, quick sort, Finding the maximum and minimum, Quick Sort, Merge sort, Heap and heap sort.

Unit-II

Greedy Algorithms: Optimal storage on tapes, Knapsack problem, Job sequencing with deadlines, Minimum Spanning trees: Prim’s algorithm and Kruskal’s algorithm, Huffman codes.

Graph Algorithms: Representation of graphs, BFS, DFS, Topological sort, strongly connected components; single source shortest paths: Bellmen-Ford algorithm, Dijkstra’s algorithm; All pairs shortest path: The Warshall’s algorithm.

Unit-III

Dynamic Programming: Overview, difference between dynamic programming and divide and conquer, Matrix chain multiplication, Traveling salesman Problem, longest Common sequence, 0/1 knapsack.

Backtracking: 8-Queen Problem, Sum of subsets, graph colouring, Hamiltonian cycles.

Unit-IV

Branch and Bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application: 0/1 Knapsack problem, Traveling Salesman Problem.

Computational Complexity: Complexity measures, Polynomial vs. nonpolynomial time complexity; NP-hard and NP-complete classes, examples.