Scribd
Upload
5 views4 pages

Algorithm Design Exam Notes Handwritten Style

The document outlines various algorithmic techniques including Brute Force, Greedy Method, Dynamic Programming, Dijkstra’s Algorithm, and Ford-Fulkerson, along with their applications and time complexities. It also discusses complexity classes, reducibility for NP-Completeness, asymptotic notations, and the Master Theorem. Additionally, it provides specific results for Dijkstra's algorithm and compares Divide & Conquer with Dynamic Programming.

Uploaded by

Priyangshu Ghatak
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views4 pages

Algorithm Design Exam Notes Handwritten Style

The document outlines various algorithmic techniques including Brute Force, Greedy Method, Dynamic Programming, Dijkstra’s Algorithm, and Ford-Fulkerson, along with their applications and time complexities. It also discusses complexity classes, reducibility for NP-Completeness, asymptotic notations, and the Master Theorem. Additionally, it provides specific results for Dijkstra's algorithm and compares Divide & Conquer with Dynamic Programming.

Uploaded by

Priyangshu Ghatak
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

GROUP B – PHOTO 1

1. Brute Force Technique:

Brute force tries all possible solutions and selects the best one.

Application in TSP:

Generate all permutations of cities.

Compute total cost of each tour.

Select minimum cost tour.

Time Complexity: O(n!)

2. Greedy Method:

Builds solution step-by-step choosing local optimum.

Prim’s Algorithm Steps:

Start from any vertex.

Select minimum weight edge connecting visited to unvisited vertex.

Repeat until all vertices included.

Time Complexity: O(V²)

3. 0/1 Knapsack (Dynamic Programming):

DP[i][w] =

If weight > capacity → exclude item

Else → max(exclude, include)

Time Complexity: O(nW)

4. Dijkstra’s Algorithm:

Initialize distances.

Pick minimum distance unvisited vertex.


Update neighbors.

Repeat.

Time Complexity: O(V²) or O(E log V)

5. Ford-Fulkerson:

Find augmenting path.

Find minimum residual capacity.

Update flow.

Repeat until no path.

Time Complexity: O(E × MaxFlow)

6. Complexity Classes:

P – Polynomial time solvable

NP – Polynomial time verifiable

NP-Hard – At least as hard as NP

NP-Complete – In NP and NP-Hard

7. Reducibility:

Problem A reduces to B if A transforms to B in polynomial time.

To prove NP-Complete:

1) Show problem in NP

2) Reduce known NP-Complete problem to it

---------------------------------------------

GROUP B – PHOTO 2

Q1. Asymptotic Notations:

Big-O → Upper bound


Omega → Lower bound

Theta → Tight bound

Q2. Master Theorem:

T(n) = aT(n/b) + f(n)

Case 1 → T(n) = Θ(n^logb a)

Case 2 → T(n) = Θ(n^logb a log n)

Case 3 → T(n) = Θ(f(n))

Given: T(n)=2T(n/2)+n/logn

Answer: Θ(n)

Q3. Recursion Tree:

T(n)=2T(n/2)+n

Answer: Θ(n log n)

Q4. Dijkstra Result (Given Graph):

Shortest distances from source 0:

1=4, 7=8, 6=9, 5=11, 2=12, 8=14, 3=19, 4=21

Q5. Quick Sort Complexity:

Best: O(n log n)

Average: O(n log n)

Worst: O(n²)

Q6. Divide & Conquer vs Dynamic Programming:

Divide & Conquer → Independent subproblems

Dynamic Programming → Overlapping subproblems + table storage

You might also like