Home
Syllabus
Classwork
[8 pts] We can define the trailing zeroes of an integer k as the zeroes following the last 1 in k's binary representation; for example, the number 20 (represented in binary as 10100) has two trailing zeroes.
The below method returns the total number of trailing zeroes for all integers from 1 to its parameter n. Given the number 10, the program fragment would return 0 + 1 + 0 + 2 + 0 + 1 + 0 + 3 + 0 + 1 = 8.
Using big-O notation in terms of its parameter n, what is the running time of the below program fragment? Give the tightest and simplest bound you can, and justify your answer.
public static int countTrailingZeroes(int n) {
int total = 0;
for(int num = 1; num <= n; num++) {
for(int div = 2; num % div == 0; div *= 2) {
total++;
}
}
return total;
}
[8 pts]
The below method computes the largest distance between any two
points within a segment of the array pts, including all
array indices from start up to but excluding
end.
Write a recurrence relation T(n) that indicates the amount of time involved in the below program fragment; you do not need to reduce it to closed form. Justify your answer.
public static double biggestDist(Point[] pts, int start, int end) {
if(end - start <= 1) {
return 0;
} else {
int mid = (start + end) / 2;
double maxFirstHalf = biggestDist(pts, start, mid);
double maxSecondHalf = biggestDist(pts, mid, end);
double maxWithinHalf = Math.max(maxFirstHalf, maxSecondHalf);
double maxBetweenHalves = 0.0;
for(int i = start; i < mid; i++) {
for(int j = mid; j < end; j++) {
double d = pts[i].distance(pts[j]);
if(d > maxBetweenHalves) maxBetweenHalves = d;
}
}
return Math.max(maxWithinHalf, maxBetweenHalves);
}
}
[6 pts] For the below recurrence, give its closed-form big-O bound. Justify your answer, presumably by referencing the Master Theorem.
[6 pts] Define what an adjacency matrix representation is for an undirected, unweighted graph.
[6 pts] For the below binary tree, give its preorder and postorder traversals.
[8 pts] How many valid topological sorts are there for the below dag? Justify your answer without resorting to listing the orderings.
[8 pts] Suppose we have a dag represented using an adjacency list, and let m represent the number of edges in the dag. Describe an algorithm that determines a valid topological sort of the dag in O(m) time.
A partially acceptable answer is O(n log n). For this answer, you have only to observe that there are precisely n iterations of the outer loop, and for each iteration, we can have a maximum of log2 n iterations of the inner loop.
However, O(n) is a better solution. Here, we observe that for half of the numbers from 1 to n, there are no iterations of the inner loop. Half of the numbers see a first iteration of this inner loop, while a quarter see a second iteration, and an eight see a third iteration, and so on. Thus, the total number of iterations of this inner loop is at most n/2 + n/4 + n/8 + … = n.
When the array segment has just one element, the method takes
O(1) time, which we represent here using
C.
Outside the base case, we have two recursive calls, each on an
array of length n / 2, so each of the two
recursive calls take T(n / 2) time.
Outside the recursive calls, the program goes through
n / 2 iterations of the outer
i loop, and for each iteration there are
n / 2 iterations of the inner loop.
Thus, the method takes O(n²) time
outside the recursive invocations.
O(n² log n). Mapping the recurrence to Master Theorem, we have a value for a of 4, for b of 2, and for d of 2. (We use 2 for d since 0.5 n² + 2 n 13 = O(n²).) Since logb a is 2, which matches d, the answer according to the Master Theorem is O(nd log n).
The adjacency matrix is an n × n matrix of 0's and 1's, where n is the number of vertices in the graph. Matrix entry (i, j) is 1 if an edge connects vertices i and j in the graph.
| preorder: | a b d e c |
| postorder: | d e b c a |
There are 18. In each ordering, A, B, E, and F must precede C, with A before B and E before F. Either A will come first or E will come first. If A comes first, then B must be either before E, between E and F, or after F. If E comes first, then F must be either before A, between A and B, or after B. Thus, there are 6 ways to order these four vertices; and after those four vertices will be C.
We must also place D, G, and H after C. G must precede H, but D might come before G, between G and H, or after H, for a total of three configurations for each of the six possible orderings of A/B/E/F. Thus the total number of orderings is 3 ⋅ 6 = 18.
Create an empty linked list, and then perform a depth-first search on
the dag. At the end of the recursive function explore,
add the explored node at the front of the linked list. Following
completion of the depth-first search, the linked list will
contain the vertices in topological order.