A: Solution meets the stated requirements and is completely correct. Presentation is clear, confident, and concise.
B: The main idea of the solution is correct, and the presentation was fairly clear. There may be a few small mistakes in the solution, or some faltering or missteps in the explanation.
C: The solution is acceptable, but there are significant flaws or differences from the stated requirements. Group members have difficulty explaining or analyzing their proposed solution.
D: Group members fail to present a solution that correctly solves the problem. However, there is clear evidence of significant work and progess towards a solution.
F: Little to no evidence of progress towards understanding the problem or producing a correct solution.
Problem  Final assessment 
1  
2  
3  
4 
Instructions: Review the course honor policy: you may not use any human sources outside your group, and must document anything you used that's not on the course webpage.
This cover sheet must be the front page of what you hand in. Use separate paper for the your written solutions outline and make sure they are neatly done and in order. Staple the entire packet together.
So here's your task: given a list of numbers `A` of length $n$, find all numbers `x` that occur more than $n/3$ times in $A$. These are the popular numbers.
Note that there can be 0, 1, or 2 popular numbers. (It's impossible to have three things that all occur *more* than onethird of the time.)
Algorithm: popular_basic(A) Input : array A of n numbers Output: list of the "popular numbers" apop = [] for i from 0 to n1 do if count(A,A[i],0,n1) > n/3 if A[i] not in apop apop.append(A[i]); Algorithm: count(A,x,i,j) Input : array A of numbers, a value x and a range i..j in A Output: number of times x occurs in A[i],...,A[j] c = 0 for each a in A[i],...A[j] do if a == x c = c+1 return cWhat's the running time of this `popular_basic` algorithm, in terms of $n$?
Algorithm: popular_better(A,i,j) Input : array A, and indices i <= j that define an nelement range in A Output: list of the "popular numbers" apop = [] if i == j apop.append(A[i]) else mid = (i+j)/2, n = j  i + 1 ← note: n is the number of elements in A[i],...,A[j] L = popular_better(A,i,m) for each x in L do if count(A,x,i,j) > n/3 ← note: this is the original range i..j! apop.append(x) U = popular_better(A,m+1,j) for each x in U do if x not in apop and count(A,x,i,j) > n/3 ← note: this is the original range i..j! apop.append(x) return apopConvince me that this algorithm is still correct, i.e., it always returns all the popular elements in `A`.
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 tugofwar, 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$:
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 w1An 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 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)$.
Analyze the number of contests that your algorithm performs in the worst case (NOT the number of primitive operations, just the number of contests).
All that you know about the DAN cryptosystem is that it consists of four functions, KEYGEN, ENCRYPT, DECRYPT, and CRACK, which are the best ways the creator of DAN (me!) has come up with to do those four tasks. All of these functions have a running time which depends on the key length $k$ as follows:
You might need to do some outside research on things like the relative speed of supercomputers, cell phones, and laptops, or the projected costs of computing in the future. That's great, but be sure to cite any sources that you used.
Feel free to be somewhat speculative, but don't expect to get credit for "cute" answers such as "key length 0, because I already installed a keylogger" or "tell the government that DAN is not properly vetted and shouldn't be used yet". You have to come up with plausible, numerical recommendations!
(d (i,j) val)
 where the meaning
is that cell (i,j) contains data val, or
(f (i,j) ((i1,j1),....,(ik,jk)) f(x1,x2,...,xk))
 where the meaning is that cell (i,j) is the result of a
calculation evaluating function f with argument x1 coming
from cell (i1,j1), x2 coming from cell (i2,j2), etc.
Example description  Example rendering as spreadsheet  
(f (0,2) ((0,0),(0,1)) average) (d (1,1) 23) (f (1,2) ((1,1),(0,2)) sum) (d (0,0) 14) (f (2,2) ((0,2)(1,2)) average) (d (0,1) 16) 

(f ((8,5),(8,6),(8,7)) sum)but cell (8,7) is empty, then we can't evaluate the spreadsheet completely. More perniciously, we can't have a situation where cell (i1,j1) requires cell (i2,j2)'s value to compute, but cell (i2,j2) requires (i1,j1)'s value to compute. If we tried to evaluate a spreadsheet with a cyclic dependency like this, we'd end up in an infinite loop. Give an algorithm for determining whether a spreadsheet (described as shown in the example above) has a cyclic dependency that would cause it to be unevaluatable ... which is a word I just made up.