Embedded Files
Extra credit opportunities listed here give you a chance to engage with the material more deeply and/or from a different perspective. Points earned will go towards the Assignments portion of your grade (and cannot be counted towards the other components like exams). The weight is given as a percentage of a single assignment. For example, extra credit worth 10% can be thought of as earning 10 additional percentage points on an assignment. Remember that your assignments make up 25% of your grade, there will be around 10, and I will drop the lowest one.
Opportunities are categorized below by topic. If you would like to propose an extra credit opportunity, please do so!
Submission process
Submission process
To submit your extra credit work, please use the form below. You must submit before 11:59pm on the last day of classes. You probably want to work on extra credit opportunities as you're also working on the corresponding topic during the semester!
You should describe what you've done in a clear and precise fashion. Include a video/walkthrough of your work (e.g., screenshots of an implementation working). Think of this like a more expanded version of what you might include on your resume. In fact, if you create a web site/page documenting what you've done, you can use it as part of an eportfolio.
For example:
I implemented the Gale-Shapley algorithm for stable matchings in python. The algorithm solves the problem of finding a stable matching given the preference lists of n families and n animals. To run my code, download it from ______ and execute the command ______. Your input should be of the form ______, and the output returned will be ______. Here is a sample run of the algorithm on an input with 5 families and 5 animals: <include screenshot/pasted text here>.or
I created a choose-your-own adventure with the https://storyboard.viget.com/ tool. The final story can be found here: ______________. My story consists of ____ vertices with directed edges to encode choices along the way. Here is the graph representing my story: <include screenshot here>.Stable matchings
Stable matchings
- 15%: Implement the Gale-Shapley propose-and-reject algorithm
Graphs
Graphs
- 10%: Create a choose-your-own adventure using the storyboard engine: https://storyboard.viget.com/.
- 10%: Create a maze for which the right-hand-rule will not work. Be sure to justify why in terms of graph connectivity.
- 10%: Implement the generic graph traversal algorithm, and show its behavior with at least 5 DF and BF examples.
- +5%: Implement the recursive DF traversal algorithm, and show its (differing) behavior from the generic version. For this, use a standardized order (e.g., lexicographic) for ordering adjacency lists.
- 10%: Implement topological sorting. Your algorithm should use data structures that achieve O(m+n) running time.
- 10%: Implement bipartite graph testing.
Report abuse