Homework 1 (assigned April 1, due April 8)

Reading: CLRS chapters 1-3.

Written assignment: Solve the following "Do" exercises and assigned problems. Turn in only the problem solutions. Please note: You are responsible for the material covered in both "Do" exercises and assigned problems.

"Do" Exercises (not to be handed in):

1. Select a Θ-notation from among
   Θ(1), Θ(lg n), Θ(n), Θ(n lg n), Θ(n²), Θ(n³), or Θ(2ⁿ)
   for the number of times the statement x ← x + 1 is executed in each of the following code fragments. Justify your answer by analyzing the pseudocode in each case.
   1. 01 i ← 1
      02 while i ≤ 2n do
      03       x ← x + 1
      04       i ← i + 2

   2. 01 for i ← 1 to n do
      02       for j ← 1 to floor[i/2] do
      03             x ← x + 1

   3. 01 for i ← 1 to n do
      02       for j ← 1 to n do
      03             for k ← 1 to n do
      04                   x ← x + 1

   4. 01 for i ← 1 to n do
      02       for j ← 1 to n do
      03             for k ← 1 to i do
      04                   x ← x + 1

2. Exercise 2.3-5 on CLRS page 37.
3. Exercise 2.1-4 on CLRS page 21.

1. Basic sorting
   
   1. Using the pseudocode on CLRS page 17, show how insertion sort sorts the array A = [2, 8, 7, 1, 3, 5, 6, 4]. Use Figure 2.2 as a model. (5 points)
   2. Using the pseudocode on CLRS pages 32 and 29, show how merge sort sorts the array A = [31, 41, 59, 26, 38, 57, 41, 58]. Use Figures 2.3 and 2.4 as a model. (5 points)

2. Order of growth
   In each of the following cases, indicate whether f = O(g), or f = Ω(g), or both (in which case f = Θ(g)). Justify your answer in one or two lines in each case. (5 points each)
   1. f (n) = n − 100; g(n) = n − 200.
   2. f (n) = n^1/2; g(n) = n^2/3.
   3. f (n) = 100n + log n; g(n) = n + (log n)².
   4. f (n) = n log n; g(n) = 10n log 10n.
   5. f (n) = log 2n; g(n) = log 3n.
   6. f (n) = 10 log n; g(n) = log(n²).

3. Analysis of Bubblesort
   Problem 2-2, part d, on CLRS page 38; i.e., analyze the pseudocode given for Bubblesort and compute its worst-case running time as a function of n. Compare the worst-case running time you obtain for Bubblesort with that of Insertion Sort. Which algorithm is faster? (10 points)

4. Analysis of Horner's rule
   Problem 2-3, part a, on CLRS page 39; i.e., how many additions and multiplications does the given routine use, as a function of n? Express your answer in Θ-notation. (10 points)

5. Inversions
   Problem 2-4, parts a, b, and c, on CLRS pages 39-40. (15 points)