EECS 380 Homework 1
Winter Semester '01
Assigned Jan 9th 2001.
Due Jan 18th, 6pm, EECS 380 box in room 2420 EECS
You are to turn this in with all parts stapled together. Your first
sheet must include your name and uniquename.
Goals
- Introduce complexity measurement.
- Measuring runtime and memory allocation of real programs.
- Learning to use gnuplot (a handout is available at the class home page).
- Practice with big-O and big-Theta.
Homework Description
This homework consists of three parts. The first is to measure the runtime
and memory allocation of the new operator as it allocates various
sized memory blocks. The second is to measure the runtime of initializing
a N by N matrix and them performing matrix multiplication on in. The third
is to answer a few theory-related questions.
Part 1: The new operator
Using new write a program which dynamically allocates 4,000,000 bytes
of memory in chunks of 4 bytes. (That is do 1,000,000 new operations each
allocating 4 bytes). Using the timer and memory allocation classes (see
below) *accurately* measure the amount of memory actually used and the run
time of one call to operator new.
Repeat this process allocating ~4,000,000 bytes in chunks of size
8, 12, 16, 20, 24, 28, and 2048. Turn in your results in table format.
Using gnuplot, graph the amount of memory used vs. the chunk size for chunk
sizes 4 through 28. Make sure your plots have an informative title (use the
GNUPLOT command set title) and correctly identify the axis (using commands
set xlabel and set ylabel).
Part 2: Matrix multiplication
Write a program which multiplies two N x N matrices. Page 117 of your book
provides a simple implementation of matrix multiplication. Initialize the
two input matrices (a and b) so that element a[x][y]=b[x][y]=x*y
Then multiply the two matrices. Separately measure the run time of the
array initialization and matrix multiplication. Use gnuplot to graph these
run times against N. Choose at least 8 values for N and be sure your run
times are large enough to be accurate. Make sure your plots have an
informative title (use the GNUPLOT command set title) and correctly
identify the axis (using commands set xlabel and set ylabel).
Part 3: Misc Problems
Do the following problems.
- Sedgewick problem 2.5
- Sedgewick problem 2.23
- Sedgewick problem 2.29
- CLR (Cormern-Leiserson-Rivest) handout problem 2.1-4
Turn-in check-list
Your name must be mentioned at the beginning of every document
that you turn in (each program listing, each plot, etc). All
sheets must be stapled.
- The text of the program (in main.cxx file) that measures and prints
runtime and memory consumption of the new operator.
You do not need to submit the code of supporting library used by
your program. Only submit the code you wrote.
- Table of data showing how the runtime and memory consumption change
with chunksize.
- Printout of 2 plots produced with GNUPLOT showing (a) how the
runtime of one "new" changes with chunk size, and (b) how the memory
consumed by one "new" changes with chunk size.
- The text of the program (in main1.cxx file) that measured and prints
runtime and memory consumption of (a) matrix initialization, and
(b) matrix multiplication.
- Printouts of plots produced with GNUPLOT showing how the
runtime and memory consumption of (a) one matrix initialization,
(b) one matrix multiplication change with matrix size.
- Detailed solutions to problems from Sedgewick and from the
CLR handout.
Note: most likely, it will be impossible to accurately
measure the runtime/memory consumption of one "new"
by performing just one "new". You need to perform many
of those an divide the overall runtime/memory consumption
by the number of operations.
Timer class, etc.
We are suppling a tar file which includes the code
needed to measure runtime and memory utilization. Download the file to a
Unix system and then type
tar xvf Proto.tar
This will create directory Proto,
which among other things includes
README file which briefly explains how to start
using this code. Play around with it for a while, you should find it fairly
straight forward.
Lastly, a brief tutorial on gnuplot is available.