Notes 
 "Mathematical and Algorithmic Puzzles" (described in the next section) is the only available project. I do not work on any other projects.
 This project requires mathematics, algorithms, and coding. Consider this project only if you are passionate about algorithms/mathematics/puzzles/programming.
 If you are an MS student and you are really interested in this project, please talk to CSE 523/524 students who are working with me (e.g.: Anurag Singla, Brijesh Gujar, and Krishna Alahari). 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 BSHonors student and you are really interested in this project, please talk to CSE 495/496 students who are working with me (e.g.: Michael Santomauro and Tahsin Ahmed). 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 puzzle if it is based on existing solutions to it. (e.g.: Circle of death puzzle in the book)
 [Step 1. Problem statement] You will be assigned a mathematical/algorithmic puzzle.
 [Step 2. Understand solution] Understand the mathematical/algorithmic solution from the assigned research paper or web link. You might have to read a lot of other web articles too. Use specific examples to show the working of the mathematical/algorithmic solutions. We will do a code review to check if we can improve the code.
 [Step 3. Implement and test] Implement the solution in Python (in Google Colab), and test your code extensively.
 [Step 4. 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 5. Repeat] Repeat steps 24 to cover all solutions for a given problem.
Your project work on a puzzle if there are no known good solutions to it. (e.g.: Sand timers puzzle in the book)
 [Step 1. Problem statement] You will be assigned a mathematical/algorithmic puzzle.
 [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 puzzle.
 [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 25 to cover different ways to attack a given puzzle.
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. Do not confuse algorithm design or problemsolving with coding. Coding is always the tiniest part of such puzzlesolving lifecycles as shown in the following analogy. Programming:Coding is same as Writing:Typing.
 If you are interested, email me again with your CV, GPA, and then we will setup a time so that I can meet students to discuss about the advanced project.

Mathematical and Algorithmic Puzzles 
Please go through this puzzle book. As many solutions as possible are given to solve each puzzle. For example, 18 algorithms are given for the circle of death puzzle (or Josephus problem) in the book which appear majorly in research papers; 3 algorithms are given for the coin weighing puzzle in the book which appear majorly in research papers, etc. A sample list of problems (almost all are algorithmic puzzles) we want to understand very deeply are given here. We are already working on some of them and hence you can find halfbaked solutions written for them in the puzzle book.
 [Horse racing.] There are n horses. There are only k number of race tracks and hence a maximum of k horses can participate in a race. Assume that there is no stop watch or timer and that there are no ties in the races. How do you select the m fastest horses in the order of their ranks minimizing the number of races?.
 Solutions → Tournament sort
 Solutions → Tournament merge sort
 Solutions → Selection based algorithm
 [Bridge crossing.] There are n friends {1, 2, 3, ... , n} who have to cross a bridge at night. We assume that the n friends are on the left side and they have to reach the right side. They have a torch and it is impossible to cross the bridge without a torch. The capacity of the bridge is c, i.e., at most c number of people can cross the bridge at a time. The time taken to cross the bridge for the ith person is ti minutes such that 0 < t1 ≤ t2 ≤ t3 ≤ ... ≤ tn. When a set of people walk together the faster ones waits for the slowest one. How can all friends cross the bridge safely in the fastest time possible?
 Solutions → Dynamic programming based algorithm
 Solutions → Integer linear programming based algorithm
 [Coin tossing.] A fair/ideal/unbiased coin is a coin whose probability of getting heads is 0.5, and the probability of getting tails is also 0.5. In contrast, an unfair/nonideal/biased coin is a coin whose probability of getting heads is p, where p ∈ (0,1) and p , 0.5, and the
probability of getting tails is q = 1 − p. Solve the following problems:
1. Suppose you have a fair coin. How do you efficiently simulate an unfair coin with success probability p using this fair coin?
2. How do you efficiently simulate an unfair coin with success probability p2 using an unfair coin with success probability p1?
 Solutions for 1. → Multilevel algorithm
 Solutions for 1. → Advanced multilevel algorithm
 [Egg dropping.] There is a nfloored building and we are given k identical eggs. We define threshold floor of a building as the highest floor in the building from and below which when the egg is dropped, the egg does not break, and above which when the egg is dropped, the egg breaks. We want to find the threshold floor of the nfloored building. The threshold floor of the building can be whole number in the range [0,n]. A threshold floor 0 means that when the egg is dropped from floor 1, the egg breaks, which in turn means that there is no threshold floor in the building. A threshold floor n means that when the egg is dropped from floor n, the egg does not break. Design an algorithm to find the threshold floor in a building and the number of drops required to find the threshold floor. The algorithm must minimize the worstcase number of drops.
 Solutions → Generalization of mary search algorithm
 Solutions → Generalization of decrement search algorithm
 Solutions → Dynamic programming based algorithm (that uses Binomial coefficients)
 Solutions → Generalization of algorithm from Peter Winkler
 [Burning ropes.] You are stranded in a jungle and you want to cook food. You have the necessary
ingredients such as firewood, pot, water, food items, lighter, etc to cook food. The
food must be cooked for exactly t minutes. Unfortunately your clock is not working
and there is no other standard way to measure time such as using mobiles, laptops,
Internet, etc. You realize that you have n ropes and they burn for t1, t2, ...., tn minutes. But each rope burns nonuniformly along its length. Assume that you can burn
the ropes from one or both of its ends. How do you measure exactly t minutes using
the n ropes and a lighter?
 Solutions → Backtracking based algorithm
 [The genie puzzle.] A lucky person finds a miraculous bottle in which resides a genie with powerful mathematical abilities. The person opens the bottle and the genie appears. The genie tells the person that the person can wish for something and it will be granted provided the person can win a 2step game with more than 90% probability. In the first step, the genie chooses an infinite sequence of real numbers and places each of these numbers in a box. In the second step, the person can open all but one boxes. Now the person must guess the exact real number present in the only unopened box with more than 90% probability. Is it possible for the person to win the game with more than 90% probability and get the person's wish granted? (Answer is yes!)
 [Nuts and bolts.] Suppose we are given n nuts and n bolts of different sizes. Each nut matches exactly one bolt and vice versa. The nuts and bolts are all almost exactly the same size, so we can’t tell if one bolt is bigger than the other, or if one nut is bigger than the other. If we try to match a nut witch a bolt, however, the nut will be either too big, too small, or just right for the bolt. Our task is to match each nut to its corresponding bolt.
Similarly, there are tens of other insanely beautiful puzzles when we go deep enough will lead to doors of exploration and investigation. Mathematics and computation are required for these puzzles.
The work done, if it is of good quality, will go to the puzzle book. We might work on a single puzzle for a few months or even an entire year until we are happy with the solution. We then move to another puzzle. 