CPSC 212 Assignment 1

Three executables (prog1, prog2, prog3) are available on ulab machines (Linux) under ~hplantin/public/212/hw1. Log into a lab machine under Linux and run them by (for example) typing cd ~hplantin/public/212/hw1 and then ./prog1.

Gather 8 runtime data points for each program, 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, or you'll be waiting a very long time for the program to finish. But still try to get a broad range of input sizes.) Enter the data into a spreadsheet in three separate columns for the three programs, and create a chart for each with log-log plots of the runtime vs. input value for the three programs. Fit a straight line to each of the three data sets Show the equations of the lines on the charts.

Print out your chart spreadsheet with data and 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.

Think about: what kind of (simple) program might generate a runtime graph like each of these? (We'll discuss this in class.)