Stuff on recurrences and graphs

[dionysus]

Hi guys,

 

I think the group's gone silent ever since the Nov 8 test takers are done! We, Dec. 13 test takers should start preparing and putting our thoughts on the forum. My preparation is all right, although I'm a bit nervous since there is stuff that I haven't looked at in two years (I've been working for a year now). And it seems impossible to cover everything in the three weeks left now. I'm basically preparing through this forum and then some of my old college text books.

 

I thought I'd include some stuff on recurrences.

 

Several times, the running time of an algorithm can be expressed as a combination of a base case (running time when the problem instance is really small), and a bunch of recursive calls to smaller problems. The most general form of a recurrence, for our purpose of running time is:

 

T(n) = a T(n / b) + f(n).

 

Several times, it is asked what is the running time of this in terms of T(n) = O(g(n)) then what is g(n).

 

Here is a general rule that may help:

 

1. If n^{log_b a} = Theta (f(n)), then T(n) = Theta (n^{log_b a} lg n)

2. If n^{log_b a} > Theta (f(n)), then T(n) = Theta (n^{log_b a})

(same as saying that n^{log_b a} = Omega (f(n)))

3. If n^{log_b a}

(same as saying that n^{log_b a} = Oh (f(n)).

 

So essentially, whenever you see a recurrence of the kind, check whether f(n) is greater than n^{log_b a}. Remember that the greater one counts! So if it is greater (asymptotically), then choose the greater one. If both happen to be same, that is they are Theta equivalent, then well, pick any one up and add a log n to it and thats the answer to your recurrence!

 

Some graph definitions:

 

An undirected graph is connected if every pair of vertices is connected by a path. The connected components of a graph are the equivalence class of vertices under the "is reachable from" relation. So, two vertices a and b are in the same connected component if and only if "a is reachable from b" (note that for undirected graph, this translates also into "b is reachable from a"). Therefore, the "is reachable from" relation is an equivalence relation ("a is reachable from a", if "a is reachable from b, then b is reachable from a" and "if a is reachable from b" and "b is reachable from c" then "a is reachable from c".). Therefore, the "is reachable from" relation partitions the set of vertices into equivalence classes called the connected components of the graph.

 

A similar notion is defined for directed graphs and is a little more tricky. Under the directed graphs, such components are called strongly connected components and two vertices are in the same strongly connected component if and only if both can reach each other. This is again an equivalence relation and divides the graph into equivalence classes.

 

Thats it for now guys - but lets start our preparation once again. I recommend going over each question in the practice set, maybe 10 at a time. Should I post the first then, with my thoughts on them now?

 

 

[AlbaLed]

dionysus,

 

I would recommend you go over all the threads posted in this forum, most of them contain good gre-style questions scatered from all the fields. I think almost all ("hard") practice questions are covered, and there is a lot of techniques for solving problems. My recommendation would be read thru the forum and study the topics covered in the threads, this will give you a full review of what you need to study, don't forget to follow the links posted thruought the forum and in the "sticky" threads they are REALLY helpful

 

GOOD LUCK TO you AND ALL DEC 13 CS-GRE-TAKERS

[Sanju]

Hi Dionysus,

As albaled has said most of the practice questions have been covered. But I think we could look at all the questions once again in order, just to make sure we have got the concept behind every question and if there are any new shortcuts.

 

So why don't you go ahead and post the answers/shortcuts to the first 10 questions. I will take up the next 10 .

 

Sanju