HW1 Solutions Page
Return to
homework page.
2.7
(a) By using rule 2 for nested for-loops on page 36, we can see that
(1) is O(n) time , (2) is O(n2), (3) is O(n3).
For (4) notice it is as if we execute for loops of lengths:
1,2,3,...n where each iteration in each for loop is contant time.
So the total time is O(1+2+3+...+(n-1)) = O(n2).
For (5) first consider the j indexed for-loop. The execution of it
entails the execute of loops of length 0,1,2,3,...,(j-1)2.
This takes time
O(1+2+3+..+(j-1)2).
Notice the sum inside the O is bounded from above by the integral
from 0 to (j-1)2 of k. This evaluates to
((j-1)2)2/2. So this loop take O(j4) time.
So the runtime of the i indexed for-loop will be bounded by
O(14+24+...+(n-1)4).
We can bound this above by the integral from 0 to n-1 of
j4. So (5) has O(n5) running-time.
For (6) notice the k indexed for-loop is only executed when j is
divisible by i. So in executing the j indexed for-loop we will
check this condition i*i-1 times and we will execute the k indexed
for-loop on values i,2i,3i,...(i-1)*i. So to execute the j indexed
for-loop will take time O(i*i) + O(i*(1+2+3+...+(i-1))) = O(i3).
So to execute the i indexed for loop will take time
O(13 + 23+...+(n-1)3)
which we can bound using integrals as in (5) by O(n4)
(b) & (c)
Below is the code I used:
public class RunTests
{
public static void main( String args[])
{
int n= Integer.parseInt(args[1]);
long curTime;
long sum;
switch(Integer.parseInt(args[0]))
{
case 1:
curTime = System.currentTimeMillis();
sum=0;
for( long i=0; i < n; i++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 2:
curTime = System.currentTimeMillis();
sum=0;
for( long i=0; i < n; i++)
for( long j=0; j < n; j++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 3:
curTime = System.currentTimeMillis();
sum=0;
for( long i=0; i < n; i++)
for( long j=0; j < n*n; j++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 4:
curTime = System.currentTimeMillis();
sum=0;
for( long i=0; i < n; i++)
for( long j=0; j < i; j++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 5:
curTime = System.currentTimeMillis();
sum=0;
for( long i=0; i < n; i++)
for( long j=0; j < i*i; j++)
for( long k=0; k < j; k++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 6:
curTime = System.currentTimeMillis();
sum=0;
for( long i=1; i < n; i++)
for( long j=1; j < i*i; j++)
if( j % i == 0)
for( long k=0; k < j; k++)
sum++;
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
}
}
}
Here are some runtimes I obtained
(Alg 1)
n Time(ms)
100000 51
200000 55 /*Notice increases by constant increment
300000 59 so looks linear */
400000 63
(Alg 2)
n Time(ms) k (assuming Time = k*n*n)
1000 91 9e-5
2000 242 6e-5
4000 778 4.9e-5
8000 2864 4.5e-5
10000 4459 4.5e-5 /* k seems pretty stable for larger
12000 6354 4.4e-5 n so algorithm 2 does look O(n2)
14000 8648 4.4e-5 like predicted */
16000 11831 4.6e-5
(Alg 3)
n Time(ms) k (assuming Time = k*n*n*n)
100 117 1.2e-4
200 452 5.6e-5
300 1413 5.2e-5
400 3283 5.1e-5 /* k seems pretty stable so looks cubic
500 6368 5.1e-5 like predicted */
600 10993 5.1e-5
(Alg 4)
n Time(ms) k (assuming Time = k*n*n)
5000 614 2.4e-5
6000 854 2.4e-5 /* k seems pretty stable so look
7000 1119 2.3e-5 quadratic */
8000 1447 2.3e-5
(Alg 5)
n Time(ms) k (assuming Time = k*n5)
40 519 5e-6
50 1350 4.3e-6 /* k seems pretty stable
60 3334 4.2e-6 so looks quintic like predicted */
70 7156 4.2e-6
80 13958 4.2e-6
(Alg 6)
n Time(ms) k (assuming Time = k*n4)
50 183 2.9e-5
100 731 7.3e-6
150 3379 6.6e-6
175 5994 6.3e-6
200 9907 6.1e-6 /* k seems pretty stable for these
225 15632 6.0e-6 larger values so looks quartic
250 23689 6.0e-6 like predicted */
275 34353 6.0e-6
2.8
(a) Algorithm (2) is the same as algorithm one except that instead
of using unordered search to check if a number has already been
chosen table look-up is used. So it suffices to see that
Algorithm (1) generates random legal permutations to show this fact
for both (1) and (2). That (1) before assigning checks if the number has
already occurred prevents duplicates. Since we assign
a[0], ...,a[n-1] values, we assign n numbers. As these are distinct
and chosen from 1 to n each number from 1 to n must eventually be
picked. So it will be a legal permutation. It will be random
as each number is equally likely not to have been picked by iteration
i and in stage i we pick a number from the remaining numbers
randomly.
That algorithm (3) produces only valid permutations can be
proven by induction on n. In the case where n=1 we assign
a[0]=1 and the for loop won't execute, so we get the only
valid permutation on one element. Assume the algorithm
works for n=N. Consider n=N+1. On this value of we just
perform a swap of a[N]=N+1 with a randomly chosen earlier
a[i]. Since a[0] ... a[N-1] contains a valid permutation
of 1 to N by our hypothesis only the numbers between
1 and N appear and they each appear once. So if we now
look at the entries a[0] to a[N], before the swap
each of the number 1,...,N+1 appeared and appeared only
once. This property is preserved by the swap so
we have a valid permutation and have shown the
induction step. To see that it is random can be similarly
proven by induction. The base case is easy as there is only
one permutation on one element and we generate it. Assume
that the permutation is random for n=N. Consider n=N+1.
N+1 is equally likely to appear in a[i] after the swap,
0 < = i <= N as we chose i randomly. If we consider any
value 1<=j<=N before the swap it is equally likely to
appear in any a[m] 1<=m<=N by the induction hypothesis. So
each value j is equally likely to be swapped to a[N]. Therefore
each value 1<=j<=N+1 is equally likely to appear in any position.
(b) There are two main components to the runtime of algorithm 1:
How long it takes to find an element we haven't seen and
how long it takes to tell we haven't seen it. The latter is
amounts to unordered search so will be O(n) on average (since
the average element of the array is O(n) size). For the former
notice at an average step less than n roughly half of the
permutation has been determined so the odds of picking an element
not in the permutation is .5. The odds of having to do this twice
are .25 and so on. The average number of steps will be the sum
over the probability of taking N Steps * N. This gives the sum
from 1 to infinity of i/2i. One can check this is
2 so finite. (To see this consider the sum of xi
from 0 to infinity. This is 1/(1-x) differentiate both sides
by x and set x = 1/2. Multiply both sides by a 1/2.)
So the unordered search part dominates the time
and we have to do it n times. Thus, the algorithm is O(n2).
For algorithm 2, we replace the unordered search part of
algorithm with a constant time array look up. So now each
index of the permutation can be determined in constant expected time
so the algorithm is O(n) time.
Since swapReferences can be done in constant time algorithm (3)
has O(n) run time.
(c) & (d)
Below is the code I used:
public class PermuteTests
{
public static void main( String args[])
{
int n= Integer.parseInt(args[1]);
int[] a = new int[n];
boolean[] used = new boolean[n+1];
long curTime;
long sum;
switch(Integer.parseInt(args[0]))
{
case 1:
curTime = System.currentTimeMillis();
for( int i=0; i < n; i++)
{
boolean notNew = true;
while(notNew)
{
a[i] =(int)(n*Math.random())+1;
notNew = false;
for(int j=0; j < i; j++)
if( a[i] == a[j] ) notNew=true;
}
}
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 2:
curTime = System.currentTimeMillis();
for( int i=0; i < n; i++)
used[i] =false;
for( int i=0; i < n; i++)
{
boolean notNew = true;
while(notNew)
{
a[i] =(int)(n*Math.random())+1;
if(!used[i]) notNew =false;
}
}
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
case 3:
curTime = System.currentTimeMillis();
for( int i=0; i < n; i++)
a[i] = i+1;
for( int i = 0; i < n; i++)
swapReferences(a, i, (int)(i*Math.random()));
curTime = curTime-System.currentTimeMillis();
System.out.println("Time took was: "+(-curTime));
break;
}
}
private static void swapReferences(int[] a, int i, int j)
{
int tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
(Alg 1)
n Time(ms) k (assuming Time = k*n*n)
250 41 6.5e-4
500 119 4.8e-4 /* hard to tell
1000 479 4.8e-4 but doesn't seem
2000 1845 4.6e-4 too off model */
(Alg 2)
n Time(ms) k (assuming Time = k*n)
2500 47 .019
5000 74 .015
10000 152 .015 /* k seems pretty
20000 298 .015 stable so linear
40000 579 .014 */
80000 1148 .014
(Alg 3)
n Time(ms) k (assuming Time = k*n)
10000 161 .016
20000 322 .016
40000 601 .015 /* k seems pretty
80000 1195 .015 stable so fits the
160000 2401 .015 model of being linear
320000 4875 .015 */
640000 9655 .015
(e) If randInt is true rnadom then for the first two algorithms
there is some very very small chance that after picking a[0]=j
for some j, randInt keeps returning j when we try to pick a
value for a[1] and these algorithms never terminate.
Since swapReferences can be done in constant time algorithm (3)
has O(n) run time.
2.12
(a) We have .0005 s = k * (100 inputs). So k = 5.0e-6 s/input.
In 60 s we can do x= 60s/(5.0e-6s/input) = 6/5e7 = 1.2e8 many inputs.
(b) We have .0005 = k * 100 log2 100. So k ~ 7.52e-7.
If 60/(7.52e-7) ~ 7.98e7 = N log2 N
then N ~ 3660000 inputs. (Easiest way to get this is just guess and check).
(c) We have .0005 = k * 1002. So k = 5e-8.
If 60/5e-8 = N2 then N ~ 34600 inputs.
(d) We have .0005 = k * 1003. So k = 5e-10.
If 60/5e-10 = N3 then N ~ 4930 inputs.
2.14
(a) To begin poly=0. When we start the for loop n=4.
We now describe each iteration through the for-loop.
1st Iteration: poly = 3 * 0 + 4 = 4.
2nd Iteration: poly = 4 * 3 + 8 = 20.
3rd Iteration: poly = 20 * 3 + 0 = 60.
4th Iteration: poly = 60 * 3 + 1 = 181.
5th Iteration: poly = 181 * 3 + 2 = 545. (Final value for poly.)
One can check that when x=3,
f(x) = 4x4 + 8x3 + x + 2 evaluates to
4(34) + 8(33) + 3 + 2 = 4(81) + 8(27) +5 = 545.
So on this input the algorithm seems to work.
(b) If we take the polynomial
(*) anxn+an-1xn-1+...+a0
and keep factoring out x from as many terms as we can we get the
following expression:
x(x(...x(0+an)...)+a2)+a1)+a0.
The for loop in the book corresponds to exvaluating the above expression
from the innermost parentheses outward.
(c) The for loop on a polynomial of degree n performs n+1 iterations.
The operations we perform each iteration are one addition and one
multiply to recompute poly. In an iteration we also check the loop
condition and decrement i. So we do contantly many operation n+1
times. This means the algorithm is O(n). This compares with
O(n2) if try to directly evaluate the expression (*).
/**
This program is run from the command line with a line like:
java cs146sec6hw1file1 abc
It then prints out all permutations of the characters in abc
(or in general any string that is supplied as the first command
line argument).
*/
public class cs146sec6hw1file1
{
// application's main entry point
public static void main( String[] args )
{
permute( args[0] ); /* pass the command-line argument to our
permute function. */
}
/**
This method prints to the standard out all the permutations of
the string str separated by spaces.
*/
public static void permute( String str)
{
permute( str.toCharArray(), 0, str.length()-1);
System.out.print("\n");
}
/*
This function prints out all permutations of str where only
indices between low and high are permuted. For instance,
if str[0] = 'a', str[1] = 'b', str[2] = 'c', str[3] = 'd'
then permute(str, 1, 2) would print:
abcd acbd
Postcondition: char array str is unchanged by this function
*/
private static void permute(char[] str, int low, int high)
{
int nextLow = low + 1;
if(low == high) // only one possible permutation so print it
{
System.out.print( str + " ");
return;
}
/* otherwise, go through each possible first char
and print the permutations for that first char
*/
permute(str, nextLow, high);
for( int i = nextLow; i <= high; i++)
{
swap(str,low, i);
permute(str, nextLow ,high);
}
for( int i = high - 1; i >= low; i--) //undo changes to str
swap(str, i, high);
}
/*
exchanges the values in str[index1] and str[index2]
*/
public static void swap( char[] str, int index1, int index2 )
{
char tmp;
tmp = str[index1];
str[index1] = str[index2];
str[index2] = tmp;
}
}