Due to the print book page limit, we cannot inlcude all good CheckPoint questions in the physical book. The CheckPoint on this Website may contain extra questions not printed in the book. The questions in some sections may have been reordered as a result. Nevertheless, it is easy to find the CheckPoint questions in the book on this Website. Please send suggestions and errata to Dr. Liang at y.daniel.liang@gmail.com. Indicate the book, edition, and question number in your email. Thanks!

Chapter 22 Check Point Questions

Section 22.2
▼22.2.1
Why is a constant factor ignored in the Big O notation? Why is a nondominating term ignored in the Big O notation?
▼22.2.2
What is the order of each of the following functions? 
(a) (n2 + 1)2/n
(b) (n2 + log2n)2 / n
(c) n3 + 100n2 + n
(d) 2n + 100n2 + 45n 
(e) n2n + n22n
Section 22.3
▼22.3.1
Count the number of iterations in the following loops. 
(a)
int count = 1;
while (count < 30) {
  count = count * 2;
}

(b)
int count = 15;
while (count < 30) {
  count = count * 3;
}

(c)
int count = 1;
while (count < n) {
  count = count * 2;
}

(d)
int count = 15;
while (count < n) {
  count = count * 3;
}
▼22.3.2
How many stars are displayed in the following code if n is 10? How many if n is 20? Use the Big O notation to estimate the time complexity. 
(a)
for (int i = 0; i < n; i++) {
  System.out.print('*');
}

(b)
for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    System.out.print('*');
  }
}

(c)
for (int k = 0; k < n; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      System.out.print('*');
    }
  }
}

(d)
for (int k = 0; k < 10; k++) {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      System.out.print('*');
    }
  }
}
▼22.3.3
Use the Big O notation to estimate the time complexity of the following methods: 
(a)
public static void mA(int n) {   
  for (int i = 0; i < n; i++) {
    System.out.print(Math.random());
  }
}

(b)
public static void mB(int n) {   
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < i; j++)
      System.out.print(Math.random());
  }
}

(c)
public static void mC(int[] m) {   
  for (int i = 0; i < m.length; i++) {
    System.out.print(m[i]);
  }

  for (int i = m.length - 1; i >= 0; )
  {
    System.out.print(m[i]);
    i--;
  } 
}

(d)
public static void mD(int[] m) {   
  for (int i = 0; i < m.length; i++) {
    for (int j = 0; j < i; j++)
      System.out.print(m[i] * m[j]);
  }
}
▼22.3.4
Design an O(n) time algorithm for computing the sum of numbers from n1 to n2 for (n1 < n2). Can you design an O(1) for performing the same task?
▼22.3.5
Example 7 in Section 22.3 assumes n = 2k Revise the algorithm for an arbitrary n and prove that the complexity is still O(logn).
Section 22.4
▼22.4.1
Put the following growth functions in order: 5n3/4032, 44logn, 10nlogn, 500, 2n2, 2n/45, 3n
▼22.4.2
Estimate the time complexity for adding two n by m matrices, and for multiplying an n by m matrix by an m by k matrix.
▼22.4.3
Describe an algorithm for finding the occurrence of the max element in an array. Analyze the complexity of the algorithm.
▼22.4.4
Describe an algorithm for removing duplicates from an array. Analyze the complexity of the algorithm.
▼22.4.5
Analyze the following sorting algorithm: 
for (int i = 0; i < list.length - 1; i++) {
  if (list[i] > list[i + 1]) {
    swap list[i] with list[i + 1];
    i = -1;
  }
}
▼22.4.6
Analyze the complexity for computing a polynomial f(x) of degree n for a given x value using a brute-force approach and the Horner's approach, respectively. A brute-force approach is to compute each term in the polynomial and add them together. The Horner's approach was introduced in Section 6.7.
f(x) = anxn + an-1xn-1 + an-2xn-2 + ... + a1x1 + a0
Section 22.5
▼22.5.1
What is dynamic programming? Give an example of dynamic programming.
▼22.5.2
Why is the recursive Fibonacci algorithm inefficient, but the nonrecursive Fibonacci algorithm efficient?
Section 22.6
▼22.6.1
Prove that the following algorithm for finding the GCD of the two integers m and n is incorrect. 
int gcd = 1;
for (int k = Math.min(Math.sqrt(n), Math.sqrt(m)); k >= 1; k--) {
  if (m % k == 0 && n % k == 0) {
    gcd = k;
    break;
  }
}
Section 22.7
▼22.7.1
Prove that if n is not prime, there must exist a prime number p such that p <= sqrt(n) and p is a factor of n.
▼22.7.2
Describe how the sieve of Eratosthenes is used to find the prime numbers.
Section 22.8
▼22.8.1
What is the divide-and-conquer approach? Give an example.
▼22.8.2
What is the difference between divide-and-conquer and dynamic programming?
▼22.8.3
Can you design an algorithm for finding the minimum element in a list using divide-and-conquer? What is the complexity of this algorithm?
Section 22.9
▼22.9.1
What is backtracking? Give an example.
▼22.9.2
If you generalize the Eight Queens problem to the n-Queens problem in an n-by-n chessboard, what will be the complexity of the algorithm?
Section 22.10
▼22.10.1
What is a convex hull?
▼22.10.2
Describe the gift-wrapping algorithm for finding a convex hull. Should list H be implemented using an ArrayList or a LinkedList?
▼22.10.3
Describe Graham's algorithm for finding a convex hull. Why does the algorithm use a stack to store the points in a convex hull?