DAA

Course Title: Data and Analysis of Algorithm
 Course No. CSC 303
 Nature of Course: Theory (3Hrs.)
 Semester: V

1. Unit 1 (10 Hrs.)
• Algorithm Analysis: worst, best and average cases, space and time complexities. Mathematical background: asymptotic behavior, solving recurrences.


• Data Structures Review: linear data structures, hierarchical data structures, data structures for representing graphs and their properties. Search structures: heaps, balanced trees, hash tables.


2. Unit 2 (14 Hrs.)
• Divide and Conquer: Concepts, applications, sorting problems(quick, merge), searching (binary), median finding problem and general order statistics, matrix multiplications.


• Greedy Paradigm: Concepts, applications, Knapsack problem, job sequencing, Huffman codes.


• Dynamic Programming: Concepts, applications, Knapsack problem, longest common subsequence, matrix chain multiplications.


3. Unit 3 (21 Hrs.)


• Graph Algorithms: breadth-first and depth-first search and their applications, minimum spanning trees (Prim's and Kruskal's algorithms), shortest path problems (Dijkstra's and flyod's algorithms), algorithm for directed acyclic graphs (DAGs).


• Geometric Algorithms: Concepts, polygon triangulation, Convex hull computation.


• NP Completeness: Introduction, class P and NP, cooks theorem, NP complete problems: vertex cover problem.


• Introductions: Randomized algorithms concepts, randomized quick sort, approximation algorithms concepts, vertex cover problem.


Download Design and Analysis of Algorithm TU Solution



Download Design and Analysis of Algorithm Exam oriented question