Design and Analysis of Algorithms

L T P : 3 0 3

Total Credits : 4.5

Pre-requisites : Data Structures

Course Outcomes

• Understand the fundamental principles of algorithm design.
• Analyze algorithm efficiency using asymptotic notations.
• Develop problem-solving skills through algorithmic thinking.
• Learn classic algorithm design paradigms and apply them to real-world problems.
• Understand computational intractability by exploring NP-completeness, and develop the ability to classify problems based on their complexity classes (P, NP, NP-Complete, NP-Hard).

2

Text books/ Reference Books

Text Books:

• Cormen, Thomas H., Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to algorithms. MIT press, 2022.
• Kleinberg, Jon, and Eva Tardos. Algorithm design. Pearson Education India, 2006.
• Ellis Horowitz, Sartaj Sahani, Sanguthevar Rajashekaran, “Fundamentals of Computer Algorithms”, Orient Black Swan, 2nd Edition (2008).
• A .V. Aho, J . E . Hopcroft, J . D . Ulman “The Design & Analysis of Computer Algorithms”, Addison Wesley, 1998.

​

• Reference websites:
• https://nptel.ac.in/courses/106101060/
• https://ocw.mit.edu/courses/6-046j-introduction-to-algorithms-sma-5503-fall-2005/

​

​

3

Syllabus of the Course

1. Introduction to Algorithms

• Algorithms vs Programs, Characteristics of algorithms, Analyzing algorithms: Time and space complexity, Asymptotic notation: Big-O, Big-Ω, Big-Θ, Small o, small- omega Recurrences and solution methods -Substitution, Recursion Tree, Master Theorem.

​

2. Divide and Conquer Approaches

