University of Zimbabwe

Faculty of Computer Engineering Informatics and Communication

Department of Computer Science

DATA STRUCTURES & ALGORITHMS

COMPLETE STUDY NOTES
HCS111 / HAI111 / HCC111 / HDS107

Course Leader: Mr. N. Zanamwe

2026 Academic Year

These notes cover EVERY topic in the course outline with clear explanations, examples,
pseudocode, Python code, and complexity tables. Study each section thoroughly and you
will pass.

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 1

TOPIC 1: Algorithm Analysis & Asymptotic Notation
KEY EXAM POINT: You must be able to determine the Big-O of any algorithm by inspecting
loops and recursive calls.

1.1 Why Algorithm Analysis?

When we write a program, we need to know how efficient it is. We measure efficiency in two
ways:
• Time Complexity — How many steps does the algorithm take?
• Space Complexity — How much memory does the algorithm use?
We do NOT measure actual clock time (which depends on hardware). Instead we count
operations.

1.2 Asymptotic Notation — The Big Picture

Asymptotic notation describes how an algorithm behaves as input size n grows very large.

Notation Name Meaning Example

O(f(n)) Big-O (Upper Bound) Worst-case — Bubble sort is O(n2)
algorithm takes AT
MOST this long
Omega(f(n)) Big-Omega (Lower Best-case — Bubble sort is Omega(n) on
Bound) algorithm takes AT sorted data
LEAST this long
Theta(f(n)) Big-Theta (Tight Exact bound — Merge sort is Theta(n log n)
Bound) algorithm is exactly
this

1.3 Common Complexities (Fastest to Slowest)

Complexity Name Example / When it appears
O(1) Constant Array access by index: arr[5]
O(log n) Logarithmic Binary search, BST operations
O(n) Linear Linear search, single loop
O(n log n) Linearithmic Merge sort, heap sort, quick sort average
O(n^2) Quadratic Bubble/insertion/selection sort, nested loops
O(n^3) Cubic Triple nested loops
O(2^n) Exponential Naive Fibonacci, subset enumeration
O(n!) Factorial Permutations, travelling salesman brute force

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 2

1.4 Rules for Calculating Big-O
• Drop constants: O(3n) = O(n)
• Drop lower-order terms: O(n^2 + n) = O(n^2)
• Single loop over n = O(n)
• Nested loop over n = O(n^2) per level of nesting
• Halving the input each step (e.g., binary search) = O(log n)
• Recursive functions: use the Master Theorem or recursion tree

Example: Analysing a simple function

def example(arr):
total = 0 # O(1)
for i in arr: # O(n)
total += i # O(1) inside loop
return total # O(1)
# Overall: O(n) — the loop dominates

Example: Nested loops

def nested(n):
for i in range(n): # O(n)
for j in range(n): # O(n)
print(i, j) # O(1)
# Overall: O(n^2)

TOPIC 2: Abstract Lists & Implementations

2.1 Arrays vs Linked Lists
Arrays have O(1) random access but O(n) insert/delete. Linked lists have O(n) access but
O(1) insert/delete at a known position.

Feature Array

Access by index O(1) — direct

Search (unsorted) O(n)

Insert at beginning O(n) — must shift

Insert at end O(1) amortised

Delete O(n) — must shift

Memory Contiguous block

Size Fixed (static array)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 3

 Feature Linked List

Access by index O(n) — must traverse

Search O(n)

Insert at beginning O(1)

Insert at end O(n) without tail pointer

Delete (given node) O(1)

Memory Non-contiguous, pointers needed

Size Dynamic

2.2 Linked List — Node Structure

class Node:
def __init__(self, data):
[Link] = data # stores the value
[Link] = None # pointer to next node

class LinkedList:
def __init__(self):
[Link] = None # start of the list

def insert_front(self, data):

new_node = Node(data)
new_node.next = [Link]
[Link] = new_node # O(1)

def search(self, data):

current = [Link]
while current: # O(n)
if [Link] == data:
return True
current = [Link]
return False

2.3 Stacks — LIFO (Last In, First Out)

