Assignment 2

COP 3530 - Data Structures

 

 

Instructions:

1.     Create a document (Word or pdf) that contains all your answers and all your code.

2.     Send, by the due date (midnight), a soft copy of the document, the java file and the class file by email to Fernando <ffarf001@cs.fiu.edu> (of course in a single email).

3.     Turn in a hard copy of your document in class on the due date. If you are unable to come to class leave it in my mailbox the same day.

The due dates are specified in the main class web page.

 

 

Questions:

 

  1. [15 points] Write a short recursive Java method that finds the minimum and maximum values in an array of integer values without using any loops. Also write its recurrence relation (recurrent complexity formula).
  2. [15 points] Give a recursive algorithm to compute the product of two positive integers, m and n, using addition and subtraction. Also give its recurrence relation.
  3. [15 points] Give an example input list that requires merge-sort to take O (n log n) time to sort, but insertion-sort runs in O (n) time. What if you reverse this list?
  4. [15 points] Consider the version of the quick sort algorithm where we choose as pivot the element at index floor(n/2). Describe the kind of sequence that would cause this version of quick-sort to run in Ω (n2)?  What is the running time of this version of quick-sort on a sequence that is already sorted?
  5. [20 points] Give an O (n log n) algorithm that, given a set S of n real numbers and another real number x, determines whether or not there exists two elements in S whose sum is exactly x.
  6. [20 points] Solve the recurrence relation T (n) = 9T (n/3) + n.