CS302

Algorithm:
- a step by step process solving a problem.
- for all inputs, the correct output must be computed.
- Must run a finite time (must stop at some point).

HOW do we measure run time for an algorithm?

Real time
Growth rate/scaling rate. (The amount of steps needed for our algorithm/code to complete
one task)
>> code can be modeled by a function of n, where n is the size of the input.

One we have the growth rate of the algorithm we want to classify it into asymptotic complexity
class.
Constant 1 Larger growth rate
Logarithmic log(n)
Linear n
Poly logarithmic nlog(n)
Quadric n^2
Cubic n^3
Slower algorithm
Exponential 2^n

3000n + 70000 = Q(n^2) (false)

Lim (3000n + 70000)/n^2 = 3000/2n = 0

Square root of n = O(logn)

√n <= O(logn) (false)

lim √n/ln(n) = (1/2√n)/(1/n) = n/(2√n) = √n/2 = ∞

Sequential/linear search
Bool find(int a[], int n, int s) {
for(int i = 0; i <= n, I++)
if(a[i] == s) return true;
return false;}
Worst case scenario: s is in the last index or not in the array.
O(n) ->upper bound for the worst case
Q(n)
Ω(n)

Best case scenario: s is in the first index of the array

O(1)
Q(1)
Ω(1)

Average case: the loop runs a fraction of n amount of times.

O(n)
Q(n)
Ω(n)

