CSE Blog - quant, math, computer science puzzles

Source: Mailed by Sudeep Kamath (EECS PhD Student, UC Berkeley, EE IITB 2008 Alumnus) Problem: A is a 300 x 300 matrix with 17 on the diagonal, and the rest of the entries being 11. What is det (A) ? Update: (21 June 2014): Solution posted by Gowtham R (Stanford), Justin Rising, Pavan Bharadwaj, Hansaplatz and gaurushh in comments! Thanks

Disclaimer: It is a made up problem. Not to be attempted by light hearted. Problem: I have a 300 word text. I have a large list of indexed strings (Length of string ~ 20, Number of strings ~ 1M). I need to figure out phrases in the 300 word text that match exactly to one of the strings in the large list of strings I have. A naive approach: Taking all 45000 (300 C 2) phrases, search in the large list of strings. Can we do better than this? We need to minimize calls to list of indexed strings!

Problem 1: Consider the problem of picking K elements randomly from N elements. Suggest an algorithm. What is the time and space complexity of your algorithm? Problem 2: Now consider that the stream is infinitely long (i.e. N is unknown). Now how do we pick K elements randomly. Update (24 June 2014): Solution: Posted by Himanshu (Prob 1), PlacementIITB2014 (Prob2) and Sid (Prob1 and Prob2) in comments! Thanks claimtoken-52ac74fbddf1e

Source: IBM Ponder This Dec 12 ( http://domino.research.ibm.com/comm/wwwr_ponder.nsf/challenges/December2012.html ) - Mailed to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: 36 people live in a 6x6 grid, and each one of them lives in a separate square of the grid. Each resident's neighbors are those who live in the squares that have a common edge with that resident's square. Each resident of the grid is assigned a natural number N, such that if a person receives some N>1, then he or she must also have neighbors that have been assigned all of the numbers 1,2,...,N-1. Find a configuration of the 36 neighbors where the sum of their numbers is at least 90. As an example, the highest sum we can get in a 3x3 grid is 20: 1 2 1 4 3 4 2 1 2 Update (24 June 2014): Solution:  Available on  IBM Research Ponder This - December 2012 Solution

Source: Mailed to me by Vashist Avadhanula (PhD Student at Columbia Business School, EE IITB 2013 Alumnus) Problem: Consider a case where you flip two fair coins at once (sample space is HH, HT, TH & TT) you repeat this experiment many times and note down the outputs as a sequence. What is the expected number of flips (one flip includes tossing of two coins) to arrive at the sequence HHTHHTT.

Source: Mailed to me by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008) Problem: Tricky Question. Let f be a continuous, real-valued function on reals such that limit_{n \rightarrow \infty} f(nx) = 0 for all real x. Show limit_{x\rightarrow \infty} f(x) = 0.

Source: Sent to me by Aashay Harlalka (Final Year Student, CSE, IITB) Problem: For a given positive integer n, what would be the minimum no. of weights required so that we can weigh all positive integers <= n Follow up Generalized problem: If we have k copies of each distinct weight, then what is the minimum no. of distinct weights required ? Old Related Puzzle: There is a very different popular problem but knit in the same story (posted 4 years back on the blog): Weighing Problem Note : Weights are of integer values only.