Description

Problem 1.           Java Review

At this point, most of you should be comfortable enough to work with Java. Let’s take some time to review a few concepts in Java so that we can limit our Java-related issues and, hence, focus on the algorithms when solving future Problem Sets.

• What is the difference between a class and an object? Illustrate with an example.
• Why does the main method come with a static modifier?
• Give an example class (or classes) that uses the modifier private incorrectly (i.e., the program will not compile as it is, but would compile if private were changed to public).
• The following question is about Interfaces.

(d)(i) Why do we use interfaces?

(d)(ii) Give an example of using an interface.

(d)(iii) Can a method return an interface?

• Refer to java. Without running the code, predict the output of the main method. Can you explain the outputs?
• Can a variable in a parameter list for a method have the same name as a member (or static) variable in the class? If yes, how is the conflict of names resolved?

Problem 2.            Asymptotic Analysis

This is a good time for a quick review of asymptotic big-O notation. For each of the expressions below, what is the best (i.e. tightest) asymptotic upper bound (in terms of n)?

• f₁(n) = 7.2 + 34n³ + 3254n
• f₂(n) = n² logn + 25nlog² n
• f3(n) = 24logn + 5n5
• f4(n) = 22n2+4n+7

Problem 3.             More Asymptotic Analysis!

Let f and g be functions of n where f(n) = O(n) and g(n) = O(logn). Find the best asymptotic bound (if possible) of the following functions.

• h₁(n) = f(n) + g(n)
• h₂(n) = f(n) × g(n)
• h₃(n) = max(f(n),g(n))
• h₄(n) = f(g(n))
• h₅(n) = f(n)^g(n)

Problem 4.            Time complexity analysis

Analyse the following code snippets and find the best asymptotic bound for the time complexity of the following functions with respect to n.

• public int niceFunction(int n) {

for (int i = 0; i < n; i++) {

System.out.println(“I am nice!”);

} return 42;

}

• public int meanFunction(int n) { if (n == 0) return 0; return 2 * meanFunction(n / 2) + niceFunction(n); }
• public int strangerFunction(int n) { for (int i = 0; i < n; i++) { for (int j = 0; j < i; j++) {

System.out.println(“Execute order?”); } } return 66;

}

• public int suspiciousFunction(int n) { if (n == 0) return 2040;

int a = suspiciousFunction(n / 2); int b = suspiciousFunction(n / 2); return a + b + niceFunction(n);

}

• public int badFunction(int n) { if (n <= 0) return 2040; if (n == 1) return 2040; return badFunction(n – 1) + badFunction(n – 2) + 0; }
• public int metalGearFunction(int n) { for (int i = 0; i < n; i++) { for (int j = 1; j < i; j *= 2) {

System.out.println(“!”);

} } return 0; }

Problem 5.              Another Application of Binary Search

Given a sorted array of n − 1 unique elements in the range [1,n], find the missing element? Discuss possible naive solutions and possibly faster solutions.