Activity Sheet 2

Manager
name:
Recorder
name:
Speaker
name:

Section 2.1

  1. Consider book problem 1.1.5 from your first activity sheet, where you discussed an algorithm for finding all the common elements between two shorted lists.
    1. What would be the input size for this problem?
    2. What would be the basic operation that we would consider for this problem?
    3. What would be the worst-case and best-case efficiencies of the algorithm you found for this problem? Explain. Can you also figure out the average-case efficiency?
  2. Exercise 2.1.8: For each of the following functions, determine how much the value will change if the parameter \(n\) is increased fourfold: \(\log_2 n\), \(\sqrt{n}\), \(n\), \(n^2\), \(n^3\), \(2^n\).

Section 2.2

  1. Exercise 2.2.10 extended: The range of a finite nonempty set of real numbers is defined as the difference of the largest minus the smallest. We can represent a set of numbers in at least five different ways. For each way describe the algorithm for finding the range of the set, and decide what the time efficiency class of that algorithm is.
  1. Unsorted array
  2. Sorted array
  3. Sorted singly linked list
  4. Sorted doubly linked list
  5. Binary search tree