printable version
Quiz 1
[1]
[2]
[3]
[4]
[5]
[6]
[7]
Problem Q1.1.
[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;
}
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.
Problem Q1.2.
[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);
}
}
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.
Problem Q1.3.
[6 pts]
For the below recurrence, give its closed-form big-O bound.
Justify your answer, presumably by referencing the Master
Theorem.
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).
Problem Q1.4.
[6 pts]
Define what an adjacency matrix representation is for an undirected,
unweighted graph.
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.
Problem Q1.5.
[6 pts]
For the below binary tree,
give its preorder and postorder
traversals.
| preorder: | a b d e c |
| postorder: | d e b c a |
Problem Q1.6.
[8 pts]
How many valid topological
sorts are there for the below dag?
Justify your answer without resorting to listing the
orderings.
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.
Problem Q1.7.
[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.
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.
Home
Syllabus
Classwork