A stack works like a pile of plates — you always add and remove from the TOP.
• push(item) — add to top → O(1)
• pop() — remove from top → O(1)
• peek() / top() — view top without removing → O(1)
• is_empty() → O(1)
Uses: function call stack, undo/redo, bracket matching, expression evaluation.
class Stack:
def __init__(self):
[Link] = []

def push(self, item):

[Link](item) # O(1)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 4

 def pop(self):
if not self.is_empty():
return [Link]() # O(1)

def peek(self):
return [Link][-1] # O(1)

def is_empty(self):
return len([Link]) == 0

2.4 Queues — FIFO (First In, First Out)

A queue works like a supermarket checkout — first person in line is served first.
• enqueue(item) — add to REAR → O(1)
• dequeue() — remove from FRONT → O(1)
• front() — view front element → O(1)
Uses: printer queue, CPU scheduling, BFS graph traversal.
from collections import deque

class Queue:
def __init__(self):
[Link] = deque()

def enqueue(self, item):

[Link](item) # add to rear O(1)

def dequeue(self):
return [Link]() # remove from front O(1)

def front(self):
return [Link][0]

2.5 Deques — Double-Ended Queue

A deque allows insertion and deletion at BOTH ends.
• add_front(item) → O(1)
• add_rear(item) → O(1)
• remove_front() → O(1)
• remove_rear() → O(1)
Uses: undo operations, sliding window problems, palindrome checking.

Operation/Algorithm Best Case Average Case Worst Case

Stack push/pop O(1) O(1) O(1)
Queue enqueue/dequeue O(1) O(1) O(1)
Deque operations O(1) O(1) O(1)
Linked List insert (head) O(1) O(1) O(1)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 5

 Operation/Algorithm Best Case Average Case Worst Case
Linked List search O(1) O(n) O(n)
Array access O(1) O(1) O(1)
Array insert (middle) O(n) O(n) O(n)

TOPIC 3: Trees & Sorted Lists

3.1 Trees — Key Terminology
Trees are non-linear data structures. They are fundamental to databases, file systems,
compilers, and network routing.
• Root — top node with no parent
• Leaf — node with no children
• Height — longest path from root to a leaf
• Depth — distance from root to a node
• Degree — number of children a node has
• Edge — connection between parent and child
• Subtree — a node and all its descendants

3.2 Binary Trees

A binary tree is a tree where every node has AT MOST 2 children (left and right).
class TreeNode:
def __init__(self, val):
[Link] = val
[Link] = None
[Link] = None

Tree Traversals — MUST KNOW ALL FOUR

Traversal Order & Description

In-order (LNR) Left → Node → Right. For BST: gives sorted output.

Pre-order (NLR) Node → Left → Right. Used to copy a tree.

Post-order (LRN) Left → Right → Node. Used to delete a tree.

Level-order (BFS) Level by level using a queue. Breadth-first.

def inorder(root):
if root:

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 6

 inorder([Link])
print([Link]) # visit node BETWEEN subtrees
inorder([Link])

def preorder(root):
if root:
print([Link]) # visit node BEFORE subtrees
preorder([Link])
preorder([Link])

def postorder(root):
if root:
postorder([Link])
postorder([Link])
print([Link]) # visit node AFTER subtrees

3.3 Binary Search Trees (BST)

Rule: for every node, left subtree values < node value < right subtree values.
In-order traversal of a BST always gives a sorted sequence — this is a key exam fact!

def insert(root, key):

if root is None:
return TreeNode(key)
if key < [Link]:
[Link] = insert([Link], key)
elif key > [Link]:
[Link] = insert([Link], key)
return root

def search(root, key):

if root is None or [Link] == key:
return root
if key < [Link]:
return search([Link], key)
return search([Link], key)

3.4 AVL Trees — Self-Balancing BST

Problem with BST: if we insert sorted data, it degenerates into a linked list → O(n) operations.
AVL Tree solution: after every insert/delete, check the balance factor and rotate if needed.
• Balance Factor = height(left) - height(right)
• Allowed values: -1, 0, +1
• If |BF| > 1 → tree is unbalanced → perform rotation

Rotation Type When Used

