Lab 7

Program 3 Note

If you are looking for a programming partner for program 3, please let your lab TA know at the beginning of the lab period or send him an e-mail with cs221-xx partner request as the subject.

Lab Partners

You may work with one partner on this in lab.

Objective

The purpose of this in-lab is to give you practical experience taking code and figuring out its statement count and time complexity. You will be asked to do something similar on the midterm tomorrow, so please make sure you understand this lab.

Task (10 points)

Each correct answer is worth 5/7 of a point. Answer the following on a sheet of paper. If it helps you to print out the code that you are analyzing, feel free to do so.

1. What is the statement count of the swap method in QuickSort.java from the lecture code on February 27?
2. What is the time complexity of this swap method?
3. Prove that the time complexity is correct.
4. What is the statement count of the partition method in Quicksort.java from the lecture code on February 27? Assume that the pivot item is the largest item. Show your work.
5. What is the time complexity of this partition method?
6. Prove that the time complexity is correct.
7. What is the statement count of the findMin method in Sort.java from the lecture code on February 22? Assume that the array is sorted in descending order.
8. What is the time complexity of the findMin method?
9. What is the best case statement count of the insert method in Sort.java from the lecture code on February 22?
10. Explain what leads to the best case.
11. What is the best case time complexity of the findMin method?
12. What is the worst case statement count of the insert method in Sort.java from the lecture code on February 22?
13. Explain what leads to the worst case.
14. What is the worst case time complexity of the findMin method?

If Time Remains

Study for the midterm tomorrow. If you don't understand something, please ask for assistance!

What to Submit

Hand in your answers to your lab TA.