**Assignment 1: Loop Invariants, Asymptotic Notation, and Total Running 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.
- Convert pseudocode to Python.
- Identify differences in code performance from data.
# Grading
This assignment will be graded as pass/no-pass by a TA. To pass the assignment, you must
1. Complete every question in the PDF and submit your answers to gradescope.
2. Complete the programming component and submit your answers to gradescope.
3. Schedule a time to meet with a TA (see section Important Dates for deadlines).
4. Walk the TA through your answers.
5. The TA will then either
- mark your assignment as 100% on gradescope, or
- inform you that you have some corrections to make.
6. If corrections are needed, then you will need to complete them and then schedule a new time to meet with the TA.
If you have concerns about the grading walk-through, you can meet with me after you've first met with a TA.
# Walk-Through Guidelines
- Walk-through should take no more than 20 minutes. You should be well prepared to walk a TA through your answers.
- You may not make any significant corrections during the walk-through. You should plan on making corrections afterward and scheduling a new walk-through time. Mistakes are expected--nobody is perfect.
- We will use the Google Sheet found on Slack to schedule your walk-through. This helps TAs manage their time and balance the grading load.
- You must be prepared to explain your answers and justify your assumptions. TAs do not need to lead you to the correct answer during a walk-through--this is best left to a mentor session.
# Important Dates
- You should start this assignment Sep 2
- Submit your work prior to end of day Sep 9
- You must meet with a TA for grading prior to end of day Sep 14
+ **It is a good idea to complete the assignment as early as possible**
+ **You must book a time to meet with a TA**
- You should complete corrections by end of day Sep 16
# Overview
This assignment includes two parts:
1. Answer the [question in this PDF](resources/time-complexity-loops.pdf).
2. Code the Insertion Sort algorithm in Python (must be compatible with Python 3.8).
You may work on this assignment alone or with a partner (**I much prefer you to work with a partner**). Please send me a message on Slack if you want me to assign you to work with a random partner. Whether you work alone or with a partner, only one partner will submit a both parts 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://pomona-division-ii.slack.com/archives/C02DGGLQBUG)**.
# Example Execution
I always like to start by showing you the end result.
If you do not see an animation above this line (or if you see the animation but you don't see the progress bar), you will need to refresh the page (sometimes more than once). Or you can go directly to the player: https://asciinema.org/a/433623
**You can copy and past from the above animation!**
# Insertion Sort
Since this is more of a warm-up algorithm, all you need to do is convert the pseudocode below into a proper Python function.
~~~text linenumbers
# Sort the given array into nondecreasing order.
#
# Args
# array : an input array of numbers
#
# Return
# the original array in nondecreasing order
#
FUNCTION InsertionSort(array)
FOR j IN [1 ..< array.length]
key = array[j]
i = j - 1
WHILE i ≥ 0 && array[i] > key
array[i + 1] = array[i]
i = i - 1
array[i + 1] = key
RETURN array
~~~
I'd encourage you to watch the example execution above and imagine how you would write a program to replicate the command line interaction. After you've had a chance to think about it (or an attempt at coding it up) feel free to fill in this skeleton code with your `insertion_sort` function: [`insertion_sort_skeleton.py`](resources/insertion_sort_skeleton.py). Note that you will need to rename this file to `insertion_sort.py`.
You will run your program with the following command:
~~~bash
python3 insertion_sort.py