Class Notes: Data Structures and Algorithms

Summer-C Semester 1999 - M WRF 2nd Period CSE/E119, Section 7344

Instructor: M.S. Schmalz -- TAs: Hongyu Guo , Lloyd Noronha, Jagadha Sivan

Homework #2 -- Due Fri 28 May 1999 : 09.30am

• Question 1. Assume that an n-element array (vector) a contains distinct integers arranged in no particular order. Write an algorithm to find the value and location of (a) the mean of a and (b) the value v in a closest to the mean. Note: If v equals the mean, then v is the value closest to the mean.

  Example. If a = (1,2,3,5,4,6,7,9), then the mean equals 37/8 = 4.625. The value 5, which is in the fourth location (i = 4), happens to be the value closest to the mean.

• Question 2. (a) Produce a budget of computational work for the algorithm you developed in Question 1. For example, the number of operations (e.g., external I/O, memory I/O, comparisons, incrementations, etc.) (b) Given this budget, produce a Big-Oh estimate of complexity, and show the assumptions you used to arrive at that estimate.

• Question 3. Now, represent the sequence stored in the array a as a singly-linked list (SLL). (a) Draw a picture of the list, using n=8, as before. (b) Using the list operations that we discussed in class, and which Dr. Sahni has in his book, write pseudocode for an algorithm that duplicates the functionality of the algorithm you developed in Question 1, but operates over the SLL you diagrammed in Part a) of this question.

• Question 4. Analyze the complexity of the algorithm you developed in Question 3, in the same way as required in Question 2.

• Question 5. Repeat Question 3 for a doubly-linked list (DLL), instead of the SLL.

• Question 6. Repeat Question 4 for the DLL representation and algorithm developed in Question 5.

Copyright © 1999 by Mark S. Schmalz.