Left Rotation (LL case) Right-heavy: inserted into right subtree of right child

Right Rotation (RR case) Left-heavy: inserted into left subtree of left child

Left-Right Rotation (LR) Inserted into right subtree of left child

Right-Left Rotation (RL) Inserted into left subtree of right child

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 7

3.5 B-Trees
B-Trees are generalised search trees used in DATABASES and FILE SYSTEMS.
• Every node can have multiple keys (not just 2 children)
• A B-tree of order m: each node has at most m children
• All leaves are at the same depth (perfectly balanced)
• Efficient for disk access — reduces number of reads needed

Operation/Algorithm Best Case Average Case Worst Case

BST Search/Insert/Delete O(log n) O(log n) O(n) unbalanced
(balanced)
AVL Search/Insert/Delete O(log n) O(log n) O(log n)
B-Tree Search/Insert/Delete O(log n) O(log n) O(log n)
Tree Traversal (any type) O(n) O(n) O(n)

TOPIC 4: Abstract Priority Queues & Heaps

4.1 Priority Queue
A priority queue is like a normal queue BUT each element has a priority. The element with
highest priority is served first (regardless of when it arrived).
Uses: Dijkstra's algorithm, operating system task scheduling, Huffman coding.

4.2 Heaps
A heap is a COMPLETE binary tree stored as an array, satisfying the heap property:
• Max-Heap: parent >= children (root is the MAXIMUM element)
• Min-Heap: parent <= children (root is the MINIMUM element)
Complete binary tree: all levels are full except possibly the last, which is filled left to right.

Array Representation of Heap

For a node at index i (0-based):
• Left child: 2i + 1
• Right child: 2i + 2
• Parent: (i - 1) // 2
import heapq

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 8

 # Min-heap operations in Python:
heap = []
[Link](heap, 5) # O(log n)
[Link](heap, 2)
[Link](heap, 8)
print([Link](heap)) # returns 2 (minimum) O(log n)

# Heapify an existing list: O(n)

data = [10, 3, 7, 1, 5]
[Link](data) # converts to min-heap in-place

4.3 Heapify Operation

heapify-down (sift-down): used after removing root. Move the replacement down to correct
position.
heapify-up (sift-up): used after inserting. Move new element up to correct position.

Operation/Algorithm Best Case Average Case Worst Case

Insert (heappush) O(log n) O(log n) O(log n)
Remove min/max (heappop) O(log n) O(log n) O(log n)
Peek (view root) O(1) O(1) O(1)
Build heap from array (heapify) O(n) O(n) O(n)
Heap sort O(n log n) O(n log n) O(n log n)

TOPIC 5: Abstract Sets / Maps — Hash Tables

5.1 What is a Hash Table?
Hash tables give O(1) average for insert, search, and delete. This is why Python dictionaries
and sets are so fast.
A hash table stores key-value pairs. A hash function maps a key to an index in an array.
Hash function: index = hash(key) % table_size
Problem: Two different keys can hash to the SAME index → collision!

5.2 Collision Resolution

Method 1: Chaining (Separate Chaining)
Each array slot holds a LINKED LIST of all keys that hash to that index.
• insert: O(1) average, O(n) worst case
• search: O(1) average, O(n) worst case
• delete: O(1) average

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 9

 class ChainedHashTable:
def __init__(self, size=10):
[Link] = [[] for _ in range(size)]
[Link] = size

def _hash(self, key):

return hash(key) % [Link]

def insert(self, key, value):

idx = self._hash(key)
for pair in [Link][idx]:
if pair[0] == key:
pair[1] = value; return
[Link][idx].append([key, value])

def search(self, key):

idx = self._hash(key)
for pair in [Link][idx]:
if pair[0] == key: return pair[1]
return None

Method 2: Linear Probing (Open Addressing)

When a collision occurs, check the NEXT slot (index + 1, index + 2, ...) until empty slot found.
• Probe sequence: h(key), h(key)+1, h(key)+2, ... (mod table size)
• Problem: Primary clustering — long runs of filled slots slow down search

Method 3: Double Hashing

