Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam – 603 110

(An Autonomous Institution, Affiliated to Anna University, Chennai)

Date: 08.03.2023

Course Code UCS2403 Course Design and Analysis of Algorithms

Name

Course Type Theory cum Course Professional Core L T P E C

Practical Category (PC)
3 0 2 0 4

Regulation 2021 Academic Year & 2022-23

Batch 2021-2025

Degree and Branch B.E. Computer Science & Engineering

Semester IV

Department Offering the Course Computer Science and Engineering

Name of the Faculty Dr. Balasubramanian V

Dr. Dhannya S M

COURSE OBJECTIVES
1. To learn algorithms analysis techniques.
2. To analyze the asymptotic performance of algorithms.
3. To apply different algorithm design strategies.
4. To prove the limitations of algorithmic power.
5. To demonstrate familiarity with important algorithms and data structures.
UNIT I INTRODUCTION AND ANALYSIS 9

Introduction: Fundamentals of algorithmic problem solving – Important problem types;

Fundamentals of the Analysis of Algorithm Efficiency: Analysis framework – Asymptotic notations
and basic efficiency classes – Mathematical analysis for recursive and non-recursive algorithms.

UNIT II DIVIDE-AND-CONQUER, BACKTRACKING 9

Divide and Conquer: Mergesort – Quicksort – Multiplication of large integers – Strassen’s matrix
multiplication; Backtracking: Subset sum – N-queens problem – Hamiltonian circuit problem.

UNIT III DYNAMIC PROGRAMMING, GREEDY 9

Dynamic Programming: Computing a binomial coefficient – Knapsack problem and memory

functions – Ordering of matrix multiplications – Warshall’s and Floyd’s algorithm; Greedy
Technique: Dijkstra’s algorithm, Prim’s algorithm – Kruskal’s algorithm.

UNIT IV ITERATIVE IMPROVEMENT, BRANCH-AND-BOUND 9

Iterative Improvement: Stable matching – Maximum Network Flow – Maximum matching in

bipartite graphs; Branch and Bound: Knapsack problem – Traveling salesman problem.

UNIT V LIMITATIONS OF ALGORITHM POWER 9

Limitations of algorithm power: Lower-bound arguments – P, NP and NP-complete problems;

Coping with the Limitations of Algorithm Power: Approximation algorithms for NP-Hard problems
– Traveling salesman problem – Knapsack problem.

TOTAL PERIODS (LAB): 30

TOTAL PERIODS: 75

SUGGESTIVE EXPERIMENTS

1. Iterative and recursive algorithms using decrease-and-conquer

2. Backtracking: subset sum, N-queens
3. Divide-and-conquer: Mergesort, Quicksort
4. Dynamic Programming: Longest Increasing Subsequence, Floyd-Warshall
5. Greedy: Prim’s, Dijkstra’s
6. Iterative improvement: Stable matching, Network flow
7. Branch and Bound: Knapsack

COURSE OUTCOMES
On successful completion of this course, the student will be able to:
1. Analyze asymptotic running time for various kinds of algorithms (K4)
2. Analyze the time and space complexity of Divide-and-Conquer and Backtracking algorithms
(K4)
3. Evaluate Dynamic Programming and Greedy techniques for a given problem (K5)
4. Use iterative improvement and branch-and-bound design techniques (K5)
5. Explain the concepts of NP completeness (K2)
TEXTBOOKS

1. Anany Levitin, “Introduction to the Design and Analysis of Algorithms”, 3rd Edition,
Pearson Education, 2012.
2. Jeff Erickson, “Algorithms”, 1st Edition, 2019

REFERENCES

1. S Dasgupta, C H Papadimitriou, U V Vazirani, “Algorithms”,1st Edition, McGraw Hill

Education, 2017.
2. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, “Introduction to
Algorithms”, 3rd Edition, PHI Learning Private Limited, 2012.
3. Steven S Skiena, “The Algorithm Design Manual”, 2nd Edition, Springer, 2008.
Lesson Plan
Content Delivery Methods P: Presentations, PS: Problem Solving, ML: Minute lectures, DA:
(CDM) Discussion activities, ICQ: In-class Quiz

Tools PowerPoint presentations / Whiteboard applications / Projector/

Board

Sl. Knowledge Proposed Actual

