Analysis & Design of Algorithms Module 4 BCS401

The Knapsack Problem

Designing a dynamic programming algorithm for the knapsack problem:
 Given n items of known
 weights w1, . . . , wn and
 values v1, . . . , vn and
 a knapsack of capacity W,
 find the most valuable subset of the items that fit into the knapsack.
To design a dynamic programming algorithm, we need to derive a recurrence relation that
expresses a solution to an instance of the knapsack problem in terms of solutions to its smaller
sub instances.
Let us consider an instance defined by the first i items, 1≤ i ≤ n, with weights w1, . . . , wi, values
v1, . . . , vi , and knapsack capacity j, 1 ≤ j ≤ W.
Let F(i, j) be the value of an optimal solution to this instance, i.e., the value of the most valuable
subset of the first i items that fit into the knapsack of capacity j.
We can divide all the subsets of the first i items that fit the knapsack of capacity j into two
categories: those that do not include the ith item and those that do. Note the following:
 Among the subsets that do not include the ith item, the value of an optimal subset is, by
definition, F(i − 1, j).
 Among the subsets that do include the ith item (hence, j – wi ≥ 0), an optimal subset is
made up of this item and an optimal subset of the first i − 1 items that fits into the
knapsack of capacity j − wi . The value of such an optimal subset is vi + F(i − 1, j − wi).

Thus, the value of an optimal solution among all feasible subsets of the first i items is the
maximum of these two values. Of course, if the ith item does not fit into the knapsack, the value
of an optimal subset selected from the first i items is the same as the value of an optimal subset
selected from the first i − 1 items.

Dept. of AI & ML, KIT, Tiptur Page 1

Analysis & Design of Algorithms Module 4 BCS401

These observations lead to the following recurrence:

Dept. of AI & ML, KIT, Tiptur Page 2

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 3

Analysis & Design of Algorithms Module 4 BCS401

Warshall’s Algorithm
The adjacency matrix A = {aij} of a directed graph is the boolean matrix that has 1 in its ith row
and jth column if and only if there is a directed edge from the ith vertex to the jth vertex.

A matrix containing the information about the existence of directed paths of arbitrary lengths
between vertices of a given graph. Such a matrix, called the transitive closure of the digraph,
would allow us to determine in constant time whether the jth vertex is reachable from the ith
vertex.

Warshall’s algorithm constructs the transitive closure through a series of n × n boolean matrices:

Dept. of AI & ML, KIT, Tiptur Page 4

Analysis & Design of Algorithms Module 4 BCS401

Thus, the series starts with R(0), which does not allow any intermediate vertices in its paths;
hence, R(0) is nothing other than the adjacency matrix of the digraph.

R(1) contains the information about paths that can use the first vertex as intermediate; thus, with
more freedom, so to speak, it may contain more 1’s than R(0).

In general, each subsequent matrix in series has one more vertex to use as intermediate for its
paths than its predecessor and hence may, but does not have to, contain more 1’s. The last matrix
in the series, R(n), reflects paths that can use all n vertices of the digraph as intermediate and
hence is nothing other than the digraph’s transitive closure.

The central point of the algorithm is that we can compute all the elements of each matrix R(k)
from its immediate predecessor R(k−1) in series.

Let r(k)ij , the element in the ith row and jth column of matrix R(k), be equal to 1. This means that
there exists a path from the ith vertex vi to the jth vertex vj with each intermediate vertex
numbered not higher than k: vi, a list of intermediate vertices each numbered not higher than k,
vj.

Dept. of AI & ML, KIT, Tiptur Page 5

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 6

Analysis & Design of Algorithms Module 4 BCS401

Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem

Given a weighted connected graph (undirected or directed), the all-pairs shortest paths problem
asks to find the distances—i.e., the lengths of the shortest paths from each vertex to all other
vertices.
It is convenient to record the lengths of shortest paths in an n × n matrix D called the distance
matrix: the element dij in the ith row and the jth column of this matrix indicates the length of the
shortest path from the ith vertex to the jth vertex. For an example, see Figure.

It is applicable to both undirected and directed weighted graphs provided that they do not contain
a cycle of a negative length.

Dept. of AI & ML, KIT, Tiptur Page 7

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 8

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 9

Analysis & Design of Algorithms Module 4 BCS401

