**Assignment 01: Loop Invariants, Asymptotic Notation, and Total Running Time** *Due Thu Feb 04 11:00 PM Pacific Time* [Back to Algorithms](http://cs.pomona.edu/classes/cs140/) # Learning Goals - Perform a proof by loop invariant. - Analyze code and proof its asymptotic complexity. - Identify differences in code performance from data. # Grading This assignment will be graded pass/no-pass. You must receive at least 80% of the available points to pass the assignment. Questions are equally weighted and will be graded using the following rubric items: - Correct (the answer is fully correct) - 100% - Mostly correct (the answer has only minor mistakes) - 80% - Incorrect (the answer has more than just minor mistakes) - 0% **Graders will provide feedback to let you know why you missed points.** # Overview For this assignment you will be submitting your hand written answers to [the questions in this PDF](resources/time-complexity-loops.pdf). You may work on this assignment alone or with a partner (**send me a message on Slack if you want me to assign you to work with a random partner**); in either case, you will submit a **single** assignment to [gradescope](https://www.gradescope.com/). Three key points: 1. you should either print the PDF and write your answers directly on the printed sheet, or add annotations to the PDF with Edge (Windows) or Preview (OSX) (using the correct format and spacing will help us grade), 2. ensure that the uploading partner adds the other partners after submission, and 3. **if you have any questions please ask them on [Slack](https://divisionii.slack.com/archives/G019H3HEXBK)**. # Code for Insertion Sort The following is an implementation of the Insertion Sort algorithm that we discussed in class. You can copy this program into a text file named [`insertion_sort.py`](resources/insertion_sort.py) (or download it using that link) and run it with the following command: ~~~bash python3 insertion_sort.py ~~~ where `` is one of the following inputs files that you will need to download ([click here to download a zip file with all input files](resources/input-files.zip)): - [decreasing10.txt](resources/decreasing10.txt) - [decreasing1000.txt](resources/decreasing1000.txt) - [decreasing10000.txt](resources/decreasing10000.txt) - [increasing10.txt](resources/increasing10.txt) - [increasing1000.txt](resources/increasing1000.txt) - [increasing10000.txt](resources/increasing10000.txt) - [random10.txt](resources/random10.txt) - [random1000.txt](resources/random1000.txt) - [random10000.txt](resources/random10000.txt) ~~~python linenumbers #!/usr/bin/env python3 import sys from timeit import default_timer as timer def inerstion_sort(array): for j, key in enumerate(array[1:], 1): i = j - 1 while i >= 0 and array[i] > key: array[i + 1] = array[i] i -= 1 array[i + 1] = key return array def main(): filename = sys.argv[1] with open(filename, 'r') as input_file: n = int(input_file.readline()) array = [int(v) for v in input_file.readlines()] start_time = timer() sorted_array = inerstion_sort(array) end_time = timer() # print(all([x < y for x, y in zip(sorted_array[0::2], sorted_array[1::2])])) print('Elapsed time:', end_time - start_time) if __name__ == '__main__': main() ~~~ # Code for Merge Sort Below is a (fairly inefficient) code listing for Merge Sort using Python3. You will need to run this code in the same way described the Code for Insertion Sort section. You can [download this file here](resources/merge_sort.py). ~~~python linenumbers #!/usr/bin/env python3 import sys from timeit import default_timer as timer def merge(left, right): combined = [] i, j = 0, 0 for k in range(len(left) + len(right)): if j >= len(right) or (i < len(left) and left[i] < right[j]): combined.append(left[i]) i += 1 else: combined.append(right[j]) j += 1 return combined def merge_sort(array): if len(array) <= 1: return array left = merge_sort(array[:len(array)//2]) right = merge_sort(array[len(array)//2:]) return merge(left, right) def main(): filename = sys.argv[1] with open(filename, 'r') as input_file: n = int(input_file.readline()) array = [int(v) for v in input_file.readlines()] start_time = timer() sorted_array = merge_sort(array) end_time = timer() # print(all([x < y for x, y in zip(sorted_array[0::2], sorted_array[1::2])])) print('Elapsed time:', end_time - start_time) if __name__ == '__main__': main() ~~~ # Submitting Your Assignment You will turn-in your assignment on [gradescope](https://gradescope.com/). **Only one partner should submit your PDF.** The submitter will add the other partner through the gradescope interface. Additional details for using gradescope can be found here: - [Submitting an Assignment](https://help.gradescope.com/article/ccbpppziu9-student-submit-work) - [Scanning Work on a Mobile Device](https://help.gradescope.com/article/0chl25eed3-student-scan-mobile-device) - [Adding Group Members](https://help.gradescope.com/article/m5qz2xsnjy-student-add-group-members) - [gradescope Student Help Center](https://help.gradescope.com/category/cyk4ij2dwi-student-workflow)