TON DUC THANG UNIVERSITY

FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 4:HASHING

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES

After study this chapter, the student should be able to:

• Understand the concept of hash tables, hash functions
• Evaluate hash table Performance
• Apply hashing to practical problems
• Implement examples using in C++/Python

5/1/2026 403148 – Hashing 2

 INTRODUCTIONS
• Hashing is is a data structure (hash table), where data (value) is
mapped to specific index obtained from a key by using a hash
function.

5/1/2026 403148 – Hashing 3

 INTRODUCTIONS
Why hashing?
Speed: Hashing allows near-instant data lookup, insertion, and
deletion (O(1) average case), faster than sorting-based (O(log n) for
binary search).
Application: Used in databases (fast record lookup), caches (quick
data retrieval), symbol tables, password hashing, and encryption.
Trade-offs: Hashing doesn’t maintain order but excels at direct access.
It may require extra space and handling of collisions (when multiple
keys map to the same index).

5/1/2026 403148 – Hashing 4

 CHAPTER 4:HASHING

Core Components of Hashing

4.1. Direct Addressing Table

4.2. Hash Table

4.3. Hash Functions

4.4. Collision Resolution

5/1/2026 403148 – Hashing 5

 4.1 DIRECT ADDRESSING TABLE
• A simple data structure where each key from a universe maps
directly to an array index for fast lookups, insertions, and deletions
in O(1) time.
• It assumes the universe of keys is small enough to allocate such a
direct table.
How it works?
• Each key maps to a unique index in an array.
• The array index is the key itself
• Example: If keys are student IDs from 0 to 99, you use an array of
size 100, where array[ID] holds the data for that ID.

5/1/2026 403148 – Hashing 6

 4.1 DIRECT ADDRESSING TABLE
Characteristics
• Speed: O(1) for lookup, insertion, and deletion since the key directly
gives the index
• Space: Requires an array large enough to cover all possible keys,
which can be wasteful if keys are sparse (e.g., only a few IDs in a
large range).
• Limitation: Works only for small, dense key ranges; impractical for
large or sparse keys (e.g., phone numbers).

5/1/2026 403148 – Hashing 7

 4.2 HASH TABLE
• A data structure that stores key-value pairs (e.g., student ID →
name).
• Uses a hash function to map keys to indices in an array.
• Example: A hash table might store {123: "Alice", 456: "Bob"}.

5/1/2026 403148 – Hashing 8

 4.3 HASH FUNCTION
• A function that converts a key into an index in the hash table.
• Goal: Distribute keys evenly to minimize collisions.

5/1/2026 403148 – Hashing 9

 4.3 HASH FUNCTION
• Simple example: For a key k and table size m, a simple hash function
is h(k) = k % m (modulo)
• Other examples:
• MD5 (Message Digest Algorithm 5)
• SHA-1 (Secure Hash Algorithm 1)
• SHA-256 (Secure Hash Algorithm 256)
• SHA-512 (Secure Hash Algorithm 512)
• CRC32 (Cyclic Redundancy Check 32)

5/1/2026 403148 – Hashing 10

 4.3 HASH FUNCTION
Key Characteristics of a Hash Function:

Deterministic: The same input always produces the same hash output.

Fixed Output Size: Regardless of input size, the output hash length is constant.

Fast Computation: It can quickly produce the hash for any given input.

Pre-Image Resistance: It is computationally difficult to reverse the hash to get the original input.

Collision Resistance: Different inputs should not produce the same hash value.

Avalanche Effect: A small change in input drastically changes the output hash.

5/1/2026 403148 – Hashing 11

 4.4 COLLISION RESOLUTION
• Collisions occur when two keys map to the same index (e.g., h(123)
= h(223) = 3).
• Solutions:
• Chaining: Store multiple keys in a linked list at the same index.
• Open Addressing: Find another empty slot in the table (e.g., linear probing).

linked list

5/1/2026 403148 – Hashing 12

 Group Discussion
• Question: design a hash table
• Discussion Points:
• Performance: How does the number of collisions affect lookup time?
• Design Choices: What table size or hash function would reduce collisions for this
dataset?
• Comparison: How would Quick Sort handle this dataset compared to a hash table?
• Applications: Where have you seen hashing used in real-world systems?

5/1/2026 403148 – Hashing 13

 EXAMPLE
class HashTable:
def __init__(self, size):
[Link] = size
[Link] = [[] for _ in range(size)] # Empty lists for chaining

def hash_function(self, key):

return key % [Link] # Simple modulo hash function

def insert(self, key, value):

index = self.hash_function(key)
[Link][index].append((key, value)) # Add key-value pair to list

def search(self, key):

index = self.hash_function(key)

for k, v in [Link][index]: # Check list at index

if k == key:
return v
return None # Key not found

5/1/2026 403148 – Hashing 14

 EXAMPLE
ht = HashTable(5) # Table size = 5

[Link](123, "Alice") # 123 % 5 = 3 → Store at index 3

[Link](128, "Bob") # 128 % 5 = 3 → Store at index 3 (collision)

[Link](456, "Charlie") # 456 % 5 = 1 → Store at index 1

print([Link](123)) # Output: Alice

print([Link](128)) # Output: Bob

print([Link](999)) # Output: None

5/1/2026 403148 – Hashing 15

 SUMMARY
Key points:

• Hashing maps keys to indices in a hash table for O(1) average-case

operations, faster than sorting-based searches (O(log n)).
• Used for quick lookups in databases, caches, and more.
• Core technology: hash function
• Collision problem

5/1/2026 403148 – Hashing 16

 ASSIGNMENT

Homework: Implement SHA-512 in

C++

Textbooks:
• [1]: Hash table (165)
Reading assignment • [2]: Better Living Through Better Hashing (57)
• [3]:Hash function (100)

5/1/2026 403148 – Hashing 17

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 5:TREES

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES

After study this chapter, the student should be able to:

