Advanced Project

We are currently working on a book series on algorithmic problem-solving. We aim to cover hundreds of problems and solutions for each algorithm design technique (such as dynamic programming, divide-and-conquer, backtracking, etc) using a specific template (currently, to the best of our knowledge, there are no such books). The ultimate goal of the project is that the books once published should be good references for interview preparation, algorithmic problem-solving, and supplementary material for algorithms courses. The work done will go to this book series. The work can be part of a 2-semester honors project, independent study, or volunteer work. If you are interested, please let me know sharing your CV, unofficial transcript, whether you are an honors student, details of your interests, etc. This project requires mathematics, algorithms, and coding in Google Colab using Python. Consider this project only if you are passionate about algorithms/mathematics/puzzles/programming.

Dynamic Programming
  • The good work done in this project will go to the DP book.
  • The template for DP is as follows. We want to solve hundreds of DP problems in the following template.
    Step 1. Subproblem -- what a subproblem is
    Step 2. Recurrence -- relationship between subproblems
    Step 3. Dependency -- recurrence visualized on the DP table
    Step 4. Algorithm -- bottomup DP algorithm code
    Step 5. Table -- input and DP table for an example
    Step 6. Complexity -- time and extra space complexity
    Step 7. Extensions -- space-optimized algorithm code and getting the solution algorithm code
Divide-and-Conquer
  • The good work done in this project will go to the DC book.
  • The template for DC is as follows. We want to solve hundreds of DC problems in the following template.
    Step 1. Subproblem -- what a subproblem is
    Step 2. Recursive formulation -- relationship between subproblems -- can be a recurrence or textual explanation
    Step 3. Algorithm -- recursive algorithm code (add non-recursive algorithm code also for decrease-and-conquer problem)
    Step 4. Example -- recursive tree for an example
    Step 5. Complexity -- time and extra space complexity
Project Details
  • If you are an MS student and you are really interested in this project, please talk to CSE 523/524 students who have worked with me (e.g.: Nitin Singh and Edward Chen). Discuss the working style, content of work, intensity of work, and my expectations. We meet and discuss progress/feedback on Fridays.
  • If you are a BS-Honors student and you are really interested in this project, please talk to CSE 495/496 students who are working with me (e.g.: Elan Shetreat-Klein). Discuss the working style, content of work, intensity of work, and my expectations. Students show progress via new algorithms, solutions, implementations, visualizations, etc. We meet and discuss as and when the student makes progress.
  • Your project work on a given problem if it is based on existing solutions to it.
    • [Step 1. Problem statement] You will be assigned a problem and possibly a web link for reference.
    • [Step 2. Understand solution] Get the solution to the problem in the template using Geeksforgeeks/Leetcode/ChatGPT/Copilot/Gemini. Note that many codes given ChatGPT/Copilot/Gemini are plain wrong. So, it is your responsibility to verify the correctness of the solutions that you provide.
    • [Step 3. Implement and test] Implement the solution in Python (in Google Colab), and test your code extensively for very large input.
    • [Step 4. Document] Create documentation (usually 2 pages) in Latex in the Overleaf project that will be shared with you. Your work will be analyzed based on this documentation and the strength of your computer program. If the documentation is not solid, you have to fix it until it is perfect.
    • [Step 5. Repeat] Repeat steps 2-4 to cover all solutions for a given problem. There can be multiple solutions to a problem.
    Your project work on a puzzle if there are no known good solutions to it. This is for advanced problems and mostly for the finest students.
    • [Step 1. Problem statement] You will be assigned a problem and possibly a web link for reference.
    • [Step 2. Brainstorm for ideas] We might meet multiple times to brainstorm for ideas and approaches.
    • [Step 3. Try solving using an approach] We might have to try using an approach by working out examples, trying to formalize the solution, trying to create diagrams that can further give ideas, and trying to prove the approach correct (if it is). Students who are mathematically very strong and algorithmically very deep will usually come up with nice ideas and approaches to solve a given problem.
    • [Step 4. Implement and test] Implement the solution in Python (in Google Colab), and test your code extensively.
    • [Step 5. Document] Create documentation in Latex, beautiful presentations with diagrams, tables, lots of examples, etc to teach the working of the algorithm in a great way. Your work will be analyzed based on this documentation and the strength of your computer program.
    • [Step 6. Repeat] Repeat steps 2-5 to cover different ways to attack a given problem.
    From experience, "understanding solutions" and "try solving using an approach" are the toughest parts and great students do excellent in these steps. Rock solid understanding automatically means easier and faster implementation.
  • If you are interested, email me with your CV and GPA.