CSE Blog - quant, math, computer science puzzles

Source: Very standard problem in Quant interviews (Taken from quantnet, xkcd forums) Problem: A bowl of spaghetti contains n strands. Thor picks two ends at random and joins them together. He does this until no ends remain. What is the a) expected number of spaghetti loops in the bowl? b) expected average length of the loops? (in strands) c) expected number of k -hoops? ( a k -hoop is a loop made from k strands) Solution: Highlight the part between the * symbols for the answer. * a) Expected number of loops = 1 + 1/3 + 1/5 + ... + 1/(2n-1) (the sum of the first n odd reciprocals, about (ln n)/2 + ln 2 + gamma/2). When m strands (2m ends) remain, pick any end: the other end you join it to is uniformly one of the 2m - 1 remaining ends, and exactly one of those closes a loop. So a loop is created with probability 1/(2m-1) at that step, and summing the indicators over m = n, n-1, ..., 1 gives the answer (NG's recurrence; Rudradev Basak's generating funct...

Source: Asked to me by Chinmay Chouhan, Junior Undergraduate, CSE IITB Problem: Given the set of numbers from 1 to n : { 1, 2, 3 .. n } We draw n numbers randomly (with uniform distribution) from this set (with replacement). What is the expected number of distinct values that we would draw? Update (Oct 30, 2011): Solution posted by Yashoteja Prabhu (RA at Microsoft Research, IITB CSE 2011 Alumnus), Garvit Juniwal (IITB CSE Senior Undergraduate), Dinesh Krithivasan (IITM Alumnus, Phd University of Michigan, Senior Qualcomm Engineer), Nikhil Garg (IITD CSE Senior Undergraduate) and Avinash in comments!

Source: A linear algebra problem book Problem: Find the function f   ( member of span {1, sin x, cos x} ) that minimizes norm of ( sin 2x − f(x) ), where the norm comes from the inner product < f , g > = integral over x from -pi to pi [ f(x)g(x) ] Update (Oct 30, 2011): Solution posted by Harsh Pareek (Graduate Student at UT Austin, CSE IITB 2011 Alumnus) in comments.