• General paradigm and recurrence relation, Binary Search, Merge Sort, Quick Sort, Matrix Multiplication (Strassen's Algorithm)

​

3. Greedy Algorithms

• Greedy choice property and optimal substructure, Minimum Spanning Tree, Prim’s and Kruskal’s Algorithms for finding minimum spanning tress, Shortest Path problem, Dijkstra’s Algorithm to compute Shortest Path, Huffman Coding for data compression, Activity selection problem, Knapsack Problem

4

Syllabus of the Course (con…)

4. Dynamic Programming

• Principle of Optimality and the distinction between bottom-up and top-down approaches in dynamic programming. Matrix Chain Multiplication, Longest Common Subsequence, 0/1 Knapsack Problem and the Floyd-Warshall algorithm for all-pairs shortest paths.

​

5. Graph Algorithms

• Graph representations including adjacency lists and matrices. Breadth-first and depth-first traversals, topological sorting of directed acyclic graphs, identification of strongly connected components.

​

6. Advanced Topics

• The theory of computational complexity, P, NP, NP-Complete, and NP-Hard classes. Polynomial-time reductions, prove that problems are NP-Complete using examples like SAT, 3-CNF-SAT.

​

5

Evaluation Scheme (Theory + Practical)

6

Motivation

We use algorithms all the time:

• School arithmetic's: Long divisions addition with carry, square roots……..
• Arranging books alphabetically on shelf.
• Finding quickest route to the university.

​

7

What is an algorithm?

• An algorithm is a step by step unambiguous instructions to solve a given problem in a finite amount of time.
• Tool for solving a well specified computational problem.
• Describes a specific computational procedure for achieving the desired output from a given input.

​

​

​

8

Algorithm to reach SAU

9

Algorithm

1. Go straight.

2. Take left turn towards Gowshala Road.

3. You will reach SAU.

​

​

​

Take 3^rd left turn

(No ambiguity)

​

10

Which Left???

Characteristics of a good algorithm

11

Properties of Algorithms

• Each Step must be a basic operation
• It should terminate in a finite amount of time
• It should produce atleast one output
• It should take 0 or more input
• Corresponding to a given set of Input we must have fixed Output
• Platform independent
• Every Statement must be unambiguous

​

12

Steps Required to Develop an Algorithm

• Problem Definition - Identify & define the problem properly
• Develop Model - Make the DFD or any other model to describe the problem graphically
• Design - Identify steps in algorithm and write them in proper sequence
• Testing - Try to find errors in the algorithm
• Analysis - Measure its Time and Space Complexity
• Optimize - Try to minimize the time and space complexity of the algorithm
• Implement - Implement in any programming language

13

Performance Analysis of algorithm

14

A Priori vs A Posteriori analysis

15

Analysis of algorithm

•  Determination of the amount of time and space resources required to execute an algorithm.

16

Time & Space Complexity

• Time Complexity of an algorithm quantifies the amount of time [CPU time] taken by the algorithm to run as a function of Input Size
• Space complexity of an algorithm quantifies the amount of main memory space taken by the algorithm to run as a function of Input Size
• Independent of the programming language selected for the implementation of the algorithm.

​

17

Importance of analysing algorithms

• Need to recognize limitations of various algorithms for solving a problem.
• Need to understand relationship between problem size and running time.
• Need to learn how to analyze an algorithm's running time without coding it.
• Need to learn techniques for writing more efficient code.

​

18

Which algorithm is better?

There can be many algorithms to solve a problem….

All the algorithms are correct….

But which is the best??

​

• Measure the running time (number of operations needed).
• Measure the amount of memory used.

​

The running time of the algorithms increase as the size of the input increases.

​

19

Asymptotic Notations

• Suppose we are considering two algorithms, A and B, for solving a given problem.

Running times of algorithm A = TA(n)

Running times of algorithm B = TB(n),

where n is a measure of the problem size.

​

• If we know the problem size n in advance, then

if TA(n)< TB(n) Algorithm A is better than Algorithm B.

Unfortunately, we usually don't know the problem size beforehand.

​

20

Asymptotic Notations

​

• Asymptotic notations allow us to analyze an algorithm’s running time by identifying its behavior as the input size for the algorithm increases.
• Asymptotic – refers to study of function f as n approaches infinity

(Asymptotes : Tangents to the Curve at Infinity)

​

• Analysis of Algorithms is generally done for a very large Input Size
• To sort 10-20 nos. we would not write a sorting program

​

• Apriori analysis gives time needed by the algorithm as a function of Input Size.

​

21

Which is better

Two algorithms: A1 A2

​

Time needed by each: n 100000n

​

​

22

Which is better

Two algorithms: A1 A2

​

Time needed by each: n 100000n

​

Mathematically A2 needs more time but Asymptotically they are same

​

23

Which is better

Two algorithms: A1 A2

​

Time needed by each: n² 100000n

​

​

24

Which is better

Two algorithms: A1 A2

​

Time needed by each: n² 10000n

​

Mathematically A2 needs more time but Asymptotically they are same

Till 9999 I/Ps they A2 needs more time, for 10000 I/Ps both need same time, beyond 10000 I/Ps A1 needs more time

25

Asymptotic Analysis

• Constants do not matter
• Take dominating term

​

Reasons

• Machine Independent
• We work for larger values of n

​

Example: f(n) = n²+4n + 20

n² is the dominant term and the term 4n + 20 becomes insignificant as n grows larger.

​

We need ways to represent time/space complexity of algorithms which is independent of Machine Specifications. These ways are Asymptotic Notations

26

Asymptotically Same

n 10000n 10000000n

n n/2 n/10000

Note

n² >>> 100000n

(1/10000) n² >>> 100000n

Big Oh Notation(O)

​

Definition:

f(n) = O(g(n))

if there are two positive constants c and n₀

such that:

f(n) ≤ c g(n) for all n ≥ n₀

​

​

​

g(n) is an asymptotic upper bound for f(n),

which means the growth rate of f(n) is no more

than the growth rate of g(n).

​

​

27

If f(n) = 2n²

g(n) is O(n³)

Big Oh Notation(O)

• To Prove f(n) = O(g(n))
• Simply prove f(n) <= g(n)
• If f(n)<g(n) then straightway f(n)=O(g(n)
• Can take the help of c (c>0)
• s.t. f(n) <= cg(n)
• And starting from which value of n? This is n₀
• For some initial values f(n) > c g(n)

​

• Example: f(n)=n, g(n)=n+2

​

28

Questions on Big Oh Notation(O)

​

1. f(n) = n g(n) = 3n+2
2. f(n) = n² g(n) = 5n²+6n+2
3. f(n) = 1000n g(n) = 5n²

​

​

f(n) = O(g(n)) ???

​

g(n) = O(f(n)) ???

​

​

29

Questions on Big Oh Notation(O)

​

1. f(n) = n g(n) = 3n+2
2. f(n) = n² g(n) = 5n²+6n+2
3. f(n) = 1000n g(n) = 5n²

​

1. f(n) = O(g(n)) & g(n) = O(f(n))

2. f(n) = O(g(n)) & g(n) = O(f(n))

3. f(n) = O(g(n)) & g(n) =! O(f(n))

​

​

​

​

30

• If f(n) is O(n)
• Then - f(n) is O(n²) ??
• Then - f(n) is O(n³) ??

​

31

• If f(n) is O(n)
• then - f(n) is O(n²) ??
• then - f(n) is O(n³) ??

​

• If f(n) <= cn obviously f(n)<=cn², cn³,….

​

• O(n) represents infinite functions

3n+2 = O(n)

3n+5 = O(n)

2n+3 = O(n) ….

​

• Always take dominating term for big O

32

f(n)=3n+2

f(n)=O(n)

f(n)=O(nlogn)

f(n)=O(n²)

f(n)=O(n³)

logn = O(n)

loglogn = O(n)

……….

O(n²) represents infinite functions

5n² + 6

8n² + 5

n

nlogn

logn ……..

Q. If f(n) = n² + 6n + 2; then f(n) is …….

Which of the following options is true

• O(n² ) ✓
• O(n³ ) ✓
• O(n⁴ ) ✓
• O(n ) ✗
• O(nlogn ) ✗
• O(n² logn) ✓

​

​

​

​

33

Most Common Big Oh Functions

• Constant O(1)
• Logarithmic O(log n)
• Linear O(n)
• Quadratic O(n²)
• Polynomial O(n^k) k is a constant
• Exponential O(2ⁿ)
• Exponential O(aⁿ), a>1 is a constant

34

​

Definition:

f(n) = Ω(g(n)

if there exist positive constants c and n₀

such that:

0 < c g(n) < f(n) for all n≥ n₀

​

​

​

g(n) is asymptotic lower bound for f(n), which

means the growth of f(n) is no lesser than the

growth rate of g(n).

35

36

37

Questions on Big Oh Notation(O)

38

39

40

41

Theta Notation(Ɵ)

​

Definition:

f(n) = Ɵ (g(n))

if there are two positive constants c and n₀

such that:

0 ≤ c₁ g(n) ≤ f(n) ≤ c₂ g(n)

​

42

This is known as asymptotic tight bound. For reasonably large values of n, the function f(n) is within the range of constant multiples of g(n). f(n) is bounded below as well as above.

Example Theta Notation(Ɵ)

1. f(n) = 3n+2 g(n) = n

​

2. f(n) = 5n²+6n+2 g(n) = n²

​

3. f(n) = 1000n g(n) = 5n²

​

f(n) = Ɵ(g(n) ??

g(n) = Ɵ(f(n)) ??

​

43