• Understand the structure and applications of trees
• Explore binary trees and binary search trees (BSTs)
• Learn self-balancing trees and their importances
• Compare trees with sorting (Ch. 3) and hashing (Ch. 4

5/1/2026 403148 – Trees 2

 TREES

5.1. Basic Trees

5.2. Binary Trees
5.3. Binary Search Trees
5.4. Self-Balancing Trees

5/1/2026 403148 – Trees 3

 5.1BASIC TREES
• What is a Tree?
• Hierarchical data structure with nodes
connected by edges
• Key Features:
• Root node: The topmost node (no parent)
• Leaf node (Terminal node): Node with no
children
• Internal node: Node with at least one child
• Height of tree: Longest path from root to a
leaf
• Depth of node: Distance from the root to that
node.
• Degree of node: Number of children

5/1/2026 403148 – Trees 4

 5.1 BASIC TREES
• Properties
• A tree with n nodes has n – 1 edges
• There is exactly one path between any two nodes
• Types of Tree
• Binary Tree : Every node has at most two children
• Ternary Tree : Every node has at most three children
• N-ary Tree : Every node has at most n children.
• Applications
• File systems: in operating systems
• Tag structure in HTML
• Organizational charts
• Decision trees (machine learning)

5/1/2026 403148 – Trees 5

 5.1 BASIC TREES
• Comparison to Other Structures
• Unlike linear arrays (Ch. 3: Sorting), trees represent hierarchies
• Unlike hash tables (Ch. 4), trees support ordered traversals
• Basic Operations Of Tree Data Structure:
• Create
• Insert
• Search
• Traversal

5/1/2026 403148 – Trees 6

 5.2 BINARY TREES
• Definition
• A tree where each node has at most two children (left, right)
• Binary tree where: left child < parent < right child
• Types:
• Full: A binary tree where each node has either zero or two children. No node has only one child.
• Complete (all levels filled except possibly last)
• Perfect (all levels fully filled)
• Applications: Expression trees, binary heaps for priority queues

5/1/2026 403148 – Trees 7

 5.2 BINARY TREE
struct Node { void inorder(Node* root) {
int data; if (!root) return;
Node* left; inorder(root->left);
Node* right; cout << root->data << " ";
Node(int val) : data(val), left(nullptr), right(nullptr) {} inorder(root->right);
}; }

void insert(Node*& root, int val) {

int main() {
if (!root) { Node* root = nullptr;
insert(root, 5);
root = new Node(val); insert(root, 3);
insert(root, 7);
return; insert(root, 2);
insert(root, 4);
} insert(root, 6);
insert(root, 8);
if (val < root->data)

insert(root->left, val); cout << "Inorder traversal: ";

inorder(root);
else cout << endl;
return 0;
insert(root->right, val); }
}
5/1/2026 403148 – Trees 8
 5.3 BINARY SEARCH TREE (BTS)
• Definition
• Operations: Insert, Search, Delete (O(h) time, h = tree height)
• Performance: O(log n) average, O(n) worst (skewed tree)
• Comparison to Ch. 3 & 4
• Sorting (Ch. 3): BSTs support ordered traversal (like sorted arrays) but allow dynamic
updates
• Hashing (Ch. 4): BST is slower but supports range queries

5/1/2026 403148 – Trees 9

 5.3 BINARY SEARCH TREE
bool search(Node* root, int val) {
if (!root) return false; The time complexity of BST operations depends on the tree's
if (root->data == val) return true;
if (val < root->data)
shape:
return search(root->left, val);
else •Best/Average case (balanced BST):
return search(root->right, val);}
• Search: O(log n)
Node* deleteNode(Node * root, int key) {
if (!root) return nullptr; • Insert: O(log n)
if (key < root->data) • Delete: O(log n)
root->left = deleteNode(root->left, key);
else if (key > root->data) •Worst case (unbalanced BST, e.g., a linked list):
root->right = deleteNode(root->right, key); • Search: O(n)
else {// Node found
if (!root->left) { • Insert: O(n)
BSTNode* temp = root->right; • Delete: O(n)
delete root;
return temp;} Space complexity:
else if (!root->right) {
Node* temp = root->left; •O(n), where n is the number of nodes (for storing the
delete root;
return temp; tree).
} else {// Node with two children
Node * succ = root->right;
while (succ->left)
succ = succ->left;
root->data = succ->data;
root->right = deleteNode(root->right, succ->data);}}
return root;}
5/1/2026 403148 – Trees 10
 5.4 SELF-BALANCE TREES
• Why Balance?
• Unbalanced BSTs can degrade to O(n) (e.g., inserting [10, 20, 30, ])
• Self-balancing trees ensure O(log n) operations by maintaining height
• Examples
• AVL Trees: Balance factor 1, uses rotations
• Red-Black Trees: Color-based balancing, used in STL
• Comparison
• BST: O(n) worst case if skewed
• Self-Balancing: O(log n) guaranteed
• Hashing (Ch. 4): O(1) average but no order; self-balancing trees support range
queries

5/1/2026 403148 – Trees 11

 An AVL tree is a type of self-
balancing binary search tree
(BST).

It automatically keeps its height

(the longest path from root to leaf)
as small as possible after every
insertion and deletion.

5/1/2026 403148 – Trees 12

 5.4 SELF-BALANCE TREES
Key properties:
• For every node, the heights of its left and right subtrees differ by at
most 1.
• If the tree becomes unbalanced after an operation, it is rebalanced
using rotations (left, right, left-right, or right-left).
• Guarantees O(log n) time for search, insert, and delete operations.
• Prevents the tree from becoming skewed (like a linked list).

5/1/2026 403148 – Trees 13

 5.4 SELF-BALANCE TREES
How balancing works:
• After each insert or delete, the tree checks the balance factor (height
difference) of each node.
• If the balance factor is outside [-1, 1], rotations are performed to
restore balance.
In the code:
• insert adds nodes and rebalances the tree if needed.
• getBalance checks the balance factor.
• leftRotate and rightRotate perform tree rotations.
• inorder prints the tree in sorted order.

5/1/2026 403148 – Trees 14

 5.4 SELF-BALANCE TREES
AVLNode* insert(AVLNode* node, int key) {
if (!node) return new AVLNode(key);
if (key < node->data)
node->left = insert(node->left, key);
else if (key > node->data)
node->right = insert(node->right, key);
else
return node; // No duplicates

node->height = 1 + max(getHeight(node->left), getHeight(node->right));

int balance = getBalance(node);
// Left Left Case
if (balance > 1 && key < node->left->data)
return rightRotate(node); AVL (Adelson-Velskii and Landis) trees are
// Right Right Case efficient BSTs that stay balanced,
if (balance < -1 && key > node->right->data)
return leftRotate(node); ensuring fast operations.
// Left Right Case
if (balance > 1 && key > node->left->data) {
node->left = leftRotate(node->left); struct AVLNode {
return rightRotate(node); int data, height;
} AVLNode* left;
// Right Left Case AVLNode* right;
if (balance < -1 && key < node->right->data) { AVLNode(int val) : data(val), height(1), left(nullptr), right(nullptr) {}
node->right = rightRotate(node->right); };
return leftRotate(node);
}
return node;
}
5/1/2026 403148 – Trees 15
 5.4 SELF-BALANCE TREES
AVL tree

AVLNode* leftRotate(AVLNode* x) { AVLNode* rightRotate(AVLNode* y) {

AVLNode* y = x->right; AVLNode* x = y->left;
AVLNode* T2 = y->left; AVLNode* T2 = x->right;
y->left = x; x->right = y;
x->right = T2; y->left = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1; y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1; x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return y; return x;
} }

5/1/2026 403148 – Trees 16

 PROBLEM-SOLVING ACTIVITY
• Task: Build a BST
• Insert keys: [50, 30, 70, 20, 40, 60, 80]
• Perform: Search(40), Delete(30)
• Discuss: Is the tree balanced? How would an AVL tree improve it?
• Step
• Sketch the BST (root = 50, left = 30, right = 70, etc.)
• Trace search path for 40 (50 30 40)
• Delete 30 (replace with 40, adjust tree)
• Check balance: Height log n? (Yes, 3 for 7 nodes)
• Group Discussion
• Compare searching 40 in this BST vs. a hash table (Ch. 4) vs. a sorted array (Ch. 3).

5/1/2026 403148 – Trees 17

 SUMMARY
• Key points
• Basic Trees: Hierarchical, used in file systems
• Binary Trees: 2 children, used in heaps, expressions
• BSTs: Ordered, O(log n) average, support dynamic updates
• Self-Balancing Trees: Ensure O(log n) via AVL/Red-Black
• vs. Ch. 3 & 4: Trees balance speed (hashing) and order (sorting)
• Questions
• What are the trade-offs of using a BST vs. a hash table?
• How do self-balancing trees improve real-world applications?

5/1/2026 403148 – Trees 18

 ASSIGNMENT

Homework: Implement Decision Tree

(learning and prediction) in
C++/Python

Textbooks:
• [1]: Variants of Trees (91)
Reading assignment • [2]: Binary Trees: Infinity in the Palm of Your Hand (153)

5/1/2026 403148 – Trees 19

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 6:HEAPS

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES

After study this chapter, the student should be able to:

• Understand the structure and applications of heaps.
• Explore heap operations like insertion and deletion.
• Learn about heap sort and its performance.
• Compare heaps with other data structures.

5/1/2026 403148 – Heaps 2

 CHAPTER 6. HEAPS

6.1. Priority Queue

6.2. Heaps
6.3. Binary Heaps
6.4. Heapsort

5/1/2026 403148 – Heaps 3

 6.1 PRIORITY QUEUE
• Definition:
A priority queue is an abstract data type where each element has
a priority, and elements with higher priority are dequeued before those
with lower priority.
This differs from a standard queue (FIFO - First-In, First-Out)
where elements are processed in the order they arrive.
• Applications:
• CPU scheduling,
• Graph algorithm like Dijkstra’s algorithm
• Data compression in Huffman coding
• …

5/1/2026 403148 – Heaps 4

 6.1 PRIORITY QUEUE

5/1/2026 403148 – Heaps 5

 6.1 PRIORITY QUEUE

5/1/2026 403148 – Heaps 6

 6.1 PRIORITY QUEUE
Key Operations:
• Insert: Add an element with a given priority.
• Deletion: Remove the highest priority item.
• Peek: View the highest/lowest priority element without removing it.
• Extract-Max/Min: Remove and return the element with the
highest/lowest priority.
• Update Priority: Change the priority of an element.

5/1/2026 403148 – Heaps 7

 6.1 PRIORITY QUEUE
Example: implements a priority queue in C++ using std::priority_queue.
priority_queue<int> pq;
[Link](1);
[Link](5); Top element: 6
[Link](3);
[Link](2); Top element: 5
[Link](6); Top element: 3
cout << "Top element: " << [Link]() << endl; [Link](); Top element: 2
cout << "Top element: " << [Link]() << endl; [Link]();
cout << "Top element: " << [Link]() << endl; [Link](); Top element: 1
cout << "Top element: " << [Link]() << endl; [Link](); Priority queue is empty.
cout << "Top element: " << [Link]() << endl; [Link]();
if (![Link]()) {
} else {
cout << "Top element: " << [Link]() << endl; [Link](); •[Link](value); — Insert an element.
cout << "Priority queue is empty." << endl; •[Link](); — Peek at the highest priority element.
} •[Link](); — Remove the highest priority element.

5/1/2026 403148 – Heaps 8

 6.1 PRIORITY QUEUE
• What is the time complexity of peak(), insert(), delete() when
implementing Priority Queue using?
• Array
• Linked List
• Binary search tree
• Heap (will study in this chapter)

5/1/2026 403148 – Heaps 9

 6.2HEAPS
• What is a Heap?
A heap is a complete tree used to manage priority queues. In a heap, the parent
node is either larger (max heap) or smaller (min heap) than its children.

5/1/2026 403148 – Heaps 10

 6.2HEAPS
• Types:
• Max-Heap: Largest element at the root.
• Min-Heap: Smallest element at the root.
• Properties:
• No ordering between siblings is guaranteed; the heap property only applies between
parents and children.
• Height is O(log n), making it efficient for priority queue operations.

5/1/2026 403148 – Heaps 11

 6.2 HEAPS
• Operations
• Heapify: Convert an array into a heap by adjusting nodes from bottom up.
• Insertion: Add new key at end, then "heapify up" to maintain heap property.
• Deletion: Replace root with last node, then "heapify down" to maintain property.

• Applications
• Priority Queues: Heaps are commonly used to implement priority queues, where
the highest (or lowest) priority element is always at the root.
• Heap Sort Algorithm: Heaps are the foundation of the efficient sorting algorithm
known as Heap Sort.
• Graph Algorithms: They are used in algorithms like Dijkstra's and Prim's algorithms.

5/1/2026 403148 – Heaps 12

 6.2 HEAPS
Example: implements a priority queue in C++ using Standard Libraries
vector<int> heap = {4, 10, 3, 5, 1};
make_heap([Link](), [Link]());
cout << "Heap elements: ";
for (int v : heap) cout << v << " ";
cout << endl;
Heap elements: 10 5 3 4 1
// Insert a new element
heap.push_back(6); After new push: 10 5 6 4 1 3
push_heap([Link](), [Link]()); Max element: 10
cout << "After new push: ";
for (int v : heap) cout << v << " "; Heap after pop: 6 5 3 4 1
cout << endl;

// Remove the max element

pop_heap([Link](), [Link]());
cout << "Max element: " << [Link]() << endl;
heap.pop_back();
cout << "Heap after pop: ";
for (int v : heap) cout << v << " ";
cout << endl;

5/1/2026 403148 – Heaps 13

 6.3 BINARY HEAP
• Definition
A binary heap is a complete binary tree that maintains the heap property, typically
implemented as an array for efficiency.
• Array Representation:
• For a node at index ith
• Parent: (i-1)/2
• Left child: 2i + 1
• Right child: 2i + 2
• Key Operations:
• Heapify: Maintain heap property by adjusting nodes O(log n).
• Insert: Add element at the end and bubble up O(log n).
• Extract-Max/Min: Remove root, move last element to root, and heapify O(log n).
• Implementation:

5/1/2026 403148 – Heaps 14

 6.3 BINARY HEAP
• Heaptify
def __init__(self, iterable=None):
HEAPIFY(heap, n, i): [Link] = []
# heap is the array representing the heap if iterable:
[Link] = list(iterable)
# n is the heap size for i in range((len([Link]) // 2) - 1, -1, -1):
# i is the index to heapify self._heapify(i)

largest ← i
left ← 2*i + 1 def _heapify(self, index):
right ← 2*i + 2 n = len([Link])
largest = index
left = 2 * index + 1
if left < n and heap[left] > heap[largest]: right = 2 * index + 2
largest ← left
if left < n and [Link][left] > [Link][largest]:
largest = left
if right < n and heap[right] > heap[largest]: if right < n and [Link][right] > [Link][largest]:
largest ← right largest = right
if largest != index:
if largest ≠ i: [Link][index], [Link][largest] = [Link][largest], [Link][index]
swap heap[i] and heap[largest] self._heapify(largest)
HEAPIFY(heap, n, largest)

5/1/2026 403148 – Heaps 15

 6.3 BINARY HEAP
• Example in Python def extract_max(self):
if not [Link]:
return None
h = MaxHeap([4, 10, 3, 15, 1]) max_val = [Link][0]
print("Built:", h) [Link][0] = [Link][-1]
val = 6 [Link]()
[Link](val) if [Link]:
print(f"After insert {val}: {h}") self._heapify(0)
print("Peek max:", [Link]())
print("Extract:", h.extract_max()) return max_val
print("After extract:", h)
out = []
while len(h):
[Link](h.extract_max())
print("Heap Sort:", out)

Built: [15, 10, 3, 4, 1]

After insert 6: [15, 10, 6, 4, 1, 3]
Peek max: 15
Extract: 15
After extract: [10, 4, 6, 3, 1]
Heap Sort: [10, 6, 4, 3, 1]
5/1/2026 403148 – Heaps 16
 6.4 HEAP SORT
Definition:
Heap Sort is nothing more than repeated extract-max on a max-heap (or extract-
min on a min-heap). The heap is the underlying data structure that makes Heap
Sort efficient.
Algorithm:
• Build a max-heap from the input array O(n).
• Repeatedly extract the maximum element and place it at the end of the array,
reducing heap size O(n log n).
• Pseudo-code:
while heap not empty:
max = extract_max()
put max at end of array

5/1/2026 403148 – Heaps 17

 6.4 HEAP SORT
Comparison to Other Structures
Heaps vs. Sorting (Ch. 3):
• Sorting: Sorting algorithms produce a fully ordered list.
• Heaps: Heaps maintain a partial order, ensuring the root is the max or min
element. They can be used to implement sorting (Heap Sort), but they are not
themselves a fully sorted data structure.
Heaps vs. Hash Tables (Ch. 4):
• Hash Tables: Offer O(1) average-case time for search, insert, and delete
operations but do not support ordered traversals or finding the min/max element
efficiently.
• Heaps: Provide efficient access to the min/max element O(1) and guarantee
logarithmic time complexity for insertion and deletion O(log n) but do not offer the
constant-time lookup of hash tables.

5/1/2026 403148 – Heaps 18

 SUMMARY
Key points
• Heaps: A complete tree that maintains the heap property (parent is
greater/less than its children).
• Heap Operations: Insertion and deletion are efficient, with a time
complexity of O(log n).
• Heap Sort: An efficient sorting algorithm with a time complexity of
O(n log n).
• Comparing to Ch. 3 & 4: Heaps provide a balance between the quick
access of hash tables and the ordered nature of sorted arrays,
excelling at problems that require finding the minimum or maximum
element efficiently

5/1/2026 403148 – Heaps 19

 ASSIGNMENT

Homework:

Textbooks:
Reading assignment • [1]: Heaps (239)
• [4]: Heapsort (161)

5/1/2026 403148 – Heaps 20

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 7:EXPLORING GRAPHS

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES

After study this chapter, the student should be able to:

• Understand the concept of graphs.
• Learn graph representations and implementations.
• Explore graph applications

5/1/2026 403148 – Exploring Graphs 2

 CHAPTER 6. HEAPS

7.1. The Concept of Graphs

7.2. Applications
7.3. Representations
7.4. Implementation
7.5. Traversal
7.6. Minimum Spanning Tree

5/1/2026 403148 – Exploring Graphs 3

 7.1THE CONCEPT OF GRAPHS
Introduction to Graphs
• A graph is a fundamental data structure in computer science and
mathematics used to model relationships between entities. It consists of a
set of vertices (also called nodes) and a set of edges (also called arcs or
links) that connect pairs of vertices.
• Graph is the extension of tree data structure, tree can only represent
hierarchical data, while nodes or vertices are randomly connected with
each other.

5/1/2026 403148 – Exploring Graphs 4

 7.1THE CONCEPT OF GRAPHS
• Example: a social network, a computer network, a network of
locations used in GPS, etc.
• Formal Definition: A graph G = (V, E) or G = (V, E, A), where:
• V is the set of vertices, e.g., V = {A, B, C, D}
• E is the set of edges, e.g., E = {(A, B), (B, C)}
• A is adjacency matrix

A graph representing a structure of friends

5/1/2026 403148 – Exploring Graphs 5
 7.1THE CONCEPT OF GRAPHS
Traveling Salesman Problem with
release dates
- Cycle detection
- Minimum spanning tree

5/1/2026 403148 – Exploring Graphs 6

 7.1THE CONCEPT OF GRAPHS

City City

City City
City

Zoom in the
Red Circle City

Warehouse City
5/1/2026 403148 – Exploring Graphs 7
 7.1THE CONCEPT OF GRAPHS
Types of Graphs: Graphs can be
classified based on various properties
• Undirected vs. Directed Graphs:
• Undirected Graph: Edges have no
direction; the relationship is symmetric
(e.g., friendship in a social network).
Edge denoted as (u, v) , which implies
(v, u).
• Directed Graph (Digraph): Edges
have a direction; the relationship is
one-way (e.g., following on Twitter).
Edge denoted as <u, v >, from ( u ) to (
v ).

5/1/2026 403148 – Exploring Graphs 8

 7.1THE CONCEPT OF GRAPHS
Other Variants:
• Weighted vs Unweighted Graphs
• Simple Graph: No self-loops (edge from a vertex to itself) or multiple
edges between the same pair.
• Multigraph: Allows multiple edges between the same vertices.
• Acyclic Graph: No cycles (e.g., trees are acyclic connected graphs).
• Cyclic Graph: Contains at least one cycle.

5/1/2026 403148 – Exploring Graphs 9

 7.1THE CONCEPT OF GRAPHS
Key Terminology
• Degree of a Vertex: Number of edges incident to it. In directed graphs: In-degree
(incoming edges) and Out-degree (outgoing edges).
• Path: A sequence of vertices connected by edges (e.g., A → B → C).
• Cycle: A path that starts and ends at the same vertex with no repeated edges
(except the start/end).
• Subgraph: A graph formed from a subset of vertices and edges of the original
graph.
• Tree: An undirected, connected, acyclic graph. Every pair of vertices is
connected by exactly one simple path.
• Forest: A collection of trees (disconnected acyclic graph).

5/1/2026 403148 – Exploring Graphs 10

 7.2 APPLICATIONS
Graphs are versatile and used across domains to model complex
relationships. Here are some key applications:
• Social Networks:
• Vertices: Users;
• Edges: Friendships or follows.
• Applications: Recommendation systems (e.g., "friends of friends"), community
detection.
• Transportation and Navigation (Robotic):
• Vertices: Cities or intersections; Edges: Roads or flights with weights as distances.
• Applications: Shortest path finding (e.g., Dijkstra's algorithm in GPS apps like
Google Maps).
• Computer Networks:
• Vertices: Devices (routers, computers); Edges: Connections.
• Applications: Routing protocols, network topology analysis, detecting bottlenecks.
5/1/2026 403148 – Exploring Graphs 11
 7.2 APPLICATIONS
• Web and Search Engines:
• Vertices: Web pages;
• Edges: Hyperlinks (directed).
• Applications: PageRank algorithm (Google) to rank web pages based on link
structure.

• Biology and Medicine:

• Vertices: Genes/proteins; Edges: Interactions.
• Applications: Protein-protein interaction networks, drug discovery.

5/1/2026 403148 – Exploring Graphs 12

 7.2 APPLICATIONS
• Graph neural network (GNN)

GNNs for multi-model (EEG & fNIRS) to detect mental state

5/1/2026 403148 – Exploring Graphs 13

 7.2 APPLICATIONS
• Graph signal processing (GSP)
Example: Graph Fourier Transform (GFT) uses the eigenvectors of the
adjacency matrix, which then become the frequency components of the
transformation

GFT to estimate
direction-of-arrival

Graph space-time domain

5/1/2026 403148 – Exploring Graphs 14
 7.2 APPLICATIONS
• Recommendation Systems:
• Vertices: Users and items; Edges: Ratings or
purchases.
• Applications: Collaborative filtering in e-commerce
(e.g., Amazon recommendations).
• Other Areas:
• Scheduling: Task dependencies as directed graphs.
• Circuit Design: Components and wires.
• Robotics path planning and navigation: e.g., A*
algorithm).

