NAMES:

LOGINS:

PRECEPT:

COS 226 Exercises on Analysis of Algorithms


Reference: Section 1.4 in Algorithms, 4th edition


1. The two Java functions below each return a string of length N whose characters are all x. Determine the order of growth of the running time of each, 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 = "";
        String x = "x";
        for (int i = 0; i < N; i++)
            s = s + x;
        return s;
    }

    public static String method2(int N)
    {
        String s = "";
        String x = "x";
	while (N != 0)
        {
	   if (N % 2 == 1) s = s + x;
           x = x + x;
           N = N/2;
        }
        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 array a[] of N distinct integers, 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 array a[] of N distinct integers, 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.