**CS10051
Knowledge Summary - Chapter 3 - Paul Durand**

Sections 001/002/005/006 - Spring 2007

1. What are the
four attributes we desire in any algorithm? Briefly explain each attribute? (p.
78-82)

2. Use Gauss's approach to summing the integers from 1 thru 100 to find
a general formula for the sum of the consecutive integers from 1 thru n (p. 80)

3. What is benchmarking? (p. 81)

4. Discuss why this statement
from the book is true, (p. 82):

*It
is the number of steps each algorithm requires, not the time an algorithm takes
on a particular machine, that is
important for comparing two algorithms that do the same task.*

5. What is
the 'data-cleanup' problem? (p. 98)

6. Three algorithms for solving the data
cleanup problem were discussed in the book, Shuffle-Left, Copy-Over and
Converging-Pointers (pp. 98-105)

Using the list below

0 |
24 |
16 |
0 |
36 |
42 |
23 |
21 |
0 |
27 |

a. Describe
how each algorithm processes the list. Show the final state of the list after
each algorithm is executed.

b.
Discuss the space efficiency of each algorithm , i.e. how much extra space does
it require beyond that to store the original list.

c.
Discuss the time efficiency of each algorithm, i.e. how many and what kind of
steps does it take to process the list

d. Generalize
the results from b. and c. to express the time and space efficiency in
terms of the size of the list, n.

7. The algorithm for the sequential
search problem is given on page 83 of the text. What is the time-efficiency
of this algorithm in the Best and Worst cases? Justify your answer.

8. What
do we mean when we say the Order of Magnitude of an algorithm is n, i.e.
*O*(n)?

9. What is the order of magnitude of the sequential search algorithm?

10.
Give an example of a
*O*(n^{2}) algorithm?

11. Suppose that we have
determined that the number of steps a certain algorithm performs is given by
the formula 3 n^{2} + 13n + 4. What is its order of magnitude?
Justify your answer.

12. Sorting is a problem that has been studied a lot
in computer science. The Selection Sort algorithm is one solution to this problem.
(p. 87-93)

a. Explain briefly how this algorithm
works using as input the list 5,7,2,8,3.

b.
Analyze this algorithm. Given a list of size n, how many steps are in the execution
trace in terms of n? (Your answer should include n^{2}, n and constants. Include
peripheral tasks done only once, data swapping steps and data comparison steps.)

c. Based on answer b. What is the
order of magnitude of the Selection Sort Algorithm

d.
Why don't we talk about Best and Worse case performance for the Selection Sort
algorithm?

13. The Binary Search Algorithm is discussed on pages
105-111.

a. In order for this algorithm to work,
there is a requirement on the list of input data. What is it?

b.
Using the following input list explain briefly how the binary search algorithm
would search for the name Ginny.

Ann |
Bob |
Ellie |
Ginny |
Horace |
Laurie |
Norm |
Randy |
Sue |

c. Using the above list, draw a binary search tree diagram
as on page 107 in the text. Label each circle (node) in the 'tree' with the proper
name. Note that this list has
9 names, and the example in the book was drawn for the 7-name example in the
book. You diagram will look different.

d. Using the diagram
from part c. above, How many comparisons does the algorithm need to find
the name 'Ginny'?

e. Also, How many comparisons are needed
to find that 'Sally' is not on the list.

f. In general,
what is the worst case number of comparisons this algorithm performs, in terms
of the size of the list, N?

g. What is the order of magnitude
of the binary search algorithm?

14.
We looked at a simple algorithm to solve the pattern matching problem. Explain
why it is order of magnitude *O*(n
x m), where n is the length of the text and m is the length of the
pattern we are searching for.(p.64-69, 111-112).

15. In section 3.5 the book discusses
the problem Traveling Salesman problem: "How do I leave from home,
visit all my clients exactly once and return home, hopefully in the shortest
total distance ?", however they refer to it as finding a Hamiltonian Circuit
in a graph. Show that the proposed 'brute force' algorithm is
*O*(2^{n})?

16.
An algorithm of order
*O*(2^{n}) is called an exponential algorithm.
They also refer to it as 'polynomially unbounded'. What does this mean? Page
113-115

17.
If there exists no polynomially bounded solution to a problem, it is called
an intractable problem. This means that they are solvable, but the solution
takes so long as to be "basically useless". What are some of these
problems?p 114-116

18. We have seen several classes of algorithms in this chapter,*
O*(1), *O*(lg n),
*O*(n),
*O*(n^{2}),
*O*(2^{n}).
What is the general shape of the work vs. n graphs for these? Page 115

`NOTE: This is a summary of the topics covered in class.
Although it is presented as a list of questions, it is not meant to be
representative of questions asked on exams in this course. The page numbers
refer to the area of the book in which these topics are discussed.`