5/1/2026 403148 – Exploring Graphs 15

 7.2 APPLICATIONS
A* pseudo-code
function A*(start, goal):
open = priority queue List of node to be visited
push(start, f=0)to open “f” is the evaluation cost function
came_from = empty map
g[start] = 0 Actual cost
while open not empty:
current = [Link]() Extract the node with the smallest “f”
if current == goal:
return reconstruct_path(came_from, current)
for (neighbor, cost) in neighbors(current):
tentative_g = g[current] + cost
if neighbor not in g or tentative_g < g[neighbor]:
came_from[neighbor] = current
g[neighbor] = tentative_g
f = tentative_g + h(neighbor, goal) “h”: heuristic estimate the cost
push(neighbor, f) to open
return "no path" function reconstruct_path(came_from, node):
path = [node]
while node in came_from:
node = came_from[node]
[Link](node)
return path

5/1/2026 403148 – Exploring Graphs 16

 7.3 REPRESENTATIONS
To work with graphs in algorithms and programs, we need efficient ways to store
them. The choice depends on graph density (sparse vs. dense).
Here are the two most common ways to represent a graph :
• Adjacency matrix
• Adjacency list

An undirected and unweighted graph An undirected and unweighted graph

5/1/2026 403148 – Exploring Graphs 17
 7.3 REPRESENTATIONS
1> Adjacency Matrix:
• A matrix of size |V|x|V|, where matrix[i][j] = 1 (or weight) if there's an edge
from vertex i to j, else 0.
• For undirected graphs, the matrix is symmetric.
• Pros: O(1) time to check if an edge exists; easy to implement.
• Cons: O(|V|^2) space, inefficient for sparse graphs (few edges).
• Example (for graph: Vertices 0-2; Edges: 0-1, 1-2, 2-3):

5/1/2026 403148 – Exploring Graphs 18

 7.3 REPRESENTATIONS
Example python code for Adjancency Matrix representation
num_vertices = 3 Undirected graph adjacency matrix:
adj_matrix = [[0] * num_vertices for _ in range(num_vertices)]
[0, 1, 1]
edges_undirected = [(0, 1), (1, 2), (2, 0)] [1, 0, 1]
for u, v in edges_undirected:
adj_matrix[u][v] = 1 [1, 1, 0]
adj_matrix[v][u] = 1
print("Undirected graph adjacency matrix:")
for row in adj_matrix:
print(row)

adj_matrix_directed = [[0] * num_vertices for _ in range(num_vertices)]

edges_directed = [(0, 1), (1, 2), (2, 0)]
for u, v in edges_directed: Directed graph adjacency matrix:
adj_matrix_directed[u][v] = 1
[0, 1, 0]
print("Directed graph adjacency matrix:") [0, 0, 1]
for row in adj_matrix_directed:
print(row) [1, 0, 0]

5/1/2026 403148 – Exploring Graphs 19

 7.3 REPRESENTATIONS
2> Adjacency List: Undirected graph
• An array or dictionary of lists, where each vertex points to a list of its neighbors.
• For weighted graphs, store pairs (neighbor, weight).
• Pros: O(|V| + |E|) space, efficient for sparse graphs; easy to iterate neighbors.
• Cons: O(degree) time to check edge existence.
• Example (same graph as above):

0: [1, 2] 1: [0, 2] 2: [0, 1]

5/1/2026 403148 – Exploring Graphs 20

 7.3 REPRESENTATIONS
Example python code for Adjancency List representation
num_vertices = 3
adj_list = [[] for _ in range(num_vertices)]
Adjacency List (undirected):
edges = [(0, 1), (1, 2), (2, 0)] 0: [1, 2]
for u, v in edges:
adj_list[u].append(v) 1: [0, 2]
adj_list[v].append(u) 2: [1, 0]
print("Adjacency List (undirected):")
for i in range(num_vertices):
print(f"{i}: {adj_list[i]}")

adj_list_directed = [[] for _ in range(num_vertices)]

for u, v in edges: Adjacency List (directed):
adj_list_directed[u].append(v)
0: [1]
print("Adjacency List (directed):") 1: [2]
for i in range(num_vertices):
print(f"{i}: {adj_list_directed[i]}") 2: [0]

5/1/2026 403148 – Exploring Graphs 21

 7.3 REPRESENTATIONS
2> Adjacency List: Directed graph

0: [] 1: [0, 2] 2: [0]

5/1/2026 403148 – Exploring Graphs 22

 7.3 REPRESENTATIONS
• Another example

5/1/2026 403148 – Exploring Graphs 23

 7.3 REPRESENTATIONS
Other Representations:
• Incidence Matrix: Rows for vertices, columns for edges; 1 if vertex
incident to edge.
• Edge List: Simple list of all edges, useful for certain algorithms like
Kruskal’s.
Comparison table
Representation Space Complexity Edge Check Time Neighbor Iteration
Adjacency Matrix O(|V|2) O(1) O(|V|)
Adjacency List O(|V|+|E|) O(|V|) O(degree of virtex)

5/1/2026 403148 – Exploring Graphs 24

 7.4 IMPLEMENTATION
• Implementing graphs in programming languages like Python involves
choosing a representation and providing methods for operations.

• Using Adjacency List in Python:

• Use a dictionary:
• keys as vertices
• values as lists of neighbors

5/1/2026 403148 – Exploring Graphs 25

 7.4 IMPLEMENTATION
Example: Graph represents by Adjacency List
class Graph: Create adjacency list
def __init__(self):
self.adj_list = {}
def add_vertex(self, vertex):
if vertex not in self.adj_list: Add a node to the adjacency list
self.adj_list[vertex] = []
def add_edge(self, u, v, directed=False):
self.add_vertex(u)
self.add_vertex(v)
self.adj_list[u].append(v)
if not directed: Add an edge to a node
self.adj_list[v].append(u)
def print_graph(self):
for vertex in self.adj_list:
print(f"{vertex}: {self.adj_list[vertex]}")
Usage
g = Graph()
g.add_edge('A', 'B')
g.add_edge('B', 'C')
g.print_graph() # A: ['B'], B: ['A', 'C'], C: ['B']

5/1/2026 403148 – Exploring Graphs 26

 7.4 IMPLEMENTATION
Example: Graph represents by Adjacency Matrix
• Use a 2D list. Map vertices to indices if non-numeric.
• Example (for numeric vertices 0 to n-1):
Create adjacency matrix
class GraphMatrix:
def __init__(self, num_vertices):
[Link] = [[0] * num_vertices for _ in range(num_vertices)]
def add_edge(self, u, v, weight=1):
[Link][u][v] = weight Add edge to adjacency matrix
[Link][v][u] = weight # For undirected

