EECS 281 Course Projects thumbnail
EECS 281 Course Projects

Undergraduate Winter 2025 Software Grade: A

EECS 281: Data Structures and Algorithms builds the theoretical and practical foundation of efficient computation — from STL container internals and custom heap implementations to graph traversals, hash-based indexing, and combinatorial optimization.

Topic 1: Search, Priority Queues & Market Systems

This section focuses on the mechanics of graph traversal and priority-driven data management. By building a word-morphing solver and a full stock-market simulator from scratch, I developed intuition for choosing the right container — queue vs. stack, sorted vs. unsorted heap — and for analyzing the real-world cost of those choices.

Project #1: Letterman — Word Morphing via Graph Search
C++ BFS / DFS Graph Search Dictionary Parsing
  • Objective: Given a dictionary and two words, find the shortest transformation sequence that converts the start word into the end word, where each step applies exactly one legal operation.
  • Build: Modeled the dictionary as an implicit graph where each word is a node and an edge exists between words reachable by a single operation. Implemented BFS (queue) for shortest-path search and DFS (stack) for deep exploration, selected at runtime via --queue / --stack flags.
  • Functionality: Supported four mutation modes — change (substitute one character), swap (transpose adjacent characters), insert, and delete (length-modifying ops) — and two output formats: Word mode (print every word in the chain) and Modification mode (print the compact edit sequence). Also handled a complex dictionary format with reversal (&), character-insertion bracket ([]), swap (!), and double (?) annotations.
Project #2A: Market Simulator — Priority Queue–Driven Order Matching
C++ Priority Queues Order Book Design Running Median Time-Travel Optimization
  • Objective: Simulate a multi-stock exchange that continuously matches buy and sell orders, tracks per-stock trade prices, and computes several analytical views over the market history.
  • Build: Maintained a per-stock order book using two std::priority_queues — a max-heap of buyers (highest willing price first) and a min-heap of sellers (lowest asking price first) — both with tie-breaking on arrival sequence for FIFO fairness. Accepted two input formats: timestamped-list (TL) and pseudo-random (PR via a seeded generator).
  • Functionality: Implemented four optional analytics flags: --verbose (print each matched trade), --median (per-timestamp median trade price via dual-heap streaming algorithm), --trader_info (net P&L per trader), and --time_travelers (maximum profit achievable by buying once and selling once per stock — solved with a single-pass greedy scan over a State machine tracking NoTrade → CanBuy → Potential → Completed transitions).
Project #2B: Priority Queue Library — Four Heap Implementations
C++ Binary Heap Pairing Heap Template Metaprogramming Amortized Analysis
  • Objective: Build four interchangeable, fully templated priority queue implementations that satisfy a common abstract interface, exposing the performance trade-offs between heap designs.
  • Build: Implemented all four classes inheriting from Eecs281PQ<TYPE, COMP_FUNCTOR>:
    • SortedPQ — sorted std::vector; $O(n)$ push, $O(1)$ top/pop.
    • UnorderedPQ — unsorted vector; $O(1)$ push, $O(n)$ top/pop.
    • BinaryPQ — classic binary max-heap with $O(\log n)$ push/pop and $O(n)$ batch construction via updatePriorities() (heapify).
    • PairingPQ — pointer-based pairing heap with $O(1)$ amortized push/merge and a updateElt() (decrease-key) operation for Dijkstra-style algorithms, using a child–sibling–previous pointer layout.
  • Functionality: All four types are drop-in replacements, with a custom comparison functor forwarded through the template chain — making P2A's order book trivially swappable to any underlying heap for benchmarking.

Topic 2: Hash-Based Indexing & Graph Optimization

This section tackles problems where brute force is computationally prohibitive. By building a multi-modal log search engine backed by hash maps and a drone routing solver using Prim’s MST, greedy heuristics, and branch-and-bound, I applied asymptotic analysis directly to observable runtime improvements.

Project #3: LogMan — Interactive Log Search & Excerpt Manager
C++ Hash Maps Binary Search Multi-Modal Querying Interactive CLI
  • Objective: Build a fast, interactive log analysis tool that ingests a large structured log file and supports several independent search modes over millions of entries.
  • Build: Stored the raw log as a vector<LogEntry> (master log, never reordered) and constructed two auxiliary indexes at load time: a sorted index (indirect sort by timestamp, enabling $O(\log n)$ range queries via lower_bound/upper_bound) and two hash maps — one keyed by lowercased category, one inverted index keyed by keyword — both mapping to vectors of master-log entry IDs.
  • Functionality: Supported four search commands — t (timestamp range), m (exact timestamp match), c (category lookup), k (keyword intersection across multiple terms) — each storing results in a search_list. A separate excerpt list (std::deque) served as a personal clipboard with commands to append individual entries (a), append the last search result (r), delete (d), move entries to the beginning/end (b/e), sort (s), clear (l), and print (p).
Project #4: Drone Router — MST, Heuristic TSP & Branch-and-Bound
C++ Prim's Algorithm Travelling Salesman Problem Branch & Bound 2-opt
  • Objective: Route a medical-supply drone across a coordinate map split into three regions — Main Campus (Quadrant I/II), Medical Campus (Quadrant III/IV), and a border corridor (the axes) — under three progressively harder optimization modes.
  • Build: Implemented three solver modes behind a single mission() dispatch:
    • MST mode — Prim's algorithm with an adjacency constraint: direct edges between Main and Medical Campus are forbidden (distance = $\infty$), forcing all cross-campus connections to route through border nodes. Runtime: $O(V^2)$.
    • FASTTSP mode — a heuristic pipeline: greedy nearest-neighbor insertion to build an initial tour, followed by furthest-insertion refinement, then a 2-opt local search to eliminate crossing edges. Produces good solutions quickly for 10,000-vertex inputs.
    • OPTTSP mode — exact branch-and-bound (genPerms()) seeded with the FASTTSP tour as an initial upper bound, pruned aggressively using an MST lower bound on the unvisited suffix plus the two cheapest connecting "arm" edges back into the partial path. Only explores permutations where running cost + arms + MST lower bound < best known.
  • Functionality: The MST cross-campus constraint required careful region detection at read time, flagging MST_computable only when vertices spanning both sides exist. OPTTSP's promising() check reuses the same Prim's implementation from Part A, making the lower-bound computation both correct and cache-friendly.

Updated: