Please iterate on this and try to improve it.
- User
Please iterate on this and try to improve it.
Assistant
Here's an improved, comprehensive exam design with better topic balance, modern applications, and varied cognitive demands. The questions progress from foundational to advanced concepts, emphasizing real-world relevance and critical thinking.
Algorithms & Data Structures Final Exam
Total: 100 points
Time: 2.5 hours1. Algorithm Analysis & Asymptotics (12 points)
a) Given the recurrence:
𝑇(𝑛) = 2𝑇(𝑛/2) + 𝑛 log 𝑛
Solve using the Master Theorem or recursion trees. Justify your answer. (6 points)
b) Compare 𝑂(𝑛!), Ω(2𝑛), and Θ(𝑛3) for large 𝑛. Provide real-world examples where each might occur. (6 points)
2. Data Structure Design (15 points)
Design an efficient data structure for a ride-sharing app that supports:
insert(driverID, rating)get_worst_driver()update_rating(driverID, newRating)
a) Specify your ADT and invariants. (3 points)
b) Justify choice of underlying structures with complexity analysis. (6 points)
c) Pseudocode forupdate_ratingandget_worst_driver. (6 points)
3. Graph Algorithms (18 points)
Graph: Cities A-F connected by roads with travel times:
A-B(4), A-C(2), B-C(1), B-D(5), C-D(8), C-E(10), D-E(2), D-F(6), E-F(3)a) Compute shortest paths from A using Dijkstra. Show:
- Priority queue state at each step
- Final distances/paths (8 points)
b) COVID now closes vertex D. Modify your solution to avoid D. (4 points)
c) Prove why Dijkstra fails with negative weights using this graph. (6 points)
4. Divide & Conquer (10 points)
Given an array of 𝑛 distinct integers:
a) Design an 𝑂(𝑛) algorithm to find the 𝑘𝑡ℎ smallest element. (6 points)
b) Derive worst-case complexity rigorously. (4 points)
No pseudocode – describe intuition and partitioning strategy.
5. Dynamic Programming (15 points)
Problem: Maximize profit from stock prices [𝑝₁, 𝑝₂, ..., 𝑝ₙ] with:
- At most two transactions
- No overlapping transactions
a) Define subproblems and recurrence. (6 points)
b) Pseudocode with 𝑂(𝑛) time/space. (6 points)
c) Apply to [3, 5, 1, 4, 6, 2]. Show DP table. (3 points)
6. Hashing & Tradeoffs (10 points)
Keys: {22, 41, 18, 44, 59, 32, 31, 73}
Hash function: ℎ(𝑘) = 𝑘 mod 13
a) Insert using double hashing (ℎ₂(𝑘)=7−(𝑘 mod 7)). Show probes. (5 points)
b) Resize table to size 19. Describe rehashing process and challenges. (5 points)
7. Advanced Trees (10 points)
a) Insert [25, 30, 20, 28, 23, 10] into an empty AVL tree. Show:
- Tree after each insertion
- Rotation types (6 points)
b) Compare B-trees (order 4) vs. AVL for database indexing. (4 points)
8. Real-World Systems (10 points)
a) Explain how Bloom Filters reduce disk I/O in databases. Include:
- Parameters affecting false positives
- Space/computation tradeoffs (5 points)
b) Why might QuickSort be preferred over HeapSort for in-memory sorting? (5 points)
Bonus: Lower Bounds (5 points)
Prove that comparison-based sorting requires Ω(𝑛 log 𝑛) time. Use decision trees.
Key Improvements:
- Modern Context
- Ride-sharing ADT (Q2), COVID constraints (Q3), stock trading (Q5), database indexing (Q7b)
- Depth over Breadth
- Focused graph problem with extensions (Q3)
- DP with transaction limits (Q5)
- Conceptual Emphasis
- Master Theorem application (Q1)
- Negative-weight proof (Q3c)
- Lower-bound proof (Bonus)
- Practical Tradeoffs
- Hashing strategies (Q6)
- B-tree vs. AVL (Q7b)
- QuickSort vs. HeapSort (Q8b)
- Cognitive Progression
- Basic analysis → DS design → Advanced algorithms → Systems integration
Sample Solutions Provided
Instructor note: Full solutions with partial credit allocation available separately.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.