CSE 373 Data Structure & Algorithms

01. Deques

Directory: main/java/deques/
Objective: Implement and compare different deque (double-ended queue) data structures

Implementations:

• ArrayDeque - Circular array-based implementation
• ArrayListDeque - ArrayList-based implementation
• LinkedListDeque - Doubly-linked list implementation

Technical Spec: https://courses.cs.washington.edu/courses/cse373/25su/projects/deques/

02. Autocomplete

Directory: main/java/autocomplete/
Objective: Build efficient string matching systems for real-time search suggestions

Click to watch me yapping about implementation

Technical Spec: https://courses.cs.washington.edu/courses/cse373/25su/projects/autocomplete/

Implementations:

1. Sequential Search - Linear scan through unsorted array
2. Binary Search - Optimized search on sorted array
3. Ternary Search Tree (TST) - Space-efficient trie variant
4. TreeSet Implementation - Red-Black BST approach

Performance Analysis:

• Asymptotic complexity comparison across all implementations
• Experimental benchmarking with real city name datasets (deleted for DEMO due to size constaints)

03. Priority Queues

Directory: main/java/minpq/
Objective: Implement various priority queue data structures with performance optimization

Click to watch me yapping about implementation

Implementations:

1. DoubleMapMinPQ - Given reference implementation using TreeMap & HashMap (not a heap)
2. UnsortedArrayListPQ - Naive linear-time operations baseline, unsorted array using excess for-loops
3. HeapMinPQ - Standard binary heap using Java's PriorityQueue implementation (client)
4. OptimizedMinPQ - Custom binary heap with HashMap indexing, adapt helper methods (sink, swim, exch, greater) to an array list. Use HashMap to speed up contains() & changePriority() by retrieving node with index in constant time (implementor)

Key Optimizations:

• O(1) contains() and changePriority() operations via HashMap indexing
• Memory-efficient array-based heap representation

Technical Spec: https://courses.cs.washington.edu/courses/cse373/25su/projects/priority-queues/

04. Shortest Path Seam Carving

Directory: main/java/seamfinding/ and main/java/graphs/shortestpaths Objective: Implement content-aware image resizing using dynamic programming and graph algorithms

Click to watch me yapping about implementation

Implementations:

Seam Detection:

• AdjacencyList Graph - Explicit graph & neighbors construction ahead of time
• Generative Graph - On-demand node's neighbor generation for memory efficiency
• Dynamic Programming - Direct DP solution without explicit graph representation

Shortest Path Solvers / Algorithms:

• Topological Sort - Optimized for DAG structure (O(V + E))
• Dijkstra's Algorithm - General-purpose shortest path (O((V + E) log V))

Technical Spec: https://courses.cs.washington.edu/courses/cse373/25su/projects/shortest-paths/

💡 Key Learning Outcomes

• Algorithm Design: Implemented and optimized fundamental algorithms from scratch
• Data Structure Mastery: Deep understanding of trade-offs between different data structures
• Performance Engineering: Experience with profiling, benchmarking, and optimization
• Software Architecture: Clean separation of concerns and modular design patterns
• Testing Methodology: Comprehensive testing strategies for algorithmic code