CS 70, Spring 2000
Assignment 6: Complexity Analysis

This assignment is due on Wednesday March 29th, at 12 midnight (i.e. right before Thursday the 30th starts).

This assignment will give you practice analyzing the running time of algorithms.

General Instructions

When answering the following questions, explain clearly why your answer is correct, and show work for significant intermediate steps of computations. For example, when analyzing the running time of a code fragment, include the running time for each individual line.

Normally, it is sufficient to provide an asymptotic (big-O) analysis. Exceptions would include where the problem statement indicates otherwise, or when you believe that constants and low-order terms have a significant impact on the answer.

The code fragments are only fragments, and they may ignore certain niceties of C++ style. Don't pick at the details. Treat them as particularly explicit pseudo-code.

Submission mechanics

Put your solutions in a text file named README and submit this file using cs70submit. Your file must be a plain text file. Do not submit (for example) a postscript file, a Word document, or an html file. Represent your equations using notation similar to the following examples:

	O(N)
	O(N log N)
	O(N^2)

Problem 1

Provide a big-O analysis of the running times for the code fragments given in Weiss, problems 5.15 and 5.16. Notice that you will need to repair a small typo in the code fragment for 5.16: the first semi-colon in the first line should be a comma. Also, the reuse of Sum in fragment #3 of problem 5.15 is obsolete C++; just assume that Sum was declared before the first for loop.

Problem 2

Suppose that we define a linked list class with the following data fields.

    class Node {
        long value;
        Node *next;
        }

    class List {
        Node *head;       
        }

How long do the following operations take, as a function of the length of the list, N?

1. Making a copy of the list
2. Adding a value to the start of the list
3. Adding a value to the end of the list
4. Removing the first value from the list
5. Removing the last value from the list
6. Determining whether the list contains some value V

Problem 3

Some of the operations in Problem 2 can be made faster by storing additional information in the head of the list (the object of class List). For which operations is this possible? What additional information should be stored for each operation? What is the new running time for each operation?

Problem 4

Suppose that we modify the classes from Problem 2 to store character strings of maximum length M characters (not including the null byte), rather than longs. Does this affect the running of any of the operations? If so, which one(s) change, why, and what is/are the new expression(s) for the running time(s)?

Notice that each list should contain its own private copy of the strings stored in it. Lists should not share strings with other lists, or with other parts of the code.

You should assume that all string copying is done with the library routine strcpy and comparisons are done with strcmp. You should also assume that these two library functions have been implemented in hand-optimized assembly language by an all-time champion programmer who was fanatic about squeezing every last bit of run time out of the functions.

Problem 5

Consider the following functions, which use the List and Node data structures from Problem 2:

   // returns the length of the list
   int List::length() {
       Node *current = head;
       int output = 0;
       while (current != NULL) {
           output++;
           current = current->next;
           }
       return output; 
       }

    // returns the nth value in the list
    long List::nth(int n) {
       if (n >= length() || n < 0)
           error("List::nth out of range position");
       Node *current = head;
       for (i = 0; i < n; i++) {
          current = current->next;
          }
       return current->value;
       }

    // prints all the values in the list
    void List::print() {
        for (i = 0; i < length(); i++) {
            cout << nth(i);
            }
        }

Analyze the running times of these three functions. For each function, show how it could be recoded (if possible) so as to improve its asymptotic running time, and provide an analysis of the new running time. If no improvement is possible, explain why. You are only allowed to modify the executable code; you may not modify or add any fields to the Node and List data structures.

This page is maintained by Geoff Kuenning and Margaret Fleck.