CSE Blog - quant, math, computer science puzzles

Source: Original problem adapted from the "Ants Problem" (Link removed) at "CMU ACM Programming Contest" . Extension to the 4 year old problem on CSE Blog - Walking Ants Puzzle  . Problem also available at  J. Paulson Programming Blog Problem: You have a bunch of ants on a meter stick, each walking 1cm/s in some direction. If an ant hits the end of the stick, it falls off. If two ants collide, they both reverse direction. Walking Ants Puzzle  earlier essentially asked: Given the starting positions and directions of all the ants, how long until the last ant falls off? The new problem is : Given the starting positions and directions of all the ants, which ant(s) are the last to fall off? Disclaimer: I do not have the solution to the problem. It just looks like an interesting problem to solve. ( Readers Please ignore: Technorati claim:  6QVZ8YSY6XSD ) Update (24 June 2014): Solution:  Posted by Strilanc and me in comments!

Guide to wall street quant jobs for IITians from Pratik Poddar Summary of the deck This is a short guide for IITians preparing for Wall Street quantitative finance jobs, adapted from Ashwin Rao's presentation at Stanford and general interview preparation for quantitative analysis roles. What is quantitative finance? Roles at large banks and hedge funds, in trading businesses that involve quant analysis. The work requires advanced skills in math, statistics and computer science, and a sound understanding of trading markets. Example job titles: derivatives trader, trading desk quant strategist, derivatives modeler / econometric modeler, algorithmic trading quant, analytics developer. Firms that have hired at IITs: Goldman Sachs (FICC), Morgan Stanley (Strats and Modeling), Tower Research Capital, and WorldQuant (Millennium Partners). Interview preparation. The interviews are mostly technical and the topics fall under three heads: Mathematics: probability ( Prob...

Problem 1: Lion in a Circular Cage Puzzle Original Link: http://pratikpoddarcse.blogspot.in/2012/02/lion-in-circular-cage-puzzle.html Source:  Asked to me by Pramod Ganapathi (PhD Student at Stony Brook University) Problem: A lion and a lion tamer are enclosed within a circular cage. If they move at the same speed but are both restricted by the cage, can the lion catch the lion tamer? (Represent the cage by a circle, and the lion and lion tamer as two point masses within it.) Problem 2: Geometry Puzzle: Center of Square in Circle Original Link: http://pratikpoddarcse.blogspot.in/2012/11/geometry-puzzle-center-of-square-in.html Source: Asked to me by a lot of people from IIT Bombay on email and posted by a few on " Post a Question " page. Problem: What is the probability that two uniform random points (to be precise: i.i.d. with respect to Lebesgue measure) in the square are such that center of the square lies in the circle formed by taking the points as d...

Source:  Flipkart Interview Question from Interview Street (taken from  Chinmay - CSE IITB Blog ) Problem: Find the smallest number of jumps (i.e. optimal number of dice throws) needed to win a snakes and ladders game. Assume you are given a board with all the necessary inputs like start/end positions of all ladders and snakes. Solution: Highlight the part between the * symbols for the answer. * Model the board as a graph: one node per square, and from square x a directed edge to square transport(x + k) for each die value k = 1..6, where transport sends ladder bottoms to ladder tops and snake heads to snake tails (squares past the final square are ignored or bounce, per the rules). Every edge costs exactly one dice throw, so the answer is the shortest path from the start square to the final square in an UNWEIGHTED directed graph: plain BFS. Complexity: each node has at most 6 outgoing edges, so BFS is O(V + E) = O(N) for an N-square board. Note: the gr...

Source: One of the very few original problems on the blog. Remember ' Mathematics of Housie '? Please share if you like! Problem: Assumptions: a) I have infinite money in my account b) The daily limit of amount of money that can be withdrawn from an ATM is finite c) You can login into an ATM Machine only once a day d) If you login into the machine and enter a large number to withdraw, you will not get anything. And hence, you will not be able to withdraw anything from the ATM for the day. e) I do not know what the daily limit is. What strategy should I choose so that I can withdraw N rupees in minimum number of days? Of course, you can do it in N days (withdrawing only one rupee daily) you could do it in N-limit + ceiling(N/limit)-1 days (check N, check N-1, .. check limit. Once you know the limit, and you have already withdrawn 'limit' rupees, you will take ceiling ((N-limit)/limit) days more. Can you do better? Update: (19-07-2012) This is e...

(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 we...

This is not a puzzle. So, for those of you who follow this puzzle blog, please bear with me for just one post. Interesting Math in this article though :P Most of my friends already read an article that I wrote more than an year back - " Speak Up " Here, inspired by the movie, The Beautiful Mind, I give a mathematical analysis of asking a girl out. Nice time it is. Feb 10. No plans for Feb 14 and I am sure this article makes me look even more geekier and all the more reason for me to believe that I will be alone, yet again. But what the hell, lets do it! Note: This is not an independent analysis. There are many "mathematics sites" which does "similar" analysis. @Consultants, correct me if I am wrong in my estimates. :P Why is there a need to be selective? From the age of 15, I guess there are approximately 3,600 girls I have liked (On average days, I don't see new girls. But going outside, I like about 30 girls. Saying that I go out once...

This is the text of the Commencement address at Stanford University by Steve Jobs, CEO of Apple Computer and of Pixar Animation Studios, delivered on June 12, 2005. I am honored to be with you today at your commencement from one of the finest universities in the world. I never graduated from college. Truth be told, this is the closest I've ever gotten to a college graduation. Today I want to tell you three stories from my life. That's it. No big deal. Just three stories. The first story is about connecting the dots. I dropped out of Reed College after the first 6 months, but then stayed around as a drop-in for another 18 months or so before I really quit. So why did I drop out? It started before I was born. My biological mother was a young, unwed college graduate student, and she decided to put me up for adoption. She felt very strongly that I should be adopted by college graduates, so everything was all set for me to be adopted at birth by a lawyer and his wife. Except tha...