* No calculators, no notes, no books, no computers.

* Show your work. Correct answers without supporting calculations will not receive full credit.

* The problems are not necessarily in increasing order of difficulty. Manage your time efficiently.

Part 1 (week 1)

1.1 (3 points). True or false?

A. A single bit can represent the symbols 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.

    TRUE     FALSE

B. The binary sequence “10001111” always represents the decimal number 143.

    TRUE     FALSE

C. Letters of the English alphabet can be represented using integers.

    TRUE     FALSE

D. The ASCII table is included in the Unicode standard.

    TRUE     FALSE

E. Musical notes can be represented using sequences of bits.

    TRUE     FALSE

F. A number represented in binary always requires more digits than the same number in decimal.

    TRUE     FALSE

1.2 (4 points). Using selection sort, order the following sequence of numbers from lowest to highest. Show each sequence after each swap.

0   12   -7   1

1.3 (3 points). For each of these functions, circle the closest family it belongs to (big O notation).

A. T = 2N + 5

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

B. T = N + logN

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

C. T = N^3 + 45N^2 + 100logN

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

D. T = 10N * 3N

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

E. T = 10N + 3N

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

F. T = number of steps merge sort takes to sort a list of N numbers

    O(logN)     O(N)     O(NlogN)     O(N^2)     O(N^3)

1.4 (10 points). Invent an algorithm that uses a password to encrypt text, and another algorithm that uses the same password to decrypt it. Briefly describe the algorithms you invented, in precise and concise English, and show how they work by encrypting and decrypting the following simple message. Note: your algorithm must depend on the password.

Message: FACED

Password: CAB

Part 2 (week 2)

2.1 (4 points). Indicate what each of the following will print:

A)  print 5*4+3**2

B)  print chr(ord("A")+3)

C)
   x = 5
   y = 3
   x += 3
   y *= x
   print str(x) + "," + str(y)

D)
   s = "ab\ncd"
   print len(s)
   print s

2.2. (8 points). In just a few words of plain English, state what these functions do in general.

A)
   def mysteryA(s, x):
      # assume x is an integer between 10 and 99 inclusive
      return (len(s) == 2) and (s[0] == str(x/10)) and (s[1] == str(x%10))

B)
   def mysteryB(x, y):
       # assume x and y are both positive integers
       return x/y*y != x

2.3 (8 points) . Without using conditionals ("if"), loops, or recursion, write the function pghHour(londonHour). This function takes an integer, the current hour in London, and returns the current hour in Pittsburgh (which is 5 hours behind London). However, London time is given in 24-hour time (so londonHour is between 0 and 23, inclusive), but Pittsburgh time must be returned in 12-hour time (so the result must be between 1 and 12, inclusive, where "am" and "pm" are ignored). Here are some examples:

londonHour	pghHour(londonHour)
0 (midnight)	7 (7pm)
10 (10am)	5 (5am)
12 (noon)	7 (7am)
17 (5pm)	12 (noon)
18 (6pm)	1 (1pm)

Note: the hardest part is when it is 12 o'clock in Pittsburgh. These cases are worth 2 points.

Part 3 (week 3)

3.1 (4 points). In just a few words of plain English, state what this function does in general.

   def mystery(x, y):
      # assume x and y are positive
      while (x >= y):
         x -= y
      return x

3.2 (8 points). Write a function sportToPlay(season, weather) which takes two strings representing a season and the current weather, and returns a string with a suggestion on a sport to play, according to the following table.

3.3 (8 points). Without using “for” loops or recursion (“while” loops are ok), write a function isReverse(s1, s2) which takes two strings, and returns True if one string is the reverse of the other, and False otherwise. For example, isReverse(‘abc’, ‘cba’) returns True, but isReverse(‘abc’, ‘dba’) returns False.

Part 4 (week 4)

4.1 (9 points). Indicate what each of the following will print or draw. Assume all required imports and other graphics code as needed.

A)
   for x in range(20, 30):
      if (x % 3 == 1):
         print x

C)

   canvas.create_rectangle(100, 100, 400, 400)
   for i in range(3):
      x1 = 100 + 50*i
      y1 = 100 + 50*i
      x2 = 400 - 50*i
      y2 = 400 - 50*i
      canvas.create_oval(x1, y1, x2, y2)

4.2 (4 points). The following function is supposed to find the smallest digit in the given integer parameter, but it contains one bug on one line. Circle the bug and provide the correct line of code.

   def smallestDigit(n):
      n = abs(n)
      smallest = 0
      while (n > 0):
         digit = n%10
         if (digit < smallest):
            smallest = digit
         n /= 10
      return smallest

4.3 (7 points). Write the function sumOfSquares(n), which takes a positive integer n and returns the sum of the squares from 1² up to n². For example, sumOfSquares(4) returns 30, since 1² + 2² + 3² + 4² = 1 + 4 + 9 + 16 = 30. Do not use a formula to do this. Instead, add each term in a “for” loop.

Part 5 (week 5)

5.1 (4 points). What will the following recursive function print when we call f(8)? Hint: it will print exactly 5 lines.

   def f(x):
      if (x < 7):
         print "done, x =", x
      else:
         f(x - 2)
         print "here, x =", x
         f(x - 1)

5.2 (6 points).

A) (4 pts) The following is a correct function that solves the "Towers of Hanoi" game. Break this code by changing one single character of it. With your change, the program is still syntactically correct, but it will never terminate (if you run it on a computer with unlimited memory, so the program will not crash because of a stack overflow).

   def hanoi(n, source, target, temp):
      if n == 1:
         print "Move", source, "to", target
      else:
         hanoi(n-1, source, temp, target)
         hanoi(1, source, target, temp)
         hanoi(n-1, temp, target, source)

B) (2 pts) Will your modified program ever print any partial results? Explain.

5.3 (10 points). Write a function turtleSpiral(size, minSize) that draws squared spirals similar to the one in the figure below, using turtle graphics and recursion. The longest side has length equal to size, and each following side is 10% shorter than the previous one. The length of the shortest side is no shorter than minSize.

Bonus problem

6 (5 bonus points). Bonus/Optional: Write a recursive function isReverse(s1, s2) that takes two strings and returns True if s1 is the reverse of s2, and False otherwise.