Assignment 1: Loop Invariants, Asymptotic Notation, and Total Running Time

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. Meet with your TA during your learning community sessions. I prefer both partners to be present during the walk-through, but you can each meet with the TA separately if needed.
  4. Walk the TA through your answers. Do not expect to make corrections during the walk-through.
  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 conduct a new walk-through with a TA.

If you have concerns about the grading walk-through, you can meet with me after you’ve first met with a TA.

Overview

This assignment includes two parts:

  1. Answer the question in this 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.

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, for example, 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.

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.

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.

# 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. Note that you will need to rename this file to insertion_sort.py.

You will run your program with the following command:

python3 insertion_sort.py <input_file>

where <input_file> is one of the following inputs files that you will need to download (click here to download a zip file with all input files):

Code for Merge Sort

Instead of asking you to implement both insertion_sort and merge_sort I am providing you with a completed implementation of merge_sort. Note that this is not an efficient implementation, just a simple one implemented by converting pseudocode from my slides.

You will run this program similar to how you ran insertion_sort.py:

python3 merge_sort.py <input_file>

Submitting Your Assignment

You will submit your PDF assignment on gradescope. Only one partner should submit your PDF. The submitter will add the other partner through the gradescope interface.

You will also submit your code to gradescope. Your file must be named insertion_sort.py. Only one partner should submit your code. The submitter will add the other partner through the gradescope interface. Please add your names in comments at the top of the file.

To pass the autograder, your output must exactly match the expected output. Your program output should be similar to the example execution above, and the autograder on gradescope will show you the correct output if yours is not formatted properly. You can use text-compare to compare your output to the expected output and that should give you an idea if you have a misspelled word or extra space (or if I do).

I’ve enabled a leaderboard for the assignment. You do not need to worry about it affecting your grade. I just thought it looked like a cute feature. Feel free to give yourself (your group) any name you’d like for the leaderboard.

Additional details for using gradescope can be found here: