[go: up one dir, main page]
Scribd
Upload
36 views1 page

DAA Syllabus ESA

The syllabus for the Design and Analysis of Algorithms course covers foundational concepts such as asymptotic notations and complexity analysis, as well as various algorithmic paradigms including brute-force, divide-and-conquer, greedy, dynamic programming, backtracking, and branch-and-bound. It also includes a module on graph algorithms, focusing on traversal, minimum spanning trees, shortest path algorithms, and topological sorting. Finally, the syllabus addresses problem reducibility and the classifications of P, NP, NP-complete, and NP-hard problems.

Uploaded by

gopogo56
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
36 views1 page

DAA Syllabus ESA

The syllabus for the Design and Analysis of Algorithms course covers foundational concepts such as asymptotic notations and complexity analysis, as well as various algorithmic paradigms including brute-force, divide-and-conquer, greedy, dynamic programming, backtracking, and branch-and-bound. It also includes a module on graph algorithms, focusing on traversal, minimum spanning trees, shortest path algorithms, and topological sorting. Finally, the syllabus addresses problem reducibility and the classifications of P, NP, NP-complete, and NP-hard problems.

Uploaded by

gopogo56
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

Syllabus for IA-2 and ESA

Design and Analysis of Algorithms (TIU-UCS-T321)

Module-1: Foundation of Algorithm & Analysis


 Asymptotic notations and their significance: Bog-Oh, Big-Omega, Big-Theta (with numerical
problem solving)
 Complexity analysis of algorithms: best case, worst case and average case with example of
Merge sort, Quick sort and Heap sort (with example)
 Analysis of recursive algorithms: Substitution method, Recursion tree method and Masters’
theorem (with numerical problem solving)

Module-2: Algorithmic Paradigms


Classification of algorithm design techniques for problem solving:
 Brute-force: General overview
 Divide-and-Conquer: 1. Merge Sort, 2. Quick Sort, 3. Binary search, 4. Maximum and minimum
finding from a set of numbers, 5. Strassen's matrix multiplication
 Greedy: 1. Knapsack problem, 2. Huffman tree & encoding scheme, 3. Minimal Spanning Tree -
Prim's and Kruskal's algorithm, 4. Scheduling problems (with and without deadline), 5. Travelling
salesman problem (TSP), 6. Optimal merge problem
 Dynamic Programming: 1. Fibonacci series, 2. Multistage graph problem, 3. Chain matrix
multiplication.
 Backtracking: N-Queen problem.
 Branch-and-Bound: 8-puzzle problem.

Module-3: Graph Algorithms:


 Traversal algorithms: DFS, BFS - concept, complexity analysis and applications
 Minimum Spanning Tree finding algorithm: Prim’s, Kruskal - concept, complexity analysis
 Shortest path finding algorithm: single source and all pairs – Dijkstra, Bellman-Ford and Floyd-
Warshall
 Topological sort

Module-4: Problem Reducibility and NP-completeness:


P, NP, NP-complete and NP-hard

You might also like