Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 3804: Assignment 1

        Your assignment should be submitted online on Brightspace as a single .pdf file. The filename should contain your name and student number. No late assignments will be accepted.You can type your assignment or you can upload a scanned copy of it. Please, use a good image capturing device. Make sure that your upload is clearly readable. If it is difficult to read, it will not be graded.

Question 1 [10 marks]

Consider the following (not so great) algorithm to find the median of a set S of n elements.

        For i = 1 to b(n/2)c do

                in linear time (in the size of S), find both min and max in S

                delete the min and max elements from S

First, write this algorithm more precisely (filling in the min and max finding, in particular). What is the time complexity of this (bad) algorithm?

Then, prove, using the loop invariant concept, that this algorithm correctly finds the median of a set of n elements.

Question 2 [15 marks]

DT claims that he can perform the operation DeleteMin from a Minheap using o(logn) comparisons.

        (a) Using this, what is the number of comparisons of the most efficient sorting algorithm that you can think about?

        (b) Using (a) argue that DT must be lying about the time complexity of DeleteMin.

Question 3 [10 marks]

Implement the two algorithms presented in class for computing Finonacci numbers, fib1 and fib2 and the direct way using the Golden Ratio.

        Each time you compute a Fibonacci number, measure how many milliseconds it takes, and print this timing information. There is a Java function, System.currentTimeMillis(), which returns a long result; call it once before you do the computation, and a second time after you do the computation; subtract to get the elapsed time. Be careful to measure only the computation time; any changes to the GUI should be made either before or after you start measuring. Do not do anything else on your computer. From time to time, your computer will do garbage collection, this may explain strange timing results.

        What is the maximum value of n for which you can compute Fibonacci? How long does it take for each n that you can compute? Hand in your code and the timing results.

Question 4 [10 marks]

(a) Write a linear-time, recursive algorithm to find the minimum of a set, S, containing n elements.

(b) State and solve the recurrence relation for the time complexity of your algorithm.

(c) Analyze its space complexity.

(e) prove its correctness.

Question 5 [30 marks]

Part I [20 marks]. Apply the master’s theorem (general form), where possible, to solve the following recurrence relations and give a Θ-bound for each of them. If the master’s theorem is not applicable, state why and then solve the recurrence using another method that we learned in class.

Part II [5 marks]. What can you say about the time complexity of an algorithm whose running time is given by this recurrence T(n) = 2T(n) + O(log log n)?

Part III [5 marks]. Which method might be most appropriate to solve the following recurrence? Use it to give its solution. T(n) = T(n/3) + T(2n/3) + n

Part IV [5 marks]. Provide a solution to T(n) = T(n/4) + T(3n/4) + n (you can assume that n is equal to some power of 4)using the guessing method, followed by an induction proof. Think what the induction should be on.

Question 6 [25 marks]

Let (p1, ..., pn) be an ordered sequence of points, stored in an array, representing a polygonal chain that is convex (see below for an example). Design a D&C algorithm that finds a vertical line that splits the chain into 2 subchains that have roughly the same number of vertices. It must be D&C (although other and more efficient algorithms exist). Prove the correctness of your algorithm and analyze its time complexity.

Convex polygonal chain

        Next, a conex polygon consists of two convex chains that are attached at the two vertices with minimim und maximum x-value, respective. (Assume distinctness )

        Now use this to design a D&C algorithm to find a vertical line that splits the convex polygon into 2 convex polygons with roughly equal number of vertices. You can assume that such a line exists and will always go through a vertex. Prove its correctness and establish its time complexity.

Convex polygon and a vertical line splitting the polygon into two that have roughly equal number of vertices.