CSE Blog - quant, math, computer science puzzles

Again: copied from Saurabh Joshi's blog Problem : Integers from 1 to n are arranged in a circle in some random permutation. Prove that there exist a set of k consecutive integers on the circle sum of which would be at least k(n+1)/2. Solution :  Highlight the part between the * symbols for the answer. * Set of k consecutive integers can be uniquely specified by the start position and the direction ( clockwise, or counter clockwise ). We will call it a k-box. Because they are arranged in a circular fashion there are n positions. We will assume clockwise direction. For each of these n position compute sum of its corresponding k-boxes. Sum of all these k-boxes would be kn(n+1)/2. The reason is that \sum_{i=1} ^{n} i = n(n+1)/2. and each number will appear in k different k-boxes. So on average, each k-box makes a contribution of k(n+1)/2. So there exist at least one k-box which makes contribution of at least k(n+1)/2. Or, in other words. If none of the k-box can make con

Problem : Let there be an abstract data structure D. D is a k-Max data structure, in a sense that on performing delete() on this data structure, it returns the k-th largest(Maximum ) element of the elements stored in it. Only two operations are allowed on D, insert(number) and delete(). Obviously, insert(n) will insert the given number n to the data structure. Prove that, it is impossible to implement D in a way such that both insert(n) and delete() takes O(1) time. Or in other words, any implementation of D will have at most one operation that can perform in O(1). The other operation can not be implemented in O(1). This has been copied from Saurabh Joshi's blog. He acknowledges Prof. Sundar (CSE, IITB) for the problem. :) Solution: Highlight the part between the * symbols for the answer. * Let us assume that we have such a data structure D. and let k=1, that is D is a 1-max data structure, which returns the largest element in D. Also, assume that insert(n) and delete() ar

Just an interesting observation: Fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21, 34... 8 miles ~ 13 kilometres 13 miles ~ 21 kilometres and so on..... This is because F(n+1) = F(n) + F(n-1) F(n+1)/F(n) = 1 + F(n-1)/F(n) For large enough n, F(n+1)/F(n) = F(n)/F(n-1) x=1+1/x x=(1+sqrt(5))/2 x~1.618 So, the ratio of consecutive numbers in fibonacci sequence is 1.618 and 1 mile ~ 1.606 km Hence, it holds. :)

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