CSE Blog - quant, math, computer science puzzles

Source: Introduction to Algorithms (by Cormen, Rivest, Leiserson) Problem: Suppose that you are given 'n' red and 'n' blue water jugs, all of different shapes and sizes. All red jugs hold different amounts of water, as do the blue ones. For every red jug, there is a blue jug that holds the same amount of water and vice versa. How can you find the grouping of the jugs into pairs of red and blue jugs that hold the same amount of water, in the minimum number of comparisons. The only operations allowed is compare between a red and a blue jar (no two reds, no two blues) Update (Dec 30, 2010): Problem statement changed a bit to make it more understandable. Solution: Posted by Nikhil Garg (CSE, IIT Delhi third year undergraduate student) and Vivek Chaurasiya (Software Eng Symantec & CSE, IITR Alumnus) in comments! Explained in detail by me in comments!

Source: Asked to me by Dinesh Dharme (CSE IITB Fifth year student) Problem: You have a array of 0's and 1's. e.g. 0001011101001010100101010101100111 Find the maximum contiguous subsequence of the above sequence so the number of 0's and 1's in that subsequence are equal Update (21 Dec 2010): Solution: Posted by Nikhil Garg (Third year student, CSE IIT Delhi) in comments!

There is a lock which is an N by N grid of switches. Each switch can be in one of two states (on/off). The lock is unlocked if all the switches are on. The lock is built in such a way that, if you toggle some switch, all the switches in its row and its column toggle too Give an algorithm which, given N and a configuration of the N^2 switches, will tell you whether the lock can be unlocked by a sequence of switch toggles Note 1: Can be done in O(N^2) time and O(1) space. Note 2: You just need to tell if a sequence which unlocks the lock exists (and not the actual sequence) Update (Dec 20, 2010): Complete solution posted jointly by Siddhant Agarwal (EE, Final year student, IITB) and Gaurav Sinha (IITK 1996 CSE Alumnus, IRS Officer). Thanks a lot

Source: Asked to me by Prateek Srivastava (CSE IITB Alumnus & Yahoo! Software Engineer) Problem: I have ten cards, Ace,2,3,4,5,6,7,8,9,10. The value of the Ace is 1. They’re shuffled, then dealt one by one, face up. For the first card, you automatically win $10. For the next 9 cards, if the card face-up is greater than every previous card, you win $10 more. What is the expected winning amount? Clarification: 1) Game does not end when you draw a card that is not a winning card. ie, if I pick a 5 first, then a 6, then a 4, the game is not over. I keep drawing until all of the cards are gone 2) It might be useful to know that the chance of winning $100 is 1/10!, because the cards will have to be drawn in the order: {A, 2, 3, 4 … , 9, 10}. Update (Dec 08, 2010) Solution: Posted by Goutham Valeti (Aero IITB Alumnus, Fair Issac Research Scientist) in comments! A more mathematical solution posted by me in comments!

Source: http://www.cut-the-knot.org/ Problem: Assume a stick is broken at random into three pieces. What is the probability that the pieces can form a triangle? Solve it in following cases: Two break points are selected randomly (and distributed uniformly) on the stick. The stick is first broken into two pieces. The longest (or rather, not the shortest) is then broken into two. The stick is first broken into two pieces. A piece randomly selected with probability 1/2 is then broken into two. The stick is first broken into two pieces. A piece randomly selected with the probability proportional to its length is then broken into two.  Update (Dec 22, 2010) Solution posted by me in comments!

(Disclaimer: This post does not contain any puzzle, but it has sufficient math to keep you interested) I saw Social Network three times in 1 week. Not for entertainment. Not because I had nothing better to do. But because I wanted to understand the math and computer science fundae used in the movie. I would like to discuss one particularly interesting scene from the movie. You may remember Mark inviting his friend Eduardo to give him his chess algorithm at the beginning of the movie (Mark was drinking, blogging and hacking simultaneously and creating Facemash.com). You may also remember the scribbles on the window: and What is this? This is actually the math behind Elo Rating System. Elo rating system is a method for calculating the relative skill levels of players in two-player games such as chess. It is named after its creator Arpad Elo, a Hungarian-born American physics professor. As explained in the movie, Facemash was quite simple. Not unlike hotornot.com, students

Source: Homepage of Tejaswi Navilarekallu, Post Doctoral Fellow, Vrije Universiteit, Amsterdam Problem: A professor decides the following grading scheme in his class. After the final exam is graded, he keeps all the papers upside down on his table in a random order so that no student can recognize his own paper. Each student during his turn can overturn at most n/2 of these papers (where n is the total number of students in the class) and guess whether he received an A or a B on the final (there are only two grades given). Obviously the student doesn't know which paper is his, so it is not guaranteed that he will find his own score by looking at n/2 scores. The papers are then turned back and kept in the original order. The students cannot pass any information to others. All the students pass the course if "everyone" guesses their grade correctly, and they fail otherwise. Come up with a strategy that the students can decide on beforehand, so that the probability