Home
Syllabus
Classwork
printable version
Section J14:
[1]
[2]
Section J21:
[1]
[2]
[3]
[4]
[5]
[6]
[7]
[8]
[9]
[10]
Section J23:
[1]
Section J26:
[1]
[2]
Section J30:
[1]
[2]
[3]
Section F2:
[1]
[2]
[3]
[4]
Section F4:
[1]
[2]
What does it mean for a problem (like Traveling Salesman or Knapsack) to be NP-hard?
If somebody were to discover some algorithm for one NP-hard problem that takes only polynomial time (i.e., O(np) for some constant p), then that would imply polynomial-time algorithms for all other NP-hard problems.
A cryptarithm is a popular mathematical puzzle where one is to find an assignment of digits to symbols. One popular example is SEND + MORE = MONEY, for which the solution is to map S to 9, E to 5, N to 6, and so on, to arrive at the correct summation 9567 + 1085 = 10652.
Below is the outline of some Python code for solving addition cryptarithms using exhaustive search. Suggest two pruning techniques.
def solve(cryptarithm, unmappedLetters, letterMap):
if len(unmappedLetters) == 0:
# confirm that letterMap is a correct solution to cryptarithm
else:
first = unmappedLetters[0] # get first unmapped letter
others = unmappedLetters[1:] # get list of all remaining letters
for i in [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]:
letterMap[first] = i
solve(cryptarithm, others, letterMap)
If first is the first digit of any number in cryptarithm, make sure we do not consider 0 as a possible value for that letter.
Before the i loop, check each column of the cryptarithm. If all three digits are already mapped for the column, then verify that the first two digits will sum to the third digit (or 10 plus it), taking into account the possibility that there may be a carry from the following column.
If there is a requirement that each letter map to a different digit, then our for loop could iterate only through those i that aren't already represented.
Write the following Big-O bounds in order, from smallest to largest.
O(1), O((log n)²), O(n0.0001), O(n log n), O(n sqrt(n)), O(n²), O(1.01n)
Using big-O notation in terms of the parameter n, how much time does the following method take? Give the tightest possible bound, and explain your answer.
public static int mystery(int n) {
int count = 0;
int cur = 1;
while(cur < n) {
count++;
cur = cur * 2;
}
return cur;
}
It takes O(log n) time. Since cur doubles with each
iteration of the loop, after going through the loop k times,
cur will be 2k. After going through the loop log2 n
times, cur will be
2log2 n,
or n, and we will stop.
Thus, there are O(log n) iterations of the loop; since each iteration
takes O(1) time, the total time consumed is
O(log n).
The below functions both determine
mn without using
Math.pow.
a.
int pow(int m, int n) {
int ret = 1;
for(int i = 0; i < n; i++) {
ret *= m;
}
return ret;
}
| b.
int pow(int m, int n) {
int ret = 1;
int k = m;
int i = n;
while(i > 0) {
if(i % 2 == 1) ret *= k;
k *= k;
i /= 2;
}
return ret;
}
|
Using big-O notation in terms of n, how much time
does each take?
Provide the tightest bound that you can.
| a. | O(n) |
| b. | O(log n) |
Consider the following method, which finds and removes all duplicated numbers in the parameter array. Note that the method has three loops.
public static int removeDuplicates(char[] arr) {
int len = arr.length;
int i = 0; // index of current item to find
while(i < len) {
int j; // will be index of duplicate of arr[i]
for(j = i + 1; j < len; j++) {
if(arr[i] == arr[j]) break;
}
if(j == len) { // no duplicate of arr[i] found; go to next i
i++;
} else { // duplicate found; shift array over arr[j]
for(int k = j + 1; k < len; k++) {
arr[k - 1] = arr[k];
}
len--;
arr[len] = 0;
}
}
return len;
}
Let n represent the length of arr.
In terms of n, how much time does
the above method take? Use Big-O notation to express your answer, and
provide the tightest bound that you can.
In terms of the variable n, how much time does the below
program fragment take?
Give your answer using Big-O notation, and give the
tightest and simplest bound possible. Justify your answer.
int i = 1;
int j = 0;
while(i < n) {
j++;
if(j == i) {
i++;
j = 0;
}
}
It takes O(n²) time. We go through the
loop once when i is 0, twice when i is
1, three times when i is 2, three times when
i is 2, and so on. We stop by the time i reaches
n; so the question is: What is
1 + 2 + 3 + … + n?
This summation is
n (n + 1) / 2
= (1/2) n² + (1/2) n
= O(n²).
Consider the following method.
public static int mystery(int n) {
int j = 0;
for(int i = 0; j <= n; i++) {
j += 2 * i + 1;
}
return i - 1;
}
In terms of the input n, what is the tightest big-O bound you can give on the running time of the above method? Describe the reasoning underlying your answer.
It takes O(sqrt(n)) time. In fact, the function computes the largest integer that is at most sqrt(n). You can see that it does this by observing that the loop maintains an invariant of j = i². (After all, if j = i² at the beginning of an iteration, then during the iteration, j becomes j + 2 i + 1 = i² + 2 i + 1 = (i + 1)².) Since i goes up by 1 each iteration, and it stops once it passes sqrt(n), there are at most 1 + sqrt(n) iterations.
(You may be tempted to use reasoning that is less formal than the above, perhaps pointing to examples that you have run. This is only a partial answer, as the reasoning is not mathematically sound. But it at least provides some evidence.)
Using big-O notation in terms of its parameter n, what is the running time of the below program fragment? Give the smallest bound that you can, and justify your answer.
int total = 0;
for(int i = 1; i < n; i++) {
int k = 1;
while(k < i) { k = k + k; }
while(k > 1) { k /= 2; total++; }
}
System.out.println(total);
O(n log n): For each i value, each inner loop has approximately log2 i iterations — the first one starting at 1 and doubling until we reach i, and the second one halving until we reach 1 again. Thus, the total time per iteration of the outer loop is O(log i + log i) = O(2 log i) = O(log i) = O(log n). (The last step comes from the fact that i ≤ n.) The outer loop has n iterations, so the total time is O(n log n).
Consider the following method that finds the smallest factor above 1 for a given number n, without using any division or multiplication. (A factor for a number n is an integer that divides into n exactly. For example, the factors of 45 are 1, 3, 5, 9, 15, and 45.)
public static int findFactor(int n) {
int i = 1;
int j = n - 1;
int p = j; // invariant: p = i * j
while(p != n && i < j) {
i++; p += j;
while(p > n) { j--; p -= i; }
}
return p == n ? i : n;
}
How much time does this method take? Give your answer using Big-O notation in terms of n, and give the tightest and simplest bound possible. Justify your answer.
An answer of O(n sqrt(n)) would be partially acceptable. The reasoning: As we go through the loop, j always decreases to a number less than n / i, and so once i reaches sqrt(n), n / i will be less than that, and the method stops. Thus, there are at most sqrt(n) iterations of the outer loop. For each iteration, j may have to decrease significantly, but it won't decrease for more than n iterations, so O(n sqrt(n)) is a valid answer.
It is possible, however, to derive a better bound by observing that the total number of iterations of inner loop, across the entire method execution, will be less than n, since j starts at n − 1, decrements each time through the inner loop, and stops once it reaches sqrt(n). Thus, the total time spent on the inner loop over the entire execution is O(n), and the total time spent on the outer loop (but not including time for the inner loop) is O(sqrt(n)); thus, the total time overall is O(sqrt(n) + n) = O(n).
Using big-O notation in terms of its parameter n, what is the running time of the below program fragment? Give the smallest bound that you can, and justify your answer.
int total = 0;
for(int i = 1; i < n; i *= 2) {
for(int j = i; j < 2 * i; j++) {
total += j;
}
}
System.out.println(total);
A first-cut solution, which would be partially acceptable,
would be O(n log n): The
reasoning would be that the outer loop has log2 n iterations since
i starts at 1 and doubles with each iteration until it
reaches n, and log2 n doublings will accomplish this,
while the inner loop has at most 2 n iterations, since
j starts at i, which is at least 1, and stops
at 2 i, which is less than 2 n since i is less
than n. Thus we have
O((log2 n) 2 n)
= O(n log n)
time.
An answer of O(n) is also possible. The reasoning is this:
The inner loop will execute only once the first time through the
outer loop (when i is 1),
twice on the second outer iteration (when i is 2),
four times on the third outer iteration (when i is 4),
and so on. Thus, the total number of iterations of the inner
loop, across all iterations of the outer loop,
is
1 + 2 + 4 + 8 + … + n
= 2 n - 1,
and so the total time
spent on the inner loop is O(n). If we ignore the inner loop,
the total time spent on the outer loop is O(log n),
so the total time overall is
O(n + log n)
= O(n).
The following method determines whether the parameter array of
booleans contains at least two true values.
In terms of n, the length of the parameter array, how much time does
this method take? Give your answer using Big-O notation, and give the
tightest and simplest bound possible. Justify your
answer.
public static int findTruePair(boolean[] flags) {
int n = flags.length;
for(int i = 0; i < n; i++) {
if(flags[i]) {
for(int j = i + 1; j < n; j++) {
if(flags[j]) return true;
}
}
}
return false;
}
O(n).
If flags contains
no true values, then the inner loop will never
execute, so every iteration of the outer loop takes
O(1) time, for a total of O(n)
time.
If flags contains
one true value, then the inner loop will be
reached only once, adding an additional
O(n)
to the above, for a total still of O(n).
And if flags contains two or more true
values, then the inner loop will still be reached only once
(since the one time the inner loop is executed, the method will
return), for a total of
O(n) time. So in any of these cases, the
amount of time is
O(n).
In terms of n, the parameter, write a recurrence representing the amount of time taken by the below recursive algorithm. You can use variables C and D to represent constants that will vary from computer to computer.
def recur(n):
if n <= 1:
return n
else:
return recur(n - 1) + recur(n / 2)
| T(1) | = C |
| T(n) | = T(n − 1) + T(n / 2) + D |
For each of the following recurrences, give its big-O bound in closed form.
| a. | T(1) | = 6 |
| T(n) | = 8 T(n / 2) + n2.5 | |
| b. | T(1) | = 10 |
| T(n) | = 9 T(n / 3) + n2.2 | |
| c. | T(1) | = 3 |
| T(n) | = 8 T(n / 4) + n1.5 |
| a. | O(n3) |
| b. | O(n2.2) |
| c. | O(n1.5 log n) |
In terms of n, the length of the list parameter
nums, write a recurrence representing the amount of time taken by
the below recursive algorithm. You can use variables
C and D to represent constants that will
vary from computer to computer.
def recur(nums):
if len(nums) == 1:
return nums[0]
else:
i = nums / 4
j = nums / 2
k = 3 * nums / 4
return recur(nums[0:j]) - recur(nums[i:k]) + recur(nums[j:len(nums)])
(Recall that nums[a:b] computes and returns a
list containing the elements from nums indexed a through
b − 1. The
amount of time taken to construct this list is proportional to
b − a.)
| T(1) | = C |
| T(n) | = 3 T(n / 2) + D ⋅ n |
Suppose I were to roll a fair six-sided die, of which four faces are labeled 3, and the other two are labeled 11 and 1. What is the expected value of a single die roll?
Suppose we have a hat containing numbers, and we know that drawing one number out of the hat has an expected value of 3. What is the expected value of drawing two numbers out of the hat and adding them together? What about multiplying them?
We know that the expected value of a sum of two events is the same as the sum of the expected values for each event; thus, the expected sum is 6. There is not a similar rule for multiplying, so we don't have enough information to compute the expected value of multiplying the two draws together. (It may be that the hat contains just two numbers, both 3, in which case the outcome will be 9. But it may also be that the hat contains just 2 and 4, in which the outcome will be 8.)
Suppose we have an array of numbers, of which half of the numbers are all equal to one another, and the other half are all different from one another. We want to identify the number that occurs in half of the array elements. Consider the following two algorithms.
for i in range(len(array)):
for j in range(i):
if array[i] == array[j]:
return array[i]
|
while True:
i = random.randrange(0, len(array))
j = random.randrange(0, len(array))
if i != j and array[i] == array[j]:
return array[i]
|
For each algorithm, what is the deterministic running time? What is the expected running time? Express your answers using big-O notation in terms of n, the length of the array.
The first algorithm has a deterministic running time of O(n²), since it could be that the all the equal numbers are bunched at the end of the array. We'll go through the inner loop 0 times, then 1 time, then 2 times, and so on up to n / 2 times; this summation is O(n²).
The expected running time for the first algorithm is the same, for exactly the same reason. [It's important to remember that when we're talking about expected running time, we're still interested in the worst-case scenario. If the algorithm doesn't involve any randomness, then the expected running time is the same as the deterministic running time.]
The second algorithm has no bound on the deterministic running time, since it could be that we are extremely unlucky and go through the loop indefinitely, never happening to choose two numbers that are equal to one another.
However its expected running time is O(1), since there's a 1/4 chance with each iteration that we happen to choose two of the equal numbers, and so the expected number of iterations before this happens is 4.
Write the preorder and postorder traversals of the below tree.
| preorder: | a b d e h c f i g |
| postorder: | d h e b i f g c a |
For the below graph, compute the pre and post number for each vertex of the graph, using alphabetical order to determine the order in which vertices are explored.
A: 0, 11
B: 2, 3
C: 1, 10
D: 5, 6
E: 7, 8
F: 4, 9
Suppose we know we have completed a depth-first search of a graph and we've identified pre and post numbers for each vertex. We know u's pre and post numbers are 6 and 9, and we know v's numbers are 2 and 4. What can we conclude about the relationship between u and v in the depth-first search tree?
Since neither interval [6,9] and [2,4] is contained in the other, one cannot be an ancestor of the other. In fact, since there's just one number 5 between v's post number and u's pre number, it must be that v's parent in the tree must be a sibling of u. (If you prefer, u must be v's aunt or uncle.)
We saw that in performing a depth-first search on a directed graph, each edge of the graph will fall into one of four categories. Name and describe each of these categories.
A tree edge is one that is traversed in the course of performing the recursion.
A back edge is one that is ignored because its destination is an ancestor of the source vertex.
A cross edge is one that is ignored because its destination was visited prior to visiting the source vertex, but the destination is not an ancestor of the source vertex.
A forward edge is one that is ignored because its destination was previously visited in the course of visiting the source vertex's other neighbors.
What is a dag?
A dag is a directed acyclic graph. That is, it is a directed graph that contains no cycles.
Give a valid topological sort of the below dag.
Any combination of the six letters is OK, as long as CFED appears as a subsequence and B appears before both A and E. One solution is CBAFED.