Use a SECOND hash function to determine the step size. Avoids clustering.
Probe sequence: h1(key), h1(key)+h2(key), h1(key)+2·h2(key), ...
• h2(key) must never return 0
• Common h2: h2(key) = prime - (key % prime)

Method Pros / Cons

Chaining Simple, handles high load; uses extra memory for pointers

Linear Probing Cache-friendly; primary clustering degrades performance

Double Hashing Eliminates clustering; slightly slower due to 2 hash calls

5.3 Load Factor

Load factor α = n / m, where n = number of keys, m = table size.
• If α > 0.7, rehash (resize the table) to maintain O(1) performance
• Java: rehash at α > 0.75; Python: rehash at α > 0.66

Operation/Algorithm Best Case Average Case Worst Case

Insert (chaining) O(1) O(1) O(n)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 10

 Operation/Algorithm Best Case Average Case Worst Case
Search (chaining) O(1) O(1) O(n)
Insert (open addressing) O(1) O(1) O(n)
Search (open addressing) O(1) O(1/(1-α)) O(n)

TOPIC 6: Sorting Algorithms

Sorting is heavily tested. Know the algorithm, code, complexity, and when to use each one.

6.1 Bubble Sort

Repeatedly compares adjacent elements and swaps if out of order. Largest elements "bubble"
to the end.
def bubble_sort(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(0, n - i - 1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # optimisation: stop early if sorted
break
return arr

6.2 Insertion Sort

Like sorting playing cards — take each element and insert it into the correct position in the
sorted portion.
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j] # shift right
j -= 1
arr[j + 1] = key # insert
return arr

6.3 Selection Sort

Find the minimum element in the unsorted portion and swap it to the front.
def selection_sort(arr):
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 11

 if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr

6.4 Merge Sort — Divide and Conquer

Split the array in half recursively, sort each half, then merge the sorted halves.
Merge sort is STABLE and always O(n log n). Best choice when stability matters or for
linked lists.

def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)

def merge(left, right):

result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
[Link](left[i]); i += 1
else:
[Link](right[j]); j += 1
[Link](left[i:])
[Link](right[j:])
return result

6.5 Quick Sort

Choose a pivot, partition elements into < pivot and > pivot, recursively sort each partition.
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
mid = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + mid + quick_sort(right)

6.6 Heap Sort

Build a max-heap, then repeatedly extract the max element to sort.
def heap_sort(arr):
import heapq
# Use min-heap (negate values for descending, or just heapify + pop)
[Link](arr) # O(n)
return [[Link](arr) for _ in range(len(arr))] # O(n log n)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 12

6.7 Bucket Sort & Radix Sort
Bucket Sort: distribute elements into buckets by range, sort each bucket, concatenate.
• Best for uniformly distributed floating-point numbers
• Time: O(n + k) average where k = number of buckets

Radix Sort: sort digit by digit, from least significant to most significant (LSD radix sort).
• Does NOT compare elements — uses counting sort internally
• Time: O(d × (n + b)) where d = digits, b = base
• Space: O(n + b)

Operation/Algorithm Best Case Average Case Worst Case

Bubble Sort O(n) O(n^2) O(n^2)
Insertion Sort O(n) O(n^2) O(n^2)
Selection Sort O(n^2) O(n^2) O(n^2)
Merge Sort O(n log n) O(n log n) O(n log n)
Quick Sort O(n log n) O(n log n) O(n^2)
Heap Sort O(n log n) O(n log n) O(n log n)
Bucket Sort O(n+k) O(n+k) O(n^2)
Radix Sort O(d(n+b)) O(d(n+b)) O(d(n+b))

Sort Algorithm Stable? | In-place? | Best Use Case

Bubble Sort YES | YES | Teaching / tiny arrays

Insertion Sort YES | YES | Nearly sorted, small arrays

Selection Sort NO | YES | When writes are expensive

Merge Sort YES | NO | Linked lists, stability required

Quick Sort NO | YES | General purpose, large arrays

Heap Sort NO | YES | Guaranteed O(n log n), no extra space

Radix Sort YES | NO | Integers with fixed digit count

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 13

