This homework assignment is entirely a written one, no machine problems. It is based on Chapters 1 and 2 of the text.

General homework requirements (non-machine problems)

• Homework is due at the beginning of class.
  
  
• Late homework: Grade is reduced 10% x number of classes late it is handed in. Late homework can be handed in to Professor Futrelle or to the TA, Arvind Meda.
  
  
• Hand in one or more sheets of paper stapled (not paperclipped) together.
  
  
• At the top of the first page put your name, your ID number, your email address, the date, "COM1201", and "Homework 1". If you attach additional pages, put your name on each page, at a minimum. Only hardcopy will be accepted (due to the need for mathematical notation and diagrams).
  
  
• The implementation of algorithms in a specific high-level language, and the practical aspects of testing algorithms for correctness and performance. You'll get a chance to further develop your programming skills.

Chapter 1 problems

For these two problems, you are required to generate 5 "random" pairs of digits. Do so in the following way: Use a white pages phone book to find the numbers. Pick five pages at random and one phone number from each page. Use the 3rd and 4th digits from the right as your pair of digits. Thus 373-4296 would generate a 4, 2 pair. If the two digits are the same, use another phone number, and do this until you have distinct pairs (4, 2 is the same as 2, 4). You must write down what phone book and what pages you used to generate your numbers.

If you work in a group with other people, have one person pick the sequence of pairs and then have everyone solve the problems separately. Then compare your results. But when you hand in your work, every student must hand in problems based on distinct sets of numbers.

Problem 1

Create a figure like Figure 1.3 that shows the operation of the Quick-find algorithm. For the same data, draw a figure like Figure 1.4. In addition to drawing the figure, add a few sentences of comment that discuss what the results are, e.g., how many distinct sets there are at each stage.

Problem 2

For this problem use the data from problem 1 and follow the steps for problem 1 except that you use the Quick-union algorithm, Figures 1.6 and 1.7.

Chapter 2 problems

The first two problems involve computing certain values of N. Rather than trying to do this precisely, which is non-trivial, estimate the values by making a table of values of the expressions involved for N = 2^k (1, 2, 4, 8, ....) From the table you can estimate the values in the ranges asked for. (If you want to refine your answer a bit more you could use the set N = 2^k/2, for k > 1, noting that lg(2^1/2) = 1/2.)

Problem 3 -- Do exercise 2.5, page 43.

Problem 4 -- Do exercise 2.6, page 43.

Problem 5 -- Do exercise 2.40, page 52. For this problem note that the sum of n^k is N^(k+1)/(k+1) + O(N^k)

Problem 6 -- Do exercise 2.47, page 58.

Go to Syllabus and Calendar page for COM1201

Return to Prof. Futrelle's home page