CSS Computer Science Algorithms & Data Structures Syllabus

What is the LIFO principle and which ADT uses it?

Last-In-First-Out: the most recently added element is removed first. Used by the Stack ADT.

Name the core stack operations and their time complexities.

push (add to top) O(1), pop (remove from top) O(1), peek/top (view top) O(1), isEmpty O(1).

Give three real applications of a stack.

Function call management (call stack/recursion), expression evaluation and conversion (infix to postfix), undo operations, and backtracking/DFS.

What is stack overflow and stack underflow?

Overflow: attempting to push onto a full stack (fixed-size). Underflow: attempting to pop from an empty stack.

What is the FIFO principle and which ADT uses it?

First-In-First-Out: the earliest added element is removed first. Used by the Queue ADT.

Name the core queue operations and the two ends they act on.

Enqueue adds at the rear/tail; Dequeue removes from the front/head; plus peek/front and isEmpty. All O(1).

What problem does a circular queue solve compared to a linear array queue?

It reuses freed space at the front by wrapping the rear pointer around to the start, avoiding the false-full condition where a linear queue wastes vacated front slots.

In a circular queue of size N, how is the rear index advanced and how is fullness detected?

rear = (rear + 1) % N. The queue is full when (rear + 1) % N == front (when one slot is left empty to distinguish full from empty).

What is a priority queue and how does it differ from a normal queue?

Elements are dequeued based on priority rather than insertion order; the highest- (or lowest-) priority element is removed first. Often implemented with a heap.

What is a deque (double-ended queue)?

A queue allowing insertion and deletion at both the front and the rear ends.

Describe linear (sequential) search and its time complexity.

Check each element sequentially from start until the target is found or the list ends. Time: O(n) worst/average, O(1) best. Works on unsorted data.

Describe binary search, its prerequisite, and its time complexity.

Repeatedly compare the target to the middle element of a SORTED array, discarding the half that cannot contain it. Time: O(log n). Prerequisite: the data must be sorted.

When is linear search preferable to binary search?

When the data is unsorted, the list is very small, or the data structure does not allow random access (e.g. a linked list).

How many comparisons does binary search need in the worst case for n elements?

⌊log₂ n⌋ + 1 comparisons, i.e. O(log n).

State the time complexity (best/average/worst) and space of Bubble Sort.

Best O(n) with optimization, average and worst O(n²); space O(1). Stable, in-place.

State the time complexity and key property of Selection Sort.

O(n²) in all cases (best/average/worst); space O(1); in-place; generally NOT stable; performs the minimum number of swaps (O(n)).

State the time complexity of Insertion Sort and when it performs best.

Best O(n) (nearly sorted data), average and worst O(n²); space O(1); stable, in-place. Efficient for small or almost-sorted arrays.

State Merge Sort's time complexity, space, stability, and core technique.

O(n log n) in all cases; space O(n) (needs auxiliary array); stable; uses divide-and-conquer by splitting, recursively sorting, and merging.

State Quick Sort's average and worst time complexity, and what causes the worst case.

Average O(n log n), worst O(n²); space O(log n) for recursion. Worst case occurs with poor pivot choices (e.g. already-sorted data with first/last pivot). In-place, typically not stable.

State Heap Sort's time complexity, space, and stability.

O(n log n) in all cases; space O(1) (in-place); NOT stable. Builds a max-heap then repeatedly extracts the max.

What makes a sorting algorithm 'stable'?

It preserves the relative order of records with equal keys. Examples: Merge Sort, Insertion Sort, Bubble Sort. Unstable: Quick Sort, Heap Sort, Selection Sort.

What is the lower bound for comparison-based sorting and why?

Ω(n log n) comparisons in the worst case, because a comparison sort's decision tree must have n! leaves and a binary tree of n! leaves has height ≥ log₂(n!) = Ω(n log n).

What is a hash table and what is its average-case lookup time?

A data structure mapping keys to values using a hash function to compute an index into a bucket array. Average-case insert/search/delete is O(1); worst case O(n).

What is a collision in hashing and name two general resolution strategies.

A collision occurs when two distinct keys hash to the same index. Resolution: separate chaining (linked lists per bucket) and open addressing (probing for another slot).

Compare separate chaining and open addressing for collision resolution.

Chaining stores colliding elements in a linked list at each bucket (handles high load factors, uses extra pointers). Open addressing stores all elements in the array itself and probes for empty slots (better cache use, but degrades as it fills).

Name three open-addressing probing techniques.

Linear probing (check next slot sequentially), quadratic probing (offsets grow as i²), and double hashing (use a second hash function for the step size).

Define the load factor of a hash table and its significance.

Load factor α = n/m (number of stored elements / number of buckets). Higher α increases collisions; tables are typically resized/rehashed when α exceeds a threshold (e.g. 0.7).

What properties make a good hash function?

It should be deterministic, fast to compute, distribute keys uniformly across buckets, and minimize collisions (avalanche effect).

Define a binary tree and the maximum number of nodes at level i (root at level 0).

A tree where each node has at most two children (left and right). Maximum nodes at level i is 2^i; a tree of height h has at most 2^(h+1) − 1 nodes.

What is the defining ordering property of a Binary Search Tree (BST)?

For every node, all keys in its left subtree are smaller and all keys in its right subtree are larger than the node's key.

Which BST traversal yields keys in sorted ascending order, and what is its order of visiting?

In-order traversal (Left, Root, Right) yields keys in ascending sorted order.

Give the time complexity of search/insert/delete in a BST for balanced vs degenerate trees.

Balanced: O(log n). Degenerate (skewed, like a linked list): O(n). Average for random insertion: O(log n).

What is a balanced tree and why is balancing needed?

A tree whose height is kept O(log n) by limiting the height difference between subtrees. Balancing prevents degeneration into a linked list, guaranteeing O(log n) operations.

What is the balance condition of an AVL tree and how is balance restored?

For every node the heights of its left and right subtrees differ by at most 1 (balance factor ∈ {-1,0,1}). Balance is restored by single or double rotations (LL, RR, LR, RL) after insert/delete.

List the key properties of a Red-Black tree.

1) Every node is red or black. 2) The root is black. 3) Red nodes cannot have red children (no two reds in a row). 4) Every root-to-NULL path has the same number of black nodes (equal black-height). This guarantees O(log n) height.

Compare AVL trees and Red-Black trees.

AVL trees are more strictly balanced, giving faster lookups but more rotations on insert/delete. Red-Black trees are less rigidly balanced, allowing faster insertions/deletions with fewer rotations—preferred when modifications are frequent (e.g. C++ std::map).