Final Project (Fall 2026)

Build something real around a data structure that makes a visible difference. Pick a problem, implement a structure that solves it well, and show, with numbers, why it beats the obvious approach.

Key Dates

Date	What
Oct 26, 11:59p	Proposal due (Gradescope)
Dec 18	Project showcase
Dec 18, 11:59p	Final repository and report due

Talk to us before you submit the proposal

Every team must discuss its idea with a TA or the instructor (office hours or lab) before submitting the proposal. Proposals without that conversation will be returned.

Requirements

Teams of 2 or 3. Working alone requires explicit instructor approval.
At least one advanced data structure, implemented by the team. Advanced means not covered in class (see the ideas below).
Write the core structure yourselves, in C++. Libraries and other programming languages are fine for everything around it (I/O, graphics, parsing, a web front end).
Show the advantage. Compare against a simple baseline (brute force, a sorted array, a plain BST, etc.) and measure it. Plots of time vs. input size are expected, as in Lab 1.
Test it. Include tests that check correctness of the structure on its own.

Deliverables

1. Proposal (Oct 26)

Submitted as a PDF:

team members, and the TA or instructor you discussed it with;
the link to your GitHub repository;
the problem and why it is interesting;
the data structure(s), and why they fit this problem better than the obvious alternative;
the baseline you will compare against, and how you will measure the difference;
what a finished project looks like (the demo you plan to show).

2. GitHub Repository (Dec 17, 11:59p)

Create the repository now, commit every week

GitHub is required. Create the repository before submitting the proposal and include its link there. We want to see consistent work in the commit history, from every team member. The history counts toward the implementation grade. A repository created at the end, or files dropped in the night before, will be graded accordingly.

Source code, tests, and benchmark scripts.
A README with: what the project does, how to build and run it, and a short example.
A commit history that shows the project growing week by week.

3. Report (Dec 18, 11:59p)

A REPORT.md in the repository, about 4-6 pages worth:

Problem — what you built and for whom.
Design — the data structure, how it works, and its key operations.
Analysis — time and space complexity of the main operations.
Evaluation — experiments against the baseline, with plots and a short discussion.
AI usage — where AI tools were used, what they got wrong, and what you had to fix or reject.
Contributions — who did what.

4. Showcase (Dec 18)

A short live demo at the CS Showcase, you will be provided a table to show your project. Show it working, show the numbers, and be ready to explain any part of the code. Every team member presents.

Grading

Component	Weight
Proposal	10%
Repository (including commit history) and report	50%
Showcase	40%

Extra credit

Outstanding projects may receive generous extra credit. Aim high.

AI Tools

You are permitted to use AI assistants, and to stay in charge of the result. Two free options for URI students:

AWS Kiro: AI coding environment, free access with your URI email [URI announcement].
Google AI Pro: free for one year for US college students [sign up].

You must be able to explain every line you submit. Expect questions about your code during the showcase.

Project Ideas

A starting point, not a menu. Each pairs a structure with an application where its advantage is easy to see. Do the research; propose your own if you have a better one.

#	Data structure / algorithm	Idea
1	Segment tree (lazy propagation)	Answer range queries (min, max, sum) on live stock prices while values keep changing. Compare against recomputing each range.
2	k-d tree	Find the nearest coffee shop, hospital, or bus stop among thousands of real map points. Compare against scanning every point.
3	Quadtree	Simulate thousands of moving particles with collision detection, rendered on screen. Watch the frame rate vs. checking every pair.
4	Splay tree	A cache or dictionary where some keys are hot. Show how self-adjusting beats a balanced tree on skewed access patterns.
5	Union-find	Generate and solve random mazes, or count connected regions in an image.
6	Dijkstra / A* with a binary heap	Route planner on a real road network (OpenStreetMap). Compare BFS, Dijkstra, and A* on nodes explored.
7	Topological sort	Course planner for the URI CS catalog: given prerequisites, produce a valid semester-by-semester plan.
8	PageRank on a directed graph	Rank pages in a slice of Wikipedia by their links. Which pages come out on top?
9	Quickhull (quicksort-style divide and conquer)	Compute convex hulls of large point sets with an animated visualization. Compare with Graham scan and brute force.
10	Huffman coding (priority queue + tree)	A file compressor and decompressor. Report compression ratios on text, code, and images.
11	Bloom filter	A spell checker or malicious-URL filter that uses a fraction of a hash set's memory. Measure false positives vs. memory.
12	Count-min sketch	Find trending words or hashtags in a large text stream using a fixed amount of memory.
13	LRU cache (hash table + doubly linked list)	Simulate a web or disk cache on a real access log. Compare hit rates with FIFO and random eviction.
14	Skip list	An ordered map built on randomization. Benchmark it against your own AVL or red-black tree.
15	Trie / radix tree	Word-game solver (Boggle, Wordle, crosswords) that prunes the search as it goes.
16	Suffix array	Fast substring search in a whole book or a DNA sequence. Compare against naive search.
17	Interval tree	Meeting scheduler that detects conflicts instantly across thousands of events.
18	B-tree	A tiny on-disk index for a large file. Count disk reads vs. a binary search tree.
19	Rope	A text editor backend that stays fast when inserting into the middle of a huge file. Compare with `std::string`.
20	External merge sort	Sort a file larger than available memory. Measure how chunk size affects running time.
21	Persistent data structure	Undo/redo or version history where every past state stays queryable without copying everything.
22	Cuckoo hashing	Guaranteed O(1) lookups. Compare against chaining and linear probing under high load.