NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Analysis of Algorithms


Section 4.1 in Introduction to Programming in Java


1. The Java function below returns a string of length N whose characters are all x. Determine the order of growth of its running time, e.g., log N, N, N log N, N^2, N^3, or 2^N. Give a brief explanation. 

 public static String method1(int N) {
     String s = "";
     for (int i = 0; i < N; i++)
         s = s + "x";
     return s;
 }
Hint: Recall that concatenating two strings in Java takes time proportional to the sum of their lengths.








2. In this exercise, you will develop a quadratic-time algorithm for the 3-sum problem. When we ask you to design an algorithm, give a crisp and concise English description of your algorithm - don't write Java code.

  1. Given an integer x and a sorted N-element array of integers a[], design a linear-time algorithm to find if there exists indices i and j such that (a[i] + a[j] == x).

    Hint: start by checking whether a[0] + a[N-1] is smaller than, greater than, or equal to x.



















  2. Given an N-element array of integers a[], design a quadratic-time algorithm to find if there exists indices i, j, and k such that (a[i] + a[j] + a[k] == 0).

    Hint: Use the result from (a). You can assume the array is sorted since sorting the array can be done in quadratic (and even linearithmic) time.