Homework 2

1. Problem 2.3-7:
   Describe a time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

   • 第十二組

2. Problem 2-1: Insertion sort on small arrays in merge sort
   Although merge sort runs in worst-cast time and insertion sort runs in worst-cast time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when sub-problems become sufficiently small. Consider a modification to merge sort in which sub-lists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

   • Show that the sub-lists, each of length k, can be sorted by insertion sort in worst-case time.
   • Show that the sub-lists can be merged in worst-case time.
   • Given that the modified algorithm runs in worst-case time, what is the largest asymptotic (Θ-notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort?
   • How should k be chosen in practice?
   • 第十一組

3. Problem 3-2: Relative asymptotic growths
   Indicate, for each pair of expressions (A, B) in the table below, whether A is O, o, Ω, ω, or Θ of B. Assume that k ≥ 1, ε > 0, and c > 1 are constants. Your answer should be in the form of the table with "yes" or "no" written in each box.

   • 第八組

A	B	O	o	Ω	ω	Θ

4. Ext. 2-1
   Show that there exists two non-negative functions f and g (i.e. f, g : N → R*) such that f≠O(g), f≠θ (g), and f≠Ω(g).

   • 第五組

5. Problem 3-3 Ordering by asymptotic growth rates

   • Rank the following functions by order of growth; that is, find an arrangement g₁, g₂, …, g₃₀ of the functions satisfying g₁ = Ω(g₂), g₂ = Ω(g₃), …, g₂₉ = Ω(g₃₀). Partition your list into equivalence classes such that functions f(n) and g(n) are in the same class if and only if f(n) = Ѳ(g(n)).
     
     
     
     
     
   • Give an example of a single non-negative function f(n) such that for all functions g_i(n) in part (a), f(n) is neither O(g_i(n)) nor Ω(g_i(n)).
   • 第四組

6. Solve the recurrence by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

   • 第十九組

7. Use a recursion tree to determine a good asymptotic upper bound on the recurrence . Use the substitution method to verify your answer.

   • 第二十組