Class Notes: COT3100

Class Notes: Applied Discrete Structures

Spring Semester 1999 - MWF 5th Period CSE/E222, Section 4617X

Instructor: M.S. Schmalz -- TAs: James Jeffers, Yasmeen Fatimah, Jang-Uk In, Arun Srinivasan, Jing Zhao

Quiz #3 -- Solution

Question 1. (5 points) Write pseudocode to find the smallest integer a_i in a sequence [a_n].

Solution.

   procedure find-min (a: array [1..n] of integer):
     min := a[1]
     location := 1
     for i = 2 to n do:
       if (a[i] < min) then
         min := a[i]
         location := i
       endif
     endfor
     return(location,min)
   end.

Question 2. (5 points) Find the complexity of the following algorithm given a sequence of positive integers [a_n] containing elements a_i, i = 1..n:

STATEMENT                   MAX # OF OPS
  p := 0                          1
  i := 1                          1
  while ( i <= n) do:           n+1
  { p := p * a[i]                      
    i := i + 1                   2n
  }
  return(p)                       1

Total maximum number of operations = 3n + 4.
Complexity: O(n).