Unlock document.
This document is partially blurred.
Unlock all pages and 1 million more documents.
Get Access
Algorithms: Sequential, Parallel and Distributed 2-1
Chapter 2
Design and Analysis Fundamentals
At a Glance
Table of Contents
• Overview
• Objectives
• Instructor Notes
• Solutions to Selected Exercises
Algorithms: Sequential, Parallel and Distributed 2-2
Lecture Notes
Overview
In Chapter 2 we introduce the basic concepts of algorithm design and analysis, including
the formalization of the best-case, worst-case, and average complexities of an algorithm.
We also describe some general guidelines for algorithm design, and review the role of
recursion in the design of algorithms. The role of data structures in designing efficient
algorithms is also discussed. A brief overview of the major design strategies for
Chapter Objectives
This chapter establishes the foundation for the design and analysis of algorithms. After
completing the chapter the student will know:
• The importance of the proper choice of a basic operation when analyzing the performance
of a given algorithm
• The importance of an appropriate measure of the input size when analyzing an algorithm
• The formal definitions of best-case, worst-case, and average behavior of algorithms.
• The proper choice of a data structure can impact the efficiency of an algorithm
• The importance of recursion in algorithm design
• The design and performance of some standard comparison-based algorithms for searching
and sorting and finding the maximum and minimum elements in a list
• How the tree of recursive calls can be used to analyze the efficiency of recursive algorithms
such as mergesort and quicksort
Instructor Notes
Parts of this chapter might be review for students having a strong background in data structures.
In any case, we expect the student to be at least familiar with the linear data structures
contained in Appendix B. However, the material in Section 2.5, where the complexities of an
algorithm is formally defined, is critical for the remainder of the text, and should at least be
reviewed carefully. These notions are illustrated by examples which are also probably familiar
to many of the students, but where the complexity analysis might not be as well understood.
size for an algorithm computing xn. When discussing complexities, the instructor might want to
mention that the principal use of determining the best-case complexity B(n) is to obtain a
lower bound for the average complexity A(n) for any probability distribution on the sample
space In of all inputs of size n. The instructor might also wish to emphasize the A(n) is only
Solutions to Selected Exercises
Section 2.2 Recursion
2.3 a)
procedure DecimalToBinary(n, B[0:m – 1])
Input: n (a decimal integer)
Output: B[0:m – 1] (a binary string representing n, where B[i] is the (i + 1)st most
significant bit of n)
b) We assume that we have function
function BinaryToDecimal(B[0:m – 1])
2.5 We use the strong form of induction, where the result is clearly true for n = 1 (basis step).
Assume true for all k < n.
Then, we have:
2.6 Let t(k) denote the number of times fib(n-k) is computed when Fib is invoked with input n,
2.7 a) Let a = fib(n), b = fib(n-1) and c = fib(n-2). Since a = b+c, we have a-b = c and
2.8 Let (a,b) be a pair of m-digit integers and let g=gcd(a,b). Then, gcd(a/g,b/g)=1, and the
sequence of iterations performed by EuclidGCD for the pair (a/g,b/g) is exactly the same as
for the pair (a,b), except that all the integers involved are divided by g. It follows that the
2.9 Basis step: fib(1) =1=2-1= fib(3) -1.
Induction step: Assume that fib(1) + fib(2) + + fib(k) = fib(n+2) – 1. Then we have
2.10 a) Basis step:
fib(1)
fib(2)
=1
1
=0 1
1 1
10
1
.
Induction step: Assume that
fib(k)
fib(k+1)
=0 1
1 1
k0
1
. Then we have
=
=
+
1
0
11
10
11
10
1
0
11
10 1kk
11
10
+)1(
)(
kfib
kfib
=
++
+
)1()(
)1(
kfibkfib
kfib
=
+
+
)2(
)1(
kfib
kfib
b) We can compute the powers
n
11
10
using the binary method (see Chapter 1) in (logn)
steps. Each step involves multiplying two 2-by-2 matrices, which can be done using 8
multiplications. Hence, the total number of multiplications required to compute fib(n)
belongs to (logn).
Section 2.3 Data Structures and Algorithm Design
2.12 We assume that the nodes of the linked list are records of the type
ListNode = record
Info: InfoType
Next: →ListNode
end
2.13 b) We assume that the nodes of the stack are records of the same type as described in
exercise 2.12, and that the pointer variable Top points to the top of the stack (beginning of
the linked list). Top = null indicates an empty stack.
2.14 a) Before enqueuing, the test
Front = (Rear +1) mod Max
is used to determine whether the queue is full. Before dequeuing, the test
Algorithms: Sequential, Parallel and Distributed 2-7
if NextAvail ≠ 0 then
index
1
2
3
4
5
6
7
8
L
7
15
23
3
11
Next
7
4
0
2
3
Start = 6
Avail
5
8
0
NextAvail = 1
Inserting an element x at the start of the linked list is accomplished by the following
pseudocode
if NextAvail ≠ 0 then
Save ← Start
2.16 Sort one of the lists and then perform binary search with each element in the second list
2.17 Note that this is basically a sequential version of the binary fan-in method described on
2.18 See the algorithm NaiveStringMatcher on pp. 632-633.
2.19 a) The algorithm based on simply making two scans of the list performs 2n-1 list
comparisons for any list of size n. The following algorithm is similar to MaxMin2. We note
Procedure LargestSecondLargest(L[0:n – 1],Largest,SecondLargest)
2.20 This exercise really anticipates the material developed in Chapter 6. Assume for simplicity
that n is even. Then if pi denotes the probability that we are searching for the ith element in
2.23 In case X is not in the list, then the final value of low in the procedure BinarySearch is
such that X should be inserted right after position low if X > L[low], or right before position
low if X < L[low]. This property can then be easily used to make the modification called for
by the exercise.
2.24
function BinSearchRec(L[0:n – 1],low,high) recursive
or -1 if X is not in the list
if low ≤ high then
mid ←
2/)( highlow +
2.26 Suppose L[0:n – 1] is a list of distinct integers sorted in increasing order. Then the
following algorithm returns an index i with L[i] = i, or returns 0 if no such index exists.
Algorithms: Sequential, Parallel and Distributed 2-10
function FixedPt(L[0:n – 1])
Input: L[0:n – 1] (a list of n distinct integers)
2.32 a) Given the array L[0:n – 1], we assume that our linked list version given below creates
an auxiliary array Link[0:n – 1] of integers representing indices of L, and that the array Link
and the integer Start implement a linked list pointing to the array L in increasing order. In
other words, the array L in increasing order is: L[Start], L[Link[Start]], L[Link[Link[Start]]],
... , .
temp ← A[i]
//See if A[i] belongs at start of list
if temp ≤ A[Start] then
Link[i] ← Start
Start ← i
endfor
end LinkInsertionSort
b) LinkInsertionSort is made stable by replacing the statement
if temp A[Start] then
with the statement
2.33 a)
procedure InsertionSortRec(L[0:n – 1]) recursive
Input: L[0:n – 1] (a list of size n)
Output: L[0:n – 1] sorted in increasing order
2.34 a)
procedure SelectionSort(L[0:n – 1])
Input: L[0:n – 1] (a list of size n)
Output: L[0:n – 1] sorted in increasing order
2.35
procedure SelectionSortRec(L[0:n – 1], high) recursive
Input: L[0:n – 1] (a list of size n), high (integer)
Output: L[0:high] sorted in increasing order
2.36 a)
procedure BubbleSort(L[0:n – 1])
Input: L[0:n – 1] (a list of size n)
Output: L[0:n – 1] sorted in increasing order
i ← 1
endwhile
end BubbleSort
Algorithms: Sequential, Parallel and Distributed 2-13
Algorithms: Sequential, Parallel and Distributed 2-14
b) The best case occurs when list is already sorted, in which case we have:
c)
procedure TwoWayBubbleSort(L[0:n – 1])
Input: L[0:n – 1] (a list of size n)
Output: L[0:n – 1] sorted in Increasing order
First ← 0
Last ← n – 2
SwapFlag ← .true.
interchange (L[j], L[j-1])
CurFirst ← j
SwapFlag ← .true.
endif
endfor
First ← CurFirst
2.40 To see an applet illustrating the action of Link Mergesort, including java code for the
2.43 a) When a decreasing list of size n is input to QuickSort, it generates a recursive tree of
calls that is essentially a path of length n – 1.
b) QuickSort is tail-recursive, so we look to translate out the second recursive call.
Unfortunately, this will not improve the worst-case depth of the recursive tree of calls as
described in part a). However, a slight variation does the job. The idea is to make a recursive
