Scribd
Upload
4 views4 pages

Chapter4 Dynamic Programming Lecture Notes

Chapter 4 of the document covers Dynamic Programming, including its introduction, key characteristics, and approaches like Memoization and Tabulation. It also discusses algorithms such as Floyd-Warshall for finding all-pairs shortest paths, Dijkstra's for single-source shortest paths, and the 0/1 Knapsack Problem for optimization. Additionally, it introduces Depth First Search (DFS) for graph traversal, detailing its algorithm, applications, and complexities.

Uploaded by

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

Chapter4 Dynamic Programming Lecture Notes

Chapter 4 of the document covers Dynamic Programming, including its introduction, key characteristics, and approaches like Memoization and Tabulation. It also discusses algorithms such as Floyd-Warshall for finding all-pairs shortest paths, Dijkstra's for single-source shortest paths, and the 0/1 Knapsack Problem for optimization. Additionally, it introduces Depth First Search (DFS) for graph traversal, detailing its algorithm, applications, and complexities.

Uploaded by

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

Design and Analysis of Algorithms (CoSc

3094)
Chapter 4: Dynamic Programming (6 Hours)

4.1 Introduction to Dynamic Programming


Dynamic Programming (DP) is an algorithm design technique used to solve problems by
breaking them into smaller subproblems and storing their solutions to avoid repeated
computations.

Key Characteristics:
• Optimal Substructure: An optimal solution can be constructed from optimal solutions of
smaller subproblems.
• Overlapping Subproblems: The same subproblems appear repeatedly.

Example: Fibonacci Sequence


F(n) = F(n-1) + F(n-2)

Without DP, many values are recomputed. With DP, results are stored and reused,
significantly improving efficiency.

Approaches:
1. Memoization (Top-Down)
2. Tabulation (Bottom-Up)

Advantages:
• Faster execution
• Reduced redundancy
• Produces optimal solutions for many optimization problems

4.2 All-Pairs Shortest Path – Floyd-Warshall Algorithm


The Floyd-Warshall Algorithm finds the shortest paths between all pairs of vertices in a
weighted graph.

Idea:
For every pair of vertices (i,j), determine whether passing through an intermediate vertex k
produces a shorter path.

Formula:
D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Algorithm:
for k = 1 to n
for i = 1 to n
for j = 1 to n
D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Applications:
• Network routing
• Transportation systems
• Social networks

Complexity:
Time Complexity = O(n³)
Space Complexity = O(n²)

4.3 Shortest Path – Dijkstra Algorithm


Dijkstra's Algorithm finds the shortest path from a single source vertex to all other vertices
in a graph with non-negative edge weights.

Steps:
1. Assign distance 0 to the source.
2. Assign infinity to all other vertices.
3. Select the unvisited vertex with minimum distance.
4. Update distances of neighboring vertices.
5. Repeat until all vertices are visited.

Example:
If A is the source:
Distance(A)=0
Distance(B)=∞
Distance(C)=∞

Applications:
• GPS navigation systems
• Internet routing
• Logistics planning

Complexity:
O(V²) using adjacency matrix
O(E log V) using priority queue
4.4 0/1 Knapsack Problem
The 0/1 Knapsack Problem is an optimization problem where each item can either be
selected (1) or not selected (0).

Problem:
Given a set of items, each with a weight and value, determine the maximum value that can
be placed in a knapsack with limited capacity.

Recurrence Relation:
If weight[i] > w:
K[i][w] = K[i-1][w]

Otherwise:
K[i][w] = max(
K[i-1][w],
value[i] + K[i-1][w-weight[i]]
)

Example:

Item Weight Value


1 1 10
2 3 40
3 4 50
4 5 70

Capacity = 8

Optimal selection:
Item 2 and Item 4
Total Value = 110

Complexity:
Time = O(nW)
Space = O(nW)

4.5 Depth First Search (DFS)


Depth First Search (DFS) is a graph traversal algorithm that explores as deeply as possible
before backtracking.

Algorithm:
DFS(v)
Mark v as visited
For each neighbor u
If u is not visited
DFS(u)

Example Traversal:

A
/\
B C
/\
D E

DFS Order:
A→B→D→E→C

Applications:
• Path finding
• Cycle detection
• Topological sorting
• Connected component analysis

Complexity:
Time Complexity = O(V + E)
Space Complexity = O(V)

You might also like