Data Structures and Algorithms

Lab 4: Algorithmic Analysis

Due on Sunday, February 21st at 11:59 PM. This is an individual lab. You are to complete this lab on your own, although you may discuss the lab concepts with your classmates. Remember the Academic Integrity Policy: do not show your code to anyone outside of the course staff and do not look at anyone else’s code for this lab. If you need help, please post on the Piazza forum or contact the instructor or ninjas. If you have any doubts about what is okay and what is not, it’s much safer to ask than to risk violating the Academic Integrity Policy.

Overview

You will complete this lab in two parts. In the first part, you will provide written answers to questions about algorithmic analysis. In the second part, you will determine the complexity of some pseudocode functions; you will then determine which of a collection of implementations of these functions are which, matching each implementation with the pseudocode based upon its apparent complexity. This lab will improve your understanding of:

Big-\(O\) notation
Proofs of correctness with respect to algorithms
The empirical implications of complexity bounds

You will submit this assignment in electronic form by committing and pushing files to the GitHub server through your repository for this lab. This lab is to be completed individually, so your repository can be cloned via git@github.swarthmore.edu:cs35-s16/lab04-<your-username>. Your submission must take one of the following forms:

A well-formatted raw text file (.txt) written in a text editor.
An Adobe PDF file containing formatted text.
A LaTeX source file (.tex) buildable by pdflatex on the CS network.

To provide specific examples, your submission may not be any of the following:

A scan of a handwritten document (even in PDF form).
A Microsoft Word file or similar word processor document (although you may export a PDF from such a document).
A piece of paper turned in by hand.

Warm-Up Exercises

You can find warm-up exercises for this lab here. The warm-up exercises will not be graded, but we will do some of them during the lab section so that you are prepared to approach this assignment on your own.

Part I: Short Answer Questions

For each function below, justify that it has the specified Big-\(O\) complexity. a. \(4n^4 + 2n^2 + \frac{1}{2}n\) is \(O(n^4)\) b. \(2^n + n^2\) is \(O(2^n)\)
Prove the following claims by induction: a. For all \(n \geq 1\), \(\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}\) b. For all \(n \geq 1\), \(\sum_{i=1}^{n} \frac{1}{2^i} = \frac{2^n-1}{2^n}\)
The function maximum, given below in pseudocode, takes as input an array \(A\) of size \(n \geq 1\) of numbers and returns the largest number in the array. Using induction and loop invariants, prove that the maximum function works correctly. (HINT: you should use the loop invariant “\(S(k):\) at the beginning of the loop iteration where \(i=k\), max is equal to the largest of the first \(i\) elements of the array”.)
Describe an algorithm for finding both the minimum and maximum (simultaneously) of \(n\) numbers using no more than \(3n/2\) comparisons of elements in \(A\). Your algorithm may return more than one value by writing e.g. Return \(x,y\). Note that the above pseudocode finds the maximum value in a list using \(n-1\) comparisons.

Part II: Mystery Functions

In this part of the lab, you will first analyze six simple loop structures and determine their runtime complexity in terms of Big-\(O\) notation. Then, using the provided program function_timer, you will graph the empirical runtimes of these functions.

Functions

Begin by identifying the Big-\(O\) runtime for each of the following functions. Provide a brief justification of your answer; a sentence or two should do. Give the strictest Big-\(O\) you can find (don’t give \(O(2^n)\) if the function is also \(O(n)\)) and leave out any unnecessary terms (give \(O(n^2)\) rather than \(O(n^2+3n)\)).

Using `function_timer` to Inspect the Functions

Each of the above functions has been implemented and packaged into an executable function_timer that was provided to you in your repository for this lab. The function_timer program will provide empirical runtime data for each function in a form that can be graphed by another tool called gnuplot.

To use this program, you must pick the following:

Which function(s) to plot. For each function, you must provide a command-line argument in the form -2, -3, etc.
The minimum and maximum values for \(n\). Remember: for slow algorithms, \(n\) should be small or the program may take a very long time. For fast algorithms, you’ll need to give a very large \(n\) or you won’t be able to see anything meaningful on the plot. Start with small \(n\) for each function and work your way up.

For instance, you can graph functions 1 and 3 within \(10 \leq n \leq 100\) by running this command:

./function_timer -1 -3 -n 10 -m 100 | gnuplot

After a moment, a window will pop up with an image like this:

Plot for functions 1 and 3 between n=10 and n=100

Note the “pipe” character (|) in the command above; this feeds the output of function_timer to the input of gnuplot so it can graph the results for you.

If you want to save the image that gnuplot makes for you, you can add a -s parameter to function_timer like so:

./function_timer -1 -3 -n 10 -m 100 -s "f1,f3 from 10 to 100.png" | gnuplot

Write-Up

To complete this part of the assignment, you must provide a write-up containing the following:

A description of which mystery function (-1, -2, etc.) matches which algorithm (fn1, fn2, etc.).
For each mystery function, a short paragraph describing why you think it matches the algorithm you named.
For two of the mystery functions, a graph (saved from function_timer) that supports your claims.