M269 – Algorithm and Data structure – Final Revision 1

M269 – Algorithm and Data structure – Final Revision 2

 Terminologies

Algorithm Purpose complexity

1 Depth first traverses a graph in a depth ward motion & uses a stack to remember O(n + m )
search DFS next vertex to start a search, when a dead end occurs in iteration
2 Breadth traverses a graph in a breadth ward motion and uses a queue to get O(n + m )
first search next vertex to start a search, when a dead end occurs in iteration
-BFS
3 Naïve For solving the string searching problem by performing Brute-Force O(mn)
matching comparison of each character in the pattern at each possible
placement of the pattern in the string.
4 Knuth- KMP Compares the pattern to text in left-to-right but shifts the O(m + n)
Morris Pratt pattern more intelligently than Brute-Force.
5 Minimum the min heap makes the key of a node is ≤ the keys of its children. So O(n log n)
heapify minimum-heapify function correct a single violation of the heap
function property in a subtree at its root.
6 Kruskal find the minimum cost spanning tree uses the greedy approach. O(E log V)
7 Dijkstra Finds shortest (minimum weight) path between a particular pair of O(V2)
vertices in a weighted directed graph with nonnegative edge weights.
8 Hash Table Stores data in array in an associative manner, each value has unique O(1)
index value. Access becomes very fast if index of desired data is
known, Collisions happened if multiple keys can hash to same slot.
9 Quick-select Is a selection algorithm to find the k-th smallest element in an
Algorithm unordered list. It is related to the quick-sortsrting algorithm.

 Paradigms of Algorithms
1 Brute force A very general problem-solving technique that compares pattern P with text T
for each possible shift, final solution is obtained by systematically enumerating
all possible candidates and exhaustively check all of them, For example,
Selection & insertion sort algorithms…naïve pattern matching algorithm.
2 Greedy The solution constructed through a sequence of steps. At each step, the next
Algorithms optimal step is selected locally, without considering whether this step leads to
the final global optimal solution or not For example, Kruskal, Dijkstra algorithm
3 Divide-and- Divide the problem to several smaller sub-problems then solve each one
Conquer independently. Finally, the solutions of these sub-problems combined to form
final solution.
For example Merge and quick sort algorithm.
4 Dynamic Solve problem of divide-conquer where identical sub-problems are computed
Programming repeatedly. Smallest sub-problems are solved first and results are placed in
table to be used to construct larger sub-instances solution.
For example Floyd-Warshall algorithm.
5 Optimization In general, optimization includes finding "best available" values of some
Programming objective function given a defined domain (or input), including a variety of
different types of objective functions and domains.
For example genetic algorithm.
 M269 – Algorithm and Data structure – Final Revision 3

 Important (What is the complexity of the following tasks?)

1 Sorting a list of N elements using Bubble-Sort algorithm. O(n2 )
2 Sorting a list of N elements using Heap-Sort algorithm. O(n log n)
3 Finding the largest element in a queue of size n. O(n)
4 Inserting an item in a queue data-structure. O(1)
5 Remove an item in a stack data-structure. O(1)
6 Searching for a pattern of size M into a string of size N using Naïve algorithm. O(MN)
7 Searching for a pattern of size M into a string of size N using KMP algorithm. O(N+M)
8 Traversing a tree using a Depth First algorithm, where E is the number of O(|V|+|E|)
edges and V is the number of vertices.
9 Finding the minimum- spanning tree for a given graph, where E is the number O(E log E) or
of edges and V is the number of vertices O(E log V)
10 Implementing Binary Search algorithm on a sorted list of length N. O(Log N)

Eulerian Path Eulerian Circuit

A path that visits every edge exactly once. An Eulerian Path which starts and ends on same vertex
1. All vertices are connected. 1. All vertices are connected.
2. If two vertices have odd degree and all 2. All vertices have even degree.
other vertices have even degree.
 M269 – Algorithm and Data structure – Final Revision 4

 Graph vs Tree
1. a non-linear data structure
2. It is a collection of nodes and edges
Graph : G = {V, E}. Tree :
Collection of two sets V and E where A tree is a finite set of one or more nodes such that
V is a finite non-empty set of vertices 1. There is a specially designated node called root.
E is a finite non-empty set of edges. 2. The remaining nodes are child
There is no unique node called root in graph There is a unique node called root in trees
A cycle can be formed There will not be any cycle

G = {{V1, V2, V3, V4, V5, V6}, {E1, E2, E3, E4, E5,
E6, E7}}
Applications: finding shortest path in network Applications: For game trees, decision trees
Graph : G = {V, E}. Tree :
Collection of two sets V and E where A tree is a finite set of one or more nodes such that
V is a finite non-empty set of vertices 1. There is a specially designated node called root.
E is a finite non-empty set of edges. 2. The remaining nodes are child
There is no unique node called root in graph There is a unique node called root in trees
A cycle can be formed There will not be any cycle

G = {{V1, V2, V3, V4, V5, V6}, {E1, E2, E3, E4, E5,
E6, E7}}
Applications: finding shortest path in network Applications: For game trees, decision trees

 tree: a connected, directed acyclic graph

 spanning tree: a subgraph of a graph, which meets the constraints to be a tree (connected,
acyclic) and connects every vertex of the original graph
 minimum spanning tree: a spanning tree with weight less than or equal to any other spanning
