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

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:

or

Stable matchings

• 15%: Implement the Gale-Shapley propose-and-reject algorithm

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.

Extra credit presentations

Lead your classmates with a 20-30 minute extra credit presentation, which could take the form of:

• an activity to reinforce earlier material (such as solving recurrence relations or asymptotic analysis)
• a presentation of a more advanced algorithm -- specific suggestions listed on the form below
• leading a problem-solving session for a simpler problem that uses a design approach from class (e.g., drawn from sample interview questions)

You can earn up to 5 points on your final average (this can be thought of as up to 25 points for a midterm exam). The amount of extra credit will depend on:

• the correctness and clarity of your materials
• the impact on student learning
• the organization of your lesson plan

Fill out the form below by Wednesday 11/13 if you want to do a presentation.