Projects
During the semester, you will complete four individual projects and one group project. The individual projects will be due roughly every three weeks, and the group project will be due at the end of the semester. The projects are designed to give you practice speaking and communicating the concepts and techniques we cover in class. The projects will be graded based on the quality of your explanations and the correctness of your solutions.
Individual Project
Deliverable: Record a 3 to 7 minute video explaining a specific algorithmic concept, problem, or application not covered during lecture.
Potential Topics:
- An algorithmic concept, setting, or technique not covered in lecture
- A challenging problem from a textbook and its solution
- Analyze an algorithm from another class (especially outside of CS)
Requirements:
- Topic must be related to what we’re covered in class (ask if you are at all unsure)
- Video must be between 3 and 7 minutes long (try to be concise and clear)
- Must include some sort of visual aid (e.g. slides, whiteboard, etc.) to help explain the topic
Submit your video by creating an Ed post with the video embedded and a brief description of the topic.
| Category | Excellent (A to B) | Satisfactory (B to C) | Needs Improvement (≤ C) |
|---|---|---|---|
| Technical Accuracy | Algorithm and logic are flawless; correct use of notation | Minor errors in logic or slight misuse of terms | Significant conceptial errors or hand-wavy logic |
| Complexity Analysis | Clearly explains the complexity of the algorithm with appropriate concepts | Somewhat explains the complexity, but with minor errors | Fails to explain or incorrectly explains the complexity |
| Clarity of Explanation | Explanation is clear, concise, and easy to follow | Explanation is somewhat clear, but may be rushed or disjointed | Explanation is unclear or confusing |
| Use of Visual Aids | Visual aids are effective and enhance understanding | Visual aids are somewhat helpful, but could be improved | Visual aids are missing or ineffective |
| Scope and Depth | Topic is appropriate for the level of the course and shows understanding | Topic is a bit too simple or lacks depth | Covers the topic superficially or misses key points |
Ideas for Project I
- Pick a problem from K&T:
- Chapter 1 Problems 1.3, 1.5, 1.6, 1.8
- Chapter 2 Problems 2.7, 2.8
- Come up with an interesting extension of the stable matching problem
- Explain the variation and how to solve it (e.g. with a modified version of the Gale-Shapley algorithm)
Explain \(\mathcal{o}(\cdot)\) and \(\omega(\cdot)\) notation and how it differs from \(O(\cdot)\) and \(\Omega(\cdot)\)
- Pick a problem from CLRS:
- Chapter 3.1 (page 52) Problems 6, 7