CSE 373 Homework Assignment 2

Problem 1

(7 pts) Weiss 2.1

Problem 2

(18 pts) (adapted from Weiss 2.7) For this problem, you will need to write some code in either C++ or Java. We've provided everything you need to get started:

For each of the following six program fragments:

  1. Give an analysis of the running time. Big-Oh will suffice.

  2. Implement the code in either C++ or Java, and give the running time (in milliseconds) for several values of n. We've set up the skeleton files to make this easier. Look for an "INSERT YOUR CODE HERE" comment. Also, the skeleton is set up to read the value of n from the command line.

  3. Compare your analysis with the actual running times (use BIG values of n). 

    1. sum = 0;
for (i=0; i<n; i++)
	sum++;

    2. sum = 0;
for (i=0; i<n; i++)
	for (j=0; j<n; j++)
		sum++;

    3. sum = 0;
for (i=0; i<n; i++)
	for (j=0; j<n*n; j++)
		sum++;

    4. sum = 0;
for (i=0; i<n; i++)
	for (j=0; j<i; j++)
		sum++;

    5. sum = 0;
for (i=0; i<n; i++)
	for (j=0; j<i*i; j++)
		for (k=0; k<j; k++)
			sum++;

    6. sum = 0;
for (i=1; i<n; i++)
	for (j=1; j<i*i; j++)
		if (j % i == 0)
			for (k=0; k<j; k++)
				sum++;

Problem 3

(14 points) Weiss 2.14 (a) and (c). In (c) analyze to get T(n) and then convert to Big Oh notation.

Problem 4

(10 points) Weiss 3.2. For part (a), assume that you are given pointers to a node p and its predecessor, while for part (b) you are only given a pointer to a node p. In both cases, you swap p and its successor.

Problem 5

(10 points)

  1. Write a recursive function to reverse a singly linked list in O(N) time. You can use O(N) extra space.
  2. Write a function to reverse a singly linked list in O(N) time but using constant (O(1)) extra space.

Note: The list has N nodes. For part (1) you can use O(N) extra space and you must use recursion. For part (2) you must use only O(1) space. Recall that recursive routines can be deceptive in the amount of space they require. For example, for each level of recursion you need to store at least the return address and therefore if you have N levels of recursion you need O(N) space. So you must write it iteratively. (HINT: you'll need several pointers to keep track of things in the iterative version.)