DYNAMIC PROGRAMMING:
⚫ Dynamic programming is a technique for solving problems with overlapping
subproblems.
⚫ These subproblems arise from a recurrence relating a given problem’s solution to
solutions of its smaller subproblems.
⚫ Rather than solving overlapping subproblems again and again, solve each of the
smaller subproblems only once and record the results in a table from which a solution
to the original problem can then be obtained.
Basic Example:
Computing Binomial Coefficient:
Knapsack problem and memory functions:
Memory Functions:
Warshall’s and Floyd’s Algorithms:
Used for computing the transitive closure of a directed graph. The transitive closure of a directed
graph with ‘n’ vertices can be defined as the n × n Boolean matrix T = {tij}, in which the element in
the ith row and the jth column is 1 if there exists a nontrivial path (i.e.,directed path of a positive
length) from the ith vertex to the jth vertex; otherwise, tij is 0.
Applications of transitive closure
● When a value in a spreadsheet cell is changed, the spreadsheet software must know all the
other cells affected by the change. If the spreadsheet is modelled by a digraph whose
vertices represent the spreadsheet cells and edges indicate cell dependencies, the transitive
closure will provide such information.
● In software engineering, transitive closure can be used for investigating data flow and
control flow dependencies as well as for inheritance testing of object-oriented software.
● In electronic engineering, it is used for redundancy identification and test generation for
digital circuits.
Rules for changing zeros to one.
⚫ If an element rij is 1 in R(k−1), it remains 1 in R(k).
⚫ If an element rij is 0 in R(k−1), it has to be changed to 1 in R(k) if and only if the element in its
row i and column k and the element in its column j and row k are both 1’s in R(k−1).
Time complexity for warshall O(n3)
Floyd’s Algorithm for the All-Pairs Shortest-Paths Problem
Given a weighted connected graph (undirected or directed), the all-pairs shortestpaths problem asks
to find the distances—i.e., the lengths of the shortest paths— from each vertex to all other vertices.
Floyd’s is applicable to both undirected and directed weighted graphs provided that they do not
contain a cycle of a negative length.
Time complexity of warshall O(n3)
GREEDY METHOD:
Prim’s algorithm:
Dijkstra’s Algorithm:
The algorithm maintains a set of visited vertices and a set of unvisited vertices.
It starts at the source vertex and iteratively selects the unvisited vertex with the
smallest tentative distance from the source. It then visits the neighbours of this
vertex and updates their tentative distances if a shorter path is found. This
process continues until the destination vertex is reached, or all reachable
vertices have been visited.
The need for Dijkstra’s algorithm arises in many applications where finding the
shortest path between two points is crucial.
For example, It can be used in the routing protocols for computer networks and
also used by map systems to find the shortest path between starting point and
the Destination.
in 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 O(|E| log |V |).
Huffman Trees and Codes: