$29
Problem 2 1-9 Solution
Give a linear-time algorithm that takes two sorted arrays of real numbers as input, and returns a merged list of sorted numbers. You should give your answer in pseudocode. Your answer should contain:
A prose explanation of the algorithm.
The algorithm below creates an array whose size is the sum of the sizes of the two input arrays. There are three "indexers" for each array so the algorithm can keep track of which element in each array is its "current" element. Since the two input arrays are sorted, these indexers will only need to be incremented up through their respective arrays.
There are three loops that populate the output array. The rst traverses through the two input arrays at the same time. The loop starts at the beginning of the two input arrays.
The loop has two conditional statements to see which element of the current position of the two input arrays is smaller. For whichever array has the smaller current element, the algorithm copies that current element’s value into the current spot of the output array. The indexer for the output and selfsame input array get incremented. The loop stops once it has reached the end of one of the two input arrays.
After the rst loop has ended, there are two possible cases for the current state of the algorithm: one, the algorithm has traversed through all elements of the rst input array and the second input array has elements remaining to be copied into the output array; or two, the algorithm has traversed through all elements of the second input array and the rst input array has elements remaining to be copied into the output array.
For both cases, there is a while loop, one for each input array, that will append to the output array the remaining elements of its respective input array. While there are two loops, only one loop (never more, never less) will be traversed for any given initialization state of the algorithm, because, by the time the rst loop terminates, one of the two input arrays has already been completely traversed and all of its elements has been copied into the output array.
After these three loops have been passed by, the algorithm terminates.
Psuedocode. (Be sure to review the two resources on pseudocode that were posted as readings for Week 2! I also suggest the algorithm / algorithmx package in LaTex.)
Algorithm Merge two sorted arrays into one array
procedure MergeTwoSortedArrays(arr1; arr2)
2:
arr3
empty array of size jarr1j + jarr2j
. Soon-to-be-sorted array of arr1 and arr2
3:
idx1
0
. Indexer for arr1
4:
idx2
0
. Indexer for arr2
5:
idx3
0
. Indexer for arr3
6:
while idx1 < jarr1j and idx2 < jarr2j do
. Traverse arr1 and arr2
7:
if arr1[idx1] < arr2[idx2] then
. Store the smaller element in arr3[idx3]
arr3[idx3] arr1[idx1]
9: idx1 idx1 + 1 . Increment the relevent indexers
idx3 idx3 + 1
else
arr3[idx3] arr2[idx2]
13: idx2 idx2 + 1 . Increment the relevent indexers
idx3 idx3 + 1
end if
end while
17: while idx1 < jarr1j do . Store the remaining elements of arr1 in arr3
idx1 idx1 + 1
idx3 idx3 + 1
arr3[idx3] arr1[idx1]
end while
22: while idx2 < jarr2j do . Store the remaining elements of arr2 in arr3
idx2 idx2 + 1
idx3 idx3 + 1
arr3[idx3] arr1[idx2]
end while
end procedure
The decrementing function for any loop or recursion.
while idx1 < jarr1j and idx2 < jarr2j do
D : X ! N which is a well-ordered set and D(x) = (jarr1j + jarr2j (idx1 + idx2)).
while idx1 < jarr1j do
D : X ! N which is a well-ordered set and D(x) = jarr1j idx1.
while idx2 < jarr2j do
D : X ! N which is a well-ordered set and D(x) = jarr2j idx2.
Justi cation of why the runtime is linear.
This algorithm is O(jarr1j + jarr2j) because, for each iteration of any of the three loops, one element of arr1 or arr2 is appended to arr3, and the algorithm terminates only once every element of arr1 and arr2 has been copied into arr3, and, by virtue of jarr3j = jarr1j + jarr2j, the algorithm’s runtime cannot be greater than jarr1j + jarr2j.
EPI-C++ 15.4 / EIP-Java 15.5 (Generate the Power Set) gives code to compute the power set of a set (without duplicates). Present this problem and solution in your own words using pseudocode.
Generating the power set means to produce every possible set of size 0 to n of a given set. To do this with code, we would do the following:
This algorithm takes an input set of n integers. It then generates an array that contains all the binary representations that can be made from n bits. This is then used to generate the power set by iterating over the binary representations and creating subsets of inputSet indexed where the binary representation is 1. These subsets are then added to the power set. The algorithm ends when all binary representations have been mapped to a subset from the input set and added to the power set.
1:
procedure GeneratePowerSet(inputSet; n)
. n is the length of inputSet
2:
Initialize
2D array of integers called powerSet
. Holds the subsets of the power set
3:
Initialize
2D array of integers called bitArray
. Holds the binary representations of numbers
4:
for i 0; n do
Append to bitArray the binary representation of inputSet[i] as a 1D array of integers
end for
7: for i 0; length of bitArray do . Generates the power set
Intialize integer array subSet
for j 0, length of array at bitArray[i] do
if bitArray[i][j] equals 1 then
Append inputSet[j] to subSet
end if
end for
Append subSet to powerSet
end for
16: Append an empty array to powerSet . The empty array here represents ;
return powerSet
end procedure
The runtime of this algorithm is O(n2n) as generating the the binary representations of the inputSet takes 2n time and iterating over that 2n array n times to generate the power set makes this run in O(n2n) time.
In EPI 15.1 (The Towers of Hanoi Problem), prove that the algorithm as presented terminates. In particular, you should give the decrementing function for the recursion.
Proof. Let’s de ne a decrementing function D : X ! N which is a well-ordered set and D(x) = num rings to move jresultj.
We can assert that the value of D(x) is non-negative at the beginning of the recurrence because of the con-dition num rings to move 0 placed upon compute tower hanoi steps() and that jresultsj is initialized to be empty.
We can also assert D(xi) D(xi+1) is true after each iteration of the recurrence because, once the recurrence arrives at the base case, jresultsj always increases.
Since D(x) decrements with every iteration of the recurrence, and since num rings to move must be nite and non-negative, the recurrence must terminate.
For the stock market problem discussed in class on September 6th (and in CLRS 4.1), walk through the algorithm for the following input:
price = f3; 6; 8; 2; 1; 10; 5; 7g:
public static void main(String args[]){
System.out.println("\n\nFinal return value is: "+stockProblem(new int []{3, 6, 8, 2, 1, 10, 5, 7},0));
}
public static int stockProblem(int [] inputArray, int level){ level++;
if(inputArray.length<=1){
return 0;
}
int [] lowArray= new int [inputArray.length/2];
int [] highArray = new int [inputArray.length/2];
for (int i = 0; i <inputArray.length/2 ; i++) {
lowArray[i]=inputArray[i];
highArray[i]=inputArray[inputArray.length/2+i];
}
int a = stockProblem(lowArray,level);
int b = stockProblem(highArray,level);
int leftMin= Arrays.stream(lowArray).min().getAsInt();
int rightMax= Arrays.stream(highArray).max().getAsInt();
System.out.println("\n\n");
System.out.println("Recursion depth is: "+ level);
System.out.println("a is:"+a);
System.out.println("b is:"+b);
System.out.println("Left Min: "+leftMin);
System.out.println("Right Max: "+rightMax);
System.out.println("Left Array: "+Arrays.toString(lowArray));
System.out.println("Right Array: " +Arrays.toString(highArray));
System.out.println("Return value is: "+Integer.max(a,Integer.max(b, rightMax-leftMin)));
return Integer.max(a,Integer.max(b, rightMax-leftMin));
}
The recurrence relation for this algorithm is T (n) = 2( n2 + (n)), and the closed form of this recurrence relation is O(n log n):
The output below is organized to look like recursion tree. The algorithm above does a pre-order traversal, splitting the input array in half every time and comparing if the max value in the right array minus the min value in the left array is greater than the current running total of the sub branches (a and b). The base case is to compare against 0 when the arrays are of size 1 or less.
Recursion depth is: 1
is:5 b is:9 Left Min: 2 Right Max: 10
Left Array: [3, 6, 8, 2]
Right Array: [1, 10, 5, 7]
Return value is: 9
/ \
/ \
Recursion depth is: 2 \
a is:3 a is:9
b is:0 b is:2
Left Min: 3 Left Min: 1
Right Max: 8 Right Max: 7
Left Array: [3, 6] Left Array: [1, 10]
Right Array: [8, 2]
Right Array: [5, 7]
Return value is: 5
Return value is: 9
/
\
/
\
/
\
/
\
/
\
/
\
Recursion depth is:
3
/
\
a is:0
a is:0
a is:0
a is:0
b is:0
b is:0
b is:0
b is:0
Left Min: 3
Left Min: 8
Left Min: 1
Left Min: 5
Right Max: 6
Right Max: 2
Right Max: 10
Right Max: 7
Left Array:
[3]
Left Array: [8]
Left Array: [1]
Left Array: [5]
Right Array: [6]
Right Array: [2]
Right Array: [10]
Right Array: [7]
Return value is: 3
Return value is: 0
Return value is: 9
Return value is: 2
Prove using induction that the closed form of:
T (n) =
(T (n 1) + n n 1
1
n = 1
is O(n2).
Proof. First, we choose n = 1 and n = 2 for our base cases. When we plug these values into the formulas given and we get T (1) = 1 and T (2) = T (2 1) + 2 = 3. So let’s nd a c such that it satis es our base cases. So we choose c = 1 because
1 1(12)
= 1
and
3 1(22)
= 4
Next, our inductive hypothesis: we assume T (n) cn2 for all positive numbers less than n. Therefore, T (n 1) c(n 1)2, which is logically equivalent to
T (n) c(n 1)2 + n
c(n2 2n + 1) + n
= cn2 2cn + n + c
cn2 (for c 1)
Therefore, T (n) 1n2 for all n 1, so T (n) 2 O(n2).
What is the closed form of the following recurrence relations? Use Master’s theorem to justify your answers:
T (n) = 16T (n=4) + (n)
a = 16 b = 4
logb a = log4 16 = 2
nlogb a = n2
f(n) = (n) Case 1
Closed form is T (n) = (n2)
T (n) = 2T (n=2) + n log n
a = 2 b = 2
logb a = log2 2 = 1
nlogb a = n
f(n) = n log n Case 3
n0 = 2; c = 1 ! af( nb ) cf(n) ! 2( 12 log 12 ) n log n = log 12 n log n holds true Closed form is T (n) = (n log n)
T (n) = 6T (n=3) + n2 log n
a = 6 b = 3
logb a = log3 6
nlogb a = nlog3 6
f(n) = n2 log n Case 3
n0 = 2; c = 1 ! af( nb ) cf(n) ! 6( n3 2 log n3 ) 1(n2 log n) holds true Closed form is T (n) = (n2 log n)
T (n) = 4T (n=2) + n2
a = 4 b = 2
logb a = log2 4 = 2
nlogb a = nlog2 4 = n2
f(n) = n2
Case 2
Closed form is T (n) = (n2 log n)
T (n) = 9T (n=3) + n
a = 9 b = 3
logb a = log3 9 = 2
nlogb a = nlog3 9 = n2
f(n) = n
Case 1
Closed form is T (n) = (n2)
Note: we assume that T (1) = (1) whenever it is not explicitly given.
The skyline problem: You are waiting for the ferry across the river to get into a big city, and notice n buildings in front of you. You take a photo, and notice that each building has the silhouette of a rectangle. Suppose you represent each building as a triple (x1; x2; y), where the building can be seen from x1 to x2 horizontally and has a height of y. Let rect(b) be the set of points inside this rectangle (including the boundary). Let building be the set of n triples. Design an algorithm that takes buildings as input, and returns the skyline, where the skyline is a sequence of (x; y) coordinates de ning [b2buildingsrect(b).
This algorithm takes in the input as a set of triples representing buildings. These triples are then broken into start- and end-points and placed in a new list of twice the size of the input list. This list is then sorted by the X-value in the start- and end-points. If the X-values are tied, check if both are end-points or start-points. If both are start-points, sort the tie by placing the point with the highest Y-value before the other. If both points are end-points, place the point with the highest Y-value after the other. If there is a mismatch between the start- and end-point during a tie, place the start-point before the end-point. Next, create a priority queue to hold Y-values of start-points. Push rst a value of 0 onto the priority queue. Update the currently maximum Y-value to be the maximum for the priority queue. Iterate through the points. If the current point is a start-point, push its Y-value onto the queue. If this value is greater than the current maximum, add the point’s X-value and its Y-value to the output as a point. Update the current maximum to the maximumof the priority queue. If the point is an end-point, remove that point’s Y-value from the priority queue. If this causes the maximum value of the priority queue to change, update current maximum to the new maximum of the priority queue and append the point’s X-value and the priority queue’s new maximum to the output as a point. Once all points have been iterated over, a set of points is generated that describes the skyline.
A video by Tushar Roy was used to help better understand this algorithm.1
procedure GenerateSkyline(inputBuildings)
Initialize list listOfBuildingsAsStartAndEndPoints
for all building in inputBuildings do
X1 building.get(0)
X2 building.get(1)
6:
Y
building.get(2)
7:
Append (X1; Y; 1) to listOfBuildingsAsStartAndEndPoints
. 1 indicates the start of a building
8:
Append (X2; Y; 0) to listOfBuildingsAsStartAndEndPoints
. 0 indicates the end of a building
end for
Perform merge sort on listOfBuildingsAsStartAndEndPoints based on the X-value in the following fashion: If there are ties, use the greatest Y-value rst. If they are both start-points, then check if they are both end-points. If so, sort such that the greatest Y-value is last; if they are mismatched, put the end-point after the start-point.
Initalize PriorityQueue queue
Push a 0 onto queue to set the initial value of its maximum
https://www.youtube.com/watch?v=GSBLe8cKu0s
currM ax queue:getM ax()
14: Initialize list skyLine . Holds points of the skyline
for all point in listOfBuildingsAsStartAndEndPoints do
16:
if point[2] equals 1 then
. The point is a start-point
17:
Push point[1] onto queue
. Add the height of the start-point to queue
18:
if maximum of queue the current maximum then . If the new point’s is the greatest...
currMax maximum of queue
Append (point[0], currMax ) to skyLine
end if
22:
else
. The point is an end-point
23:
Remove point[1] from queue
. Remove height from queue
if currMax != the maximum of queue then . Removing point’s height changes the maximum
currMax maximum of queue
Append (point[0], currMax ) to skyLine
end if
end if
end for
return skyLine
end procedure
The runtime of this algorithm is as follows.
n is the number of buildings in the input array. The rst for loop runs n times. The sort runs at O(n log n) if merge sort is utilized. The runtime of the second for loop is 0(2n). So the runtime of the algorithm is O(n log n).
The rand() function in the standard C library returns a uniformly random number in [0,RANDMAX-1]. Does rand() mod n generate a number uniformly distributed in [0; n 1]?
Note I: This is the second variant in EPI 5.12.
Note II: When asked questions of this form, you are expected to justify your Answer.
No, because, for example, let’s say RANDMAX = 3. By this RANDMAX, rand() will produce a uniformly random number in [0, 2]. Now let’s say n = 2. Therefore, all possible outputs of rand() mod 2 are
0 mod 2 = 0
1 mod 2 = 1
2 mod 2 = 0
thus producing a 2-to-1 ratio of 0s and 1s | which shows that rand() mod n does not always produce a uniformly random number in [0, n-1].
Algorithms where we use randomization to nd a deterministic answer are known as Las Vegas algorithms. Monte Carlo algorithms also use randomization, but might not always give the right answer; however, they either have a high probability of being correct or close to correct.
(a) Give a Monte Carlo algorithm to estimate .
procedure MonteCarlo(num points)
2: num points in circle 0
for i 0; num points do
4: rand x randReal(0; 1) . For a raidus = 1
rand y randReal(0; 1)
6: if rand x2 + rand y2 < 1 then . x2 + y2 < 1 means point is within circle of r = 1
Increment num points in circle by 1
end if
end for
return 4
10: end procedure
(b) Let n be the number of random numbers used by your algorithm. Explain why as n ! 1, the expectation of the output for your algorithm is .
As n ! 1, the amount of points within a square surrounding a circle of r = 1 will become more and more densely populated. Mathematically, the chance a point landing within the circle will be equal to
the ratio of the area of the r = 1 circle to the area of the 1 1 square | that is, (1)2 = , where the
2 2 4
2s in the original denominator come from length of the square being equal to 2r = 2(1) = 2. As the number of points gets closer and closer to 1, the closer and closer the resultant proportion will converge on this true proportion of 4 .
(c) Implement this algorithm and plot a line graph of the values returned for at least 10 values of n.
The points plotted are, from i = 1 to i = 10, [2, 3.28, 3.244, 3.1248, 3.14544, 3.139968, 3.1415484, 3.14137188, 3.1416332, 3.1415718708].
Note: We can use the function randReal(a; b) that returns a random real number between a and b inclusive.
14
