Design and Analysis of Algorithms
0%
Course Title: Design and Analysis of Algorithms
Course No: CSC325
Nature of the Course: Theory + Lab
Semester: 5
Full Marks: 60 + 20 + 20
Pass Marks: 24 + 8 + 8
Credit Hours: 3
Course Description
Course Objectives
Course Contents
1.1. Algorithm Analysis Basics
- Algorithm and its properties
- RAM model
- Time and Space Complexity
- Detailed analysis of algorithms (Like factorial algorithm)
- Concept of Aggregate Analysis
1.2. Asymptotic Notations
- Big-O, Big-Ω and Big-Θ Notations, their Geometrical Interpretation and Examples
1.3. Recurrences
- Recursive Algorithms and Recurrence Relations
- Solving Recurrences (Recursion Tree Method, Substitution Method, Application of Masters Theorem)
2.1. Basic Algorithms
- Algorithm for GCD, Fibonacci Number and analysis of their time and space complexity
2.2. Searching Algorithms
- Sequential Search and its analysis
2.3. Sorting Algorithms
- Bubble, Selection, and Insertion Sort and their Analysis
3.1. Searching Algorithms
- Binary Search, Min-Max Finding and their Analysis
3.2. 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
3.3. Order Statistics
- Selection in Expected Linear Time, Selection in Worst Case Linear Time and their Analysis
4. Greedy Algorithms
6 hrs
4.1. Greedy Strategy Fundamentals
- Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy
4.2. Greedy Algorithms
- Fractional Knapsack
- Job sequencing with Deadlines
- Kruskal's Algorithm
- Prims Algorithm
- Dijkstra's Algorithm
- Analysis of Greedy Algorithms
4.3. Huffman Coding
- Purpose of Huffman Coding
- Prefix Codes
- Huffman Coding Algorithm and its Analysis
5.1. Dynamic Programming Fundamentals
- Greedy Algorithms vs Dynamic Programming
- Recursion vs Dynamic Programming
- Elements of DP Strategy
5.2. DP Algorithms
- Matrix Chain Multiplication
- String Editing
- Zero-One Knapsack Problem
- Floyd Warshall Algorithm
- Travelling Salesman Problem
- Analysis of DP Algorithms
5.3. Memoization Strategy
- Memoization Strategy, Dynamic Programming vs Memoization
6. Backtracking
5 hrs
6.1. Backtracking Fundamentals
- Concept of Backtracking, Recursion vs Backtracking
6.2. Backtracking Algorithms
- Subset-sum Problem, Zero-one Knapsack Problem, N-queen Problem and their Analysis
7.1. Basic Number Theory
- Number Theoretic Notations, Euclid's and Extended Euclid's Algorithms and their Analysis
7.2. Modular Arithmetic and Primality
- Solving Modular Linear Equations, Chinese Remainder Theorem, Primality Testing: Miller-Rabin Randomized Primality Test and their Analysis
8. NP Completeness
5 hrs
8.1. Complexity Theory Fundamentals
- Tractable and Intractable Problems, Concept of Polynomial Time and Super Polynomial Time Complexity
- Complexity Classes: P, NP, NP-Hard and NP-Complete
8.2. NP-Completeness Theory
- NP Complete Problems, NP Completeness and Reducibility, Cooks Theorem, Proofs of NP Completeness (CNF-SAT, Vertex Cover and Subset Sum)
8.3. Approximation Algorithms
- Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem
Laboratory Works
- 1.Implement comparison sorting algorithms and perform their empirical analysis
- 2.Implement divide-and-conquer sorting algorithms and perform their empirical analysis
- 3.Implement algorithms for order statistics and perform their empirical analysis
- 4.Implement algorithms by using Greedy, DP and backtracking paradigm
- 5.Implement NP-complete problems and realize their hardness
Reference Books
- 1.Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein, Introduction to Algorithms, Third Edition, The MIT Press, 2009
- 2.Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, Computer Algorithms, Second Edition, Silicon Press, 2007
- 3.Kleinberg, Jon, and Eva Tardos, Algorithm Design, Addison-Wesley, First Edition, 2005