Due Dates:  Oral presentations of material begin on 29 November.
Written descriptions of material presented due one week after presentation.

Topics: Measuring Complexity (Chapter 7).

An integral part of this class is understanding and presenting the problems assigned as homework. Everyone is expected to do all the problems, but we will take turns on who presents the problem solutions to the class (every 2-3 weeks, depending on the number of students in the class). Within a week of presenting a problem solution to the class, you must submit a written description of it, via the Blackboard system. The written solutions will be posted on the Blackboard website for the class, so, they can used by everyone to study for the exams. Since it's hard to write down answers that are concise and are easily readable by all, if you wish to improve a grade on any problem, you may resubmit it for grading.

Undergraduate Problems

All students enrolled should complete the following:

  1. Are the following TRUE or FALSE. Justify your answer.
    • 2n = O(n)
    • 5n + 6 = O(n)
    • n2 = O(n)
    • log n = O(n)

  2. Are the following TRUE or FALSE. Justify your answer.
    • n2 = O(n2)
    • n3 = O(n2)
    • n log n = O(n2)
    • n2 = O(n log2 n)

  3. What is the running time of the following function:
    A: list of n numbers
    mystery(A):
       count = 0
       for each element x in A:
           count = count + x
       return count
    
  4. What is the running time of the following function:
    A: list of n numbers
    mysterySwap(A):
       for i in range(length(A)-1):
           if A[i] > A[i+1]:
               swap A[i] and A[i+1]
    
  5. What is the running time of the following function:
    A: list of n numbers
    mysteryNestedSwap(A):
       count = 0
       for j in range(length(A)):
       	   for i in range(length(A)-1):
               if A[i] > A[i+1]:
                   swap A[i] and A[i+1]
    
  6. What is the running time of the following function:
    A: list of n numbers
    enigma(A):
       if length(A) <= 1:
           return 1
       else:
           return A[0:length(A)/2] + A[length(A)/2:length(A)]
    

Graduate Problems

Students enrolled for graduate credit, should complete all the undergraduate problems, as well as:

  1. Which of the following pairs of numbers are relatively prime? Show the calculations that led to your conclusions.