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

    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²) algorithm?
11. Suppose that we have determined that the number of steps a certain algorithm performs is given by the formula 3 n² + 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², 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.

   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ⁿ)?
16. An algorithm of order O(2ⁿ) 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²), O(2ⁿ). 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.