Considerations (homeworks):
• Handle directed variants by modifying add_edge.
• For large graphs, use libraries like NetworkX in Python for advanced
features.
5/1/2026 403148 – Exploring Graphs 27
 7.5 TRAVERSAL
• Graph traversal visits all vertices systematically, Difference types of Traversal
useful for searching, connectivity checks, etc.

• Graph traversal can be solved in various ways,

such as using Depth-First Search (DFS) or
Breadth-First Search (BFS).

5/1/2026 403148 – Exploring Graphs 28

 7.5 TRAVERSAL
Depth-First Search (DFS):
• Explores as far as possible along a branch before backtracking.
• Uses a stack (recursive or explicit).
• Applications: Cycle detection, topological sort, connected components.
• Algorithm (Recursive):
• Mark vertex as visited.
• Recur for all unvisited neighbors.

• Example Python (using adjacency list):

5/1/2026 403148 – Exploring Graphs 29

 7.5 TRAVERSAL
DFS: example Python (using adjacency list):
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
Create a set of visited nodes
[Link](start) Add a node to the set
print(start, end=' ')
for neighbor in graph[start]:
if neighbor not in visited:
Recursive call the function for
dfs(graph, neighbor, visited)
every new neighbor node
Traversal on example graph
graph = {
'A': ['B', 'C'],
'B': ['A', 'D', 'E'],
'C': ['A', 'F'], What are the results of the DFS for dfs(graph, ‘A’) and dfs(graph, 'B')?
'D': ['B'],
'E': ['B', 'F'],
'F': ['C', 'E']}
5/1/2026 403148 – Exploring Graphs 30
 7.5 TRAVERSAL

5/1/2026 403148 – Exploring Graphs 31

 7.5 TRAVERSAL
• DFS’s example:

Illustration of a DFS of a graph

5/1/2026 403148 – Exploring Graphs 32

 7.5 TRAVERSAL

Illustration of a DFS of a graph

5/1/2026 403148 – Exploring Graphs 33
 7.5 TRAVERSAL
BFS:
• Explores level by level from the start.
• Uses a queue
• Applications: Shortest path in unweighted graphs, level-order
traversal.
• Algorithm:
• Enqueue start, mark visited.
• While queue not empty: Dequeue, visit neighbors, enqueue unvisited.

5/1/2026 403148 – Exploring Graphs 34

 7.5 TRAVERSAL
BFS: example Python (using adjacency list):
def bfs(graph, start):
Create a set of visted nodes
visited = set()
queue = deque([start]) Initialized the queue

[Link](start) Add the first node to

the set
while queue:
node = [Link]() Process the first element in queue
print(node, end=' ')
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor) Add the node to the set
[Link](neighbor) Add the node to the queue

5/1/2026 403148 – Exploring Graphs 35

 7.5 TRAVERSAL
• Example

5/1/2026 403148 – Exploring Graphs 36

 7.5 TRAVERSAL
Illutration of BFS of a graph

5/1/2026 403148 – Exploring Graphs 37

 7.5 TRAVERSAL

Illustration of a BFS of a graph

5/1/2026 403148 – Exploring Graphs 38
 7.5 TRAVERSAL
Comparison:
• DFS: Good for deep searches; may use less memory in recursion.
• BFS: Guarantees shortest path; better for wide graphs.

Aspect DFS BFS

Data structure used Stack Queue

Explores all nodes at current depth (or level) before moving

Traversal approach Explores as far as possible along each branch before backtracking
deeper

Search order Explores down one branch before backtracking Explores nodes level-by-level

Completeness May not be complete for infinite-depth or cyclic graphs Complete (if graph is finite)

Typical applications Exploring entire search space, topology sorting, cycle detection Finding shortest path, web crawling

Time Complexity O(|V| + |E|) O(|V| + |E|)

Space Complexity O(d) where d is depth of search tree O(b^d) where b is branching factor

5/1/2026 403148 – Exploring Graphs 39

 7.6 MINIMUM SPANNING TREE
• Minimum Spanning Tree (MST) is a subset of edges that connects all
vertices with minimum total edge weight, without cycles.

Illustration of spanning trees within a graph

5/1/2026 403148 – Exploring Graphs 40
 7.6 MINIMUM SPANNING TREE
• Properties: |V|-1 edges; no cycles; minimum weight.
• Example of algorithms
• Kruskal's: Better for sparse graphs; focuses on sorting edges and avoiding cycles using Union-
Find.
• Prim's: Better for dense graphs; grows the tree incrementally using a priority queue, efficient
with adjacency lists or matrices.
• Kruskal's Algorithm:
• Sort all edges by weight.
• Add edges to MST if they don't form a cycle (use Union-Find for cycle detection).
• Stop when |V|-1 edges added.
• Time: O(|E| log |E|).

5/1/2026 403148 – Exploring Graphs 41

 7.6 MINIMUM SPANNING TREE
Kruskal’s algorithm

5/1/2026 403148 – Exploring Graphs 42

 7.6 MINIMUM SPANNING TREE
Kruskal’s algorithm

5/1/2026 403148 – Exploring Graphs 43

 7.6 MINIMUM SPANNING TREE
def kruskal(adj_list):
def find(parent, i): edges = []
if parent[i] != i: vertices = list(adj_list.keys())
parent[i] = find(parent, parent[i]) added = set()
return parent[i] for u in adj_list:
for v, w in adj_list[u]:
def union(parent, rank, x, y):
if (u, v) not in added and (v, u) not in added:
if rank[x] > rank[y]:
Attach smaller rank [Link]((u, v, w))
parent[y] = x
tree under root of [Link]((u, v))
elif rank[x] < rank[y]:
high rank tree parent = {v: v for v in vertices}
parent[x] = y (Union by Rank) rank = {v: 0 for v in vertices}
else:
[Link](key=lambda e: e[2]) # Sort by weight
parent[y] = x
mst = []
rank[x] += 1
for u, v, w in edges:
x, y = find(parent, u), find(parent, v)
if x != y:
[Link]((u, v, w))
Kruskal’s algorithm union(parent, rank, x, y)
return mst
5/1/2026 403148 – Exploring Graphs 44
 7.6 MINIMUM SPANNING TREE
Prim’s algorithm:
• Start from an arbitrary vertex, grow the MST by repeatedly adding the
minimum-weight edge that connects a vertex in the MST to a vertex
outside it.
• Use a priority queue (e.g., min-heap) to select the minimum-weight
edge efficiently.
• Time: O(|E| log |V|) with a binary heap.

5/1/2026 403148 – Exploring Graphs 45

 7.6 MINIMUM SPANNING TREE
Prim’s algorithm:
1. Initialize an empty MST, a priority queue, and a set of visited vertices.
2. Start with a chosen vertex, mark it visited, and add its edges to the
priority queue.
3. While the queue is not empty:
1. Extract the minimum-weight edge (u, v, w).
2. If v is not visited, include the edge in the MST, mark v visited, and add
v's edges to the queue.
4. Stop when all vertices are included (|V|-1 edges).

5/1/2026 403148 – Exploring Graphs 46

 7.6 MINIMUM SPANNING TREE
def prim(graph, start):
visited = set([start]) Create a set of visited nodes
mst = []
pq = [] Create a priority queue
total_weight = 0
for neighbor, weight in graph[start]:
heappush(pq, (weight, start, neighbor)) Push all the edges to the queue
while pq and len(visited) < len(graph):
weight, u, v = heappop(pq) Extract the minimum-weight edage
if v in visited:
continue
[Link](v) Add new new node to the visited set
[Link]((u, v, weight))
total_weight += weight
for neighbor, w in graph[v]:
if neighbor not in visited:
heappush(pq, (w, v, neighbor)) Push the edges of new node to the queue
return mst, total_weight

5/1/2026 403148 – Exploring Graphs 47

 7.6 MINIMUM SPANNING TREE
Prim’s algorithm

5/1/2026 403148 – Exploring Graphs 48

 7.6 MINIMUM SPANNING TREE
Prim’s algorithm

5/1/2026 403148 – Exploring Graphs 49

 SUMMARY
• Graph = Vertices + Edges (directed/undirected, weighted/unweighted)
• Key terms: degree, path, cycle, subgraph, tree
• Applications: social networks, GPS routing, search engines, biology,
AI (GNN, GFT)
• Representations: adjacency matrix, adjacency list
• Traversal: DFS (deep search), BFS (level search)
• MST: Kruskal’s, Prim’s → connect all nodes with min cost

5/1/2026 403148 – Exploring Graphs 50

 ASSIGNMENT
• Visualization Tools: Use Graphviz or online graph editors.

Textbooks:
• [1]: Exploring Graphs (243)
Reading assignment • [4]: Graph Algorithms (547)

5/1/2026 403148 – Exploring Graphs 51

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
DATA STRUCTURES AND ALGORITHMS
Minh Hà Ngọc, Ths
Email minhhangoc269@[Link]
Tel/Zalo 0962108438
Office M306
Hours Monday: 9h – 11h
Thursday: 13h – 17h
Youtube
15/8/2023 403148 – Introduction and Requirement 1
 COURSE INFORMATION

No of credits: 2(2,0)
Theory
Practice Self-study
Time allocation: (hours) 30 0 60
(hours): (hours):
:
Prerequisite: No Prerequisite code: No
Programming Prior-Completion
Prior-Completion: 502008
Fundamentals code:
Co-requisite: No Co-requisite code: No
Programme: Have 4 programs Programme code:
15/8/2023 403148 – Introduction and Requirement 2
 COURSE OBJECTIVES

No Contents CO
Understand the fundamental concepts of data structures and
1 CO1
their applications

2 Analyze and compare the efficiency of different algorithms CO2

3 Understand data structures and algorithms of graph CO3

15/8/2023 403148 – Introduction and Requirement 3

 COURSE LEARNING OUTCOMES

CLO Contents PLO

Understand the fundamental concepts of data structures
1 PLO1
and their applications
Analyze and compare the efficiency of different
2 PLO2
algorithms
Apply theoretical knowledge to solve problems using
3 PLO3
appropriate data structures and algorithms

15/8/2023 403148 – Introduction and Requirement 4

 COURSE CONTENTS

Chapter 1: Introduction to Algorithms (3)

Chapter 2: Elementary Data Structures (6)
Chapter 3: Sorting (3)
Chapter 4: Hashing (3)
Chapter 5: Trees (6)
Chapter 6: Heap (3)
Chapter 7: Exploring Graphs (6)
15/8/2023 403148 – Introduction and Requirement 5
 EVALUATION
N Weig CL CLO CLO
Category Types of question
o ht (%) O1 2 3
Process Exercise
1 Process Evaluation 1 20 (In-class test, X X
E-Learning Quiz)
2 Mid-term Test 30 Essay X

- Multiple Choice
3 Final Examination 50 X X X
- Constructed response test

Bonus points for students who actively participate in class activities

15/8/2023 403148 – Introduction and Requirement 6
 REQUIREMENT
▪ Go to Library to download and master: Course syllabus and Lecture’s
slides
▪ Do assignment
▪ Submit homework to the e-learning on time
▪ Each of below equal to 1 time class absent:
▪ Go to class late for more than 15 minute
▪ Cannot answer the given homework
▪ Don’t submit the e-learning assignment on time
▪ Absent 3 time or more – final exam prohibition

15/8/2023 403148 – Introduction and Requirement 7

 TEXTBOOK AND REFERENCES

❖Textbook

[1]. Marcin J., [2024], C# Data Structures and Algorithms Harness the
power of C# to build a diverse range of efficient applications, 2nd Ed,
Packt, Birmingham, UK.

[2]. Geoge T. Heineman [2021], Learning Algorithms – A Programmer’s

Guide to Writing Better Code, O’Reilley, CA.

15/8/2023 403148 – Introduction and Requirement 8

 TEXTBOOK AND REFERENCES

❖Supplementary Readings

