COURSE PLAN - CST306 ALGORITHM ANALYSIS AND DESIGN S6 Computer Science &
Engineering February 2023
Format - F 7.5.1-01b
PLANNED ACTUAL UTILISATION
PLAN
DATES(P HOURS
NED REMARK
HOU TOPICS UTILISE
S
ERIODS) D
R
MODULE 1
1 Introduction to Algorithm Analysis: Characteristics
of Algorithms.
2 Criteria for Analysing Algorithms, Time and Space
Complexity - Best,Worst and Average Case
Complexities.
3 Asymptotic Notations - Properties of Big-Oh (O),
Big- Omega (Ω), BigTheta (Θ), Little-Oh (o) and
Little- Omega (ω).
4 Illustration of Asymptotic Notations
5 Classifying functions by their asymptotic growth
rate
6 Time and Space Complexity Calculation of
algorithms/code segments.
7 Analysis of Recursive Algorithms: Recurrence
Equations, Solving Recurrence Equations –
Iteration Method.
8 Recursion Tree Method
9 Substitution method and Master’s Theorem and its
Illustration
Module 1 Hours Taken
MODULE 2
1 Self Balancing Trees - Properties of AVL Trees,
Rotations of AVL Trees
2 AVL Trees Insertion and Illustration
3 AVL Trees Deletion and Illustration
4 Disjoint set operations
5 Union and find algorithms
6 Illustration of Union and find algorithms
7 Graph Algorithms: BFS traversal, Analysis.
8 DFS traversal, Analysis.
9 Strongly connected components of a Directed graph
10 Topological Sorting.
Module 2 Hours Taken
MODULE 3
1 Divide and Conquer: The Control Abstraction.
2 2-way Merge Sort, Analysis
3 Greedy Strategy: The Control Abstraction
4 Fractional Knapsack Problem
5 Strassen’s Algorithm for Matrix Multiplication,
Analysis
6 Minimum Cost Spanning Tree Computation-
Kruskal’s Algorithm, Analysis.
7 Single Source Shortest Path Algorithm - Dijkstra’s
Algorithm
8 Illustration of Dijkstra’s Algorithm-Analysis
Module 3 Hours Taken
MODULE 4
1 Dynamic Programming: The Control Abstraction,
The Optimality Principle.
2 Matrix Chain Multiplication-Analysis.
3 Illustration of Matrix Chain Multiplication-
Analysis.
4 All Pairs Shortest Path Algorithm- Analysis and
Illustration of FloydWarshall Algorithm.
5 Back Tracking: The Control Abstraction
6 Back Tracking: The Control Abstraction – The N
Queen’s Problem.
7 Branch and Bound:- Travelling salesman problem.
8 Branch and Bound:- Travelling salesman problem.
Module 4 Hours taken
MODULE 5
1 Introduction to Complexity Theory: Tractable and Intractable
Problems
2 Complexity Classes – P, NP
3 NP- Hard and NP-Complete Problems
4 NP Completeness Proof of Clique Problem.
5 NP Completeness Proof of Vertex Cover Problem.
6 Approximation algorithms- Bin Packing Algorithm and
Illustration.
7 Graph Colouring Algorithm and Illustration.
8 Randomized Algorithms (definitions of Monte Carlo and Las
Vegas algorithms).
9 Randomized Version of Quick Sort Algorithm with Analysis.
10 Illustration of Randomized Version of Quick Sort Algorithm with
Analysis.
Module 5 Hours Taken
Objective:-
1. To provide a solid background in the design and analysis of the major classes of algorithms.
2. To analyze any given algorithm and express its time and space complexities in asymptotic notations.
3. To Classify a problem as computationally tractable or intractable, and discuss strategies to address
intractability
4. To Identify the suitable design strategy to solve a given problem.
5. To develop their own versions for a given computational task and to compare and contrast their
performance.
Prepared by: Reviewed and approved by:
Arya A R HOD, CSE
AP, CSE
Subject : - ALGORITHM ANALYSIS AND DESIGN
Code : - CST 306
Periods : - Lecture-3, Tutorial-1,Practical-0
Marks : - 100 + 50 (University-100, Sessional-50)
Sessional : - Attendance-10, Assignment-15, Test paper -25
University Exam :- 2 parts
PART A: Short answer questions (10 x 2 marks = 20 marks)
All questions are compulsory. There should be at least two questions from each
module and not more than three questions from any module.
PART B: Descriptive/Analytical/Problem solving questions ( 4 x 20 marks = 80 marks )
Candidates have to answer one question out of two or two questions out of four from
each module. Each question may contain sub-questions a), b) etc
Assignment: - 1. Problems related to various algorithm.
2. Class note evaluation.
3. Previous years University Question Papers
Reference Books
1. T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, Introduction to Algorithms, 2nd Edition, Prentice-
Hall India (2001)
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”,
2nd Edition, Orient Longman Universities Press (2008).
3. Sara Baase and Allen Van Gelder ―Computer Algorithms, Introduction to Design and Analysis,
3rd Edition, Pearson Education (2009)
4. JonRobert Sedgewick, Kevin Wayne, “Algorithms”,4th Edition Pearson (2011)
5. Kleinberg, Eva Tardos, “Algorithm Design”, First Edition, Pearson (2005)
