1. COMP.CS.300 Data Structures and Algorithms 1 »
  2. Course week 5 - STL library »
  3. Course week 5 exercises

Course week 5 exercises

These submissions are due in course week 5 and they will be discussed on week 6 exercise sessions.

big-O notation

For each function, the size of parameter v is N. For each question, always choose the tightest bound.

1
2
3
4
5
6
   Mean(Vector v):
     int sum = 0
     FOR elem IN v :
       sum = sum + elem
     END LOOP
     RETURN sum/SIZE(v)

What is the efficiency of Mean()?

1
2
3
4
5
6
   MeanOfRange(Vector v, int index1, int index2):
     int sum = 0
     FOR elem IN RANGE FROM index1 TO index2 :
       sum = sum + elem
     END LOOP
     RETURN sum/(index2-index1 +1)

Let index1 and index2 be arbitrary positive integers, such that index1 <= index2. What is the runtime efficiency of MeanOfRange() ?

1
2
3
4
5
6
7
   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"

What is the runtime efficiency of FindIfOutliers()? (The Mean-function was given in the first question.)

Calculating asymptotic efficiency

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
 Mystery1(Array[a1, a2, ... , aN]):
   B := []
   FOR elem IN Array LOOP
     IF first THEN
       B[0] := elem
     ELSEIF elem > LAST(B)
       APPEND(B, elem)
     END IF
   END LOOP
   RETURN  B
Assume the APPEND-function runs in constant time. The runtime efficiency of the Mystery1 algorithm is
If the APPEND-function has a linear O(N) in the worst case, but still runs in constant time on average, how would that affect the efficiency of the whole algorithm?
1
2
3
4
5
6
7
8
FindAPair(Array A, Array B):
  FOR a_index IN A LOOP
    FOR b_index IN B LOOP
      IF A[a_index] == B[b_index] THEN
        RETURN (a_index, b_index)
      END IF
    END LOOP
  END LOOP
Which of the following give the tightest bounds on the runtime efficiency of the FindAPair-algorithm? Note that you may assume SIZE(A) == SIZE(B).
1
2
3
4
5
6
  Mean(Vector v):
    int sum = 0
    FOR elem IN v :
      sum = sum + elem
    END LOOP
    RETURN sum/SIZE(v)
When N is the size of parameter v, what is the efficiency of Mean()? (Choose the tightest bound.)
1
2
3
4
5
6
  MeanOfRange(Vector v, int index1, int index2):
    int sum = 0
    FOR elem IN RANGE FROM index1 TO index2 :
      sum = sum + elem
    END LOOP
    RETURN sum/(index2-index1 + 1)
Let index1 and index2 be arbitrary positive integers, such that index1 <= index2. When N is the size of parameter v, what is the efficiency of MeanOfRange()? (Choose the tightest bound.)
1
2
3
4
5
6
7
   FindIfOutlier(Vector v, int max_var):
     FOR elem IN v:
       IF max_var > |elem - Mean(v)|:
         RETURN elem
       END
     END
     RETURN "Failure to find outlier"
When N is the size of parameter v, what is the efficiency of FindIfOutlier()? (Choose the tightest bound.)
1
2
3
4
5
6
RecursiveSum(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSum(N - 1)
  ELSE
    RETURN 1
  END IF

1
2
3
4
5
6
RecursiveSumEveryThird(int N)
  IF N > 1 THEN
    RETURN N + RecursiveSumEveryThird(N - 3)
  ELSE
    RETURN 1
  END IF
What is the efficiency of RecursiveSum-algorithm?
Which one of the following is true?

Drilling algorithms & complexities

A+ presents the exercise submission form here.