1. 18pts,
graded by Liang
The most straightforward way is to prove when
N->infinity, (logN)^k / N goes to 0. As long as you pointed this out and
show briefly how to do it, I gave you full credit.
(logN)^k
k(logN)^(k-1)/N
k!
lim --------------- = lim---------------------
= ...= lim -------- = 0
N->inf
N
N->inf
1
N->inf N
so (logN)^k = o(N).
an induction proof doesnĄ¯t work here, especially you
canĄ¯t do induction on k which is a constant and insignificant to N since N is
the variable here.
4. 24pts,
graded by Liang
recursive:
draw_ruler(int left, int right, int start_height,
int num_subdivisions)
{
draw_mark(left,
start_height);
draw_mark(right,
start_height);
draw_ruler_helper(left,
right, start_height-1, num_subdivisions);
}
draw_ruler_helper(int
left,int right, int start_height, int num_subdivisions)
{
if
(num_subdivisions<1)
return;
int
mid = (left+right)/2;
draw_mark(mid,
start_height);
draw_ruler_helper(left,mid,start_height-1,
num_divisions-1);
draw_ruler_helper(mid,right,start_height-1,num_divisions-1);
}
interative:
draw_ruler(int
left, int right, int start_height, int num_subdivisions)
{
int
total_length = right ¨C left;
draw_mark(left,
start_height);
draw_mark(right,
start_height);
for
(int I=0; I< num_subdivisions; I++)
{
int
num_marks = pow(2,I);
for ( int j=0;
j< num_marks; j++)
{
step =
total_length/num_marks;
if (j%2 !=0)
draw_mark(left+
j*step, start_height-i);
}
}
}
This is O(N),
N is the total number of marks. Because the first loop is 2^0, the second 2^1,Ą,
the total is 2^0 + 2^1 + Ą+ 2^(num_divisions-1) = 2^num_divisions = N.
Some
of you first calculate N and the outer loop is on N, then in the inner loop,
test if a mark should be drawn by shifting bits or in a similar fashion( divide
by 2^k). This is correct in effect, but more time consuming. ItĄ¯s O(NlogN).