This is the archived website of SI 335 from the Spring 2013 semester. Feel free to browse around; you may also find more recent offerings at my teaching page.
We saw in class that MergeSort takes \(\Theta(n\log n)\) time in the worst case. Unfortunately, MergeSort also takes \(\Theta(n\log n)\) time in the best case. This is worse than some sorting algorithms, such as InsertionSort, that only take \(\Theta(n)\) time in the best case.
Run through your improved algorithm for the following array:
[81, 66, 76, 16, 40, 89, 95]
Should everyone use your algorithm all the time instead of the normal MergeSort? Why or why not?
There are n Mids trying out for the varsity tug-of-war team. Some of them are strong and some of them are weak. For simplicity, assume that all the strong Mids have exactly the same strength, as do all the weak Mids. You can also assume that there is at least one strong Mid and at least one weak Mid. (In particular, n must be at least two.)
Your task is to determine who the strong Mids are, to decide who will be on the team. And the only tool you have to determine who is strong and weak is running contests. A contest involves pitting some Mids against some others in a tug-of-war, and the outcome can be either that one side wins, or the other side wins, or they tie. This pseudocode might help clarify:
# Calling this function represents a single contest. def winner(group1, group2): if group1 wins: return group1 elif group2 wins: return group2 else: return 'tie'
There can be any number of Mids in any contest, but it should always be the same number on each side of the contest. The side with more strong Mids (or, equivalently, with fewer weak Mids) wins.
For example, here is an algorithm for \(n=3\):
Input: 3 Mids called
M0,M1,M2Output: A list of the strong Mids
def strongOf3(M0, M1, M2): w1 = winner({M0}, {M1}) if w1 == 'tie': if winner({M1}, {M2}) == {M1}: return {M0, M1} else: return {M2} else: if winner(w1, {M2}) == 'tie': return w1 + {M2} else: return w1
An here's an algorithm for \(n=4\):
def strongOf4(M0, M1, M2, M3): w1 = winner({M0}, {M1}) w2 = winner({M2}, {M3}) if w1 == 'tie' and w2 == 'tie': return winner({M0,M1}, {M2,M3}) elif w1 == 'tie': # w1 is a tie, but w2 is not if winner({M0}, w2) == 'tie': return {M0, M1} + w2 else: return w2 elif w2 == 'tie': # the opposite here; w1 is not a tie if winner({M2}, w1) == 'tie': return w1 + {M2, M3} else: return w1 else: return w1 + w2
State the number of contests performed by strongOf3 and by strongOf4 in each of their worst cases.
Give a lower bound on the number of contests required to determine who the weak Mids are for an input of size n, in the worst case. (Hint: follow the example of the lower bound for sorting from class, and for search in the DQ that followed!)
State your exact lower bound as a function of n, showing all your work. Then state what the asymptotic big-\(\Omega\) bound is that results, simplified as much as possible.
For example of what I'm asking for, in class we showed that sorting requires at least \(\lg (n!)\) comparisons (the exact bound), which is \(\Omega(n\log n)\).
Give an algorithm for any n that determines who the strong Mids are. In describing your algorithms, you can call the Mids by their number like an array: M[0], M[1], ..., M[n-1].
Analyze the number of contests that your algorithm performs in the worst case (NOT the number of primitive operations, just the number of contests).
Is your algorithm asymptotically optimal? Say why or why not. (Hint: there is an asymptotically optimal algorithm for this problem!)
Bonus: Determine the exact number of contests your algorithm performs, for \(n=1,2,3,\ldots,10\). Then determine the exact number of contests required by your lower bound from part (b). Try to make your algorithm faster or your lower bound higher so that these match up as much as possible.
Ultra bonus: Either develop an algorithm so that the exact number of contests matches the lower bound for all sizes n, or prove that no such algorithm exists.
There is a website called secretbook.com that offers free accounts to anyone in the world, and allows its members to send secret (encrypted) messages to each other. The way it works is, every user gets assigned a public/private key pair when they sign up for their free account, and the website publishes everybody's public key along with their username and public profile. Then any member can post encrypted messages and files with anyone else's public key, so only that person can read the message.
This website is used by all sorts of people, including political dissidents, underage kids, hackers, professors, and illegal file-sharers. The U.S. government has requested the founders of secretbook.com to let them read all the messages, presumably so they can prosecute people sharing illegal things, but the website owners have refused the request.
Here's the problem: you notice that every public key issued by the website has exactly the same modulus n. The website owners thought this was OK, since they only issue the public key \((e,n)\) and private key \((d,n)\) to its users, never the prime factors p and q of n or any other information. But you notice there is a vulnerability there...
What is the vulnerability? Describe how an attacker could do something that shouldn't be allowed, more easily than he would be able to do otherwise. Say exactly what can be done, and how easy it would be to do it.
Note: For full credit, there is an attack that can be performed in polynomial-time against this system, if you are clever enough! But you will still get most of the credit for any vulnerability you find, even if it would still require a great deal of computing power.
Regardless of whether you figure out the vulnerability for part (a), take my word that there is one that would allow you to read anyone's encrypted messages on the site. And you seem to have been the first person to notice this!
Now the question is what to do with this information. You have a few options:
Keep in mind that if you tell anyone, it leaves the possibility that they will use this information in a way that you find unethical. For example, some of the scientists that worked on the Manhattan project were not happy that their work was used to develop a weapon of mass destruction.
Assignment: Write a short essay stating what you would do, and why. I'm looking for about 300-500 words with some good supporting arguments for your position. You can draw on historical background, your own ethical or moral reasoning, technical considerations, or (even better!) all of these. You will be judged mostly on the quality of your arguments, but also on standard things like writing style, spelling, and grammar.
Keep in mind that there is not a single right answer — that's why it's called a dilemma! And no weaseling out either, like saying "if such-and-such then I would do X, but otherwise Y, or maybe Z". Based on the information provided in this made-up scenario, make a decision and justify it.