1
Important Questions and Answers
CP25C01- Advanced Data Structures and Algorithms
Syllabus
1. Linear Data Structures and Memory Optimization: Advanced arrays: Sparse arrays,
dynamic arrays, cache-aware structures, Linked lists: Skip lists, unrolled linked lists, XOR
linked lists, Stacks and Queues: Priority queues, double-ended queues, circular buffers,
Hashing: Perfect hashing, cuckoo hashing, extendible hashing.
Practical:
• • Implement skip lists and measure performance compared with balanced BST.
• • Experiment with cache-aware data structures and analyze memory utilization.
2. Advanced Tree Data Structures: Balanced Trees: AVL, Red-Black Trees, Splay Trees,
Treaps, Multi-way Trees: B-Trees, B+ Trees, R-Trees, Segment Trees, Fenwick Trees,
Suffix Trees and Tries for string processing, Applications in indexing, text retrieval,
computational geometry.
Practical:
• • Implement B+ tree for database indexing use-case.
• • Design a suffix tree-based algorithm for DNA sequence matching.
3. Graph Data Structures and Algorithms: Representation: Adjacency list/matrix, incidence
matrix, compressed storage, Traversals: DFS, BFS with applications, Shortest Path
Algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson’s algorithm, Minimum
Spanning Trees: Prim’s, Kruskal’s, Borůvka’s algorithm, Network Flow Algorithms: Ford-
Fulkerson, Edmonds-Karp, Push-Relabel.
Practical:
es
• • Implement Johnson’s algorithm for sparse graph shortest paths.
ot
• • Demonstration of Maximum flow in traffic or network routing simulation.
N
C
./E
4. Algorithm Design and Paradigms: Divide and Conquer: Karatsuba’s multiplication,
of
Strassen’s algorithm, Greedy Methods: Huffman coding, interval scheduling, set cover
Pr
approximation, Dynamic Programming: Matrix chain multiplication, Floyd-Warshall,
y,
knapsack variants, Backtracking and Branch-and-Bound, Randomized Algorithms and
h
at
ap
m
U
V.
, 2
Probabilistic Analysis.
Practical:
• • Implement Strassen’s algorithm and compare with naive matrix multiplication.
• • Develop a randomized algorithm for primality testing (Miller–Rabin).
5. Computational Complexity and Approximation Algorithms: Complexity Classes: P, NP,
NP-Complete, NP-Hard, Reductions: Polynomial-time reductions, Cook-Levin theorem
(overview), Approximation Algorithms: Vertex cover, set cover, TSP, k-center problem,
Heuristic Algorithms: Local search, simulated annealing, genetic algorithms.
Practical:
• • Implement approximation algorithm for vertex cover.
• • Complexity analysis of a chosen NP-hard problem and implement a heuristic.
6. Advanced Topics and Emerging Trends: Randomized Algorithms – Monte Carlo
Algorithms, Parallel and Distributed Algorithms – PRAM Model, Divide and Conquer in
Parallel, Load Balancing, Streaming Algorithms – Data Stream Models, Sketching and
Sampling, Frequency Moments, Advanced String Matching – Suffix Trees, Suffix Arrays,
Pattern Matching in Linear Time.
Practical:
• • Implement randomized and streaming algorithms on real-world datasets.
• • Design of parallel and distributed algorithms.
S.No. Description
Unit-I
Linear Data Structures and Memory Optimization
Basic Concepts
Concept Important Basic Concepts / Equations
Arrays containing mostly zero or default values. Store only non-zero elements as
Sparse Arrays (row, column, value). Space: O(k), where k = non-zero elements, instead of O(m ×
n).
Arrays that automatically resize when capacity is reached. Append: amortized
Dynamic Arrays
O(1); resizing typically doubles capacity.
Cache-Aware Organize data to improve CPU cache locality and reduce cache misses.
es
ot
Structures Contiguous memory access improves performance.
N
Multi-level linked lists that enable fast searching. Average search, insertion and
C
Skip Lists
deletion: O(log n); worst case: O(n).
./E
Unrolled Linked Each node stores multiple elements, reducing pointer overhead and improving
of
Pr
Lists cache efficiency. Search: generally O(n).
y,
XOR Linked Lists Each node stores the XOR of previous and next addresses. Equation: npx =
h
at
ap
m
U
V.
, 3
address(previous) XOR address(next). Uses less pointer storage but is difficult to
implement safely.
Elements are removed according to priority. Binary heap: insert O(log n), delete-
Priority Queues
min/max O(log n), peek O(1).
Double-Ended Insertion and deletion are possible at both front and rear. Efficient
Queues (Deque) implementations support O(1) operations at both ends.
Fixed-size buffers where indices wrap around. Equation: next_index =
Circular Buffers (current_index + 1) MOD capacity. Useful in streaming and producer-consumer
systems.
A hash function maps a fixed set of keys without collisions. Ideal lookup time:
Perfect Hashing
O(1).
Uses two or more hash functions; collisions relocate existing keys to alternate
Cuckoo Hashing positions. Lookup: O(1) worst case with a fixed number of hash locations;
insertion may require rehashing.
Extendible Dynamic hashing technique that uses a directory and bucket splitting. Uses global
Hashing depth and local depth to expand efficiently as records increase.
Important Equations for Revision
Sparse array storage: Space = O(k), where k is the number of non-zero elements.
Dynamic array amortized append: O(1)
Skip list average search: O(log n)
Binary heap insertion/deletion: O(log n)
Circular buffer index: next = (current + 1) % capacity
XOR linked list: npx = prev_address XOR next_address
Hash table average lookup: O(1) with a suitable hash function and controlled load factor.
Hash table load factor: α = n / m, where n = number of stored keys and m = number of slots.
Exam tip: Focus on the definition, main advantage, time complexity, and one practical application of
each structure.
Multiple Choice QA
1. Which data structure is most suitable for storing a matrix containing mostly zero elements?
es
ot
A) Dynamic array
N
C
./E
B) Sparse array
of
Pr
C) Circular buffer
y,
h
at
ap
m
U
V.
, 4
D) Skip list
Answer: B) Sparse array
Reason: A sparse array stores only non-zero elements and their positions, reducing memory usage
when most elements are zero.
Equation:
Memory savings = Dense array memory − Sparse array memory
2. What is the main advantage of a skip list over a conventional linked list?
A) It requires no extra memory
B) It provides faster searching on average
C) It stores elements contiguously
D) It eliminates pointer usage
Answer: B) It provides faster searching on average
Reason: A skip list uses multiple levels of links to skip over elements, achieving average search time
of O(log n), compared with O(n) for a conventional linked list.
Equation:
Average search time: Skip list = O(log n)
Conventional linked list = O(n)
3. Which data structure allows insertion and deletion at both the front and rear? es
A) Stack
ot
N
B) Priority queue
C
./E
C) Double-ended queue (Deque)
of
Pr
hy,
at
ap
m
U
V.
Important Questions and Answers
CP25C01- Advanced Data Structures and Algorithms
Syllabus
1. Linear Data Structures and Memory Optimization: Advanced arrays: Sparse arrays,
dynamic arrays, cache-aware structures, Linked lists: Skip lists, unrolled linked lists, XOR
linked lists, Stacks and Queues: Priority queues, double-ended queues, circular buffers,
Hashing: Perfect hashing, cuckoo hashing, extendible hashing.
Practical:
• • Implement skip lists and measure performance compared with balanced BST.
• • Experiment with cache-aware data structures and analyze memory utilization.
2. Advanced Tree Data Structures: Balanced Trees: AVL, Red-Black Trees, Splay Trees,
Treaps, Multi-way Trees: B-Trees, B+ Trees, R-Trees, Segment Trees, Fenwick Trees,
Suffix Trees and Tries for string processing, Applications in indexing, text retrieval,
computational geometry.
Practical:
• • Implement B+ tree for database indexing use-case.
• • Design a suffix tree-based algorithm for DNA sequence matching.
3. Graph Data Structures and Algorithms: Representation: Adjacency list/matrix, incidence
matrix, compressed storage, Traversals: DFS, BFS with applications, Shortest Path
Algorithms: Dijkstra, Bellman-Ford, Floyd-Warshall, Johnson’s algorithm, Minimum
Spanning Trees: Prim’s, Kruskal’s, Borůvka’s algorithm, Network Flow Algorithms: Ford-
Fulkerson, Edmonds-Karp, Push-Relabel.
Practical:
es
• • Implement Johnson’s algorithm for sparse graph shortest paths.
ot
• • Demonstration of Maximum flow in traffic or network routing simulation.
N
C
./E
4. Algorithm Design and Paradigms: Divide and Conquer: Karatsuba’s multiplication,
of
Strassen’s algorithm, Greedy Methods: Huffman coding, interval scheduling, set cover
Pr
approximation, Dynamic Programming: Matrix chain multiplication, Floyd-Warshall,
y,
knapsack variants, Backtracking and Branch-and-Bound, Randomized Algorithms and
h
at
ap
m
U
V.
, 2
Probabilistic Analysis.
Practical:
• • Implement Strassen’s algorithm and compare with naive matrix multiplication.
• • Develop a randomized algorithm for primality testing (Miller–Rabin).
5. Computational Complexity and Approximation Algorithms: Complexity Classes: P, NP,
NP-Complete, NP-Hard, Reductions: Polynomial-time reductions, Cook-Levin theorem
(overview), Approximation Algorithms: Vertex cover, set cover, TSP, k-center problem,
Heuristic Algorithms: Local search, simulated annealing, genetic algorithms.
Practical:
• • Implement approximation algorithm for vertex cover.
• • Complexity analysis of a chosen NP-hard problem and implement a heuristic.
6. Advanced Topics and Emerging Trends: Randomized Algorithms – Monte Carlo
Algorithms, Parallel and Distributed Algorithms – PRAM Model, Divide and Conquer in
Parallel, Load Balancing, Streaming Algorithms – Data Stream Models, Sketching and
Sampling, Frequency Moments, Advanced String Matching – Suffix Trees, Suffix Arrays,
Pattern Matching in Linear Time.
Practical:
• • Implement randomized and streaming algorithms on real-world datasets.
• • Design of parallel and distributed algorithms.
S.No. Description
Unit-I
Linear Data Structures and Memory Optimization
Basic Concepts
Concept Important Basic Concepts / Equations
Arrays containing mostly zero or default values. Store only non-zero elements as
Sparse Arrays (row, column, value). Space: O(k), where k = non-zero elements, instead of O(m ×
n).
Arrays that automatically resize when capacity is reached. Append: amortized
Dynamic Arrays
O(1); resizing typically doubles capacity.
Cache-Aware Organize data to improve CPU cache locality and reduce cache misses.
es
ot
Structures Contiguous memory access improves performance.
N
Multi-level linked lists that enable fast searching. Average search, insertion and
C
Skip Lists
deletion: O(log n); worst case: O(n).
./E
Unrolled Linked Each node stores multiple elements, reducing pointer overhead and improving
of
Pr
Lists cache efficiency. Search: generally O(n).
y,
XOR Linked Lists Each node stores the XOR of previous and next addresses. Equation: npx =
h
at
ap
m
U
V.
, 3
address(previous) XOR address(next). Uses less pointer storage but is difficult to
implement safely.
Elements are removed according to priority. Binary heap: insert O(log n), delete-
Priority Queues
min/max O(log n), peek O(1).
Double-Ended Insertion and deletion are possible at both front and rear. Efficient
Queues (Deque) implementations support O(1) operations at both ends.
Fixed-size buffers where indices wrap around. Equation: next_index =
Circular Buffers (current_index + 1) MOD capacity. Useful in streaming and producer-consumer
systems.
A hash function maps a fixed set of keys without collisions. Ideal lookup time:
Perfect Hashing
O(1).
Uses two or more hash functions; collisions relocate existing keys to alternate
Cuckoo Hashing positions. Lookup: O(1) worst case with a fixed number of hash locations;
insertion may require rehashing.
Extendible Dynamic hashing technique that uses a directory and bucket splitting. Uses global
Hashing depth and local depth to expand efficiently as records increase.
Important Equations for Revision
Sparse array storage: Space = O(k), where k is the number of non-zero elements.
Dynamic array amortized append: O(1)
Skip list average search: O(log n)
Binary heap insertion/deletion: O(log n)
Circular buffer index: next = (current + 1) % capacity
XOR linked list: npx = prev_address XOR next_address
Hash table average lookup: O(1) with a suitable hash function and controlled load factor.
Hash table load factor: α = n / m, where n = number of stored keys and m = number of slots.
Exam tip: Focus on the definition, main advantage, time complexity, and one practical application of
each structure.
Multiple Choice QA
1. Which data structure is most suitable for storing a matrix containing mostly zero elements?
es
ot
A) Dynamic array
N
C
./E
B) Sparse array
of
Pr
C) Circular buffer
y,
h
at
ap
m
U
V.
, 4
D) Skip list
Answer: B) Sparse array
Reason: A sparse array stores only non-zero elements and their positions, reducing memory usage
when most elements are zero.
Equation:
Memory savings = Dense array memory − Sparse array memory
2. What is the main advantage of a skip list over a conventional linked list?
A) It requires no extra memory
B) It provides faster searching on average
C) It stores elements contiguously
D) It eliminates pointer usage
Answer: B) It provides faster searching on average
Reason: A skip list uses multiple levels of links to skip over elements, achieving average search time
of O(log n), compared with O(n) for a conventional linked list.
Equation:
Average search time: Skip list = O(log n)
Conventional linked list = O(n)
3. Which data structure allows insertion and deletion at both the front and rear? es
A) Stack
ot
N
B) Priority queue
C
./E
C) Double-ended queue (Deque)
of
Pr
hy,
at
ap
m
U
V.
