Difference between revisions of "CISC220 F2021 Project"
| Line 6: | Line 6: | ||
* [https://en.wikipedia.org/wiki/Treap Treaps] | * [https://en.wikipedia.org/wiki/Treap Treaps] | ||
* [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour] | * [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour] | ||
| + | * [https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm Rabin-Karp string matching] | ||
* [https://courses.grainger.illinois.edu/cs225/fa2021/resources/kd-tree/ k-d trees], [https://en.wikipedia.org/wiki/Nearest_neighbor_search nearest neighbor search] | * [https://courses.grainger.illinois.edu/cs225/fa2021/resources/kd-tree/ k-d trees], [https://en.wikipedia.org/wiki/Nearest_neighbor_search nearest neighbor search] | ||
* Compression (text at the word/sentence level, image/video/audio) | * Compression (text at the word/sentence level, image/video/audio) | ||
Revision as of 08:21, 18 November 2021
The final project is your opportunity to explore an advanced data structure topic that was NOT covered in class this semester.
The main focus here is to write C++ code which implements and/or applies a data structure and/or algorithm of your choosing. You may use STL or other APIs/libraries, but only in a supporting role. If you use *any* code written by someone else (looking at you, Github), then you must cite it and be completely clear about what you added or changed. I am primarily interested in the code that you write and what your whole program does. Potential topics:
- Red-black balanced binary trees
- Treaps
- Knight's tour
- Rabin-Karp string matching
- k-d trees, nearest neighbor search
- Compression (text at the word/sentence level, image/video/audio)
- Cryptography (encoding/decoding, "breaking" codes, rainbow tables)
- Cryptocurrency, blockchain (e.g., hash chains, hash trees)
You may work alone or as part of a pair.
Send me an e-mail with your proposal and partner name, if applicable, as soon as possible so that I can give some feedback. As soon as I approve your proposal, you can pick a time slot for an in-person demo (not in front of the class) on Friday, December 10. Your code must also be submitted on this day.
