DAA NOTES
Data= data is information that has been translated into a form that is efficient for movement or processing.
Algorithm= An algotithm is a finite set of instruction that accomplishes a particular task in a finite number
of time .
Chracteristic of algorithm=Language Independent: The Algorithm designed must be language-independent, i.e. it must be
just plain instructions that can be implemented in any language,
Feasible: The algorithm must be simple, and practical it should not contain any future technology
Finite-ness: The algorithm must be finite, i.e. it should not end up in an infinite loops or similar.
Well-Defined Inputs, Well-Defined Outputs,clear
PROCESS OF DESIGN ALGORITHM=UNDERSTAND THE PROBLEM, SOLUTION as an algorithm, algorithm technique ,prove
correctness(testing algorithm),then analze an algorithm,coding an algorithm( it should not in particular langugee), we use
general notation pseudo code.
Disadvantages of Algorithms: Writing an algorithm takes a long time so it is time-consuming., Branching and Looping statements are difficult to show
Algorithms.
PERFORMANCE ANALYSIS= Performance ana lysi s of an algorithm is don e to unde rstan d how e fficient that a lgorith m is
compare d to anothe r a lgorit hm . We take two thin g into consideration , Space ComplexityThe space re quirement is
relate d to memory resou rce needed by the al go rithm to solv e a computational problem . Time Complexity The time
complexit y is the amount of time re quired to run the program to completion .BEST CASE O(1)= INPUT ARE PROVIDED
IN SUCH A WAY MINIM UM T IME IS REQUIRED ,AVERAGE CASE,WORST CASE O(n) .
Asymptotic notations are the mathematical notations used to describe the running time of an algorithm. There are mainly three
asymptotic notations:Big-O notation,Omega notation,Theta notation.
Big-O notation represents the upper bound of the running time of an algorithm. it gives the worst-case complexity of an algorithm .
Omega notation represents the lower bound of the running time of an algorithm. Thus, it provides the best case complexity of an algorithm .
Theta notation= it represents the upper and the lower bound of the running time of an algorithm, it is used for analyzing the average-case complexity of an algorithm
Little oh notation.
Pseudocode : It is a simpler version of a programming code in plain English which uses short phrases to write code for a program before it is implemented in a specific
programming language.
Program : It is exact code written for problem following all the rules of the programming language
A flowchart is a graphical representation of an algorithm .
Recurence relation= A recurrence is an equation or inequality that describes a function in terms
of its values on smaller inputs. To solve a Recurrence Relation means to obtain a function defined on the
natural numbers that satisfy the recurrence.
https://www.javatpoint.com/daa-recurrence-
relation#:~:text=A%20recurrence%20is%20an%20equation,numbers%20that
%20satisfy%20the%20recurrence.
Divide and conquer= IT IS A algorithm design technioque
The "divide-and-conquer" technique involves solving a p problem by dividing it into one or more sub-problems of
smaller size, recursively solving each sub-problem and then "merging" the solution of sub-problems to produce a
solution to the original problem.
Application of DnC= SOME METHOD ARE = Binary search,quick sort,merge sort.
Binary search= it is SEARCHING TECHNIQUE which work only with sorted list. The method start with looking middle elemnt.kif
it matches with the search element,search complete.otherwise it may be in first half or second half
Algorithm of binary search=Compare x with the middle element.
If x matches with the middle element, we return the mid index.
Else If x is greater than the mid element, then x can only lie in the right half subarray after the mid element. So we recur for
the right half.
Else (x is smaller) recur for the left half.
Advantage of binary search= it is faster than sequential search,it take fewer comparision.
Disadvantage= It can apply only to sorted list
Quick sort= is a sorting algorithm. The algorithm picks a pivot element and rearranges the array elements so that all
elements smaller than the picked pivot element move to the left side of the pivot, and all greater elements move to the right
side.
Algorithm= Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list
excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and
right
Step 8 − if left ≥ right, the point where they met is new pivot
Advantage of QS=fast sorting method among all sorting method
Merge sort= it is sorting algorithm. The algorithm divides the array into two halves, recursively sorts
them, and finally merges the two sorted halves.
Algorithm =Step 1 − if it is only one element in the list it is already
sorted, return.
Step 2 − divide the list recursively into two halves until it can
no more be divided.
Step 3 − merge the smaller lists into new list in sorted order.
Efficiency of merge sort= O(nLogn) in all three case, and space complexity 0(2n).
Advantage/ application= Merge Sort is useful for sorting linked lists in O(n Log n) time.
Merge sort can be implemented without extra space for linked lists.
Disadvantage= mergesort requires an additional space of O(n).
• Even if the array is sorted, the merge sort goes through the entire process.
Greedy method = It is most straight forward method. It is popular for obtaining the
optimized solutions.
Optimization Problem: An optimization problem is the problem of finding the best solution (optimal
solution) from all the feasible solutions (practicable of possible solutions).
In an optimization problem we are given a set of constraints and an optimization functions. Solutions that satisfy
the constraints are called feasible solutions.
A feasible solution for which the optimization function has the best possible value is called optimal solution.
APPLICATION = 1) job seq with deadline=This problem consists of n jobs each associated with a deadline and profit and our
objective is to earn maximum profit. We will earn profit only when job is completed on or before deadline. We assume that each job will take unit time to complete.
It can be optimized using Priority Queue(max heap).
Algorithm for job seq= 1)we Sort all jobs in decreasing order of profit.
2) Iterate on jobs in decreasing order of profit.For each job
a)we Find a time slot i, such that slot is empty and i < deadline and i is greatest. We Put the job in
this slot and mark this slot filled.
b) If no such i exists, then ignore the job
2)KNAP SACK PROB= Given the weights and values of n items, we need to put these items in a knapsack of
capacity W to get the maximum total value in the knapsack. we can break items for maximizing the total value
of knapsack. The basic idea of the greedy approach is to calculate the ratio value/weight for each item and sort
the item on basis of this ratio. Then take the item with the highest ratio and add them until we can ’t add the next
item as a whole and at the end add the next item as much as we can.
3) MST= In a weighted graph, a minimum spanning tree is a spanning tree that has minimum weight than all other spanning trees
of the same graph. In real-world example this weight can be measured as distance,traffic
Prims algo is a greedy algorithm that is used to find the minimum spanning tree from a graph. Prim's algorithm finds the
subset of edges that includes every vertex of the graph such that the sum of the weights of the edges can be minimized.
Prim's algorithm starts with the single node and explores all the adjacent nodes with all the connecting edges at every step.
The edges with the minimal weights causing no cycles in the graph got selected.
The steps are= First, we have to initialize an MST with the randomly chosen vertex.
Now, we have to find all the edges that connect the tree in the above step with the new vertices. From the edges found, select
the minimum edge and add it to the tree
Repeat step 2 until the minimum spanning tree is formed.
Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The
main target of the algorithm is to find the subset of edges by using which we can traverse every vertex
of the graph. It follows the greedy approach that finds an optimum solution at every stage instead of
focusing on a global optimum. The steps -First, sort all the edges from low weight to high.
2)Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be
added creates a cycle, then reject the edge. 3)Continue to add the edges until we reach all
vertices, and a minimum spanning tree is created.
Minimum spaning tree= A spanning tree is a subset of Graph G, which has all the
vertices covered with minimum possible number of edges. Hence, a spanning tree does not
have cycles and it cannot be disconnected. Every connected and undirected Graph G has at
least one spanning tree. A disconnected graph does not have any spanning tree.
Maximum n power n-2 spanning tree
Properties of spanning tree= no loop, does not have any cycle
A connected graph can have more than one st
Spanning tree have n-1 edge, complete graph have n power n-2 spanning tree.
Application of spaning tree= network planning, computer network routing
Dijkstra’s algorithm is very similar to Prim’s algorithm. The shortest-path tree is
built up, edge by edge. We maintain two sets: a set of the vertices already included in the
tree and the set of the vertices not yet included. The Greedy Choice is to pick the edge that
connects the two sets and is on the smallest weight path from source to the set that contains
not yet included vertices.
Create a (shortest path tree set) that keeps track of vertices
Dijkstra’s Algorithm
included in shortest-path tree, i.e., whose minimum distance from the source
is calculated and finalized. Initially, this set is empty.
Then we Assign a distance value to all vertices in the input graph. Initialize all
distance values as INFINITE. Assign distance value as 0 for the source vertex so that
it is picked first.
While sptSet doesn’t include all vertices 1)Pick a vertex u which is not there in sptSet
and has a minimum distance value. 2)Include u to sptSet.2)Update distance value of
all adjacent vertices of u. To update the distance values, iterate through all adjacent
vertices. For every adjacent vertex v, if the sum of a distance value of u (from
source) and weight of edge u-v, is less than the distance value of v, then update the
distance value of v.
Optimal merge pattern =When two or more sorted files are to be merged altogether to form a
single file, the minimum computations are done to reach this file are known as OptimalMerge
Algorithm=Add all the nodes in a priority queue (Min Heap).{node.weight = file size} (2)Initialize count = 0 //
variable to store file computations
(3).Repeat while (size of priority Queue is greater than
a) create a new node
b)new node = pq.poll().weight+pq.poll().weight;//pq denotes priority queue, remove 1st smallest and 2nd
smallest element and add their weights to get a new node
c) count += node.weigh t d)add this new node to priority queue;
GRAPH= A Graph is a non-linear data structure consisting of nodes and edges. A
graph can be represented in mainly two ways. They are:
Adjacency matrix representation makes use of a matrix (table) where the first row and first column
of the matrix denote the nodes (vertices) of the graph. The rest of the cells contains either 0 or
1 (can contain an associated weight w if it is a weighted graph).it work on DENSE GRAPH
In the adjacency list representation, we have an array of linked-list where the size of the array is the
number of the vertex (nodes) present in the graph. Each vertex has its own linked-list that contains the
nodes that it is connected to. It work on SPARSE GRAPH
Breadth First Search:
BFS stands for Breadth First Search is a vertex-based technique for finding the shortest path in the graph. It
uses a Queue data structure that follows first in first out. In BFS, one vertex is selected at a time when it is
visited and marked then its adjacent are visited and stored in the queue. It is slow er than DFS.
Depth First Search:
DFS stands for Depth First Search is an edge-based technique. It uses the Stack data structure and performs
two stages, first visited vertices are pushed into the stack, and second if there are no vertices then visited
vertices are popped .
A connected component or simply component of an undirected graph
isa subgraph in which each pair of nodes is connected with each other via a path
BackTracking= Backtracking is an algorithmic-technique for solving problems
recursively by trying to build a solution one piece at a time, removing those
solutions that fail to satisfy the constraints of the problem at any point of time.
Uses brute force approach A brute force approach is an approach that finds all the possible solutions to find a
satisfactory solution to a given problem.
Backtracking is dfs (DEPETH FIRST SEARCH ) with some bounding function.
Explicit constraint/implicit constraintExplicit constraints are rules that restrict each xi to take on values only
from a given set. – Explicit constraints depend on the particular instance I of problem being solved – All
tuples that satisfy the explicit constraints define a possible solution space for I
Implicit constraints are rules that determine which of the tuples in the solution space of I satisfy the
criterion function. – Implicit constraints describe the way in which the x is must relate to each other
state-space tree is the tree of the construction of the solution from partial solution starting with the root with no
component solution
Application= Nqueen problem= The N Queen is the problem of placing N chess queens on an
N×N chessboard so that no two queens attack each other.
2) A queen attacks another queen if the two are in the same row, column, or diagonal
3) two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|
Algorithm= 1) Start in the leftmost column ,(2) If all queens are placed then return true,(3) Try all rows in the
current column, Do following for every tried row.
(a) If the queen can be placed safely in this then mark this [row, column] as part of the solution and recursively
check if placing queen here leads to a solution
b) If placing the queen in [row, column] leads to a solution then return true.
c) If placing queen doesn't lead to a solution then unmark this [row, column] (Backtrack) and go to step (a) to try other row 4)
If all row have been tried and nothing worked, return false to trigger backtracking.
sum of subset prob= Subset sum problem is to find subset of elements that are selected from a given
set whose sum adds up to a given number K.In this problem, there is a given set with some integer elements. And
another some value is also provided, we have to find a subset of the given set whose sum is the same as the given
sum value.Here backtracking approach is used for trying to select a valid subset when an item is not valid, we will
backtrack to get the previous subset and add another element to get the solution.
Graph coloring= problem involves assigning colors to certain elements of a graph subject to certain restrictions
and constraints
Algorithm=By using the backtracking method, the main idea is to assign colors one by one to different vertices right from the first
vertex (vertex 0).Before color assignment, check if the adjacent vertices have same or different color by considering already
assigned colors to the adjacent vertices.If the color assignment does not violate any constraints, then we mark that color as part of
the result. If color assignment is not possible then backtrack and return false.
Hamiltonian cycles= In an undirected graph, the Hamiltonian path is a path, that visits each vertex exactly once, and the
Hamiltonian cycle or circuit is a Hamiltonian path, that there is an edge from the last vertex to the first vertex.
ALGORITHM HAMILTONIAN CYCLE=Create an empty path array and add vertex 0 to it. Add other vertices, starting from the
vertex 1. Before adding a vertex, check for whether it is adjacent to the previously added vertex and not already added. If w e
find such a vertex, we add the vertex as part of the solution. If we do not find a vertex then we return false.
Backtracking Branch n bound
[1] It is used to find all possible solutions available to the problem. [1] It is used to solve optimization problem.
[2] It traverse tree by DFS(Depth First Search). [2] It may traverse the tree in any manner, DFS or BFS.
[3] It realizes that it has made a bad choice & undoes the last choice by backing up. [3] It realizes that it already has a better optimal solution that the pre-
[4] It search the state space tree until it found a solution. solution leads to so it abandons that pre-solution.
[5] It involves feasibility function.
[4] It completely searches the state space tree to get optimal solution.
[5] It involves bounding function.
DYNAMIC PROGRAMING= Dynamic Programming is method an algorithmic paradigm
that solves a given complex problem by breaking it into subproblems and stores the results of
subproblems to avoid computing the same results again Dynamic Programming is mainly used
when solutions of the same subproblems are needed again and again.
Application = all pair shortest path= The all pair shortest path algorithm is also known as Floyd-Warshall
algorithm is used to find all pair shortest path problem from a given weighted graph. As a result of this
algorithm, it will generate a matrix, which will represent the minimum distance from any node to all other
nodes in the graph.
travelling salesperson problem= Travelling sales person problem is to find the route travelled by the salesman starting from
one vertex and touching each vertex exactly once and returning back to the starting vertex. The main objective of this
problem is to minimize the travelling cost of the sales person.
0-1 knapsack problem= In this we have Given some weights and values of n items, we put these items in a knapsack of
capacity W to get the maximum total value in the knapsack. W which represents knapsack capacity, we need to find out
the maximum value such that sum of the weights of this subset is smaller than or equal to W. we cannot break an item,
either pick the complete item or don’t pick it (0-1 property)
diff b/w DP AND divide and conquer
Branch and bound=An algorithmic technique to find the optimal solution by keeping the
best solution found so far. If a partial solution cannot improve on the best, it is abandoned.
Application = Travelling salesman problem=Given a set of cities and distance between every pair of cities,
the problem is to find the shortest possible tour that visits every city exactly once and returns to the starti ng
point.
Difference Hamiltonian cycle and travelling salesman problem
Hashing
Hashing is the process of transforming any given key or a string of
characters into another value. This is usually represented by a
shorter, fixed-length value or key that represents and makes it easier to
find or employ the original string. The most popular use for hashing is
the implementation of hash tables.
Hash collsion and resolution technique
https://www.tutorialandexample.com/collision-resolution-techniques-in-data-
structure#:~:text=The%20hash%20value%20is%20used,we%20use%20collision%20r
esolution%20techniques.
B-tree
B-tree is a special type of self-balancing search tree in which each node can contain
more than one key and can have more than two children. It is a generalized form of
the binary search tree.
Btree properties=Each B-Tree node has a maximum of m children. (2)Each node in a B tree
includes at least m/2 children, except the root node and the leaf node.(3)At least two root
nodes are required. (4)All nodes of the leaf must be on the same level.
Operation= insertion
1) Initialize x as root.
2) While x is not leaf, do following
..a) Find the child of x that is going to be traversed next. Let the child be y.
..b) If y is not full, change x to point to y.
..c) If y is full, split it and change x to point to one of the two parts of y. If k is smaller
than mid key in y, then set x as the first part of y. Else second part of y. When we split
y, we move a key from y to its parent x.
3) The loop in step 2 stops when x is leaf. x must have space for 1 extra key as we
have been splitting all nodes in advance. So simply insert k to x.
Deletion=Deleting an element on a B-tree consists of three main events: searching
the node where the key to be deleted exists, deleting the key and balancing the
tree if required.
https://www.geeksforgeeks.org/delete-operation-in-b-tree/
Threaded binary tree=hreaded binary tree is a simple binary tree but they have a
speciality that null pointers of leaf node of the binary tree is set to inorder
predecessor or inorder successor.
The main idea behind setting such a structure is to make the inorder and preorder
traversal of the tree faster without using any additional data structure(e.g auxilary
stack) or memory to do the traversal.