Course Content CDM Number of Number of
No. level
Hours to be Hours
handled handled

Unit I - Introduction and Analysis (CO1, K4)

P K1 1
1 Introduction and Motivation

Basics steps in problem solving

2 Important Problem Types P K2 1
Overview of Algorithm Design Techniques

Understand the Analysis Framework

Input Size
3 Worst-case, Best-case, Average-Case P/PS K2 2
Asymptotic Notations
Basic Efficiency Classes

Apply the framework in analyzing non-recursive

Algorithms
Sub-linear (Max value in a list)
4 Linear (Simple for loop) P/PS K3 2
Quadratic (Insertion sort)
Cubic (Matrix multiplication)
Exponential (Brute force)

Apply the framework in analyzing recursive

algorithms
Solve recurrences for:
5 P/PS K3 2
● Binary Search
● Fibonacci
● Tower of Hanoi

P/PS/
6 Numericals to solve recurrences K4 1
ML

Unit II - Divide-and-Conquer, Backtracking (CO2, K4)

Divide & Conquer using Binary Search

● Algorithm
1 P K2 1
● Example
● Analysis

Mergesort
2 P K3 1
● Algorithm
 ● Example
● Analysis

Quicksort
● Algorithm
3 P K3 2
● Example
● Analysis

Multiplication of large integers

● Motivation
4 P/PS K3 1
● Algorithm idea using an example
● Analysis

Strassen’s matrix multiplication

● Naive algorithm for matrix multiplication
5 P/PS K4 1
● Strassen’s algorithm idea using an example
● Analysis

Backtracking using Subset-Sum

● Problem Statement
6 P/PS K2 1
● State Space Tree
● Analysis

N-queens problem
● Problem Statement P/PS/
7 K3 1
● State Space Tree ML
● Analysis

Hamiltonian Circuit problem

● Problem Statement P/PS/
8 K3 1
● State Space Tree ICQ
● Analysis

Unit III - Dynamic Programming, Greedy Algorithm (CO3, K4)

Dynamic Programming using Fibonacci

● Recall recursive Fibonacci and its time complexity
1 P/PS K2 1
● Memoization
● Fibonacci using DP, Analysis

Computing a binomial coefficient

● Problem Statement
2 ● DP Solution P/PS K3 1
● Recurrence relation
● Time Complexity Analysis

Ordering of Matrix multiplication

● Problem Statement
3 ● DP Solution P/PS K3 1
● Recurrence relation
● Time Complexity Analysis

Floyd-Warshall algorithm
● Problem Statement
P/PS/
4 ● DP Solution
ML
K3 1
● Recurrence relation
● Time Complexity Analysis

Greedy Technique using Dijkstra’s algorithm

6 ● Problem Statement
P K3 1
 ● Greedy Solution
● Correctness proof
● Time Complexity Analysis using adj matrix and adj
list

Prim’s algorithm
● Problem Statement
● Greedy Solution
7 ● Correctness proof
P K3 1
● Time Complexity Analysis using adj matrix and adj
list

Kruskal’s algorithm
● Problem Statement
● Greedy Solution
8 ● Correctness proof
P K3 1
● Time Complexity Analysis using adj matrix and adj
list

Analyze design technique for knapsack problem

●Problem Statement
P/PS/
9 Greedy / DP
ML
K4 2
● Recurrence relation
Time Complexity Analysis

Unit IV - Iterative improvement, Branch-and-bound (CO4, K4)

Introduce Iterative improvement using Stable

Matching
1 ● Problem Statement P K2 1
● Algorithm
● Correctness

Maximum Network Flow

● Problem Statement
2 ● Algorithm
P/PS K3 2
● Correctness

Maximum Matching in bipartite graphs

● Problem Statement
3 ● Algorithm
P/PS K3 2
● Correctness

Brand-and-bound using Knapsack

4 ● Problem Statement P/PS K3 2
● State Space tree

Traveling Salesman problem

P/PS/
5 ● Problem Statement
ML
K4 2
● State Space tree

Unit V - Limitations of Algorithm Power (CO5, K2)

Lower-bound arguments
1 P, NP problems P/DA K2 1
Examples

NP-Hard, NP-Complete problems

2 Examples P K2 2
Idea of reduction
 Approximation Algorithms for TSP
