Page 252 - Discrete Mathematics and Its Applications

3.3 Complexity of Algorithms 231

a) Show that Algorithm 1 in Section 3.1 is an optimal 38. Find the complexity of the greedy algorithm for schedul-
algorithm with respect to the number of comparisons ing the most talks by adding at each step the talk with the
of integers. [Note: Comparisons used for bookkeep- earliest end time compatible with those already scheduled
ing in the loop are not of concern here.] (Algorithm 7 in Section 3.1). Assume that the talks are
b) Is the linear search algorithm optimal with respect to not already sorted by earliest end time and assume that
the number of comparisons of integers (not including the worst-case time complexity of sorting is O(n log n).
comparisons used for bookkeeping in the loop)?
39. Describe how the number of comparisons used in the
25. Describe the worst-case time complexity, measured in worst case changes when these algorithms are used to
terms of comparisons, of the ternary search algorithm search for an element of a list when the size of the list
described in Exercise 27 of Section 3.1. doubles from n to 2n, where n is a positive integer.
26. Describe the worst-case time complexity, measured in a) linear search b) binary search
terms of comparisons, of the search algorithm described
40. Describe how the number of comparisons used in the
in Exercise 28 of Section 3.1.
worst case changes when the size of the list to be sorted
27. Analyze the worst-case time complexity of the algorithm
doubles from n to 2n, where n is a positive integer when
you devised in Exercise 29 of Section 3.1 for locating a
these sorting algorithms are used.
mode in a list of nondecreasing integers.
a) bubble sort b) insertion sort
28. Analyze the worst-case time complexity of the algorithm
you devised in Exercise 30 of Section 3.1 for locating all c) selection sort (described in the preamble to Exer-
modes in a list of nondecreasing integers. cise 41 in Section 3.1)
29. Analyze the worst-case time complexity of the algorithm d) binary insertion sort (described in the preamble to Ex-
you devised in Exercise 31 of Section 3.1 for finding the ercise 47 in Section 3.1)
first term of a sequence of integers equal to some previous An n × n matrix is called upper triangular if a ij = 0 when-
term.
ever i> j.
30. Analyze the worst-case time complexity of the algorithm
you devised in Exercise 32 of Section 3.1 for finding all 41. From the definition of the matrix product, describe an
terms of a sequence that are greater than the sum of all algorithm in English for computing the product of two
previous terms. upper triangular matrices that ignores those products in
the computation that are automatically equal to zero.
31. Analyze the worst-case time complexity of the algorithm
you devised in Exercise 33 of Section 3.1 for finding the 42. Give a pseudocode description of the algorithm in Exer-
first term of a sequence less than the immediately preced- cise 41 for multiplying two upper triangular matrices.
ing term.
43. How many multiplications of entries are used by the al-
32. Determine the worst-case complexity in terms of com-
gorithm found in Exercise 41 for multiplying two n × n
parisons of the algorithm from Exercise 5 in Section 3.1 upper triangular matrices?
for determining all values that occur more than once in a
sorted list of integers. In Exercises 44–45 assume that the number of multiplications
of entries used to multiply a p × q matrix and a q × r matrix
33. Determine the worst-case complexity in terms of compar- is pqr.
isons of the algorithm from Exercise 9 in Section 3.1 for
determining whether a string of n characters is a palin- 44. What is the best order to form the product ABC if A, B,
drome. and C are matrices with dimensions 3 × 9, 9 × 4, and
34. How many comparisons does the selection sort (see 4 × 2, respectively?
preamble to Exercise 41 in Section 3.1) use to sort n 45. What is the best order to form the product ABCD if A, B,
items? Use your answer to give a big-O estimate of the C, and D are matrices with dimensions 30 × 10, 10 × 40,
complexity of the selection sort in terms of number of 40 × 50, and 50 × 30, respectively?.
comparisons for the selection sort.
∗ 46. Inthisexercisewedealwiththeproblemof stringmatch-
35. Find a big-O estimate for the worst-case complexity in
ing.
terms of number of comparisons used and the number of
a) Explain how to use a brute-force algorithm to find
terms swapped by the binary insertion sort described in
the first occurrence of a given string of m characters,
the preamble to Exercise 47 in Section 3.1.
called the target, in a string of n characters, where
36. Show that the greedy algorithm for making change for n
m ≤ n, called the text.[Hint: Think in terms of find-
centsusingquarters,dimes,nickels,andpennieshasO(n)
complexity measured in terms of comparisons needed. ing a match for the first character of the target and
checking successive characters for a match, and if
Exercises 37 and 38 deal with the problem of scheduling the they do not all match, moving the start location one
most talks possible given the start and end times of n talks.
character to the right.]
37. Find the complexity of a brute-force algorithm for
scheduling the talks by examining all possible subsets b) Express your algorithm in pseudocode.
of the talks. [Hint: Use the fact that a set with n elements c) Give a big-O estimate for the worst-case time com-
n
has 2 subsets.] plexity of the brute-force algorithm you described.