Assignment 6: Individual Deep Dive

Overview

This assignment will consist of an individual deep dive on an application or algorithm related to the themes of this class.

Areas of Investigation

For your project, you should choose one or more of the following areas of investigation. In terms of scoping, this should equate to about 8 hours of work (not including the time to come up with the project topic and write the proposal).

  • Learn about and (likely) implement a new algorithm. You could choose a true classic: All Pairs Shortest Path, Ford-Fulkerson for maximum network flow, Page Rank, Fast-Fourier Transform, Viterbi Algorithm for Hidden Markov Models, K-Means clustering, Policy Iteration for optimal planning, Simplex Method for linear programming, etc. You could choose an algorithm from a research paper of interest.
  • Apply an algorithm we already learned about to an interesting problem. Take one of the algorithms you’ve already implemented and try it on a non-trivial problem.
  • Take one of the assignments further. You might try various optimizations to your code to improve runtime (make sure to pair this with benchmarks that show the change in performance). You might want to implement additional features or variants of your algorithm (e.g., additional sorting algorithms).
  • Do some research to determine how a particular algorithm is being applied currently or has been applied in the past.

Deliverables

Project Proposal (2 points)

Turn in a project proposal that lays out your plan for the project. Clearly specify what your project will entail, what deliverables you will create, and how much time you think each part will take. With your proposal, include a rubric for grading your project (what does “A”-level performance look like, “B”-level, etc.).

Other Deliverables (8 points)

You are required to include a brief summary of what you did for the project and a summary of all other deliverables. Some other deliverables you might have (this is a list of options… you will not have all of these):

  • Kotlin code (so you will want to send a link to a repository).
  • A summary of how an algorithm a particular algorithm you studied works
  • A report on former and current applications of your algorithm.
  • A report on the changes in performance that resulted in optimizing your code.
  • A report that summarizes an application or experiment you did.

Advice for Choosing a Project

Think back to why you took this class. Are there learning goals that you would like to bolster now that we are roughly halfway through the semester? Is there a new area you learned about that you are excited about that you want to investigate in greater detail? What sort of work do you want your project experience to consist of (e.g., writing code, reading papers, recording a whiteboard walkthrough of an algorithm)?

Some Sample Projects from Last Time

  • learn about the KMP algorithm and use it to efficiently implement a find / replace feature.
  • Implement and benchmark the Fast Fourier Transform (FFT)
  • Implement Floyd Warshall (x2)
  • Karatsuba algorithm for fast integer multiplication
  • Quantum Fourier Transform (QFT) via the Deutsch-Josza algorithm
  • Ford-Fulkerson Algorithm (x2)
  • 1D and 2D Fast Fourier Transform (FFT)
  • Learn about, implement, and test the Q-learning algorithm for reinforcement learning
  • PageRank (x2)
  • K-Means clustering (x2)
  • Policy Gradient algorithm for reinforcement learning
  • Approximation algorithms for the traveling salesman problem
  • Benchmark and implementation of a hybrid sorting algorithm