Lab 3 -- Algorithm Analysis Practice

Computer Science 385
Design and Analysis of Algorithms

Spring 2017, Siena College

Lab 3: Algorithm Analysis Practice
Due: Start of your next lab session

In this week's lab, you will think about some algorithms and practice some of the algorithm analysis techniques we have been learning in class.

You will be assigned a partner to work with on this lab. Please work right on the handout. Have your instructor check your work periodically (it does not need to be after each question completed). Only one submission per group is needed.

Textbook Exercises

Question 1: Levitin Exercise 1.1.6, part a, p. 8. (4 points)

Question 2: Levitin Exercise 1.1.6, part b, p. 8. (2 points)

Question 3: Levitin Exercise 1.1.8, p. 8. (3 points)

Question 4: Levitin Exercise 1.2.1, p. 17. (5 points)

Question 5: Levitin Exercise 1.4.4, part a, p. 37. (4.5 points)

Question 6: Levitin Exercise 1.4.4, part b, p. 37. (4.5 points)

Question 7: Levitin Exercise 2.1.1, p. 50. (6 points)

Question 8: Levitin Exercise 2.1.4 part a, p. 51. (5 points)

Question 9: Levitin Exercise 2.1.4 part b, p. 51. (6 points)

Question 10: Levitin Exercise 2.1.8, p. 51. (6 points, 1 each)

Question 11: Levitin Exercise 2.1.9, p. 52. (12 points)

Question 12: Levitin Exercise 2.2.2, p. 58-59. (8 points)

Question 13: Levitin Exercise 2.2.3, p. 59. Use limits to prove your answers. (20 points)

Question 14: Levitin Exercise 2.2.5, p. 60. (6 points)

Question 15: Levitin Exercise 2.2.11, p. 61. (8 points)