[3]. Aditya Y. Bhargava [2023], Grokking Algorithms, 2nd Ed, Manning

Publication, NY

[4]. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest,

Clifford Stein, [2009], Introduction to Algorithms, 3rd Edition, MIT
Press, Boston.

15/8/2023 403148 – Introduction and Requirement 9

 TEXTBOOK AND REFERENCES

❖Additional readings
[5]. Narasimha K. [2017], Data Structures and Algorithms Made Easy,
5th Ed, CareerMonk, Bombay, India.

[6]. Robert S., Kevin W., [2014], Algorithms, 4th Edition, Addison-
Wesley Professional, New Jersey.

15/8/2023 403148 – Introduction and Requirement 10

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 1: Introduction to Algorithms

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES
After study this chapter, the student should be able to:
• Define and identify algorithms
• Understand different notations for representing algorithms
• Classify algorithms by type and application
• Analyze computational complexity
• Develop algorithmic thinking
• Understand Algorithm Development Cycle

09 - 12 - 2024 403148 – Introduction to Algorithms 2

 CHAPTER 1: INTRODUCTION

1.1. What is an Algorithm?

1.2. Algorithm Representation

1.3. Types of Algorithms

1.4. Computational Complexity

1.5. Algorithm Development Cycle

09 - 12 - 2024 403148 – Introduction to Algorithms 3

 1.1. WHAT IS AN ALGORITHM?
DEFINITION

❖A well-defined sequence of steps for solving a problem

❖It takes an input, performs a set of well-defined operations, and
produces an output
❖Must be finite (terminate after a finite number of steps)

09 - 12 - 2024 403148 – Introduction to Algorithms 4

 1.1. WHAT IS AN ALGORITHM?
DEFINITION

09 - 12 - 2024 403148 – Introduction to Algorithms 5

 1.1. WHAT IS AN ALGORITHM?
DEFINITION

Algorithm: FindMaximum

Input: A list of numbers A[1],

A[2], ..., A[n]
Output: The maximum value in A

1. Set max = A[1]

2. For i = 2 to n:
If A[i] > max, then set max
= A[i]
3. Return max
09 - 12 - 2024 403148 – Introduction to Algorithms 6
 1.1. WHAT IS AN ALGORITHM?
KEY CHARACTERISTICS

❖Finiteness: Must terminate after a finite number of steps

❖Definiteness: Each step must be precisely defined or unambiguously
specified
❖Generality: an algorithm must be generic enough to solve all problems
of a particular class
Input: May have zero or more inputs
❖Output: Must produce at least one output
❖Effectiveness: Each step must be simple enough to be carried out
exactly
09 - 12 - 2024 403148 – Introduction to Algorithms 7
 1.1. WHAT IS AN ALGORITHM?
WHAT IS THE NEED FOR ALGORITHMS?

❖Every daily activity need algorithms to perform.

❖Any task that involves a sequence of steps, decision points, or
optimization can be expressed as an algorithm
❖Essential for solving complex computational problems efficiently and
effectively.
• Solving problems: Algorithms break down problems into smaller,
manageable steps.
• Optimizing solutions: Algorithms find the best or near-optimal
solutions to problems.
• Automating tasks: Algorithms can automate repetitive or complex
tasks, saving time and effort.
09 - 12 - 2024 403148 – Introduction to Algorithms 8
 1.1. WHAT IS AN ALGORITHM?
WHAT IS THE NEED FOR ALGORITHMS?

Prompt(s):
- Examples of Algorithms in Everyday Activities

- Examples of Algorithms for [Warehouse Automation Optimization]

- Examples to Illustrate the Importance of Algorithms in [Problem

Solving]

- Example to Illustrate the Importance of Algorithms in Optimizing

Solutions, especially related to [automation system]

09 - 12 - 2024 403148 – Introduction to Algorithms 9

 1.2 ALGORITHM REPRESENTATION
PSEUDOCODE

• An important part of designing an algorithm

• Informal, high-level description of an algorithm
• Uses structural conventions of programming languages
• Omits details unnecessary for understanding
• Helps the programmer in planning the solution to the problem
• Help the reader in understanding the approach to the problem

What is PseudoCode: A Complete Tutorial | GeeksforGeeks

09 - 12 - 2024 403148 – Introduction to Algorithms 10
 1.2 ALGORITHM REPRESENTATION
PSEUDOCODE

function BinarySearch(A, target):

INSERTION-SORT.A; left = 0
for i = 2 to n right = length(A) - 1
key = A[i] while left <= right:
//Insert A[i]into mid = (left + right) / 2
//the sorted subarray //A[1 : i-1] if A[mid] == target:
j = i - 1 return mid
while j > 0 and A[j] > key else if A[mid] < target:
A[j + 1] = A[j] left = mid + 1
j = j – 1 else:
A[j - 1] = key right = mid - 1
return -1

09 - 12 - 2024 403148 – Introduction to Algorithms 11

 1.2 ALGORITHM REPRESENTATION
PSEUDOCODE – BEST PRACTICES

• Use clear and concise statements: Each line should represent a

single action or decision in the algorithm.

• Maintain structure: Use indentation and capitalization to denote

structure and control flow, similar to how you would in Python.

• Avoid language-specific syntax: Stick to general programming

concepts and avoid Python-specific syntax to keep the pseudocode
language-agnostic.

09 - 12 - 2024 403148 – Introduction to Algorithms 12

 1.2 ALGORITHM REPRESENTATION
PSEUDOCODE – BEST PRACTICES

• Utilize uppercase for control structures: For constructs

like IF, ELSE, WHILE, and FOR, use uppercase letters to distinguish
them from other text.

• Include comments if necessary: While pseudocode is inherently

descriptive, adding comments can provide additional clarity when
needed.

09 - 12 - 2024 403148 – Introduction to Algorithms 13

 1.2 ALGORITHM REPRESENTATION
FLOWCHARTS

• Visual representation of algorithm steps

• Uses symbols for different operations

• Arrows show flow of control

• Oval: Start/End

• Rectangle: Assign/Process

• Diamond: Decision

• Parallelogram: Input /Output

09 - 12 - 2024 403148 – Introduction to Algorithms 14
 1.2 ALGORITHM REPRESENTATION
FLOWCHARTS

09 - 12 - 2024 403148 – Introduction to Algorithms 15

 1.2 ALGORITHM REPRESENTATION
FLOWCHARTS

[Link]
Flowgorithm - Flowchart Programming Language
09 - 12 - 2024 403148 – Introduction to Algorithms 16
 1.2 ALGORITHM REPRESENTATION
FLOWCHARTS

09 - 12 - 2024 403148 – Introduction to Algorithms 17

 1.2 ALGORITHM REPRESENTATION
FLOWCHARTS

09 - 12 - 2024 403148 – Introduction to Algorithms 18

 1.3 TYPES OF ALGORITHMS
Algorithms

Design Paradigm Implementation Application

• Recursive • Sorting
• Divide and Conquer • Iterative • Searching
• Greedy • Serial/Parallel • Graph
• Dynamic Programming • Deterministic/Non- • String
• Back Tracking deterministic • Geometric
• Exact/Approximate • Numerical
09 - 12 - 2024 403148 – Introduction to Algorithms 19
 1.3 TYPES OF ALGORITHMS
BY DESIGN PARADIGM
• Divide and Conquer
• Break problem into smaller subproblems
• Solve subproblems recursively
• Combine solutions (e.g., Merge Sort, Quick Sort)
• Greedy Algorithms
• Make locally optimal choice at each step
• Hope for globally optimal solution
• Examples: Dijkstra's algorithm, Huffman coding
09 - 12 - 2024 403148 – Introduction to Algorithms 20
 1.3 TYPES OF ALGORITHMS
BY DESIGN PARADIGM
• Dynamic Programming
• Break down into overlapping subproblems
• Store solutions to avoid recomputation
• Examples: Fibonacci sequence, knapsack problem
• Backtracking
• Build solution incrementally
• Abandon solution as soon as it's invalid
• Examples: N-Queens, Sudoku solver
09 - 12 - 2024 403148 – Introduction to Algorithms 21
 1.3 TYPES OF ALGORITHMS
BY APPLICATION
• Sorting
• Bubble Sort, Insertion Sort, Merge Sort, Quick Sort
• Arrange elements in a specific order
• Searching
• Linear Search, Binary Search
• Find an element in a collection

09 - 12 - 2024 403148 – Introduction to Algorithms 22

 1.3 TYPES OF ALGORITHMS
BY APPLICATION
• Graph
• BFS, DFS, Dijkstra's algorithm
• Process relationships between entities
• String
• Pattern matching, parsing
• Process text and patterns

09 - 12 - 2024 403148 – Introduction to Algorithms 23

 1.4 COMPUTATIONAL COMPLEXITY
WHAT IS COMPUTATIONAL COMPLEXITY?

• Same problem can frequently be solved with algorithms that differ in efficiency
• The differences between algorithms
• Insignificant with small number of data items
• Grow with the amount of data
• Computational complexity:
• Developed by Juris Hartmanis and Richard E. Stearns
• A theoretical framework to analyze the efficiency of algorithms
• Measures resources required by an algorithm as a function of input size
09 - 12 - 2024 403148 – Introduction to Algorithms 24
 1.4 COMPUTATIONAL COMPLEXITY
WHY STUDY COMPUTATIONAL COMPLEXITY?

• Predicts algorithm performance on large inputs

• Allows comparing algorithms independently of hardware
• Identifies bottlenecks and inefficiencies
• Essential for designing scalable systems and applications
• Establishes theoretical limits of computation

09 - 12 - 2024 403148 – Introduction to Algorithms 25

 1.4 COMPUTATIONAL COMPLEXITY
THE RAM MODEL OF COMPUTATION

• RAM: Random Access Machine

• Each simple operation (+, *, -, =, if, call) takes exactly one time step
• Loop:
Tloop = kN
• k – loop’s interations
• N – total single operation in each loop
• Each memory access takes exactly one time step, independent on memory size
and type
• The run time is measured by counting the number of steps an algorithm takes
on a given problem instance
09 - 12 - 2024 403148 – Introduction to Algorithms 26
 1.4 COMPUTATIONAL COMPLEXITY
TIME COMPLEXITY BASICS

• Counts the number of elementary operations

• Independent of hardware, programming language, or
implementation details
• Focuses on growth rate rather than exact operation count
• Usually considers worst-case scenarios (but also best-case and
average-case)
09 - 12 - 2024 403148 – Introduction to Algorithms 27
 1.4 COMPUTATIONAL COMPLEXITY
BEST, AVERAGE, AND WORST CASE

• Best case: minimum number of steps taken in any instance of size n

• Average case: Expected time on random input

• Worst case: maximum number of steps taken in any instance of size n

• Example: Quick Sort

• Best/Average: O(n log n)

• Worst: O(n²)

09 - 12 - 2024 403148 – Introduction to Algorithms 28

 1.4 COMPUTATIONAL COMPLEXITY
BIG O NOTATION
• Mathematical notation describing the upper bound of growth rate
• f(n) = O(g(n)) means c·g(n) is an upper bound on f(n). Thus, there exists some
constant c such that f(n) ≤ c·g(n) for every large enough n (that is, for all n ≥ n0,
for some constant n0)
• f(n) = Ω(g(n)) means c·g(n) is a lower bound on f(n). Thus, there exists some
constant c such that f(n) ≥ c·g(n) for all n ≥ n0
• f(n) = Θ(g(n)) means c1.g(n) is an upper bound on f(n) and c2·g(n) is a lower
bound on f(n), for all n ≥ n0. Thus, there exist constants c1 and c2 such that f(n)
≤ c1·g(n) and f(n) ≥ c2·g(n) for all n ≥ n0. This means that g(n) provides a nice,
tight bound on f(n).
09 - 12 - 2024 403148 – Introduction to Algorithms 29
 1.4 COMPUTATIONAL COMPLEXITY
BIG O NOTATION