tree for the given graph
 M269 – Algorithm and Data structure – Final Revision 5

 Hash table
o Stores data in array in an associative manner, each value has unique index value. Access
becomes very fast if index of desired data is known, Collisions happened if multiple keys
can hash to same slot (Slot collision), solved by :

1. linear Probing
 All elements stored in hash table itself.
 When collisions occur, use a systematic (consistent) procedure to store elements in
free slots of the table.
2. Chaining:
 Store all elements that hash to the same slot in a linked list.
 Store a pointer to the head of the linked list in the hash table slot

 Simple uniform hashing O(1)

o Is most commonly used as a foundation for mathematical proofs describing the properties
and behavior of hash tables in theoretical computer science. Minimizing hashing collisions
can be achieved with a uniform hashing function. These functions often rely on the specific
input data set and can be quite difficult to implement. Assuming uniform hashing allows
hash table analysis to be made without exact knowledge of the input or the hash function
used.
o There are two cases, once when the search is successful and when it is unsuccessful, but in
both the cases, the complexity is O(1+alpha) where 1 is to compute the hash function and
alpha is the load factor.

 Quick-select Algorithm
Examples: Input: arr[] = {7, 10, 4, 3, 20, 15} k = 3 output: 7
Input: arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output: 10
Important Points:
1. Like quicksort, it is fast in practice, but has poor worst-case performance. It is used in
2. The partition process is same as QuickSort, only recursive code differs.
3. There exists an algorithm that finds k-th smallest element in O(n) in worst case, but
QuickSelect performs better on average.
 Minimum heapify function
1. Build Min Heap from unordered array;
2. Find minimum element A[1];
3. Swap elements A[n] and A[1]
4. Discard node n from heap
5. Run minimum_heapify.
6. Go to Step 2 unless heap is empty
 M269 – Algorithm and Data structure – Final Revision 6

 The types of problems: P, NP, NP-Complete, NP-Hard problem

1 P problems Are questions that have yes/no answer & can be easily solved by computer?
For example, determining whether a number is a prime or not.
2 NP problems Are questions that have yes/no answers that are easy to verify, but are hard
to answer.
For example, the travelling salesman problem is trying to figure out the
shortest trip through a bunch of cities, visiting each city only once
3 NP-complete Are special kinds of NP problems. You can take any kind of NP problem and
problems twist and contort it until it looks like an NP-complete problem.
For example, the knapsack problem is NP.
4 NP-Hard Are worst than NP problems. Even if someone suggested you a solution to a
problems NP-Hard problem, it'd still take forever to verify if they were right.
For example, in travelling salesman, trying to figure out the absolute shortest
path through 500 cities in your state would take forever to solve.

 Logic
1 Prepositional Is the branch of logic that studies ways of joining and/or modifying entire
Logic: sentences to form more complicated sentences, as well as the logical
relationships and properties that are derived from these methods of
combining or altering statements.
Other names: Propositional logic, sentential logic, statement logic
2 Predicate logic is a formal language in which propositions are expressed in terms of
predicates, variables and quantifiers. It should be viewed as an extension to
propositional logic, which lacks quantifiers.
Other names: first-order logic or quantified logic
3 Logic is a type of programming which is largely based on formal logic. Any program
programming written in a logic programming language is a set of sentences in logical form,
expressing facts and rules about some problem domain.

4 Turing is a mathematical model of computation that operates on an infinite memory

machine tape divided into cells. The machine put its head over a cell and "reads" the
symbol there. Then, as per the symbol take place in a finite table of user-
specified instructions, each instruction either proceeds or halts the
computation.
5 Finite State is a mathematical model of computation that can be in exactly one of a finite
Machine number of states at any given time. The FSM can change from one state to
(FSM) another in response to some external inputs; the change of states called a
transition.
6 The Halting Given a program and an input to the program, determine a particular input to
problem stop the program. If the program does not stop, then it is in an infinite loop
and this problem is unsolvable.
 M269 – Algorithm and Data structure – Final Revision 7

 Computability and Limits of Computation:

1 Limits on Arithmetic Hardware limitation on representations of maximum number of
significant digits is limited to a certain value (integer & real numbers)
2 Limits on Although most errors caused by software, hardware components do
Components fail
3 Limits on They are the limits that make communication as such possible, as in,
Communications for example, distinctions between signal and noise.
4 Limits of software Commercial software contains errors. Software testing can show the
presence of bugs but cannot show their absence.
 M269 – Algorithm and Data structure – Final Revision 8

 Selection sort vs bubble sort

SELECTION SORT BUBBLE SORT
Basic Largest element is selected & swapped with the Adjacent element is compared
last element (in case of ascending order). and swapped
Best case time O(n2) O(n)
complexity
Efficiency Improved efficiency as compared to bubble sort Inefficient

Stable No Yes

Method Selection Exchanging

Speed Fast as compared to bubble sort Slow
M269 – Algorithm and Data structure – Final Revision 9
 M269 – Algorithm and Data structure – Final Revision 10

This algorithm is better since it has O(n) as linear time.

M269 – Algorithm and Data structure – Final Revision 11