CS51 preparation check #

This self-administered quiz is intended to determine your readiness for CS 51. You should be able to get these problems right easily in a relatively short period of time. Some of the examples use code examples written in C or Python, but no knowledge of the details of those languages should be necessary to understand and complete the problems.

While there is no minimum score required for enrollment, if you find yourself confused by any of the concepts, get more than one or two questions wrong for reasons of preparation, or find the programming exercises quite difficult, you should carefully consider whether you are prepared for the course and talk to course staff for placement advice.

Problem 1 #

Consider the following block of C code:

int i, j;
for (i = 0; i < 5; i++)
  for (j = i; j < 5; j++)
    printf("*");

How many asterisks does this print in total?

1. 5
2. 10
3. 15
4. 20
5. 25
6. 30
7. None of the above

Problem 2 #

Now, we generalize the code by using a loop limit of n instead of 5:

int i, j;
for (i = 0; i < n; i++)
  for (j = i; j < n; j++)
    printf(" * ");

If we run this program with different values of n, will there ever be cases in which the number of asterisks printed exceeds $100 \cdot n \cdot \log n$

1. No, there will not.
2. Yes, there will.
3. There isn’t enough information to determine.

Problem 3 #

In binary, what is $10111111 + 00000001$?

1. 10000000
2. 10111111
3. 11111101
4. 11000000
5. None of the above

Problem 4 #