TOPIC 7: Searching Algorithms
7.1 Linear Search
Check every element one by one from the beginning.
• Works on UNSORTED and SORTED arrays
• Time: O(n) — must check all elements in worst case
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # return index
return -1 # not found

7.2 Binary Search

Requires a SORTED array. Eliminate half the search space each step.
Binary search is O(log n) — searching 1 billion elements takes only ~30 comparisons!

def binary_search(arr, target):

lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid # found
elif arr[mid] < target:
lo = mid + 1 # search right half
else:
hi = mid - 1 # search left half
return -1

Recursive version:
def binary_search_rec(arr, target, lo, hi):
if lo > hi: return -1
mid = (lo + hi) // 2
if arr[mid] == target: return mid
elif arr[mid] < target: return binary_search_rec(arr, target, mid+1, hi)
else: return binary_search_rec(arr, target, lo, mid-1)

Operation/Algorithm Best Case Average Case Worst Case

Linear Search O(1) O(n) O(n)
Binary Search O(1) O(log n) O(log n)
BST Search (balanced) O(1) O(log n) O(log n)
Hash Table Search O(1) O(1) O(n)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 14

TOPIC 8: Graph & DAG Algorithms
8.1 Graph Terminology
Graphs model relationships — social networks, road maps, websites, dependencies. Master
graph algorithms for the exam!
• Vertex (node) — a point in the graph
• Edge — connection between two vertices
• Directed graph (Digraph) — edges have direction (one-way)
• Undirected graph — edges go both ways
• Weighted graph — edges have a numeric cost/weight
• DAG — Directed Acyclic Graph (no cycles)
• Degree — number of edges at a vertex

8.2 Graph Representations

Adjacency Matrix
2D array of size V×V. matrix[i][j] = 1 (or weight) if edge from i to j exists.
• Space: O(V²)
• Check if edge exists: O(1)
• Best for: dense graphs where V² ≈ E

Adjacency List
Array of linked lists. Each vertex stores its neighbours.
• Space: O(V + E)
• Check if edge exists: O(degree of vertex)
• Best for: sparse graphs (most real-world graphs)
# Adjacency list using dictionary
graph = {
0: [1, 2],
1: [2],
2: [0, 3],
3: [3]
}

8.3 Graph Traversals

Breadth-First Search (BFS)
Visit all neighbours at the current depth before going deeper. Uses a QUEUE.
Finds shortest path in unweighted graphs.

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 15

 from collections import deque

def bfs(graph, start):

visited = set()
queue = deque([start])
[Link](start)
while queue:
vertex = [Link]()
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
[Link](neighbour)
[Link](neighbour)

Depth-First Search (DFS)

Go as deep as possible before backtracking. Uses a STACK (or recursion).
def dfs(graph, vertex, visited=None):
if visited is None: visited = set()
[Link](vertex)
print(vertex, end=" ")
for neighbour in graph[vertex]:
if neighbour not in visited:
dfs(graph, neighbour, visited)

8.4 Topological Sort (DAG only)