● Recall Problem Statement
3 ● Algorithm P K2 2
● Approximation Factor
● Proof

Approximation Algorithm for Knapsack problem

● Recall Problem Statement
4 ● Algorithm P K2 2
● Approximation Factor
● Proof

Linear Programming
● Fractional Solution, Simplex Method
● Integer Solution
5 ● Comparing hardness of finding the above two
P/ML K2 2
solutions
● Examples

Contents beyond syllabus topic:

● Linear Programming

Reason: Linear Programming is a powerful tool in obtaining approximate solutions for many
combinatorial problems using a mathematical model that defines linear relationships. It is also
used in ML, where many real-world ML problems are often formulated as linear equations and
inequalities, not just because they are naturally linear but because modeling as a linear program
is a practical compromise.
 Mapping of Course Outcomes with Program Outcomes

CO-PO/PSO mapping using Performance Indicators

CO1 CO2 CO3 CO4 CO5
PO
/PSO
PI MS PI M PI M PI MS PI M
S S S

1 1.1.1(3), 3 1.3.1(3) 3 1.3.1(3) 3 1.3.1(3) 3 1.4.1(3) 3

1.3.1 (3), 1.4.1(3) 1.4.1(3) 1.4.1(3)
1.4.1 (3)

2 2.1.1(3) 2 2.1.3(2) 2 2.1.3(2), 2 2.1.3(2), 2 2.1.3(2), 2

2.1.3(2) 2.4.1(2) 2.4.1(2) 2.4.1(2) 2.4.1(2)
2.4.3(2) 2.4.3(2) 2.4.3(2)

3 - - 3.1.1(2) 2 3.1.1(2) 2 3.1.1(2) 2 - -

3.2.1(3) 3.2.1(3) 3.2.1(3)

4 - - - - - -

5 - - - - - - - - - -

6 - - - - - - - - - -

7 - - - - - - - - - -

8 - - - - - - - - - -

9 - - - - - - - - - -

10 - - - - - - 10.1.1(3) 3 - -

11 - - - - - - - - - -

12 - - - - - - 12.3.1(3) 3 - -

PSO1 13.3.1(2) 2 13.3.1(2) 3 13.3.1(2) 3 13.3.1(2) 3 13.3.1(2) 2

13.3.2(2) 13.3.2(2) 13.3.2(2)
13.4.1(3) 13.4.1(3) 13.4.1(3)

PSO2 - - - - - - - - - -

PSO3 - - - - - - - - - -
 PI Description

1.1.1 Apply the knowledge of discrete structures, linear algebra, statistics, and numerical
techniques to solve problems

1.3.1 Apply engineering fundamentals

1.4.1 Apply theory and principles of computer science and engineering to solve engineering
problems

2.1.1 Evaluate problem statements and identify objectives

2.1.3 Identify mathematical and algorithmic knowledge that applies to a given problem

2.4.1 Apply engineering mathematics to develop solutions

2.4.3 Identify the limitations of solutions and sources/causes

3.1.1 Define precise problem statements with objectives and scope

3.2.1 Explore design alternatives

10.1.1 Read, understand, and interpret technical and non-technical information

12.3.1 Search and comprehend technical literature and other credible sources of information

13.3.1 Apply fundamentals of problem solving

13.3.2 Design solutions in a modular way

13.4.1 Analyze the effectiveness of solutions

Course CO Target for

Gap
Outcomes Attainment CO-PO
CO 1 2.49 2.00 0.49

CO 2 2.48 2.00 0.48

CO 3 1.95 2.00 -0.05

CO 4 0.60 2.00 -1.40

CO 5 1.85 2.00 -0.15

In the attainment, CO4 there is a gap, additional problems will be given in each unit to bridge
the gap in the ensuing offering
CO to PO/PSO Mapping

PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12 PSO1 PSO2 PSO3

CO1 3 2 2

CO2 3 2 2 3

CO3 3 2 2 3

CO4 3 2 2 3 3 3

CO5 3 2 2

Total 15 10 6 3 3 13

Score 3 2 2 3 3 3

Assessment Format and Details (TCP Course)

Course Assessment Matrix