f(n) = O(g(n)) f(n) = Ω(g(n)) f(n) = Θ(g(n))

09 - 12 - 2024 403148 – Introduction to Algorithms 30

 1.4 COMPUTATIONAL COMPLEXITY
BIG O NOTATION

• Mathematical notation describing the upper bound of growth rate

• O(f(n)): Algorithm doesn't grow faster than f(n)
• Simplification rules:
• Drop lower-order terms: O(n² + n) = O(n²); O(n² + n log n) = O(n²)

• Drop constants: O(2n) = O(n)

• Examples: O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ), O(n!)
09 - 12 - 2024 403148 – Introduction to Algorithms 31
 1.4 COMPUTATIONAL COMPLEXITY
COMMON TIME COMPLEXITIES

• Constant Time O(1): Array access, basic arithmetic

• Logarithmic Time O(log n): Binary search, balanced tree operations

• Linear Time O(n): Linear search, array traversal

• Linearithmic Time O(n log n): Efficient sorting (merge sort, heap sort)

• Quadratic Time O(n²): Bubble sort, insertion sort, nested loops

• Exponential Time O(2ⁿ): Brute force solutions to NP-complete

problems
09 - 12 - 2024 403148 – Introduction to Algorithms 32
 1.4 COMPUTATIONAL COMPLEXITY
COMPARISON OF COMMON COMPLEXITIES

Complexity Name Example Algorithm

O(1) Constant Array access
O(log n) Logarithmic Binary search
O(n) Linear Linear search
O(n log n) Linearithmic Merge sort
O(n²) Quadratic Bubble sort
O(2ⁿ) Exponential Tower of Hanoi

09 - 12 - 2024 403148 – Introduction to Algorithms 33

 1.4 COMPUTATIONAL COMPLEXITY
COMPARISON OF COMMON COMPLEXITIES

09 - 12 - 2024 403148 – Introduction to Algorithms 34

 1.4 COMPUTATIONAL COMPLEXITY
SPACE COMPLEXITY

• Measures the amount of memory an algorithm uses

• Also expressed in Big O notation

• Trade-offs between time and space

• Includes:
• Input storage
• Auxiliary storage for variables
• Call stack for recursive algorithms
09 - 12 - 2024 403148 – Introduction to Algorithms 35
 1.5. ALGORITHM DEVELOPMENT
CYCLE
1. Problem Definition and Analysis

7. Deployment and Integration

2. Algorithm Design
6. Documentation and Maintenance

3. Implementation
5. Analysis and Optimization

4. Verification and Testing

09 - 12 - 2024 403148 – Introduction to Algorithms 41
 1.5. ALGORITHM DEVELOPMENT CYCLE
1. PROBLEM DEFINITION AND ANALYSIS
Clarify the problem statement: Understand precisely what needs to be solved

Identify inputs and outputs: Define what information is available and what
results are required

Set constraints and requirements: Determine time/space complexity limits,

accuracy needs, etc.

Break down into subproblems: Decompose complex problems into managea-

ble components

Research existing solutions: Investigate if similar problems have been solved

before
09 - 12 - 2024 403148 – Introduction to Algorithms 42
 1.5. ALGORITHM DEVELOPMENT CYCLE
2. ALGORITHM DESIGN
Choose an approach: Select appropriate algorithm design paradigm (greedy,
divide & conquer, dynamic programming, etc.)
Develop abstract solution: Create high-level solution strategy

Sketch pseudocode: Draft the logical structure without implementation details

Design data structures: Determine optimal data structures to represent and
manipulate the information
Define procedures and functions: Outline key routines and their interfaces

Handle edge cases: Consider boundary conditions and exceptional scenarios

09 - 12 - 2024 403148 – Introduction to Algorithms 43
 1.5. ALGORITHM DEVELOPMENT CYCLE
3. IMPLEMENTATION
Choose programming language: Select appropriate language based on
requirements
Code the algorithm: Translate pseudocode into actual code
Document the code: Add comments and documentation for clarity
Implement error handling: Add appropriate error detection and recovery
mechanisms
Optimize critical sections: Refine performance-critical parts of the
implementation
Follow coding standards: Ensure code adheres to relevant style guidelines
09 - 12 - 2024 403148 – Introduction to Algorithms 44
 1.5. ALGORITHM DEVELOPMENT CYCLE
4. VERIFICATION AND TESTING
Develop test cases: Create tests including normal cases, edge cases, and
boundary conditions

Unit testing: Test individual components in isolation

Integration testing: Test components working together

Performance testing: Measure execution time and resource usage

Validate correctness: Verify algorithm produces correct outputs for all inputs

Compare with requirements: Ensure the solution meets all specified

requirements
09 - 12 - 2024 403148 – Introduction to Algorithms 45
 1.5. ALGORITHM DEVELOPMENT CYCLE
5. ANALYSIS AND OPTIMIZATION
Analyze time complexity: Determine how execution time scales with input
size

Analyze space complexity: Evaluate memory requirements

Identify bottlenecks: Find performance limitations

Optimize algorithm: Improve efficiency without compromising correctness

Consider tradeoffs: Balance time, space, and implementation complexity

Benchmark against alternatives: Compare with other possible solutions

09 - 12 - 2024 403148 – Introduction to Algorithms 46
 1.5. ALGORITHM DEVELOPMENT CYCLE
6. DOCUMENTATION AND MAINTENANCE
Create technical documentation: Write detailed algorithm description and
implementation notes
Develop user documentation: Prepare usage instructions and examples
Version control: Maintain history of changes and versions
Refine based on feedback: Incorporate improvements based on user
experiences
Monitor performance: Track algorithm in real-world usage
Plan for future enhancements: Identify potential improvements for future
versions
09 - 12 - 2024 403148 – Introduction to Algorithms 47
 1.5. ALGORITHM DEVELOPMENT CYCLE
7. DEPLOYMENT AND INTEGRATION
Package the algorithm: Prepare for distribution or integration

Deploy to target environment: Install in production systems

Integrate with existing systems: Connect with other components or systems

Monitor real-world performance: Track behavior in actual usage conditions

Address emerging issues: Fix problems that appear in deployment

Gather usage metrics: Collect data to inform future improvements

09 - 12 - 2024 403148 – Introduction to Algorithms 48
 SUMMARY
❖In this chapter, we have learnt:
✓Define and identify algorithms

✓Understand different notations for representing algorithms

✓Classify algorithms by type and application

✓Analyze computational complexity

✓Develop algorithmic thinking

✓Understand algorithm development cycle

09 - 12 - 2024 403148 – Introduction to Algorithms 49

 ASSIGNMENT
❖Homework
▪ All related exercises
❖Reading assignment
▪ Slides of chapter 2
▪ Textbooks:
[1]: 31-101; 105 – 111; 112-125; 156-188; 231-266; 283-308
[2]:119-141; 161-180; 180-188; 124-210;
[3]: 91-100; 256-262;
[4]: 14-23; 87-108
[5]: 11-13; 14-46; 23-87
[6]: 95-103; 110-147

09 - 12 - 2024 403148 – Introduction to Algorithms 50

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 2
Elementary Data Structures

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES
After study this chapter, the student should be able to:
• Understand the concepts of Array, Linked Lists, Stack and Queue
data structures.
• Learn the operations performed on Array, Linked Lists, Stack and
Queue.
• Analyze the time and space complexity of elementary data
structures.
• Implement examples using in C#.
• Apply Array, Linked Lists, Stack and Queue to solve real-world
problems.

17 - 06 - 2025 403148 – Elementary Data Structures 2

 CONTENTS

2.1. Array

2.2. Linking List

2.3. Stack

2.4. Queue

17 - 06 - 2025 403148 – Elementary Data Structures 3

 2.1 ARRAY
Definition and Characteristics
❖Definition:
• A collection of the same type elements
• Stored in contiguous memory locations
1D Array 2D Array

17 - 06 - 2025 403148 – Elementary Data Structures 4

 2.1 ARRAY
• Key Characteristics:

• Fixed size: Once created, the size cannot be changed without creating a
new array.

• Elements are accessed using indices, starting from 0.

• Stored in consecutive memory locations, enabling fast access.

17 - 06 - 2025 403148 – Elementary Data Structures 5

 2.1 ARRAY
Operations on Arrays
• Access: Retrieve an element at a specific index. Time complexity: O(1).
• Search: Find if an element exists in the array. Time complexity: O(n).
• Insertion: Add an element at a specific position. Time complexity: O(n) due to
shifting.
• Deletion: Remove an element from a specific position. Time complexity: O(n)
due to shifting.
• Example in C#:
int[] myArray = new int[10]; // Declare an array of size 10
myArray[0] = 5; // Insert 5 at index 0
[Link](myArray[0]); // Access element at index 0

17 - 06 - 2025 403148 – Elementary Data Structures 6

 2.1 ARRAY
• Advantages:
• Fast access to elements by index (O(1)).
• Efficient use of memory.
• Easy to implement.
• Disadvantages:
• Fixed size: Cannot resize dynamically without creating a new
array.
• Inserting or deleting elements in the middle requires shifting
elements (O(n)).
• Wasted memory if the array is not fully utilized.
17 - 06 - 2025 403148 – Elementary Data Structures 7
 2.1 ARRAY
Use Cases
• Storing a fixed number of elements of the same type.
• Implementing other data structures like stacks, queues, or matrices.
Problem Solving Exercise
• Exercise: Write a function to find the second-largest element in an array.
• Solution in C#:

17 - 06 - 2025 403148 – Elementary Data Structures 8

 2.1 ARRAY
static int FindSecondLargest(int[] arr)
{
if ([Link] < 2) return -1; // Edge case: array too small
int largest = [Link], secondLargest = [Link];
foreach (int num in arr){
if (num > largest){
secondLargest = largest;
largest = num;
}else if (num > secondLargest && num != largest){
secondLargest = num;}
}
return secondLargest == [Link] ? -1 : secondLargest;
}

17 - 06 - 2025 403148 – Elementary Data Structures 9

 2.1 ARRAY
Group Discussion
• Question:
• Discussion Points:
• Arrays are simple, efficient structures for fixed-size data but lack flexibility
for dynamic operations.
• They are foundational for understanding more complex data structures.

17 - 06 - 2025 403148 – Elementary Data Structures 10

 2.2 LINKED LISTS
Definition and Types
• Definition: A linked list is a linear data structure where each element (node)
contains data and a reference to the next node.
• Types:
• Singly Linked List: Each node points to the next node.
• Doubly Linked List: Each node points to both the next and previous nodes.
• Circular Linked List: The last node points back to the first node.
Singly Linked List

17 - 06 - 2025 403148 – Elementary Data Structures 11

 2.2 LINKED LISTS
Singly Linked List

Doubly Linked List

Circular Linked List

17 - 06 - 2025 403148 – Elementary Data Structures 12

 2.2 LINKED LISTED
Characteristics

• Dynamic size: Can grow or shrink as needed.

• Elements are not stored in contiguous memory.

• Access to elements is sequential (traversal required).

17 - 06 - 2025 403148 – Elementary Data Structures 13

 2.2 LINKED LISTS
• Operations on Linked Lists
• Insertion:
• At beginning: O(1)
• At end: O(n)
• In middle: O(n)
• Deletion:
• At beginning: O(1)
• At end: O(n)
• In middle: O(n)
• Traversal: Visit each element once. O(n)
• Search: Find if an element exists. O(n)
• Example in C#:

17 - 06 - 2025 403148 – Elementary Data Structures 14

 2.2 LINKED LISTS
public class LinkedList{ public class Node{
public Node head; public int data;
public void InsertAtEnd(int data){ public Node next;
Node newNode = new Node(data); public Node(int data){
if (head == null){ [Link] = data;
head = newNode; [Link] = null;
return; }
} }
Node current = head;
while ([Link] != null){
current = [Link];
}
[Link] = newNode;
}
}

17 - 06 - 2025 403148 – Elementary Data Structures 15

 2.2 LINKED LISTS
