Difference between revisions of "CISC220 F2023 Project"

From class_wiki
Jump to: navigation, search
 
(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) [https://en.wikipedia.org/wiki/Red%E2%80%93black_tree Red-black] balanced binary trees
+
* [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 must also be submitted on the day of your demo.
+
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.