Linear ordering of vertices such that for every edge u → v, u comes BEFORE v.
Used in: build systems, course prerequisites, task scheduling.
Algorithm (Kahn's — uses BFS):
1. Compute in-degree of every vertex
2. Add all vertices with in-degree 0 to a queue
3. While queue is not empty: dequeue vertex, add to result, reduce in-degree of
neighbours, add any with in-degree 0 to queue
4. If result has all vertices: valid topological order. Else: graph has a cycle.

8.5 Minimum Spanning Tree (MST)

A spanning tree connects ALL vertices with MINIMUM total edge weight. Only for undirected
weighted graphs.

Kruskal's Algorithm
5. Sort all edges by weight (ascending)
6. Pick the cheapest edge that does NOT create a cycle
7. Repeat until V-1 edges are selected
Uses Union-Find (Disjoint Set Union) to detect cycles. Time: O(E log E)

Prim's Algorithm
8. Start from any vertex

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 16

 9. Greedily add the cheapest edge connecting the growing tree to a new vertex
10. Repeat until all vertices are included
Uses a priority queue (min-heap). Time: O(E log V)

8.6 Shortest Path Algorithms

Dijkstra's Algorithm
Finds shortest path from a SOURCE to ALL other vertices. Works on non-negative weights only.
import heapq

def dijkstra(graph, source):

dist = {v: float("inf") for v in graph}
dist[source] = 0
pq = [(0, source)] # (distance, vertex)
while pq:
d, u = [Link](pq)
if d > dist[u]: continue
for v, weight in graph[u]:
if dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
[Link](pq, (dist[v], v))
return dist
# Time: O((V + E) log V)

Operation/Algorithm Best Case Average Case Worst Case

BFS / DFS O(V+E) O(V+E) O(V+E)
Topological Sort (Kahn) O(V+E) O(V+E) O(V+E)
Kruskal's MST O(E log E) O(E log E) O(E log E)
Prim's MST (heap) O(E log V) O(E log V) O(E log V)
Dijkstra's Shortest Path O(E log V) O(E log V) O(E log V)

QUICK REFERENCE — All Complexities

Print this page and stick it above your desk. Review it the night before every test.

Structure / Algorithm Best Average Worst Space

Array access O(1) O(1) O(1) O(n)
Array insert/delete O(1) O(n) O(n) O(n)
Linked list access O(n) O(n) O(n) O(n)
Linked list insert/del (head) O(1) O(1) O(1) O(n)
Stack push/pop O(1) O(1) O(1) O(n)
Queue enqueue/dequeue O(1) O(1) O(1) O(n)

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 17

 Structure / Algorithm Best Average Worst Space
BST search/insert (balanced) O(log n) O(log n) O(n) O(n)
AVL search/insert/delete O(log n) O(log n) O(log n) O(n)
Heap insert O(log n) O(log n) O(log n) O(n)
Heap extract min/max O(log n) O(log n) O(log n) O(n)
Hash table insert/search O(1) O(1) O(n) O(n)
Bubble / Insertion / Selection O(n) O(n^2) O(n^2) O(1)
Merge Sort O(n log n) O(n log n) O(n log n) O(n)
Quick Sort O(n log n) O(n log n) O(n^2) O(log n)
Heap Sort O(n log n) O(n log n) O(n log n) O(1)
Linear Search O(1) O(n) O(n) O(1)
Binary Search O(1) O(log n) O(log n) O(1)
BFS / DFS O(V+E) O(V+E) O(V+E) O(V)
Dijkstra's O(E log V) O(E log V) O(E log V) O(V)

EXAM TIPS & STUDY STRATEGY

The exam is 2 hours — 50% of your final mark. Continuous assessment is the other 50%
(tests + group project + assignment).

High-Priority Topics (Most Likely to Appear)

• Big-O analysis — given code, determine the complexity
• BST operations — insert, delete, search, in-order traversal
• Sorting algorithms — trace through bubble/merge/quick sort step by step
• Hash table collision resolution — chaining vs linear probing
• Heaps — draw the heap, show insert/extract operations
• Graph traversal — BFS and DFS step-by-step traces
• Dijkstra's shortest path — trace the algorithm on a weighted graph
• AVL rotations — identify which rotation and perform it

Common Exam Question Types

11. Trace an algorithm on given data (show every step)
12. Write pseudocode or Python code for a data structure operation
13. Determine time/space complexity and justify your answer
14. Compare two data structures or algorithms
15. Draw the result of operations on a tree/heap/graph

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 18

Memory Tricks
• LIFO = Stack (Last In First Out) = a stack of plates
• FIFO = Queue (First In First Out) = a queue at a shop
• BST in-order traversal = always sorted
• Hash table = dictionary = O(1) average for everything
• Merge sort = ALWAYS O(n log n) = most reliable sort
• Quick sort worst case O(n^2) = happens with already-sorted data and bad pivot
• Dijkstra = shortest path = needs non-negative weights
• BFS uses QUEUE, DFS uses STACK (or recursion)
• AVL balance factor must be -1, 0, or +1

Good luck! You have all the content you need. Revise consistently and practice
tracing algorithms by hand.

HCS111/HAI111 — Data Structures & Algorithms — UZ | Page 19