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 algorithmdon't write Java code.

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.

Give an efficient algorithm to determine if there exists an integer i such that Ai = i in an array of integer Ai < A2 < A3 < . . . AN. What the running time of your algorithm?

Give efficient algorithms ( along with the running time analyses) to a.

Find minimum subsequence sum

Find minimum positive subsequence sum

Find the maximum subsequence of product

An algorithm takes 0.5 ms for input sizw 100. How long will it take for input size 500 if the running time is the following (assume low-order terms are negligible)?

Linear

O9N log N)

Quadratic

Cubic

Write a routine to list out the nodes of a binary tree in level-order. List the root, then nodes at depth 1, followed by nodes at depth 2 and so on. You must do this in linear time. Prove your time bound

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.