ANALYSIS OF ALGORITHMS
ENCT 388
Lecture :3 Year : III
Tutorial :2 Part : II
Practical :1
Course Objectives:
The objective of this course is to provide students with a strong foundation in the analysis
of algorithm efficiency and computational complexity. It aims to develop understanding
of key algorithm design paradigms, including divide-and-conquer, greedy methods,
dynamic programming, and backtracking, and covers fundamental concepts of NP-
completeness and approximation algorithms.
1 Introduction to Algorithm Analysis (5 hours)
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
1.5.1 Recursion tree method
1.5.2 Substitution method
1.5.3 Using masters theorem
2 Iterative and Numeric Algorithms (8 hours)
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 hours)
3.1 Binary search, min max finding algorithm
3.2 Analysis of sorting algorithms
3.2.1 Merge sort
3.2.2 Heap sort
3.2.3 Quick sort
3.2.4 Randomized quick sort
3.3 Order statistics
3.3.1 Selection in expected linear time
3.3.2 Selection in worst case linear time
4 Greedy Algorithms (7 hours)
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 hours)
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 hours)
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 hours)
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
Tutorial (30 hours)
1. Algorithm analysis
2. Iterative and numeric algorithms
3. Divide and conquer algorithms
4. Greedy algorithms
5. Dynamic programming
6. Backtracking techniques
7. NP-Hard and NP-complete problems
Practical (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
Final Exam
The questions will cover all the chapters in the syllabus. The evaluation scheme will be
as indicated in the table below:
Chapter Hours Marks distribution*
1 5 6
2 8 10
3 8 11
4 7 9
5 8 12
6 4 5
7 5 7
Total 45 60
* There may be minor deviation in marks distribution.
References
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.