# 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.
1. 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.
2. Table of data showing how the runtime and memory consumption change with chunksize.
3. 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.
4. 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.
5. 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.
6. 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.