Requirements for CS330 Fall 2001 Project 1

1a. Chapter 1 & 2

Pick a change to the War program described in one (1) of these exercises: 1,2,3,5,6, or 7 at the end of chapter 2 (pages 42-43). Carry out this change on your program and make it correct.

1b. Chapter 3

Write a program that simulates algorithms that take O(n), O(n ln(n)), O(n^2), and O(n^3) at the choice of the user with n=10, 20, 30, 40, 50. Use a loop that repeats a constant operation the right number of times. Run these programs to get a feel for the difference between the O(...)s.

It helps if you use a function that takes a constant time when called and does nothing else. The UNIX Standard function int sleep( int) is a good example:

#include <iostream>

#include <unistd.h>

int main()

{ cout <<"1"<<endl;

sleep(2); // roughly a 2 second delay

cout <<"2"<<endl;

return 0;


1.c Chapter 4

Learn how to use the C++ <ctime> or C <time.h> libraries to time parts of programs. The library is described in

Test your understanding by changing the program in project 1b above. Hand in an example of a program that prints out the time (in seconds) that the program takes to execute part of the program.

Hand in: The source code (containing identifying and helpful comments).

Grading: Each part will be given the same weighting. The grade depends on writing simple and obviously correct code. The code should include comments explaining all errors and clever ideas. It should also give any simple invariants, pre-conditions, and post-conditions that help convince the reader that the code works.