Problem 2 1-9 Solution

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

1. 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]

8. arr3[idx3] arr1[idx1]

9: idx1 idx1 + 1 . Increment the relevent indexers

10. idx3 idx3 + 1

10. else

10. arr3[idx3] arr2[idx2]

13: idx2 idx2 + 1 . Increment the relevent indexers

14. idx3 idx3 + 1

14. end if

14. end while

17: while idx1 < jarr1j do . Store the remaining elements of arr1 in arr3

18. idx1 idx1 + 1

18. idx3 idx3 + 1

18. arr3[idx3] arr1[idx1]

18. end while

22: while idx2 < jarr2j do . Store the remaining elements of arr2 in arr3

• 23. idx2 idx2 + 1

• 23. idx3 idx3 + 1

• 23. arr3[idx3] arr1[idx2]

• 23. end while

• 23. end procedure

The decrementing function for any loop or recursion.

• 23. 1. while idx1 < jarr1j and idx2 < jarr2j do

D : X ! N which is a well-ordered set and D(x) = (jarr1j + jarr2j (idx1 + idx2)).

2. while idx1 < jarr1j do

D : X ! N which is a well-ordered set and D(x) = jarr1j idx1.

3. 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.

5. Append to bitArray the binary representation of inputSet[i] as a 1D array of integers

5. end for

7: for i 0; length of bitArray do . Generates the power set

8. Intialize integer array subSet

8. for j 0, length of array at bitArray[i] do

8. if bitArray[i][j] equals 1 then

8. Append inputSet[j] to subSet

8. end if

8. end for

8. Append subSet to powerSet

8. end for

16: Append an empty array to powerSet . The empty array here represents ;

17. return powerSet

17. end procedure

The runtime of this algorithm is O(n2ⁿ) as generating the the binary representations of the inputSet takes 2ⁿ time and iterating over that 2ⁿ array n times to generate the power set makes this run in O(n2ⁿ) 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(x_i) > D(x_i+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( ⁿ₂ + (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]

Prove using induction that the closed form of:

T (n) =	(T (n 1) + n n > 1
	1	n = 1

is O(n²).

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(1²)

= 1

and

3 1(2²)

= 4

Next, our inductive hypothesis: we assume T (n) cn² for all positive numbers less than n. Therefore, T (n 1) c(n 1)², which is logically equivalent to

T (n) c(n 1)² + n

c(n² 2n + 1) + n

= cn² 2cn + n + c

cn² (for c 1)

Therefore, T (n) 1n² for all n 1, so T (n) 2 O(n²).

What is the closed form of the following recurrence relations? Use Master’s theorem to justify your answers:

1. T (n) = 16T (n=4) + (n)

a = 16 b = 4

log_b a = log₄ 16 = 2

_n^logb ^a _{= n}²

f(n) = (n) Case 1

Closed form is T (n) = (n²)

2. T (n) = 2T (n=2) + n log n

a = 2 b = 2

log_b a = log₂ 2 = 1

_n^logb ^a _{= n}

f(n) = n log n Case 3

n₀ = 2; c = 1 ! af( ⁿ_b ) cf(n) ! 2( ¹₂ log ¹₂ ) n log n = log ¹₂ n log n holds true Closed form is T (n) = (n log n)

3. T (n) = 6T (n=3) + n² log n

a = 6 b = 3

log_b a = log₃ 6

_n^logb ^a _{= n}^log3 ⁶

f(n) = n² log n Case 3

n₀ = 2; c = 1 ! af( ⁿ_b ) cf(n) ! 6( ⁿ₃ ² log ⁿ₃ ) 1(n² log n) holds true Closed form is T (n) = (n² log n)

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 (x₁; x₂; y), where the building can be seen from x₁ to x₂ 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)

2. Initialize list listOfBuildingsAsStartAndEndPoints

3. for all building in inputBuildings do

4. X1 building.get(0)

5. X2 building.get(1)

9. end for

9. 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.

9. Initalize PriorityQueue queue

9. Push a 0 onto queue to set the initial value of its maximum

• https://www.youtube.com/watch?v=GSBLe8cKu0s

13. currM ax queue:getM ax()

14: Initialize list skyLine . Holds points of the skyline

15. for all point in listOfBuildingsAsStartAndEndPoints do

19. currMax maximum of queue

19. Append (point[0], currMax ) to skyLine

19. end if

24. if currMax != the maximum of queue then . Removing point’s height changes the maximum

24. currMax maximum of queue

24. Append (point[0], currMax ) to skyLine

24. end if

24. end if

24. end for

24. return skyLine

24. 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 .

1. procedure MonteCarlo(num points)

2: num points in circle 0

3. for i 0; num points do

4: rand x randReal(0; 1) . For a raidus = 1

5. rand y randReal(0; 1)

6: if rand x² + rand y² < 1 then . x² + y² < 1 means point is within circle of r = 1

7. Increment num points in circle by 1

7. end if

7. 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, ⁽¹⁾² = , 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 ₄ .

(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.