Tag Archives: cs 212

CS 6212 – Practice Final

[#cs6212gwu] I have heard a few requests for the answers to the “practice final”. However, I do not provide answers to the practice final, as that allows me to use the practice final as the real final in case I don’t get any time to make one. (If I also gave answers, then I would really NEED to make a new final, as opposed to merely WANT to make a new final.)

The good news is there is absolutely no constraints on how you can obtain answers to the practice final. You can call Sergey Brin and Larry Page (they have this utility called Google, which I hear works kinda ok.) Also, you can call anyone physically (using a cell phone with a voice plan). You can also visit friends and ask them in person. You can put this on Craigslist and offer a $ reward. So, in short, there are no restrictions. Nada. Zilch. Cipher. Nul.

Wait, actually, there is one constraint. You just can’t ask ME! (As the politicians would say, I didn’t lie or make a mistake, I “misspoke”. Alternatively, I can have my office issue a clarification that, “that was not meant to be a factual statement.”)

And that is all I have to say about that.

Finding the smallest and the largest number from an unsorted array

#cs6212gwu – Spring 2011 – HW1 – Q4

This is a common puzzle.  Given an array of n sorted numbers, how to find BOTH the minimum and the maximum using as few comparisons as possible.  If only the minimum (or the maximum) is to be found, then that can be done by using n-1 comparisons.  So, the first algorithm could be to find the minimum, and then to find the maximum from the remaining, in a total of (n-1) + (n-2) comparisons.

A better algorithm is that we first compare pairs of numbers (in n/2) comparisons, and collect n/2 “winners” and n/2 “losers”.  Then, find the maximum from the winners, in n/2 – 1 comparisons, and the minimum from the losers in n/2 – 1. That is a total of 3n/2 – 2 comparisons.

Finding min and max in array using pairwise comparisons

So much is straightforward. Much more interesting question arises, if we ask:

Is the algorithm presented above optimal?  In other words, can we say that any algorithm that is based on comparisons will need at least 3n/2 – 2 comparisons, regardless of in which sequence it does the comparisons.

We want to prove that for any given algorithm (let us call it algorithm A), there is a sequence of numbers for which A takes at least 3n/-2 comparisons to find both the maximum and minimum numbers.  Such a proof can be constructed based on adversary (or game theoretic approach); essentially saying that an adversary will actively work against the algorithm to maximize the number of comparisons needed, but with the condition that the adversary cannot contradict itself.  For example, adversary cannot say a > b, b > c and then also say c > a.

Adversary thinks in terms of numbers in 4 buckets:

  • Bucket Q – contains numbers that have never been compared to anything yet.
  • Bucket W – Contains numbers that have only won games that they have played.  So, they are candidates for being the maximum.
  • Bucket L – Contains numbers that have only lost games that they have played.  So, they are candidates for being the minimum.
  • Bucket X – Contains numbers that have both won and lost games they have played.  So, they are not candidates for being the minimum or the maximum.

Min Max - 4 buckets of numbers

These buckets start with the following state when the algorithm A starts:

Bucket Q: n numbers, Buckets W, L, X: 0 numbers each.

Finally, when algorithm A finishes, this must be the state:

Bucket Q: 0 numbers; Bucket W: 1 number; Bucket L: 1 number; Bucket X: n-2 numbers

Adversary goes by the following rules for creating outcomes of comparisons:

  • C1: When comparing two numbers in bucket Q – one number will go into W bucket, and one number will go into L bucket.  (Net change: -2, +1, +1, 0)
  • C2: When comparing a number from W bucket to a number from Q bucket, the number  from W will win and will remain in W.  Number from Q bucket will go into L.  (Net change -1,0,+1,0)
  • C3: When comparing a number from L bucket to a number from Q bucket, the number  from L will lose and will remain in L.  Number from Q bucket will go into W.  (Net change -1,+1,0,0)
  • C4: When comparing a number from W bucket to a number from X bucket, the number  from W will win and will remain in W.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
  • C5: When comparing a number from L bucket to a number from X bucket, the number  from L will lose and will remain in L.  Number from X bucket will remain in X.  (Net change 0,0,0,0)
  • C6: When comparing a number from W bucket to a number from L bucket, the number  from L will lose and will remain in L.  Number from W bucket will remain in W.  (Net change 0,0,0,0)
  • C7: When comparing two numbers from W bucket, one will remain in W, and one will go into X.  (Net change, 0, -1, 0, +1)
  • C8: When comparing two numbers from L bucket, one will remain in L, and one will go into X.  (Net change, 0, 0, -1, +1)

These rules ensure the following points:

  • Maximum of 2 numbers can be removed from Q bucket during each comparison, and during this comparison, no number goes into the X bucket.   [This happens in comparison C1.]
  • During each comparison, maximum of 1 number can enter the X bucket.  [This happens in comparisons C7, C8, and in those comparisons, there is no change in the size of the Q bucket.]

So, we observe that we need n-2 comparisons (of type C7/C8) simply to fill up the X bucket (we need n-2 numbers there by the end).  Further, since those comparisons do not involve Q bucket, we need at least additional n/2 comparisons just to empty out the Q bucket (it starts with n numbers and needs to have 0 numbers).  So, in total, we need to make at least 3n/2 – 2 comparisons just to make sure Q and X buckets have the desired state before algorithm A can draw its conclusions.

QED.

Why do we study algorithms?

Algorithms_BookAs I get ready to teach another session of CS 6212 (Design and Analysis of Algorithms – Graduate – earlier used to be known as CS 212) at GWU, question arises one more time – why do we study algorithms at all?

Here are some problems that arise all the time, and hopefully you can see an analogy between these problems and similar ones you have seen elsewhere.

  1. You have  an address book consisting of 5 million records.  Let us assume structure is very simple – first name, last name, phone number and company name.  You can search on any of these fields, and can search partially using “begins with” syntax. For example, you can search for – first name is like “Ron…”.  Another search can be – phone number like “202…”.  You want the search to be super super fast, and cannot afford to make any database calls.  (Btw, the telephone number is a string, not a number, right?)  To test the effectiveness of your program, I will give it about 200 searches (some on first name, some on last name, some on telephone number, some on company name), and take the average response time.
  2. You have a network topology (setup of nodes and interconnecting edges), and would like to know if deletion of a single node is going to leave the topology disconnected.
  3. Looking for a text pattern in a big file.  Say you have a text file that is about 10 M.  You can be looking for a text “designed to efficiently support unlimited number of subscribers” or text “flexible error correction results in more efficient use of spectrum”, or something else.  How can we make this search super efficient?
  4. Your customers are scattered across 100 cities, and you know demand from each of the 100 cities and distances between cities.  You would like to open 3 warehouses (distribution centers).  Where do you locate the warehouses?
  5. There is a competition for the best “Go” program.  The first prize is $5000.  You need the money.
  6. You are designing your company’s marketing strategy, as defined here.

If you already know the algorithms and the techniques for these problems that is a very good start.  Otherwise, you should consider taking some formal classes in a school convenient to you.  Or, continue your informal learning in the school of life.  I will be posting some more hints and pointers in the comments section later.

[If you would like to follow the CS6212 related tweets, you can follow using twitter hashtag #cs6212gwu]