CPSC 212 Assignment 1

Three executables (prog1, prog2, prog3) are available on ulab machines (Linux) under ~hplantin/public/212/hw1. If you are not in the ulab, you can get to them if you ssh to cs-ssh.calvin.edu. Run them by (for example) typing cd ~hplantin/public/212/hw1 and then ./prog1.

Gather 8 runtime data points for each, for inputs that grow by a factor of two each time. (For prog3, instead of growing by a factor of two each time, your last few points will have to grow more slowly.) Enter the data into a spreadsheet and create a log-log plot of the runtime vs. input value. Fit a straight line to each of the three data sets on the same log-log plot. Show the equations of the lines on the chart.

Print out your chart. Below it, write the empirical asymptotic runtime of the three functions in big-O notation, assuming the form of the runtime is polynomial. Also write estimates for the runtime for each algorithm for an input of 1,000,000. Write your name on this sheet and turn it in.

Can you guess what kind of (simple) program might generate a runtime graph like each of these?