Advanced Project

Please read every single line below, especially the Notes section.

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 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.: 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 2-4 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 2-5 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 problem-solving with coding. Coding is always the tiniest part of such puzzle-solving 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 half-baked 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/non-ideal/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. → Multi-level algorithm Solutions for 1. → Advanced multi-level algorithm [Egg dropping.] There is a n-floored 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 n-floored 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 m-ary 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 2-step 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.

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 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.: 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 2-4 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 2-5 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 problem-solving with coding. Coding is always the tiniest part of such puzzle-solving 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 half-baked 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/non-ideal/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. → Multi-level algorithm
- Solutions for 1. → Advanced multi-level algorithm
[Egg dropping.] There is a n-floored 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 n-floored 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 m-ary 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 2-step 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.