Assessment KL Course Outcomes Weightage
Tools CO1 CO2 CO3 CO4 CO5
CAT 1 K3 Y Y Y 15 Marks
(Units 1, 2)
Theory K5 Y Y 10 Marks
Assignments
Lab K4, Y Y Y Y 15 Marks
Assignments K5
Model Lab K4 Y Y Y Y 10 Marks
Examination
End Semester K4 Y Y Y Y Y 15 Marks
Lab Exam
End Semester K4 Y Y Y Y Y 35 Marks
Theory Exam
Total 100 Marks
 Assessment I (50% weightage) Assessment II (50% weightage) End Semester
(Theory Component) (Laboratory Component) Exam

Individual Written Test Evaluation of Test Theory Lab

Assignment Laboratory
Part A (4 X 2) Observation, Record Part A (5
Part B (3 X 6) X 2)
Part C (2 X 12) Part B
(5X 6)
Part C
(5 X 12)

15
40% 60% 75% 25% 35 marks
marks

50 Marks 50 Marks

Lab Schedule:

Language/Tools/Packages: Linux, Python, Repl.it, LMS

S.No Topic CO KL Proposed Actual

Hours Hours
1 Iterative algorithms K3 6
2 Divide and conquer algorithms K3 6
3 Dynamic Programming K4 6
4 Greedy Algorithms K3 4
5 Branch-and-bound Algorithms K4 8
Total 30

Evaluation criteria <Lab>:

Sl.No. Assessment Tool Assessment Weightage Marks
Technique

1 Assignments Algorithm 40 8 X 5 = 40 Marks

Demo 40 Learning Experience /

LMS Record Submission -
Modular and 20 5 Marks
Incremental coding
 Algorithm design 20 15 Marks
2 Model Examination

Demo 70

Modr:lar and 10
Incremental coding

F,nd Semester Algorithm design 10 40 N4arks

6
Practical
Eramination Demo 75

Modular and 5

Incremental coding

Viva-voce 10

Total 100 Marks

Prepared By Verified By Approved By

\
prfr,- I zl

Dr. Balasubramanian V
(Course ln-charge) UG - PAC Team (HOD / CSE)

Dr. Dhannya S lVl

Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam - 603 110
(An Autonomous Institution, Affiliated to Anna University, Chennai)

UCS2403: DESIGN & ANALYSIS OF ALGORITHMS

CO1, K3, 2.1.3

Assignment 1
• Write a Python code that takes as input a value n, and generates a list of
n unique random values. You may use this code to generate the numbers
to be given as input for the searching and sorting code for the questions
below. [5 points]
• Implement insertion sort, shell sort and radix exchange sort, and test the
code for arrays of the following size: [5 points]

– 10
– 100
– 1000
– 10000
– 100000

• Implement insertion sort, shell sort and radix exchange sort for an array
of size 10000 when the input array is: [5 points]
– Sorted in ascending order
– Sorted in descending order
– Not sorted
• Plot the graphs for both the above implementations with n on the x-axis
and time of execution in milliseconds on the y-axis. You may use standard
Python packages for plotting the graph. [5 points]

• Implement recursive and non-recursive algorithms for binary search. Com-

pare the performance of both versions using an array of size 10000.
[5 points]

1
Sri Sivasubramaniya Nadar College of Engineering, Kalavakkam - 603 110
(An Autonomous Institution, Affiliated to Anna University, Chennai)

UCS2403: DESIGN & ANALYSIS OF ALGORITHMS

Assignment 2 CO1, K3, 2.1.3

1. (a) Write a program to find unique (non-repeating) elements in a list.

That is, find those elements that do not have duplicates in the list.
For example, in the list [3, 6, 9, 2, 3, 9, 1, 15, 21, 3, 1], the unique ele-
ments are [6, 2, 15, 21, 1]. The order of elements in the output list
should be the same as that in the original list.
(b) What is the time complexity of your algorithm? You may ignore the
improvements introduced by language specific implementations (say,
using set in Python).
2. (a) Given an integer n as input, write a program to print the sum of the
following series up to n terms.

1 + (1 + 2) + (1 + 2 + 3) + . . . + (1 + 2 + 3 + . . . + n)

(b) What is the time complexity of your code?

3. (a) Write a program to print all the most frequently occurring characters
in a given string, as a list.
For example, if the input string is “example”,the output should be
[e]. If the input string is “exist”, then the output should be [e,x,i,s,t].
(b) What is the complexity of your code?