CSCI 132 Data Structures

    Assignment 7

    Home | | Syllabus | | Assignments | | Lecture Notes

    Programming Style: You will be graded not only on whether your program works correctly, but also on programming style, such as the use of informative names, good comments, easily readable formatting, and a good balance between compactness and clarity (e.g. do not define lots of unnecessary variables, or write multiple statements to perform a task that can be expressed clearly in a single statement.) Create appropriate functions for tasks that can be encapsulated.

    Part 1: Implement and Analyze.

    Do problem P1 on page 314 of the textbook: Write a program to test on the computer how long it takes to do nlgn, n2, n5, 2n, and n! additions for n = 5, 10, 15, and 20. You will likely need the following libraries: 
    #include < ctime>
#include < iostream>
#include < iomanip>
#include < cmath>
    The < cmath > library includes the pow() and log() functions that may prove useful to you.

    The < ctime > library includes a function clock() that returns the number of clock ticks elapsed since the program was launched. Therefore, you may use the following code to measure how much time the for loop takes and store it in the variable, difference. 

      int start_clock = clock();
 
  for (i = 0; i < n; i++)
    result = result + result;

  int difference = clock() - start_clock;

    After you examine your program's results, answer the following questions:

    1. When n=20, why is the number of iterations a negative number for n!?
    2. For what n and what function does your not immediately display results?
    3. What does it mean when it says it took 0 clock ticks to perform the additions?

    Part 2: Asymptotic analysis

    Do exercises 7.6 E2 and E15 on pages 312 - 314 of the textbook.

    Show your work and explain your answers. For example, for problem E2, indicate the appropriate rule or show the limit that lets you place one function above or below another in your list of functions. Also indicate which is fastest and which is slowest.

    What to turn in:

    • A hard copy of the compareAdd.cc program.
    • Submit the soft copy of your program using the command:
      ~csci132/bin/submit csci132 assign7
    • The answers to the questions for part 1.
    • The explanation and answers to the problems listed in part 2.
    • A discussion log.

    Home | | Syllabus | | Assignments | | Lecture Notes


    Computer Science 132--Data Structures
    Last Modified: February 5, 2010
    Page Expires: January 14, 2011