• Advantages:
• Efficient insertion and deletion (O(1) at the beginning for singly linked lists).
• No need to specify size in advance.
• Memory is utilized efficiently.
• Disadvantages:
• Accessing an element by index is O(n) due to traversal.
• More memory required per element due to references.
• Use Cases
• Implementing stacks and queues.
• Dynamic memory allocation.
• Applications requiring frequent insertions and deletions.

17 - 06 - 2025 403148 – Elementary Data Structures 16

 2.2 LINKED LIST
Problem Solving Exercise
• Exercise: Write a function to detect a cycle in a linked list.
• Solution:
public bool HasCycle(Node head){
if (head == null || [Link] == null) return false;
Node slow = head, fast = head;
while (fast != null && [Link] != null){
slow = [Link];
fast = [Link];
if (slow == fast) return true;
}
return false;
}

17 - 06 - 2025 403148 – Elementary Data Structures 17

 2.2 LINKED LISTS
Group Discussion
• Question:
What are the trade-offs between arrays and linked lists for dynamic data
management?
• Discussion Points:
• Arrays offer O(1) access but O(n) insertion/deletion.
• Linked lists provide O(1) insertion/deletion at the beginning but O(n) access.
• Linked lists offer flexibility for dynamic data but require more memory and slower
access times.
• They are essential for understanding advanced data structures like trees and graphs.

17 - 06 - 2025 403148 – Elementary Data Structures 18

 2.3 STACK
Definition and Characteristics
Definition: A stack is a linear data structure that follows the Last In, First Out
(LIFO) principle.
Key Characteristics:
• The last element added is the first to be removed.
• Operations occur at one end, called the top.
• Can be implemented using arrays or linked lists.

Example of Stack

17 - 06 - 2025 403148 – Elementary Data Structures 19

 2.3 STACK
Operations on Stacks
• Push: Adds an element to the top. Time complexity: O(1).
• Pop: Removes the top element. Time complexity: O(1).
• Peek: Returns the top element without removing it. Time complexity:
O(1).
• IsEmpty: Checks if the stack is empty. Time complexity: O(1).
• Example in C#:

17 - 06 - 2025 403148 – Elementary Data Structures 20

 2.3 STACK
public class Stack{ public int Pop(){
private int[] array; if (top < 0){
private int top; [Link](" Underflow");
private int capacity; return -1;}
return array[top--];
public Stack(int size){
}
array = new int[size];
capacity = size; public int Peek(){
top = -1; if (top < 0){
} [Link]("Underflow");
return -1;}
public void Push(int item){
return array[top];
if (top >= capacity - 1){
}
[Link]("Overflow”);
return;} public bool IsEmpty(){
array[++top] = item;} return top < 0;} }//end class

17 - 06 - 2025 403148 – Elementary Data Structures 21

 2.3 STACK
• Advantages:
• Efficient operations at the top (O(1) for push and pop).
• Ideal for managing function calls and recursion.
• Simple to implement.
• Disadvantages:
• Limited access to only the top element.
• Not suitable for operations requiring access to middle elements.
• Use Cases
• Managing function calls in recursion.
• Evaluating postfix expressions.
• Undo/redo operations in text editors.
• Backtracking algorithms.

17 - 06 - 2025 403148 – Elementary Data Structures 22

 2.3 STACK
• Example in C#: Write a function to reverse a string using a stack.
public static string ReverseString(string input)
{
Stack<char> stack = new Stack<char>();
foreach (char c in input)
{
[Link](c);
}
string reversed = "";
while ([Link] > 0)
{
reversed += [Link]();
}
return reversed;
}
17 - 06 - 2025 403148 – Elementary Data Structures 23
 2.3 STACK
Discussion
• Question: When is a stack more suitable than an array or linked list?
• Discussion Points:
• Stacks excel in LIFO scenarios, like recursion or undo operations.
• Arrays offer random access, while linked lists support flexible insertions.
• Stacks are simple, efficient structures for LIFO data management.
• They are foundational for understanding recursion and algorithmic design.

17 - 06 - 2025 403148 – Elementary Data Structures 24

 2.4 QUEUE
Definition and Characteristics
• Definition: A queue is a linear data structure that follows the First In, First Out
(FIFO) principle.

Example of Queue

17 - 06 - 2025 403148 – Elementary Data Structures 25

 2.4 QUEUE
• Key Characteristics:
• The first element added is the first to be removed.
• Operations occur at two ends: front (deletion) and rear (insertion).
• Can be implemented using arrays or linked lists.

17 - 06 - 2025 403148 – Elementary Data Structures 26

 2.4 QUEUE
• Operations on Queues
• Enqueue: Adds an element to the rear. Time complexity: O(1).
• Dequeue: Removes the front element. Time complexity: O(1).
• Peek: Returns the front element without removing it. Time complexity: O(1).
• IsEmpty: Checks if the queue is empty. Time complexity: O(1).
• IsFull: Checks if the queue is full (for fixed-size queues). Time complexity: O(1).
• Example in C#:

17 - 06 - 2025 403148 – Elementary Data Structures 27

 2.4 QUEUE
public class Queue{ public int Dequeue(){
private int[] array; if (front == -1 || front > rear){
private int front, rear, capacity; [Link]("Underflow");return -1;}
int item = array[front++];
public Queue(int size){ if (front > rear){front = -1;rear = -1;}
array = new int[size]; return item;}
capacity = size;
front = -1; public int Peek(){
rear = -1;} if (front == -1){
[Link]("Underflow");
public void Enqueue(int item){ return -1;}
if (rear == capacity - 1){ return array[front];}
[Link]("Overflow");
return;} public bool IsEmpty(){return front == -1;}
if (front == -1) front = 0; public bool IsFull(){
array[++rear] = item; return rear == capacity - 1;}}// end class
}
17 - 06 - 2025 403148 – Elementary Data Structures 28
 2.4 QUEUE
• Advantages:
• Efficient operations at both ends (O(1) for enqueue and dequeue).
• Supports fair task scheduling (first come, first served).
• Useful for sequential processing.
• Disadvantages:
• Inefficient for accessing or modifying middle elements (O(n)).
• Fixed-size queues may lead to overflow issues.

17 - 06 - 2025 403148 – Elementary Data Structures 29

 2.4 QUEUE
Use Cases

❖Managing printer jobs.

❖Handling customer requests in call centers.

❖Breadth-First Search (BFS) in graphs.

❖Simulating real-world queues (e.g., ticket lines).

17 - 06 - 2025 403148 – Elementary Data Structures 30

 2.4 QUEUE
Problem Solving Exercise
❖Write a program to simulate a printer queue with FIFO order.
public class PrinterQueue
{
private Queue<string> queue = new Queue<string>();

public void AddJob(string job){

[Link](job);
}

public string PrintNextJob(){

if ([Link] == 0)
{
return "No jobs in the queue.";
}
return [Link]();
}
}
17 - 06 - 2025 403148 – Elementary Data Structures 31
 2.4 QUEUE

17 - 06 - 2025 403148 – Elementary Data Structures 32

 2.4 QUEUE
Group Discussion

❖Question: When is a queue more suitable than a stack or array?

❖Discussion Points:
• Queues are ideal for FIFO scenarios, like task scheduling or BFS.
• Stacks suit LIFO scenarios, while arrays support random access.
• Queues are essential for FIFO data management.
• They are widely used in operating systems and graph algorithms.

17 - 06 - 2025 403148 – Elementary Data Structures 33

 SUMMARY
❖In this chapter, we have learnt:
✓Structures of Array, Linked Lists, Stack and Queue

✓Use cases

✓Key operations

✓Exercise with codes

✓Applications

17 - 06 - 2025 403148 – Elementary Data Structures 34

 ASSIGNMENT

Using stack to implement Backtracking algorithms

Homework
(N-queen, Tower of Hanoi)

Textbooks:
Reading • [1]: Dictionaries and Sets (182-207)
assignment • [2]: Dijkstra’s Algorithm (225 -237)

17 - 06 - 2025 403148 – Elementary Data Structures 35

 TON DUC THANG UNIVERSITY
FACULTY OF ELECTRICAL & ELECTRONICS ENGINEERING

403148
CHAPTER 3:SORTING

Minh Hà Ngọc, Ths

 CHAPTER OBJECTIVES

After study this chapter, the student should be able to:

• Understand the concept of sorting algorithms
• Learn different types of sorting methods
• Analyze the efficiency of various sorting techniques
• Implement examples using in C++.

28 - 06 - 2025 403148 – Sorting 2

 INTRODUCTIONS
• Sorting is a fundamental operation in computer science that involves
arranging a collection of elements in a specific order, typically
ascending or descending.
• It is crucial in applications such as organizing data in databases,
optimizing search algorithms, and improving the efficiency of
computational tasks.
• In this lecture, we will explore six key sorting algorithms: Selection
Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, and Radix
Sort. Each algorithm has its own strengths, weaknesses, and use
cases.

28 - 06 - 2025 403148 – Sorting 3

 CHAPTER 3:SORTING
3.1. Selection sort

3.2. Buble sort

3.3. Insertion sort

3.4. Quick sort

3.5. Merge sort

3.6. Radix sort

28 - 06 - 2025 403148 – Sorting 4

 3.1 SELECTION SORT
• Description:
Selection sort is a simple, in-place comparison-based sorting algorithm
that repeatedly finds the minimum element from the unsorted portion
of the array and swaps it with the first unsorted element.
Example: -11, 12, -42, 0, 1, 90, 68, 6,
and -9
Output: -42, -9, 0, 1, 6, 11, 12, 68, 90

28 - 06 - 2025 403148 – Sorting 5

 3.1 SELECTION SORT
How It Works
• Start with the entire array as unsorted.
• Find the smallest element in the unsorted portion.
• Swap it with the first element of the unsorted portion.
• Move the boundary of the unsorted portion one element to the right.
• Repeat until the entire array is sorted.

28 - 06 - 2025 403148 – Sorting 6

 3.1 SELECTION SORT
Pseudo-code for selectionSort
Input: Array A, size of array n

for i from 0 to n - 2 do
minIndex ← i
for j from i + 1 to n - 1 do
if A[j] < A[minIndex] then
minIndex ← j
end for
if minIndex ≠ i then
swap A[i] and A[minIndex]
end if
end for
Output: Array A is sorted in ascending order

28 - 06 - 2025 403148 – Sorting 7

 3.1 SELECTION SORTING
Time Complexity
• Worst Case: O(𝑛2 )
• Best Case: O(𝑛2 )
• Average Case: O(𝑛2 )
Space Complexity
• O(1)
When to Use
• Suitable for small datasets or when minimizing memory writes is critical (e.g., in
embedded systems).
• Not efficient for large datasets due to its quadratic time complexity.

28 - 06 - 2025 403148 – Sorting 8

 3.1 SLECTION SORT
Advantages
• Simple to implement.
• In-place, requiring no additional memory.
• Performs fewer swaps compared to other O(𝑛2 ) algorithms.
Disadvantages
• Inefficient for large datasets.
• Not adaptive; always performs O(𝑛2 ) operations, even for nearly sorted arrays.
• Not stable (may change the relative order of equal elements).

28 - 06 - 2025 403148 – Sorting 9

 3.1 SLECTION SORT
[Link]
mode=Selection&run=true

Visualize selection sort by imagining a deck of cards where you

repeatedly pick the smallest card and place it at the front. Online tools
like Visualgo can show step-by-step animations.

28 - 06 - 2025 403148 – Sorting 10

 3.2 BUBBLE SORT
Description
Bubble sort is a simple comparison-based sorting algorithm that
repeatedly steps through the list, compares adjacent elements, and
swaps them if they are in the wrong order, causing larger elements to
"bubble up" to the end.
How It Works
• Start from the beginning of the array.
• Compare the first two elements. If the first is greater than the second, swap them.
• Move to the next pair of elements and repeat until the end of the array.
• After each pass, the largest unsorted element is placed at the end.
• Repeat until no more swaps are needed.

28 - 06 - 2025 403148 – Sorting 11

