BSc CSIT · Semester V
Design and Analysis of Algorithms syllabus
Official TU syllabus for Design and Analysis of Algorithms (CSC325): 8 units, 28 topics, 3 credit hours. Every unit links to its notes and solved questions.
1
Foundation of Algorithm Analysis
4h · 13 Q- Algorithm and its properties
- RAM model
- Time and Space Complexity
- detailed analysis of algorithms (Like factorial algorithm)
- Concept of Aggregate Analysis
- Asymptotic Notations: Big-O, Big-Ω and Big-Ө Notations their Geometrical Interpretation and Examples
- Recurrences: Recursive Algorithms and Recurrence Relations
- Solving Recurrences (Recursion Tree Method, Substitution Method, Application of Masters Theorem)
2
Iterative Algorithms
4h · 7 Q- Basic Algorithms: Algorithm for GCD, Fibonacci Number and analysis of their time and space complexity
- Searching Algorithms: Sequential Search and its analysis
- Sorting Algorithms: Bubble, Selection, and Insertion Sort and their Analysis
3
Divide and Conquer Algorithms
8h · 10 Q- Searching Algorithms: Binary Search, Min-Max Finding and their Analysis
- Sorting Algorithms: Merge Sort and Analysis, Quick Sort and Analysis (Best Case, Worst Case and Average Case), Heap Sort (Heapify, Build Heap and Heap Sort Algorithms and their Analysis), Randomized Quick sort and its Analysis
- Order Statistics: Selection in Expected Linear Time, Selection in Worst Case Linear Time and their Analysis
4
Greedy Algorithms
6h · 10 Q- Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy
- Greedy Algorithms: Fractional Knapsack, Job sequencing with Deadlines, Kruskal's Algorithm, Prims Algorithm, Dijkstra's Algorithm and their Analysis
- Huffman Coding: Purpose of Huffman Coding, Prefix Codes, Huffman Coding Algorithm and its Analysis
5
Dynamic Programming
8h · 10 Q- Greedy Algorithms vs Dynamic Programming, Recursion vs Dynamic Programming, Elements of DP Strategy
- DP Algorithms: Matrix Chain Multiplication, String Editing, Zero-One Knapsack Problem, Floyd Warshwall Algorithm, Travelling Salesman Problem and their Analysis
- Memoization Strategy, Dynamic Programming vs Memoization
6
Backtracking
5h · 9 Q- Concept of Backtracking, Recursion vs Backtracking
- Backtracking Algorithms: Subset-sum Problem, Zero-one Knapsack Problem, N-queen Problem and their Analysis
7
Number Theoretic Algorithms
5h · 4 Q- Number Theoretic Notations, Euclid's and Extended Euclid's Algorithms and their Analysis
- Solving Modular Linear Equations, Chinese Remainder Theorem, Primility Testing: Miller-Rabin Randomized Primility Test and their Analysis
8
NP Completeness
5h · 9 Q- Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity
- Complexity Classes: P, NP, NP-Hard and NP-Complete
- NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem, Proofs of NP Completeness (CNF-SAT, Vertex Cover and Subset Sum)
- Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem
Textbooks and references
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, "Introduction to algorithms", Third Edition.. The MIT Press, 2009.
- Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekiaran, "Computer Algorithms", Second Edition, Silicon Press, 2007.
- Kleinberg, Jon, and Eva Tardos, "Algorithm Design", Addison-Wesley, First Edition, 2005
Study CSC325 the smart way
Solved questions, flashcards & practice