COMP2011 Tutorial Exercises 2, Week 3

Analysis of Algorithms

• Order the following list of functions using Order notation. Group together those functions that are big-Theta of one another:

  6 n log n	2100	log log n	log2n	2log n
  22n	sqrt(n)	n0.01	1/n	4 n3/2
  3 n0.5	5 n	2 n log2 n	2n	n log4n
  4n	n3	n2 log n	4log n	sqrt(log n)

  Hint: When in doubt about two functions f(n) and g(n), consider log f(n) and log g(n) or 2^f(n) and 2^g(n).

• Any questions about Assignment 1.

• C-1.7 Write a fast Java method that can take any int value, i, and return 2ⁱ, as a long value. Your method should not multiply 2 by itself i times; there are much faster ways of computing 2ⁱ.

• (If time permits) What is the difference between checked and unchecked exceptions?
  Why are most of the exceptions in java.lang unchecked, whereas most in java.io are checked?

• Challenge Question: C-1.4 Write a short Java program that outputs all possible strings formed by using the characters 'c','a','r','b','o' and 'n' exactly once.
  Hint: look up the StringBuffer class in the online documentation.