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.

implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise.

Animal behavior researchers would like to get information on animal movements in a valley. They have placed N motion sensors along a straight line crossing the valley at various heights. For 0 <= i <= N-1, the i-th sensor's height is h_i (0 <= h_i <= 1 000 000 000). No two sensors are on the same height.
Since the line is on a valley, the heights of sensors satisfy these constraints:

• there is an integer k (0 <= k <= N-1), such that the k-th sensor has the minimum height,
• for all 0 <= i < k, h_i > h_i+1, and
• for all k <= i < N-1, h_i < h_i+1.

However, because the sensor installation team forgot to measure the sensors' heights, the value of k, and all the heights h_i's are not known.
You would like to find if there is a sensor at height X. This seems to be hopelessly impossible, but you recall that each sensor has a height meter and can report its height. To minimize the power usage, you would like to make only a small number of height queries.

Implement

You have to implement procedure find(N,X) that returns 1 if there exists a sensor at height X and returns 0 otherwise. Your procedure can call a procedure query(i) to get h_i. However, you can make at most 50 calls, for each run of procedure find.
Note: In a single run, the sample grader, provided with the prototype, may perform many calls to find in one run. While the sample grader uses the same heights for all calls, the real grader may use different heights between each call to procedure find. Therefore, you should not assume that two different calls to procedure find share the same height information.

Example

Suppose that N=4 and the height of each sensor is:

sensor	height
0	10
1	7
2	9
3	15

Note that in this case, k=1. The following are the return values from procedure query:

calls	returns
query(0)	10
query(1)	7
query(2)	9
query(3)	15

The correct implementation of procedure find, when called by the grader, should return as in the following table.

calls	returns
find(4,10)	1
find(4,2)	0
find(4,9)	1
find(4,15)	1
find(4,100)	0