Spanning Tree:
A spanning tree of an undirected connected graph is its connected acyclic subgraph (i.e., a tree)
that contains all the vertices of the graph.
If such a graph has weights assigned to its edges, a minimum spanning tree is its spanning tree of
the smallest weight, where the weight of a tree is defined as the sum of the weights on all its
edges.
The minimum spanning tree problem is the problem of finding a minimum spanning tree for a
given weighted connected graph.

Dept. of AI & ML, KIT, Tiptur Page 10

Analysis & Design of Algorithms Module 4 BCS401

Prim’s algorithm
Prim’s algorithm constructs a minimum spanning tree through a sequence of expanding subtrees.
 The initial subtree in such a sequence consists of a single vertex selected arbitrarily from
the set V of the graph’s vertices.
 On each iteration, the algorithm expands the current tree in the greedy manner by simply
attaching to it the nearest vertex not in that tree. (By the nearest vertex, we mean a vertex
not in the tree connected to a vertex in the tree by an edge of the smallest weight. Ties
can be broken arbitrarily.)
 The algorithm stops after all the graph’s vertices have been included in the tree being
constructed. Since the algorithm expands a tree by exactly one vertex on each of its
iterations, the total number of such iterations is n − 1, where n is the number of vertices in
the graph.

Here is pseudocode of this algorithm.

The nature of Prim’s algorithm makes it necessary to provide each vertex not in the current tree
with the information about the shortest edge connecting the vertex to a tree vertex.
We can provide such information by attaching two labels to a vertex:
The name of the nearest tree vertex and the length (the weight) of the corresponding edge.
Vertices that are not adjacent to any of the tree vertices can be given the ∞ label indicating
their “infinite” distance to the tree vertices and a null label for the name of the nearest tree
vertex.

Dept. of AI & ML, KIT, Tiptur Page 11

Analysis & Design of Algorithms Module 4 BCS401

Example:

Time Efficiency:
If a graph is represented by its weight matrix and the priority queue is implemented as an
unordered array, the algorithm’s running time will be in Θ(|V|2).

Dept. of AI & ML, KIT, Tiptur Page 12

Analysis & Design of Algorithms Module 4 BCS401

Apply Prim’s algorithm to the following graphs.

Dept. of AI & ML, KIT, Tiptur Page 13

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 14

Analysis & Design of Algorithms Module 4 BCS401

Kruskal’s Algorithm
Another greedy algorithm for the minimum spanning tree problem that also always yields an
optimal solution
Kruskal’s algorithm looks at a minimum spanning tree of a weighted connected graph G = <V,
E> as an acyclic subgraph with |V| − 1 edges for which the sum of the edge weights is the
smallest.
The algorithm constructs a minimum spanning tree as an expanding sequence of subgraphs that
are always acyclic but are not necessarily connected on the intermediate stages of the
algorithm.
The algorithm begins by
 Sorting the graph’s edges in nondecreasing order of their weights.
 Then, starting with the empty subgraph, it scans this sorted list, adding the next edge on
the list to the current subgraph if such an inclusion does not create a cycle and simply
skipping the edge otherwise.

Dept. of AI & ML, KIT, Tiptur Page 15

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 16

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 17

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 18

Analysis & Design of Algorithms Module 4 BCS401

Dijkstra’s Algorithm (To find single-source shortest-paths.)

For a given vertex called the source in a weighted connected graph, find shortest paths to all its
other vertices.
The single-source shortest-paths problem asks for a family of paths, each leading from the source
to a different vertex in the graph, though some paths may, of course, have edges in common.
This algorithm is applicable to undirected and directed graphs with nonnegative weights only.
Dijkstra’s algorithm finds the shortest paths to a graph’s vertices in order of their distance from a
given source.
 First, it finds the shortest path from the source to a vertex nearest to it, then to a second
nearest, and so on.
 The set of vertices adjacent to the vertices in Ti (sub tree of the given graph) can be
referred to as “fringe vertices”; they are the candidates from which Dijkstra’s algorithm
selects the next vertex nearest to the source.
 To identify the ith nearest vertex, the algorithm computes, for every fringe vertex u, the
sum of the distance to the nearest tree vertex v (given by the weight of the edge (v, u))
and the length dv of the shortest path from the source to v and then selects the vertex
with the smallest such sum.
 Finding the next nearest vertex u* becomes a simple task of finding a fringe vertex with