Below are four different Python programs that each print the string “hello world” a different number of times. Rank them from 1 to 4 by the number of times each prints “hello world”, where 1 prints “hello world” the fewest times and 4 the most. (For reference, the Python operator // used in hello_two is the integer division operator, so for instance, 5 // 2 is 2.)

def hello_one(n):
  if n <= 0:
    return
  else:
    print("hello world")
    hello_one(n - 1)
hello_one(50)

def hello_two(n):
  if n <= 0:
    return
  else:
    print("hello world")
    hello_two(n // 2)
hello_two(50)

def hello_three(n):
  if n <= 0:
    return
  else:
    print("hello world")
    hello_three(n - 1)
    hello_three(n - 1)
hello_three(50)

def hello_four(n):
  if n <= 0:
    return
  else:
    print("hello world")
    print("hello world")
    print("hello world")
    hello_four(n - 1)
hello_four(50)

The next two problems ask you to write short programs. Try to write a correct solution without the aid of a compiler or interpreter and then run your code to check your work. See if you can get the correct output on your first try. You may use any programming language of your choice.

Problem 5 #

Write a program that prints the numbers from 1 to 100, one per line, but for multiples of three print “Fizz” instead of the number and for multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”: 1, 2, Fizz, 4, Buzz, Fizz, 7, 8, Fizz, Buzz, 11, Fizz, 13, 14, FizzBuzz, 16…

def fizzbuzz(n):
  for i in range(1, n + 1):
    if i % 3 == 0:
      if i % 5 == 0:
        print("FizzBuzz")
      else:
        print("Fizz")
    elif i % 5 == 0:
      print("Buzz")
    else:
      print(i)
fizzbuzz(100)

Write the following functions that deal with lists of floating-point numbers.

Problem 6 #

Write a function that returns the arithmetic mean of a list of numbers (that is, their sum divided by the number of elements).

def mean(lst):
  sum = 0
  length = 0
  for i in lst:
    sum += i
    length += 1
  return sum / length

def mean(lst):
  return sum(lst) / len(lst)

def sum(lst):
  if lst == []:
    return 0
  else:
    return lst[0] + sum(lst[1:])

def len(lst):
  if lst == []:
    return 0
  else:
    return 1 + len(lst[1:])

def sum(lst):
  accum = 0
  for i in lst:
    accum += i
  return accum

def len(lst):
  accum = 0
  for i in lst:
    accum += 1
  return accum

Problem 7 #

The median element in a list is the element in the “middle”, with the same number of larger and smaller elements in the list. For instance, the median element of the list 5, 1, 8, 3, 2, 4, 8 is 4, since there are three elements smaller (1, 2, 3) and three larger (5, 8, 8). (For even length lists (like 1, 2, 3, 4), you can use either of the two middle elements (2 or 3) as the median.) Write a function that returns the median of a list of numbers.

def median(lst):
  sorted_list = sorted(lst)
  midpoint = len(lst) // 2
  return sorted_list[midpoint]

Problem 8 #

Alice has fallen down the rabbit hole into Wonderland, where she meets the Queen of Hearts and her King. While the Queen challenges Alice to Croquet, the King challenges Alice to a series of puzzles. The King tells Alice that the Queen is always either happy (☺) or sad (☹). There are four different spells the King can put on the Queen to try to change her mood: $\heartsuit, \diamondsuit, \clubsuit, \spadesuit$. If the Queen is happy about someone being beheaded, but sad about losing croquet, the King can put the $\diamondsuit$ spell on her to make her completely happy again. In our symbolic notation, this would mean that: $\diamondsuit$(☺, ☹) = ☺.

The other spells can influence the Queen’s moods as follows:

$$ \begin{aligned} \spadesuit(☺) &= ☹ \cr \spadesuit(☹) &= ☺ \cr \heartsuit(☺, ☺) &= ☺ \cr \heartsuit(☺, ☹) &= ☹ \cr \heartsuit(☹, ☹) &= ☹ \cr \diamondsuit(☺, ☺) &= ☺ \cr \diamondsuit(☺, ☹) &= ☺ \cr \diamondsuit(☹, ☹) &= ☹ \cr \clubsuit(☺, ☺) &= ☹ \cr \clubsuit(☹, ☺) &= ☺ \cr \clubsuit(☹, ☹) &= ☹ \end{aligned} $$

Note that the order of moods within the spells does not matter, so $\clubsuit(☺, ☹) = \clubsuit(☹, ☺)$. In all of the following situations, Alice must tell the King which spell he should use in place of the $\square$ symbol to make the Queen happy! Choose the corresponding answers below.

• $\square(☹)$

  1. $\spadesuit$
  2. $\heartsuit$
  3. $\diamondsuit$
  4. $\clubsuit$
  5. None of the above

• $\spadesuit(\square(☺, ☹))$

  1. $\spadesuit$
  2. $\heartsuit$
  3. $\diamondsuit$
  4. $\clubsuit$
  5. None of the above

• $\diamondsuit(☹, \spadesuit(\square(☺, ☺)))$

  1. $\spadesuit$
  2. $\heartsuit$
  3. $\diamondsuit$
  4. $\clubsuit$
  5. None of the above

Problem 9 #

Consider the following pseudocode program:

for each student
  if student average > 60
    award student a D
  else if student average > 70
    award student a C
  else if student average > 80
    award student a B
  else if student average > 90
    award student an A
  else
    award student an E

If a student gets 100 in the class, what grade is that student awarded?

1. A
2. B
3. C
4. D
5. E
6. None of the above

In the next two problems, you’ll work with Python logical values and operators). In Python, the values True and False are used for the logical values indicating truth and falsity, the logical negation operator is not, the logical conjunction operator is and, the logical disjunction operator is or, the equality operator is ==, and the inequality operator is !=.

Problem 10 #

Which of the following conditions are sufficient for not (A or B) to evaluate to True? Select all options that apply:

1. A is True and B is True
2. A is True and B is False
3. A is False and B is True
4. A is False and B is False
5. (not A) and (not B) is True

Problem 11 #

Which of the following conditions are sufficient for (A != B) and (A or B) to evaluate to True? Select all options that apply:

1. A is True and B is True
2. A is True and B is False
3. A is False and B is True
4. A is False and B is False

Problem 12 #

Imagine that the school registrar has asked you to build a program to verify student enrollments. You have one text file containing the names of all students in good standing with the University, and another set of files containing the names of all students who have enrolled in courses. You need to find out which students enrolled in courses are not in good standing, and plan to read one of the text files into a data structure.

Which of the following data structures is best suited for this task?

1. array
2. binary search tree
3. hash table
4. linked list
5. none of the above

Problem 13 #

What is the derivative $f^\prime(x)$ of the function $f(x) = 3 x^2 + \sin x$?

The following definition for the derivative operator $^\prime$ may be useful:

$$ \begin{aligned} (x)^\prime &= 1 \cr (n)^\prime &= 0 \text{\qquad where } n \text{ is any constant} \cr (f(x)+g(x))^\prime &= f^\prime(x)+g^\prime(x) \cr (f(x)-g(x))^\prime &= f^\prime(x) - g^\prime(x) \cr (f(x) \cdot g(x))^\prime &= f^\prime(x) \cdot g(x) + f(x) \cdot g^\prime(x) \cr (f(x) ^ n)^\prime &= n\cdot f^\prime(x) \cdot f(x)^{n-1} \text{\qquad where } n \text{ is any constant} \cr \left( \frac{f(x)}{g(x)} \right)^\prime &= \frac{(f^\prime(x) \cdot g(x) - f(x) \cdot g^\prime(x))}{g(x)^2} \cr (\sin f(x))^\prime &= f^\prime(x) \cdot \cos f(x) \cr (\cos f(x))^\prime &= f^\prime(x) \cdot {-\sin f(x)} \cr (\ln f(x))^\prime &= \frac{f^\prime(x)}{f(x)} \cr \end{aligned} $$