Analysis of Algorithms

Course Title: Analysis of Algorithms

Course No: ENCT388

Nature of the Course: Theory + Lab

Semester: 6

Full Marks: 60 + 40 + 25

Pass Marks: 24 + 16 + 10

Credit Hours: 3

Course Description

This course provides students with a strong foundation in the analysis of algorithm efficiency and computational complexity. It covers key algorithm design paradigms including divide-and-conquer, greedy methods, dynamic programming, and backtracking, and covers fundamental concepts of NP-completeness and approximation algorithms.

Course Objectives

Upon completion, students will be able to:

Understand and apply key algorithm design paradigms including divide-and-conquer, greedy methods, dynamic programming, and backtracking
Analyze algorithm efficiency and computational complexity
Understand fundamental concepts of NP-completeness and approximation algorithms

Course Contents

1. Introduction to Algorithm Analysis

5 hrs6 marks

1.1. Algorithm and its properties, RAM model, time and space complexity, detailed analysis of algorithms, Concept of Aggregate Analysis

1.2. Asymptotic notations (Big-O, Big-Ω and Big-Θ), their geometrical interpretations and examples

1.3. Concept of best case, average case and worst case performance of an algorithm

1.4. Modeling algorithms by recurrence relation

1.5. Solving recurrence relation for evaluating computational complexity

Recursion tree method

Substitution method

Using masters theorem

2. Iterative and Numeric Algorithms

8 hrs10 marks

2.1. Algorithm for GCD and Fibonacci number

2.2. Sequential search

2.3. Review of bubble sort, selection sort, and insertion sort algorithms

2.4. Number theoretic notations

2.5. Euclid's and Extended Euclid's algorithms

2.6. Solving modular linear equations using Chinese remainder theorem

2.7. Fermat's theorem

2.8. Miller-Rabin randomized primility test and algorithm

3. Divide and Conquer Algorithms

8 hrs11 marks

3.1. Binary search, min max finding algorithm

3.2. Analysis of sorting algorithms

Merge sort

Heap sort

Quick sort

Randomized quick sort

3.3. Order statistics

Selection in expected linear time

Selection in worst case linear time

4. Greedy Algorithms

7 hrs9 marks

4.1. Basic concepts

4.2. Fractional knapsack problem

4.3. Job sequencing with deadlines

4.4. Analysis of minimum spanning trees related algorithms

4.5. Analysis of single source shortest path algorithm

5. Dynamic Programming

8 hrs12 marks

5.1. Basic concepts

5.2. All pair shortest path algorithm

5.3. Travelling salesperson problem

5.4. String editing

5.5. 0/1 knapsack problem using dynamic programming

5.6. Matrix chain multiplication

5.7. Flow shop scheduling

6. Backtracking Techniques

4 hrs5 marks

6.1. Basic concepts

6.2. The N-Queen problem

6.3. Sum of subsets

6.4. Graph coloring

6.5. Hamiltonian cycles

6.6. 0/1 knapsack problem using backtracking approach

7. NP-Hard and NP-Complete Problems

5 hrs7 marks

7.1. Basic concepts

7.2. Cook's theorem

7.3. NP-Hard graph problems

7.4. NP-Hard scheduling problems

7.5. NP-Hard code generation problems

7.6. Simplified NP-hard problems

7.7. Approximation algorithms: ε-approximation, polynomial time approximation scheme, probabilistically good algorithms

7.8. Vertex cover problem, subset sum problem

Laboratory Works

Practical sessions covering implementation and complexity analysis of iterative, numeric, recursive, greedy, divide-and-conquer, dynamic programming, and backtracking algorithms. (15 hours)

1.Implementation and complexity analysis of iterative, numeric and recursive algorithms
2.Implementation and complexity analysis of greedy algorithms
3.Implementation and complexity analysis of algorithms involving divide and conquer strategy
4.Implementation and complexity analysis of algorithms based on dynamic programming
5.Implementation and complexity analysis of algorithms using backtracking concept

Text Books

1.Horowitz, E., Sahni, S., Rajasekaran, S. (2007). Fundamentals of computer algorithms. Universities Press.
2.Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. (2022). Introduction to algorithms. MIT Press.
3.Kleinberg, J., Tardos, É. (2006). Algorithm design. Pearson.
4.Skiena, S. S. (2020). The algorithm design manual. Springer.
5.Dasgupta, S., Papadimitriou, C. H., Vazirani, U. V. (2006). Algorithms. McGraw-Hill Education.

Notes:

This syllabus follows the official BCT curriculum of Tribhuwan University. In case of any doubt or revision, the university's published syllabus shall be considered authoritative. https://ioe.tu.edu.np/pages/computer-engineering-curriculum-structure-2635

Design and Analysis of Algorithm