Design and Analysis of Algorithms Syllabus (CSC 314) – TU BSc CSIT 5th Semester

Tribhuvan University
Institute of Science and Technology
Bachelor of Science in Computer Science and Information Technology

Course Description: This course introduces basic elements of the design and analysis of computer algorithms. Topics include asymptotic notations and analysis, divide and conquer strategy, greedy methods, dynamic programming, basic graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, one or more representative problems and their algorithms shall be discussed.

Course Objective:

• Analyze the asymptotic performance of algorithms
• Demonstrate a familiarity with major algorithm design techniques
• Apply important algorithmic design paradigms and methods of analysis
• Solve simple to moderately difficult algorithmic problems arising in applications
• Demonstrate the hardness of simple NP-complete problems

Course Contents

Unit 1. Foundation of Algorithm Analysis (4 Hrs.)

• 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 Master’s Theorem)

Unit 2. Iterative Algorithms (4 Hrs.)

• 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

Unit 3. Divide and Conquer Algorithms (8 Hrs.)

• 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

Unit 4. Greedy Algorithms (6 Hrs.)

• Optimization Problems and Optimal Solution, Introduction of Greedy Algorithms, Elements of Greedy Strategy
• Greedy Algorithms: Fractional Knapsack, Job Sequencing with Deadlines, Kruskal’s Algorithm, Prim’s Algorithm, Dijkstra’s Algorithm and their Analysis
• Huffman Coding: Purpose of Huffman Coding, Prefix Codes, Huffman Coding Algorithm and its Analysis

Unit 5. Dynamic Programming (8 Hrs.)

• 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-Warshall Algorithm, Travelling Salesman Problem and their Analysis
• Memoization Strategy, Dynamic Programming vs Memoization

Unit 6. Backtracking (5 Hrs.)

• Concept of Backtracking, Recursion vs Backtracking
• Backtracking Algorithms: Subset-sum Problem, Zero-one Knapsack Problem, N-queen Problem and their Analysis

Unit 7. Number Theoretic Algorithms (5 Hrs.)

• Number Theoretic Notations, Euclid’s and Extended Euclid’s Algorithms and their Analysis
• Solving Modular Linear Equations, Chinese Remainder Theorem, Primality Testing: Miller-Rabin Randomized Primality Test and their Analysis

Unit 8. NP Completeness (5 Hrs.)

• 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, Cook’s Theorem, Proofs of NP Completeness (CNF SAT, Vertex Cover and Subset Sum)
• Approximation Algorithms: Concept, Vertex Cover Problem, Subset Sum Problem

Laboratory Works

This course can be learnt effectively only if focus is given to the practical aspects of the algorithms and techniques discussed in class. Students should implement the following algorithms in C/C++ and analyze their time and space complexity:

• Basic iterative algorithms: GCD algorithm, Fibonacci sequences, Sequential and Binary Search
• Basic iterative sorting algorithms: Bubble Sort, Selection Sort, Insertion Sort
• Binary Search with divide and conquer approach
• Merge Sort, Heap Sort, Quick Sort, Randomized Quick Sort
• Selection problem with divide and conquer approach
• Fractional Knapsack Problem, Job Sequencing with Deadlines, Kruskal’s Algorithm, Prim’s Algorithm, Dijkstra’s Algorithm
• Dynamic programming algorithms
• Algorithms using the backtracking approach
• Approximation algorithms

Text 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. Jon Kleinberg and Éva Tardos, “Algorithm Design”, First Edition, Addison-Wesley, 2005