How fast can robots can complete the given sequence

Blue and Orange are friendly robots. An evil computer mastermind has locked them up in separate hallways to test them, and then possibly give them cake.
Each hallway contains 100 buttons labeled with the positive integers {1, 2, ..., 100}. Button k is always k meters from the start of the hallway, and the robots both begin at button 1. Over the period of one second, a robot can walk one meter in either direction, or it can press the button at its position once, or it can stay at its position and not press the button. To complete the test, the robots need to push a certain sequence of buttons in a certain order. Both robots know the full sequence in advance. How fast can they complete it?
For example, let's consider the following button sequence:
   O 2, B 1, B 2, O 4
Here, O 2 means button 2 in Orange's hallway, B 1 means button 1 in Blue's hallway, and so on. The robots can push this sequence of buttons in 6 seconds using the strategy shown below:

Time | Orange           | Blue
-----+------------------+-----------------
  1  | Move to button 2 | Stay at button 1
  2  | Push button 2    | Stay at button 1
  3  | Move to button 3 | Push button 1
  4  | Move to button 4 | Move to button 2
  5  | Stay at button 4 | Push button 2
  6  | Push button 4    | Stay at button 2

Note that Blue has to wait until Orange has completely finished pushing O 2 before it can start pushing B 1.

catalan number pdfs

http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf
http://www-math.mit.edu/~rstan/ec/catadd.pdf

How many paths from one corner to the diagonally opposite corner in an n x n matrix do not cross the diagonal?

A sequence of n numbers, 1 thru n, is processed as follows: we either drop the next number into a stack, or we pop the topmost number of the stack. In 2n operations, all numbers would have been processed and the stack would also be empty. The output is the sequence of elements that were popped. How many output sequences are possible?

In how many ways may we pick a subset from 1, 2, 3, 4, … n so that no two successive numbers are picked?

The Britney Spears Problem ,Tracking who's HOT and who's not , presents an algorithmic challenge ?

 By Brian Hayes

• Back in 1999, the operators of the Lycos Internet portal began publishing a weekly list of the 50 most popular queries submitted to their Web search engine. Britney Spears—initially tagged a "teen songstress," later a "pop tart"—was No. 2 on that first weekly tabulation. She has never fallen off the list since then—440 consecutive appearances when I last checked. Other perennials include ­Pamela Anderson and Paris Hilton. What explains the enduring popularity of these celebrities, so famous for being famous? That's a fascinating question, and the answer would doubtless tell us something deep about modern culture. But it's not the question I'm going to take up here. What I'm trying to understand is how we can know Britney's ranking from week to week. How are all those queries counted and categorized? What algorithm tallies them up to see which terms are the most frequent?

                                  

• One challenging aspect of this task is simply coping with the volume of data. Lycos reports processing 12 million queries a day, and other search engines, such as Google, handle orders of magnitude more. But that's only part of the problem. After all, if you have the computational infrastructure to answer all those questions about Britney and Pamela and Paris, then it doesn't seem like much of an added burden to update a counter each time some fan submits a request. What makes the counting difficult is that you can't just pay attention to a few popular subjects, because you can't know in advance which ones are going to rank near the top. To be certain of catching every new trend as it unfolds, you have to monitor all the incoming queries—and their variety is unbounded.
• In the past few years the tracking of hot topics has itself become a hot topic in computer science. Algorithms for such tasks have a distinctive feature: They operate on a continuous and unending stream of data, rather than waiting for a complete batch of information to be assembled. Like a worker tending a conveyor belt, the algorithm has to process each element of the stream in sequence, as soon as it arrives. Ideally, all computations on one element are finished before the next item comes along.
• Much of the new interest in stream algorithms is inspired by the Internet, where streams of many kinds flow copiously. It's not just a matter of search-engine popularity contests. A similar algorithm can help a network manager monitor traffic patterns, revealing which sites are generating most of the volume. The routers and switches that actually direct the traffic also rely on stream algorithms, passing along each packet of data before turning to the next. A little farther afield, services that filter spam from e-mail can use stream algorithms to detect messages sent in thousands or millions of identical copies.
• Apart from the Internet, stream algorithms are also being applied to flows of financial data, such as stock-market transactions and credit-card purchases. If some government agency wanted to monitor large numbers of telephone calls, they too might have an interest in stream algorithms. Finally, the designers of software for some large-scale scientific experiments adopt a stream-oriented style of data processing. Detectors at particle-physics laboratories produce so much data that no machine can store it all, even temporarily, and so preliminary filtering is done by programs that analyze signals on the fly....................................................to be contd. :)

Interested People Can Read Full Article Here
http://amsciadmin.eresources.com/libraries/documents/2008631225466814-2008-07Hayes.pdf

Identify the ‘Bottleneck Spanning Tree’ of an undirected graph

Given an undirected graph, identify the ‘Bottleneck Spanning Tree’ of an undirected graph, which is defined to be any spanning tree that minimizes the weight of the heaviest edge used in the tree. In the usual ‘Minimum Spanning Tree’ problem, the sum of weights is minimized.

Identify if a given graph is a scorpion or not.

A scorpion is an undirected graph with 3 special vertices: the sting, the tail, and the body. The sting has degree one and is connected to the tail. The tail has degree two and is connected to the sting and the body. The body has degree n – 2 and is connected to all vertices except the sting. The other vertices may be arbitrarily connected with each other. Identify if a given graph is a scorpion or not.

Gray Code for Fibonacci Sequences: identify the starting string and then enumerate these positions in time proportional to the number of strings.

The number of binary strings of length k such that two 1′s are never adjacent in any string equals the k-th Fibonacci number. Further, these strings can be ordered to form a Gray code, which means that successive strings differ in only one position. For example, a Gray code for 3-bit strings is 100 101 001 000 010. The goal is to identify the starting string and then enumerate these positions in time proportional to the number of strings.

Working Computer Problem :discover an undamaged computer in as few queries as possible.

A room has n computers, less than half of which are damaged. It is possible to query a computer about the status of any computer. A damaged computer could give wrong answers. The goal is to discover an undamaged computer in as few queries as possible.