Class Project

In this project, students work in small groups to design and deliver a lecture on an algorithm not covered in this class. The goal is to deepen your understanding of algorithms while developing skills in research, collaboration, organization, and oral communication.

Each group will be responsible for teaching the topic to the class as if you were the instructor for that session. This means your presentation should not only demonstrate knowledge, but also engage your audience and facilitate learning.

Your group lecture should:

  • Be 60-70 minutes in length (reserving five mintues for the end-of lecture survey)
  • Clearly explain key concepts, terms, and ideas related to the topic
  • Include visual or instructional support (e.g., slides, handouts, demonstrations)
  • Actively engage the class (e.g., discussion questions, brief activities, examples, or case studies)
  • Use external resources for preparing (please discuss these resources with Dr. Fasy)

Your presentation might (helpful, but optional pieces):

  • Demonstrate an implementation of the algorithm
  • Walk-through small examples
  • Prove runtime
  • If there is a loop, state what the loop invariant is!

End-Of Lecture Survey

Each student in the class (including those presenting) will submit “one up / one down” at the end of the class. These will be collected by Dr. Fasy and presented in aggregate to the presenters. These surveys will count as an in-class assignment grade.

  • One up: what went well, and (briefly) why.
  • One down: what could have been improved, and (briefly) why.

Grading rubric: Your group will be graded on the following:

  • [20 points] Organization and clarity of the lecture, including quality of supporting materials (slides, handouts, etc.)
  • [20 points] Accuracy and depth of content
  • [20 points] Evidence of effective group collaboration
  • [20 points] Engagement and instructional effectiveness
  • [20 points] Professionalism and delivery

List of Potential Topics

  1. Convex Hull in 2D (a divide and conquer algorithm)
  2. Linear Programming, Simplex Algorithm
  3. Frechet distance (a dynamic program)
  4. Multi-threaded merge sort
    • CLRS Section 27.3
  5. RSA Encryption
  6. Skyline Algorithm
  7. Smallest enclosing circle (a randomized algorithm)
  8. Union-Find (where heuristics make actual improvements!)