EECS268:Lab5

Navigation
Home
Information
Syllabus Schedule
Classwork
Labs Submitting Work

Due time

This lab is due Friday July 10th by 11:59pm

Lab conduct

• Do not use any unauthorized aid, such sites like rentacoder or chegg to obtain answers
• Do not use code provided by another student
• Do not reuse code (by you or anyone) from prior semesters
• If you need help, seek it from:
  • Your lab TA.
  • Me, Dr. Gibbons, my email is jwgibbo@ku.edu / jwgibbo@gmail.com
• If equipment you don't own (e.g. cycle servers) needs attention or you're having account issues put in a ticket!

Overview

In this lab we will time various methods from the data structures we've made so far, save those times, and plot them to see if they match the theoretical expectations.

Timing a block of code

The standard libary <time.h> include timing methods like clock() and time(). It's important to use clock() instead of time() because clock tells how much processor time was spent doing something versus how much actual time. Why don't we want actual time? Well, if your machine is doing a LOT of other tasks (e.g. watching netflix, playing a game, download 100% legal music) then your sorting algorithm could appear slower than it actually is only because other processes were using the processor instead.

Example of timing: Original from C++ Reference. It had an error in it that I fixed below. I did not fix the shameful formatting they used.

/* clock example: frequency of primes */
#include <stdio.h>      /* printf */
#include <time.h>       /* clock_t, clock, CLOCKS_PER_SEC */
#include <math.h>       /* sqrt */

int frequency_of_primes (int n) {
  int i,j;
  int freq=n-1;
  for (i=2; i<=n; ++i) for (j=sqrt(i);j>1;--j) if (i%j==0) {--freq; break;}
  return freq;
}

int main ()
{
  clock_t t;
  int f;
  t = clock();
  printf ("Calculating...\n");
  f = frequency_of_primes (99999);
  printf ("The number of primes lower than 100,000 is: %d\n",f);
  t = clock() - t;
  printf ("It took me %d clicks (%f seconds).\n",(int)t,((float)t)/CLOCKS_PER_SEC);
  return 0;
}

Requirements

You will time several methods from Stacks, Queues, and Lists using several values for n (size of the data structure)

Data sets

You will fill each data structure with an increasing number of elements and record a time for each. For each method, start with a data size of 1000 then increase by 1000, recording another time, and repeat until you've reached 100,000 elements

For example. Let's say I want to time Pop for a Stack. I would do the following:

1. Fill a stack with 1000 elements
2. Record time to perform a single pop with that size stack
3. Fill a stack with 2000 elements
4. Record a time to perform a single pop with that size stack
5. Repeat these steps, increasing the size by 1000 each time until I've recorded a time for a stack with 100,000 elements in it

Operations to time

Operation
Stack's pop
Stack's destructor
Queue's enqueue
Linked List getEntry at specifically index 1
Linked List getEntry at specifically the last index
Printing all elements in a LinkedList using getEntry

Plotting

In addition to your code, you will submit graphs (e.g. excel graphs) of the data you've collected. One graph for each operation.

Rubric

• [5pts] Proper submission (email subject, tarball, etc)
• [10pts] No memory leaks or segfault
• [10pts] Modularity
• [5pts] Documentation
• [10pts] Pop data
• [10pts] Destructor data
• [10pts] Enqueue data
• [10pts] getEntry at index 1
• [10pts] getEntry at last index
• [20pts] printing entire list using getEntry

Remember, if we type "make" into the console and your program fails to compile, we do not grade it.

Submission instructions

Send a tarball with all the necessary files (*.h, *.cpp, and makefile) in a tar file to your GTA email. Do not include any object (*.o) or executable file.

Creating a File Archive Using Tar

The standard Unix utility for created archived files is tar. Tar files, often called tarballs, are like zip files.

1. Create a folder to hold the files you will be sending in. The folder should be named like LastName-KUID-Assignment-Number:

   mkdir Smith-123456-Lab-0#

2. Now, copy the files you want to submit into the folder:
3. Tar everything in that directory into a single file:

   tar -cvzf Smith-123456-Lab-0#.tar.gz Smith-123456-Lab-0#

   That single command line is doing a number of things:

   • tar is the program you're using.
   • -cvzf are the options you're giving to tar to tell it what to do.
     • c: create a new tar file
     • v: operate in verbose mode (show the name of all the files)
     • z: zip up the files to make them smaller
     • f: create a file
   • Smith-123456-Lab-0#.tar.gz: the name of the file to create. It is customary to add the .tar.gz extension to tarballs created with the z option.
   • Smith-123456-Lab-0#: the directory to add to the tarball

Please note that it is your responsibility to make sure that your tarball has the correct files. You can view the contents of a tarball by using:

tar -tvzf filename.tar.gz

Emailing Your Submission

Once you have created the tarball with your submission files, email it to your TA. The email subject line must look like "[EECS 268] SubmissionName":

[EECS 268] Lab 0#

Note that the subject should be exactly like the line above. Do not leave out any of the spaces, or the bracket characters ("[" and "]"). In the body of your email, include your name and student ID.