Difference between revisions of "CISC220 F2023 Project"
| (10 intermediate revisions by the same user not shown) | |||
| Line 3: | Line 3: | ||
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 (first come, first served!): | 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 (first come, first served!): | ||
| − | * | + | * [Charmaine and Mithra] [Siddharth and Alex] [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-black] balanced binary trees |
* [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] or other kinds of searches with backtracking | + | * [Molly and Ilana] [Jasnoor and Andrew] [https://en.wikipedia.org/wiki/Knight%27s_tour Knight's tour] or other kinds of searches with backtracking |
| − | * [https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm Rabin-Karp string matching] | + | * [Rubina and Listowel], [Kevin] [https://en.wikipedia.org/wiki/Rabin%E2%80%93Karp_algorithm Rabin-Karp string matching] |
* [Madison and MJ] [https://courses.grainger.illinois.edu/cs225/fa2021/resources/kd-tree/ k-d trees], [https://en.wikipedia.org/wiki/Nearest_neighbor_search nearest neighbor search] -- basically spatial binary search trees | * [Madison and MJ] [https://courses.grainger.illinois.edu/cs225/fa2021/resources/kd-tree/ k-d trees], [https://en.wikipedia.org/wiki/Nearest_neighbor_search nearest neighbor search] -- basically spatial binary search trees | ||
* Compression (text at the word/sentence level, image/video/audio) | * Compression (text at the word/sentence level, image/video/audio) | ||
** [Trung and Araf] LZMA compression | ** [Trung and Araf] LZMA compression | ||
* [Mateo] Minimax game tree search for checkers | * [Mateo] Minimax game tree search for checkers | ||
| − | * Automatic creation of crossword puzzles, sudoku, or other puzzles | + | * [Sammy and Maanav] Automatic creation of crossword puzzles, sudoku, or other puzzles |
* Automatic solution of a particular type of puzzle through graph search | * Automatic solution of a particular type of puzzle through graph search | ||
| − | * Bigram/trigram/n-gram text modeling and generation | + | ** [Daniel] Nonograms |
| + | * [Roger], [Coleman] Bigram/trigram/n-gram text modeling and generation | ||
| + | * [Lindsey] Mutable priority queues | ||
* Your own scintillating idea | * Your own scintillating idea | ||
You may work alone or as part of a pair. | 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. I don't just want a single word from the list above but also at least a sentence or two on what existing code/libraries you might use and a link to data that you intend to apply your program to. Time slots for 20-minute in-person demos (not in front of the class) on Tuesday, December 12 (reading day) will be posted after Thanksgiving break. Your code | + | Send me an e-mail with your proposal and partner name, if applicable, as soon as possible so that I can give some feedback. I don't just want a single word from the list above but also at least a sentence or two on what existing code/libraries you might use and a link to data that you intend to apply your program to. Time slots for 20-minute in-person demos (not in front of the class) on Monday, December 11 and Tuesday, December 12 (reading day) will be posted after Thanksgiving break. Your code and a 1+ page description of what you tried, how much you got done, and any results/statistics are officially due at midnight on December 12. Demos will take place in my lab, Smith 211. |
Latest revision as of 14:23, 7 December 2023
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 (first come, first served!):
- [Charmaine and Mithra] [Siddharth and Alex] Red-black balanced binary trees
- Treaps
- [Molly and Ilana] [Jasnoor and Andrew] Knight's tour or other kinds of searches with backtracking
- [Rubina and Listowel], [Kevin] Rabin-Karp string matching
- [Madison and MJ] k-d trees, nearest neighbor search -- basically spatial binary search trees
- Compression (text at the word/sentence level, image/video/audio)
- [Trung and Araf] LZMA compression
- [Mateo] Minimax game tree search for checkers
- [Sammy and Maanav] Automatic creation of crossword puzzles, sudoku, or other puzzles
- Automatic solution of a particular type of puzzle through graph search
- [Daniel] Nonograms
- [Roger], [Coleman] Bigram/trigram/n-gram text modeling and generation
- [Lindsey] Mutable priority queues
- Your own scintillating idea
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. I don't just want a single word from the list above but also at least a sentence or two on what existing code/libraries you might use and a link to data that you intend to apply your program to. Time slots for 20-minute in-person demos (not in front of the class) on Monday, December 11 and Tuesday, December 12 (reading day) will be posted after Thanksgiving break. Your code and a 1+ page description of what you tried, how much you got done, and any results/statistics are officially due at midnight on December 12. Demos will take place in my lab, Smith 211.