Binary search
bool find(int a[], int n, int s){
int l, r, m;
l=0;
r = n-1;
while (l<=r)
m= l+(r-l)/2;
if (a[m]==s) return true;
if (a[m]<s)
l=m+1;
else
r=m-1;
Return false;
Worst case scenario: s is not in the array or when l==r
O(logn)
Q(logn)
Ω(logn)

For sorted array

Linear search O(n)
Binary search O(logn)

Unsorted array
Linear Search O(n)
Binary search: does not work.

- Suppose we are given an unsorted array, and suppose we decide to sort the array first then run
binary search.
- depend on the amount of searches because sorting is performed on time.
O(logn) + O(mlogn)
M: amount of search.
Logn: runtime for binary search.
O(logn): sort runtime

Many search -> worth sorting the array.

Note: log(n!) = Q(nlogn).

Insert sort

Merge sort
• Divide and conquer algorithm
• Recursive function

Given an array ion size n (indices range from 0 to n-1)

• Divide the array into two halves.
• Call merge sort on each half. (Obtain two sorted halves)
• Merge the two sorted halves, we have one sorted size n array.

Merge function

1 2 5 7 3 6 11 12

i j

1 2 3 5 6 7 11 12

k
Compare arr[i] to arr[j], then pass the smaller value to arr[k], then increment by one for k
and (i or j).
Merge has a linear runtime. Runtime to merge n/2 size sorted arrays take O(n) time.

Merge < Insertion

Quick Sort
• Divide and conquer
• Recursive function
• Run the partition function (essentially divide the array into two sides)
- Smaller elements on the left side, larger elements to the right.
• Quick sort the smaller side
• Quick sort the larger side

Partition(array, left, right)

- Choose an element as the pivot (pivot = array[left]).
- i = left + 1
- j = right
- While (i <= j)
{if (array[i] < pivot) i++
if (array[j] > pivot) j- -
}
If i and j both didn’t move
swap(array[i], array[j])
i++
j- -
return j

quicksort(array, left, right)

Int p = partition(array, left, right)
swap(array[left], array[p])
Elements from left to p-1
quicksort(array, left, p-1)
elements from p+1 to right
quicksort(array, p+1, right)

Some methods to avoid the worst case of quick sort

1. Don’t worry about it.
2. Choose a pivot randomly in the array.
3. Choose the median as the pivot. (You can find a median of an unsorted array without sorting
O(n) time)
Binary tree

Class binTreeNode
{
public:
int data;
binTreeNode* left;
binTreeNode* right;
};

Template <class T>

Class binTreeNode
{
public:
T data;
binTreeNode<T>* left;
binTreeNode<T>* right;
};

Traversal (Binary tree)

Preorder
For any trees Recursive
Postorder
Inorder For only binary tree
Level order Not recursive

Recursive def of a binary tree

• Empty tree (base case).
• A binary tree node whose left and right pointers point to a binary tree.

void preorder (binTreeNode* r){

if(r == nullptr)
return;
cout <<r->data <<endl;
preorder(r->left);
preorder(r->right);
return;
}
 Preorder Output
5
5
3
3 7 2
4
1 11 8———- 7
2
1
12
4 8 11
15
15 22 22

int main(){ Postorder Output

binTreeNode* root; 4
//… 8
preorder(root); 2
return 1; 3 ———-1
} 15
22
12
11
7
void postorder (binTreeNode* r) {
5
if (r == nullptr)
return; int main(){
binTreeNode* root;
postorder(r->left); //…
postorder(r->right); postorder(root);
return 1;
cout <<r->data <<endl; }
return;
}

Write a recursive function that counts the amount of leaves in the binary tree
int leaves (binTreeNode* r){
if (r==nullptr)
return 0; int main(){
if (r->left == nullptr && r->right == nullptr) binTreeNode* root;
return 1; //…
int leftLeaves = leaves(r->left); cout <<
int rightLeaves = leaves(r->right); postorder(root);
return leftLeaves + rightLeaves; return 1;
} }
BINARY TREE search
Use a binary tree as a search structure.
A search structure is a structure that is organized to find elements quickly.
Every search structure has a key-value pair.

template <class t1, class t2>

Class binTreeNode
{
public:
t1 key;
t2 value;
binTreeNode <t1, t2> * left;
binTreeNode<t1, t2>* right;
binTreeNode() : left(nullptr), right(nullptr) { }
};

To have a valid binary search tree for every node r

r->left->key < r->key
r->right->key > r->key
The result is that r’s entire left subtree contains keys less than r.. the entire right subtree contains
keys larger than r.

Value (int)
Key (string) Eugene
4

Chris Larry
3 9

Alex Danielle Francise Marry

7 8 12 14
Template <class t1, class t2>
Bool find ()

if(r == nullfptr){
return false;
if( r->key == s)
return true;
if (r-> key > s),
Return true;
if (r->key < s)
return find(r->key, )
if (r->key) 7 to 6)

Runtime find function

- find function body has runtime of O(1)
- traverse the largest path from the root to a leaf
Best/avg O(logn)
Worst O(n)

INSERTION

template <class t1, class t2>

binTreeNode<t1, t2> * insert (binTreeNode <t1, t2>* r, t1 k, t2 v)
{
if (r == nullptr){
binTreeNode<t1, t2> *t;
t = new binTreeNode<t1, t2>();

t->key = k;
t->value = v;
return t;
}

if (r->key < k) {
r->right = insert(r->right, k, v);
} else {
r->left = insert(r->left, k, v);
}
return r;
}
int main() {
root = insert(root, “Garry”, 7);
}

The height of a binary search tree depends on the order in which we insert elements.

AVL Trees
• A self balancing binary search tree.
• When the tree become unbalanced, we rotate the tree to fix the unbalance.

How do we know if the tree is balanced?

template<class t1, class t2>
Class binTreeNode
{
public:
t1 key;
t2 value;
size_t height;

binTreeNode<t1, t2>* left;

binTreeNode<t1, t2>* right;
binTreeNode(): left(nullptr), right(nullptr), height(0){}
};

To have a valid AVL tree (balanced binary search tree), for each node r
- The difference of r’s left height and r’s right height is at most 1.
- An empty tree has a height of -1
- R->height = new (r->left->height, r->right->height) +1

Rotations
- left rotate if the right side is too large
- Right rotate if the left side is too large
- X->right = y->left;
- Y->left = x;

Double rotation
When a gets zigzag imbalance occurs
Midterm review

1. True/false section
1. Sorting runtimes
2. Pseudo code
3. Def if each sorting algorithm
4. Linear vs binary search (O(n) vs O(logn)) (Binary works on sorted list - better runtime
growth rate. Can sort array first then use binary. Unsorted array -> Linear search)
2. O, Q, Om question
1. 30n+22= O(n^2) (<=)
2. O is <= (larger or equal)
3. lim(n->n->inf) (3n+22)/(n^2) = (LH rule) 30/2n=0 (n^2 has larger growth rate than 30n+22)
4. 30000n + 50000 = Om(n^2) (>=) lim (30000n + 50000)/(n^2) = 0 (30000n 50000 < Om) x
5. Lim (400n lnn +20n)/(n lnn) = n(400 lnn + 20)/n lnn = (400 lnn + 20)/lnn =
3. Rearrange function by growth rate
1. 1.000001^n n√n + 1000n. n^18. n^1000000. 44n+3000log2(n) + 30000√n. 5n^2 -
22000. n^3/2. log10(n!). nlog2(n)+1000n. n^1.1 + log10(n). 2^n
2.
4. C++ code snippet
1. Nested loop: loop variable i, add/subtract i by a constant (linear loop), multiple/div by a
constant (logarithmic)
5. Output a binary tree preorder and postorder
6. Write a recursive function that process a binary tree (how many nodes have 1 child/no child)
7. Trace insertion sort
8. Trace merge sort
9. Trace quick sort
10. AVL tree insertion (single rotation )
Custom hash map

• we use a hash function to map to an index of the hash table (array).

• inset/find in a has map: hash(key) -> value % table size => index

Hash function properties:

1. The hash function computes the same number/value for the same key every time.
2. The hash function should be unbiased.
3. Ideally/usually
hash(key(x)) -> value(x) % table size => index (x)
hash(key(y)) -> value(y) % table size => index (y)

Collision
hash(key(x)) -> value(x) % table size => index (x)
hash(key(y)) -> value(y) % table size => index (x)
Separate chaining (stack the cars)
- Maintain an array of linked lists for our hash table
Template <class t1, class t2> (key, value)
class hashMap
{
Private:
struct node
{
t1 key;
t2 value;
node* link;
};
node ** table;
size_t capacity; //table size
size_t items;

//hash function

Public:
hashMap()
{
capacity = s;
items = 0;
table = new node* [capacity];
for(int i = 0; i < capacity, i++) {
 table[i] = nullptr;
}
+2& operator[](f1 k)
{
size_t index = hash(k) % capacity;
if (table[index] == nullptr)
{
//create a new has entry
//return this new entry’s value field
}
for (node* i = table[index]; i != nullptr; i= i->next)
{
if (i->key == k)
return i->value;
//k was not found
//insert a new entry to the front or back of table[index]
//and return this entry’s value field
}
};

int main()
{
hashMap<string, int> sega;
sega[“Sonic”] = 17;
//hash(“Sonic”) -> 45 % 5 => 0 (index)
//key = Sonic, value = 17
sega[“Tails”] = 37;
//hash(“Tails”) -> 21 % 5 => 1
sega[“Knuckles”] = 45;
//hash(“Knuckles”) -> 20 % 5 => 0 (collision)
sega[“Knuckles”] = 47;
//hash(“Knuckles”) -> 20 % 5 => 0
sega[“Robotnik”] = 12;
//hash(“Robotnik”) -> 35 % 5 => 0
cout << sega[“Robotnik”] <<endl;
}
HASH OPEN ADRESSING

Maintain an array of linked lists (each linked list contains at most one node).
If a collision occurs, insert the record somewhere else.
Linear probing
[[hash(key) % capacity] + i] % capacity]
i: collision counter (inc by 1 after each collision) i [] reset to 0 for a new search

template<class t1, class t2>

Class hashMap
{
Private:
struct node
{
t1 key;
t2 value;
};
node ** table;
size_t capacity;
size_t items;

size_t hash(t1);

Public:
hashMap()
{
capacity = 10;
items = 0;
table = new node*[capacity];
for (int i=0; i < capacity; i++)
{
table[I]=nullptr;
}
}

t2& operator[] (t1 k)

{
size_t index = hash(k) % capacity;
size_t i = 0;
 while(1)
{
if (table[index] == nullptr)
{
table[index] == new node;
table[index] -> key = k;
table[index] -> value = t2;

items++;
return table[index]->value;
}
if (table[index] -> key == k)
return table[index]->value;

//we have a collision

i++;
index = (index + i)%capacity;
}
}
};

HASHING RESIZE
 PRIORITY QUEUES

• A queue structure.
• Each element in the queue has a priority value.
• On insertion, we insert to the back of the queue and potentially move the element up if needed.
• The front of the queue has the highest priority value.
• Use a binary min heap to implement a priority queue. (Smallest element is at the front)
• Maintain an array that emulates the binary tree.
• Given an array
- The element at index 1 is the root node
- For any element at index i
- Left child is at index 2*i
- The right child is at index 2*i+1
- Parent is at index [i/2]

3 7 2 4 8 10 5 6

0 1 2 3 4 5 6 7 8

7 2

4 8 10 5

To have a binary tree as a valid binary min heap, the following property must apply
• For each element i is the array, the priority value at index i must be less than or equal its two children’s
priority value
template <class t1, class t2>
Class priorityQ
{
Private:
class priority Type
{
public:
t1 key;
t2 priority;
};
priority Type * heapArray;
size_t capacity;
size_t size;

unordered_map <t1, t2> KeyToIndex;

void bubbleUp(size_t);
void bubbleDown(size_t);
Public:
priorityQ()
{
size = 0;
capacity = 10;
heapArray = new priorityType[capacity + 1];
}
void push_back(t1 k, t2 p)
{
if (size == capacity)
{
//resize
}
size++;
heapArray[size].key = k;
heapArray[size].priority = p;

bubbleUp(size);
}
};
int main ()
{
priorityQ <string, int> mario_kart;

Priority Queues Pop Front

• Remove the highest priority element (remove the element with smallest priority value), remove
the root element.
• The result is the second smallest priority element goes to the root.

Void pop_front
{
heapArray[1] = heapArray[size];
size —;
bubbleDown(1);
}

CONSTRUCT a priority queue

Given an array of (key, priority) Paris in no particular order

Construct a PQ (binary min heap) using the given array

1. Declare a PQ object
Push back each item from the given array on by one into the PQ. O(nlogn)

2. Shallow copy of the given array into the heap array.

for (int i = size; i > 0; i—)
bubbleDown(i);
 GRAPH THEORY
Graph is defined as G(v, e)
V is the set of vertices. (điểm)
E is the set of edges. (cạnh)

0 3
Undirected graph
2

1 4

V = {0, 1, 2, 3, 4,}
E= {(0,1), (0,2), (0,3), (2,3), (2,4), (1,4)}

Spare graphs:
graphs with not many edges, with respect to the amount of vertices.
|E| = O(|V|) - size of the set.
The amount of edges is linear with respect to the amount of vertices. (Not many connection in the graph)

Dense graph:
Graphs with many edges with respect to the amount of vertices.
Max amount of edges:
directed graph: V^2 - V
Undirected graph: (V^2 - V)/2
|E| = O(|V^2|) - the amount of edges is quadratic with respect to the amount of vertices.
DEPTH FIRST SEARCH (DFS)
A graph traversal
Similar to preorder traversal
When you arrive at a node:
pick a neighbor (go to this neighbor)
you might reach a dead end, backtrack to the predecessor.
when you back up to the predecessor, pick a different neighbor.
Data structures needed
1. Current node id
2. Adjacency matrix/list
3. Visited array/map
4. Predecessor array/map (store the path in reverse).

void dfs (int current, vector<list<int>> adjList, vector<bool>& visited, vector<int>& predecessor)
{
if (visited[current])
return;
visited[current] = true;
cout <<current <<endl;

for (int neighborId : adjList[current])

if (!visited[neighborId])
{
predecessor[neighborId] = current;
dfs(neighborId, adjList, visited, predecessor);
}
return;
}

int main()
{
vector<list<int>> adjList;
vector<bool> visited;
vector<int> predecessor;
int v;

for(int I = 0; I < v; I++)

dfs(i, adjList, visited, predecessor);

return 0;
}

USE DFS to determine if a graph contains a cycle. 0

1. Current node id
2. Adjacency list/matrix
3. Visited array/map
1 2
4. In path array/map

bool cyclic(int current, vector <list<int>> adjList, vector<bool>& visited, vector<bool>& inPath)
{
if (visited[current])
return false;
Visited[current] = true;
inPath[current] = true;

for(int neighbor : adjList[current])

{
if (inPath[neighbor])
return true;
if (!visited[neighbor])
{
bool cycleFound;
cycleFound = cyclic(neighbor, adjList, visited, inPath);
if (cycleFound)
return true;
}
}
inPath[current] = false;
return false;
}
Dijkstra’s Minimum Weight Path Algorithm
• Single source graph traversal
• Weighted graph
• Find the minimum path weight from a start node to all nodes in the graph
• Greedy algorithm

Dijkstra (start, adjList)

Allocate a W array
Allocate a pi array
Allocate a PQ
Push start:0 onto the PQ
While PQ is not empty
pop x.v off the PQ (x: node id, v: path weight from start to node x)
for each neighbor y of x
relax(x, y, pi, PQ)
Relax(x, y, pi, PQ)
If x.v + edgeweight(x, y) < y.v
pi[y] = x
update/push y.v = x.v + edgeweight(x, y)

If a graph contains negative cycle, then there is no minimum path weight solution.

3 Fibonacci heap as a PQ
Pop he PQ |v| times
pop_front takes O(log|v|)
O(|v|log|v|)
Relax each neighbor |E| of them, push/update takes O(i) time
O(|E|)
O(|E| + |V|log|V|)
Sparse graph O(|V|log|V|) =>Better than (1), same as (2)
Dense graphO(|V|^2) => same as (1), better than (2)
Kruskals Minimum Spanning Tree
What is a tree?
it’s a graph with exactly |V| - 1 edges.
minimally connected graph
What is a spanning tree?
given an undirected graph 6(V, E)
elect a set of edges S, its size |V| - 1 S (subset) E
S contains a set of edges that connects the graph
What is a minimum spanning tree?
a spanning tree of a graph with minimal weight among all possible spanning tree.

Union - Find (Disjoint set) data structure

maintain an array of predecessor/leaders
Find (x) -> return the leader of the group x is in
If the leader[x] == x
return x;

leader[x] = Find(leader[x]) (//path compression, compress to one edge)

return leader[x]

union (x, y)
leader[x] = leader[y] //x is in the larger graph
or
leader[y] = leader[x] //y is in the larger graph

Pseudo code for kruskals algorithm

Given a graph 6(V, E)
Build a binary min heap using the set E
Allocate a set MST
Declare a union-find structure
While PQ is not empty
pop an edge (x, y) off the PQ
if find (x) != find (y)
union (X, Y)
add (x, y) to the MST

Runtime analysis
- build Heap using the set E, O(|E|)
- While the PQ is not empty, first pop the PQ => O(log|E|), find O(1), union O(1) => total of O(|E|)
O (|E| + |E| log|E|) => O(|E|log|E|)
Sparse: log|V|
Dense: log|V|^2 = 2log|V|
=> O(|E|.log|V|)
FINAL EXAM REVIEW

Thursday Dec 11th, 2025

TBE B-176, 6pm - 8pm

OUTLINE:
• Conceptual content:
T/F
Short Answers (DFS)

• AVL tree double rotation

• Hashing (linear probing), worksheet 15
Table size: 10 (%10, right most digit -> index)

• Priority queue (binary min heap)

Push (after push, update array)
Pop (pop once > show result > pop again)

• Graphs
Given a direct graph (image) > construct an adjacency list and matrix.

• Trace Dijkstra’s algorithm (worksheet)

• Trace kruskal’s algorithm (one by one, pick smallest edge)

[Link] is the lower bound on comparison based sorting and what does it mean?
Ω(n^2), no sorting algorithm can have runtime worse than this in its worst case
Ω(nlogn), no sorting algorithm can have better runtime than this in its worst case.
Ω(n), no sorting algorithm can have better runtime than this in its best case
Ω(nlogn), every sorting algorithm has this runtime in its worst case
Ω(n), every sorting algorithm has this runtime in its best case

[Link] and queues can be implemented using linked lists. Which option gives the correct optimal
implementation and run time
O(n) for all operations; stacks push and pop from the head, queues enqueue at the head and dequeue
at the tail
O(1) for all operations; stacks push and pop from the head, queues enqueue at the tail and dequeue
at the head
O(n) for all operations; stacks push and pop from the head, queues enqueue at the tail and dequeue
at the head
O(1) for push/enqueue, O(n) for pop/dequeue stacks push and pop from the head, queues enqueue at
the tail and dequeue at the head
O(1) for all operations; stacks push from the head, O(n) queues enqueue at the head and dequeue at
the tail

3. Which of the following algorithms typically has the worst run-time?

quick sort (in the average case)
merge sort
bubble sort
none of these choices
heap sort

[Link] of the following is the most likely cause of primary clustering in a hashtable?
none of these options are correct
rehashing
linear probing
quadratic probing
double hashing

5. Which of the following is correct for a minimum spanning tree?

only one loop is allowed in a minimum spanning tree

there are always at least |V| edges

there is always a unique minimum spanning tree for every graph

all of these choices are correct

a tree formed from the graph edges that connects all the vertices of graph G
at the lowest total cost

[Link] the following 3 program fragments

for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cout << "" << endl;

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)
for (int k = 0; k < n; k++)
cout << "" << endl;
for (int i = 0; i < n; i++)
cout << "" << endl;

O(n^3), O(n), O(n^2)

O(n), O(n^2), O(n^3)
O(n^3), O(n^2), O(n)
O(n), O(n^3), O(n^2)
O(n^2), O(n^3), O(n)
None of these choices are correct

9. Using asymptotic complexity, how much time does it take to perform the
following operations? (Each operation is done separately)
I. Given a balanced binary search tree (e.g., AVL or Red-Black) with
n elements, insert another n elements
II. Search for 10 values in a binary search tree with n elements
III. Delete n elements in a heap with n elements

O(nlogn), O(n), O(n^2)

O(n^2), O(n^2), O(nlogn)
O(nlogn), O(n), O(nlogn)
O(n^2), O(n), O(nlogn)

10. Given G = (V, E) and noting that G is sparse, which is the best
implementation approach to store the graph?
Adjacency List

None of these

Binary Search Tree

Hash Table

Adjacency Matrix
11. Which of the following is/are true about hash tables?
I. In general, the more space used for a table (lower load factor),
the faster the performance for insert and delete operations
II. If an entry collides with another entry, the rst thing we usually do
is increase the size of the hash table
III. Assuming enough memory, separate chaining without rehashing
allows us to insert in nitely many entries

I, II, and III

III only

I only

II only

I and III
fi
fi