the smallest d value. Ties can be broken arbitrarily.
After we have identified a vertex u* to be added to the tree, we need to perform two operations:
1. Move u* from the fringe to the set of tree vertices.
2. For each remaining fringe vertex u that is connected to u* by an edge of weight w(u*,
u) such that du*+ w(u*, u) < du, update the labels of u by u* and du*+ w(u*, u),
respectively.

Dept. of AI & ML, KIT, Tiptur Page 19

Analysis & Design of Algorithms Module 4 BCS401

Pseudocode of Dijkstra’s algorithm.

Dept. of AI & ML, KIT, Tiptur Page 20

Analysis & Design of Algorithms Module 4 BCS401

Example:

from a to b : a−b of length 3

from a to d : a−b−d of length 5
from a to c : a−b−c of length 7
from a to e : a − b − d − e of length 9

The time efficiency of Dijkstra’s algorithm depends on the data structures used for
implementing the priority queue and for representing an input graph itself.
 It is in Θ(|V|2) for graphs represented by their weight matrix and the priority queue
implemented as an unordered array.
 For graphs represented by their adjacency lists and the priority queue implemented as a
min-heap, it is in Θ(|E| log |V |).

Dept. of AI & ML, KIT, Tiptur Page 21

Analysis & Design of Algorithms Module 4 BCS401

Solve the following instances of the single-source shortest-paths problem with vertex ’a’ as
the source.

Dept. of AI & ML, KIT, Tiptur Page 22

Analysis & Design of Algorithms Module 4 BCS401

Solve the following instances of the single-source shortest-paths problem with vertex ’a’ as
the source.

Dept. of AI & ML, KIT, Tiptur Page 23

Analysis & Design of Algorithms Module 4 BCS401

Huffman Trees and Codes

A Huffman tree is a binary tree that minimizes the weighted path length from the root to the
leaves of predefined weights. The most important application of Huffman trees is Huffman
codes.

A Huffman code is an optimal prefix-free variable-length encoding scheme that assigns bit
strings to symbols based on their frequencies in a given text.

This is accomplished by a greedy construction of a binary tree whose leaves represent the
alphabet symbols and whose edges are labelled with 0’s and 1’s.

Code word: Encoding a text that comprises n characters from some alphabet by assigning to each
of the text’s characters some sequence of bits. This bits sequence is called code word.

Fixed length encoding: Assigns to each character a bit string of the same length.

Variable length encoding: Assigns code words of different lengths to different characters.

Problem:

How can we tell how many bits of an encoded text represent ith character?

We can use prefix free codes

Prefix free code: In Prefix free code, no codeword is a prefix of a codeword of another character.

Binary prefix code:

 The characters are associated with the leaves of a binary tree.

 All left edges are labelled 0
 All right edges are labelled 1
 Codeword of a character is obtained by recording the labels on the simple path from the
root to the character’s leaf.
 Since, there is no simple path to a leaf that continues to another leaf,
 no codeword can be a prefix of another codeword

Dept. of AI & ML, KIT, Tiptur Page 24

Analysis & Design of Algorithms Module 4 BCS401

Huffman algorithm:
 Constructs binary prefix code tree
 By David A Huffman in 1951.
 Huffman’s algorithm achieves data compression by finding the best variable length
binary encoding scheme for the symbols that occur in the file to be compressed.
 Huffman coding uses frequencies of the symbols in the string to build a variable rate
prefix code
 Each symbol is mapped to a binary string
 More frequent symbols have shorter codes
 No code is a prefix of another code
 Huffman Codes for Data Compression achieves 20-90% Compression

Huffman’s algorithm

Step 1: Initialize n one-node trees and label them with the symbols of the alphabet given. Record
the frequency of each symbol in its tree’s root to indicate the tree’s weight. (More generally, the
weight of a tree will be equal to the sum of the frequencies in the tree’s leaves.)

Step 2: Repeat the following operation until a single tree is obtained. Find two trees with the
smallest weight (ties can be broken arbitrarily). Make them the left and right subtree of a new
tree and record the sum of their weights in the root of the new tree as its weight.

Dept. of AI & ML, KIT, Tiptur Page 25

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 26

Analysis & Design of Algorithms Module 4 BCS401

Dept. of AI & ML, KIT, Tiptur Page 27