Quizzes 1-4

There was a request from the audience to recap the quiz questions from the semester so far. If you were present for all 4 quizzes, your graded solutions are in your blue book and you can ignore the rest of this post. Here they are:

Quiz 1

Describe an algorithm that takes a list of n distinct integers and finds the location of the largest even integer in the list or returns $0$ if there are no even integers.

Quiz 2

Show that f(x)=x^3 is O(x^3) but that f(x)=x^4 is not O(x^3).

Quiz 3

Pick one of the following pairs and show that f(x) and g(x) have the same order.

  • f(x)=3x+7 and g(x)=x
  • f(x)=2x^2-x-7 and g(x)=x^2
  • f(x)=\lfloor x+ \frac{1}{2} \rfloor and g(x)=x
  • f(x)=\log_2(x^2+1) and g(x)=\log_2(x)
  • f(x)=\log_{10}(x) and g(x)=\log_2(x)

Quiz 4 (team quiz)

(Teams were assigned either the bubble sort or the insertion sort algorithm)

  1. Determine the complexity of your team’s algorithm by counting the number of comparisons required. Ignore comparisons needed to determine whether the end of a loop has been reached.
  2. Apply your sorting algorithm to the set \{4, 1, 2, 6\}. Show all the comparisons that are made and count the total number of comparisons. Check that this agrees with your answer from the first part.
This entry was posted in Quizzes. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *