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.

  Answer:

  FindMean(a : array [1..n] of int):
  { sum = 0; posmean = -1, posclose = -1
    for i = 1 to n do:
      sum = sum + a[i]
    endfor
    mean = float(sum) / n
    mdif = 9E13
    for i = 1 to n do:
      dif = abs(a[i] - mean)
      if (dif < mdif) then
        if (dif = 0) then
          posmean  = i
        endif
        posclose = i
      endif
    endfor
    print "mean = ", mean
    print "position of mean in a = ", posmean
    print "position of closest value to mean in a = ", posclose
  

• 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.
  Answer:

  FindMean(a : array [1..n] of int):         # n ext I/O
  { sum = 0; posmean = -1, posclose = -1     # 3 mem I/O
    for i = 1 to n do:                       # n-1 incr.
      sum = sum + a[i]                       # n x :  1 add, 2 mem I/O
    endfor
    mean = float(sum) / n                    # 1 mult,  1 mem I/O
    mdif = 9E13                              # 1 mem I/O
    for i = 1 to n do:                       # n-1 incr.
      dif = abs(a[i] - mean)                 # n x :  1 add, 1 bit op, 1 mem I/O
      if (dif < mdif) then                   # n x :  1 comp
        if (dif = 0) then                    # n x :    1 comp    [max. work]
          posmean  = i                       # n x :    1 mem I/O [max. work]
        endif       
        posclose = i                         # n x :  1 mem I/O   [max. work]
      endif 
    endfor
    print "mean = ", mean                    # 3 print's = 3 ext. I/O
    print "position of mean in a = ", posmean
    print "position of closest value to mean in a = ", posclose
  
    WORK BUDGET  Ext I/O      n + 3
                 Mem I/O     5n + 5 [max. work]
                 Incr.       2n - 2
                 Adds        2n
                 BitOps       n
                 Comp's      2n     [max. work]
                 Mult's           1
  
    Big-Oh Estimate:  O(n) in comparisons
  

• 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.
  Answer:

  FindMean(a : SLL of int):
  { sum = 0; posmean = -1, posclose = -1
    for i = 1 to n do:
      sum = sum + ElementAt[i].value
    endfor
    mean = float(sum) / n
    mdif = 9E13
    for i = 1 to n do:
      dif = abs(ElementAt[i].value - mean)
      if (dif < mdif) then
        if (dif = 0) then
          posmean  = i
        endif
        posclose = i
      endif
    endfor
    print "mean = ", mean
    print "position of mean in a = ", posmean
    print "position of closest value to mean in a = ", posclose
  

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

  FindMean(a : SLL of int):                  # n ext I/O, 4n mem I/O (build-SLL)
  { sum = 0; posmean = -1, posclose = -1     # 3 mem I/O
    for i = 1 to n do:                       # n-1 incr.
      sum = sum + ElementAt[i].value         # n x :  1 add, O(n) mem I/O
    endfor
    mean = float(sum) / n                    # 1 mult,  1 mem I/O
    mdif = 9E13                              # 1 mem I/O
    for i = 1 to n do:                       # n-1 incr.
      dif = abs(ElementAt[i].value - mean)   # n x :  1 add, 1 bit op, O(n) mem I/O
      if (dif < mdif) then                   # n x :  1 comp
        if (dif = 0) then                    # n x :    1 comp    [max. work]
          posmean  = i                       # n x :    1 mem I/O [max. work]
        endif       
        posclose = i                         # n x :  1 mem I/O   [max. work]
      endif 
    endfor
    print "mean = ", mean                    # 3 print's = 3 ext. I/O
    print "position of mean in a = ", posmean
    print "position of closest value to mean in a = ", posclose
  
    WORK BUDGET  Ext I/O      n + 3
                 Mem I/O     O(n2) [max. work]
                 Incr.       2n - 2
                 Adds        2n
                 BitOps       n
                 Comp's      2n     [max. work]
                 Mult's           1
  
    Big-Oh Estimate:  O(n) in comparisons
                      O(n2) in memory I/O
  

  Note: If you used the "this.next.value" construct, or similar notation, then you would have O(n) memory I/O's.

• Question 5. Repeat Question 3 for a doubly-linked list (DLL), instead of the SLL.
  Answer: The same result as Question 3, since the DLL and its associated ADT operations have all the capabilities of the SLL and its associated ADT operations.

• Question 6. Repeat Question 4 for the DLL representation and algorithm developed in Question 5.
  Answer: The same result as Question 4, except that two more memory I/Os per list element aTre required to build the DLL, due to the backwards ("previous") pointer.

Copyright © 1999 by Mark S. Schmalz.