Lab 3 -- Algorithm Analysis Practice

Computer Science 385
Design and Analysis of Algorithms

Spring 2018, Siena College

Home Syllabus Schedule

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

You will be assigned a partner to work with on this lab. Only one submission per group is needed.

Group members:

Learning goals:

To practice with developing algorithms to solve a given problem
To practice reasoning about algorithm complexity
To work with the definitions of Big O, Big Ω, and Big Θ

Submitting

Once all written items are initialed to indicate completion, turn in one copy of this handout. Be sure names of all group members are clearly on the first page.

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)