 3.2 BUBBLE SORT
Pseudo code for Bubble Sort
Input: Array A, size of array n
for i from 0 to n - 1 do
for j from 0 to n - i - 2 do
if A[j] > A[j + 1] then
swap A[j] and A[j + 1]
end if
end for
end for
Output: Array A is sorted in ascending order

28 - 06 - 2025 403148 – Sorting 12

 3.2 BUBBLE SORT
Time Complexity
• Worst Case: O(𝑛2 )
• Best Case: O(n) (if already sorted, with an optimization to check for swaps)
• Average Case: O(𝑛2 )
Space Complexity
• O(1)
When to Use
• Rarely used in practice due to its inefficiency.
• Useful for educational purposes or when simplicity is prioritized over performance.

28 - 06 - 2025 403148 – Sorting 13

 3.2 BUBBLE SORT
Example
Consider the array [5, 3, 8, 4, 2]:
• First pass: Compare and swap: [3, 5, 4, 2, 8].
• Second pass: Compare and swap: [3, 4, 2, 5, 8].
• Third pass: Compare and swap: [3, 2, 4, 5, 8].
• Fourth pass: Compare and swap: [2, 3, 4, 5, 8].
• Result: [2, 3, 4, 5, 8].

28 - 06 - 2025 403148 – Sorting 14

 3.2 BUBBLE SORT
Advantages
• Simple to implement.
• Can detect if the array is already sorted early with an optimization.
Disadvantages
• Very slow for large datasets.
• Not efficient even for moderately sized arrays.

28 - 06 - 2025 403148 – Sorting 15

 3.3 INSERTION SORT
Description
Insertion sort is a simple sorting algorithm that builds the final sorted
array one item at a time by inserting each new element into its correct
position in the already sorted portion.
How It Works
• Start with the second element (assume the first is sorted).
• Compare it with the first element and swap if necessary.
• Move to the third element, inserting it into the correct position among the sorted
elements.
• Repeat for each subsequent element, maintaining a sorted subarray at the
beginning.

28 - 06 - 2025 403148 – Sorting 16

 3.3 INSERTION SORT
Pseudo code for Insertion Sort
Input: Array A, size of array n
for i from 1 to n - 1 do
key = A[i]
j=i–1
while j >= 0 and A[j] > key do
A[j + 1] = A[j]
j=j-1
end while
A[j + 1] = key
end for
Output: Array A is sorted in ascending order
28 - 06 - 2025 403148 – Sorting 17
 3.3 INSERTION SORT
Example
Consider the array [5, 3, 8, 4, 2]:
• Step 1: Start with [5]. Insert 3: [3, 5].
• Step 2: Insert 8: [3, 5, 8].
• Step 3: Insert 4: [3, 4, 5, 8].
• Step 4: Insert 2: [2, 3, 4, 5, 8].
• Result: [2, 3, 4, 5, 8].

28 - 06 - 2025 403148 – Sorting 18

 3.3 INSERTION SORT
Time Complexity
• Worst Case: O(𝑛2 )
• Best Case: O(n) (if already sorted)
• Average Case: O(𝑛2 )
Space Complexity
• O(1)
When to Use
• Efficient for small datasets or nearly sorted data (e.g., online sorting where data
arrives incrementally).
• Useful in scenarios requiring stable sorting.

28 - 06 - 2025 403148 – Sorting 19

 3.3 INSERTION SORT
Advantages
• Simple to implement.
• Adaptive: Performs well on nearly sorted arrays.
• Stable: Preserves the relative order of equal elements.
Disadvantages
• Inefficient for large datasets.

28 - 06 - 2025 403148 – Sorting 20

 3.4 QUICK SORT
Description
Quick sort is a divide-and-conquer algorithm that selects a "pivot"
element and partitions the array into two sub-arrays based on whether
elements are less than or greater than the pivot, then recursively sorts
the sub-arrays.
How It Works
• Choose a pivot element (e.g., the last element, first element, or a random element).
• Partition the array:
• Elements less than the pivot go to the left.
• Elements greater than the pivot go to the right.
• Recursively apply quick sort to the left and right sub-arrays.

28 - 06 - 2025 403148 – Sorting 21

 3.4 QUICK SORT
Pseudo code for Quick Sort
Input: Array A, left=0, right= size of array -1
quicksort(arr, left, right)
if left < right then
set pivot = arr[right]
set i = left - 1
for j = left to right - 1
if arr[j] <= pivot then
increment i
swap arr[i] with arr[j]
end if
end for
swap arr[i + 1] with arr[right]
set pivotIndex = i + 1
quicksort(arr, left, pivotIndex - 1)
quicksort(arr, pivotIndex + 1, right)
end if
end quicksort
Output: Array A is sorted in ascending order
28 - 06 - 2025 403148 – Sorting 22
 3.4 QUICK SORT
Example
Consider the array [5, 3, 8, 4, 2]:
• Choose pivot = 2.
• Partition: [3, 4, 5, 8] (left) and [2] (pivot).
• Sort left: Choose pivot = 8, partition into [3, 4, 5] and [8].
• Sort [3, 4, 5]: Choose pivot = 5, partition into [3, 4] and [5].
• Continue until sorted: [2, 3, 4, 5, 8].

28 - 06 - 2025 403148 – Sorting 23

 3.4 QUICK SORT
Time Complexity
• Worst Case: O(𝑛2 ) (e.g., when the pivot is always the smallest or largest)
• Best Case: O(n log n)
• Average Case: O(n log n)
Space Complexity
• (O(log n)) (due to recursion stack)
When to Use
• Generally efficient for large datasets.
• Works well with random pivot selection or when data fits in memory.

28 - 06 - 2025 403148 – Sorting 24

 3.4 QUICK SORT
Advantages
• Fast in practice due to cache-friendly memory access.
• In-place sorting (minimal extra space).
Disadvantages
• Worst-case performance can be poor if the pivot is poorly chosen.
• Not stable.

28 - 06 - 2025 403148 – Sorting 25

 3.5 MERGE SORT
Description
Merge sort is a divide-and-conquer algorithm that divides the array into
two halves, recursively sorts them, and then merges the sorted halves
into a single sorted array.
How It Works
• Divide the array into two equal halves.
• Recursively sort each half.
• Merge the two sorted halves into a single sorted array.

28 - 06 - 2025 403148 – Sorting 26

 3.5 MERGE SORT
Peseudo-code for merge sort
Input: Array A, left=0, right= size of array -1
mergesort(arr, left, right)
if left < right then
set mid = (left + right) / 2
mergesort(arr, left, mid)
mergesort(arr, mid + 1, right)
merge(arr, left, mid, right)
end if
end mergesort

Output: Array A be sorted in ascending order

28 - 06 - 2025 403148 – Sorting 27

 3.5 MERGE SORT
Example
Consider the array [5, 3, 8, 4, 2]:
• Divide into [5, 3, 8] and [4, 2].
• Sort [5, 3, 8]:
• Divide into [5, 3] and [8].
• Sort [5, 3] to [3, 5].
• Merge to [3, 5, 8].
• Sort [4, 2]:
• Divide into [4] and [2].
• Merge to [2, 4].
• Merge [3, 5, 8] and [2, 4] to [2, 3, 4, 5, 8].

28 - 06 - 2025 403148 – Sorting 28

 3.5 MERGE SORT
Time Complexity
• Worst Case: O(n log n)
• Best Case: O(n log n)
• Average Case: O(n log n)
Space Complexity
• O(n) (due to temporary arrays for merging)
When to Use
• Efficient for large datasets.
• Preferred when stable sorting is required.
• Suitable for linked lists or external sorting (e.g., disk-based data).

28 - 06 - 2025 403148 – Sorting 29

 3.5 MERGE SORT
Advantages
• Consistent O(n log n) performance.
• Stable sorting.
Disadvantages
• Requires additional space for merging.
• Not in-place (needs extra memory proportional to the size of the data).

28 - 06 - 2025 403148 – Sorting 30

 3.6 RADIX SORT
Description
Radix sort is a non-comparative sorting algorithm that sorts data with
integer keys by grouping keys by individual digits that share the same
significant position and value, using counting sort as a subroutine.
How It Works
• Sort the array based on the least significant digit (LSD) first, using counting sort.
• Repeat for each subsequent digit (tens, hundreds, etc.) until all digits are processed.
• Maintains stability to ensure correct ordering.

28 - 06 - 2025 403148 – Sorting 31

 3.6 RADIX SORT
Peseudo-code for radix sort
Input: Array A, =size of array
radixsort(arr)
set max = maximum element in arr
set digits = number of digits in max
for exp = 1 to digits
set count[0..9] = 0
for i = 0 to length(arr) - 1
increment count[(arr[i] / exp) % 10]
end for
for i = 1 to 9
set count[i] = count[i] + count[i - 1]
end for
create output array of size length(arr)
for i = length(arr) - 1 down to 0
set digit = (arr[i] / exp) % 10
set output[count[digit] - 1] = arr[i]
decrement count[digit]
end for
for i = 0 to length(arr) - 1
set arr[i] = output[i]
end for
end for
end radixsort
Output: Array A is sorted in ascending order
28 - 06 - 2025 403148 – Sorting 32
 3.6 RADIX SORT
Example
Consider the array [170, 45, 75, 90, 802, 24, 2, 66]:
• Units digit: Sort by units: [170, 90, 802, 2, 24, 45, 75, 66].
• Tens digit: Sort by tens: [2, 24, 45, 66, 75, 90, 170, 802].
• Hundreds digit: Sort by hundreds: [2, 24, 45, 66, 75, 90, 170, 802].
• Result: [2, 24, 45, 66, 75, 90, 170, 802].

28 - 06 - 2025 403148 – Sorting 33

 3.6 RADIX SORT
Time Complexity
• (O(d(n + b))), where (d) is the number of digits, (n) is the number of elements, and
(b) is the base of the number system (e.g., 10 for decimal).
Space Complexity
• O(n + b))
When to Use
• Efficient for sorting integers or strings with fixed-size keys.
• Works well when the number of digits is small compared to the number of elements.

28 - 06 - 2025 403148 – Sorting 34

 3.6 RADIX SORT
Advantages
• Can be faster than comparison-based sorts for large datasets with small digit counts.
• Stable sorting.
Disadvantages
• Only works for integers or strings.
• Requires additional space for buckets.
• Less flexible than comparison-based sorts.

28 - 06 - 2025 403148 – Sorting 35

 Group Discussion
• Question:
• Discussion Points:
• Implement one algorithm in a programming language (e.g., Python, C#).
• Compare performance on different datasets (e.g., random, nearly sorted, reversed).
• Discuss trade-offs (e.g., speed vs. stability).

28 - 06 - 2025 403148 – Sorting 36

 SUMMARY

Time Complexity Time Complexity

Algorithm Space Complexity Stable In-Place
(Worst) (Best)

Selection Sort O(𝑛2 ) O(𝑛2 ) O(1) No Yes

Bubble Sort O(𝑛2 ) O(n) O(1) Yes Yes

Insertion Sort O(𝑛2 ) O(n) O(1) Yes Yes

Quick Sort O(𝑛2 ) O(n log n) O(log n) No Yes

Merge Sort O(n log n) O(n log n) O(n) Yes No

Radix Sort O(d (n + b)) O(d (n + b)) O(n + b) Yes No

28 - 06 - 2025 403148 – Sorting 37

 SUMMARY
Key points:
• O(𝑛2 ) algorithms (Selection, Bubble, Insertion) are simple but slow.
• O(n log n) algorithms (Quick, Merge) are faster for large datasets.
• Radix Sort excels for specific data types.

28 - 06 - 2025 403148 – Sorting 38

 ASSIGNMENT

Homework: Merge sort with 3-parts

Textbooks:
Reading assignment • [1]:Arrays and Sorting (51)
• [2]: Sorting Without a Hat (123)

28 - 06 - 2025 403148 – Sorting 39