practice.md

CS107 -- Exam 1 Practice

Here are some practice problems for the upcoming exam. These are somewhat representative, but won't be precisely what's on the exam: they exercise the same kinds of ideas.

I'll just do a quick dump of problems. I won't be giving a key right now, because my experience is that studnets don't work the questions but just look at the key if they have one. I am happy to check your answers if you write them up. I'll also comment on problems a bit tomorrow.

1. In git, briefly explain what a merge conflict is and how you might fix it. You do not need to give precise line-by-line instructions, but a rough 1-3 sentence idea of the steps you'd take.

2. Draw a call tree for foo(3).

def foo(x):
  return bar(x-1)

def bar(x):
  if (x == 2): return 1
  else: return foo(x)

3. Write a recursive function that terminates for any multiple of three, but runs forever (does not terminate) for any other input

4. Consider the following functions:

def f(x):
  if (x < 1): return x
  else: return (x/2) * g(x)

def g(x):
  if (x < 1): return 1
  else: return g(x-3)

What is the worst-case running time (big-O) of f(x)?

5. Consider the following functions:

def isEmpty(x): return x == []

def h(x):
   if (isEmpty(x)): return []
   # Note that int(..) truncates the number to an int, e.g., int(.5) = 0 and int(1.5) = 1
   else: return h(x[0:int(len(x)/2)])

• Describe in english the return value of h(x) (for any x)
• What is the running time (worst-case / big-O) of h(x)

6. Consider the following functions, meant to check if an element e is in a list.

def forall(l,f):
    if (l == []): return True
    else: return f(l[0]) and forall(l[1:],f)

def lookup(l,e):
    if (l == []): return None
    elif (l[0] > e): return False
    elif (l[0] == e): return True
    else: return lookup(l[1:],e)

(a) Write--in English prose--a precondition such that--if the precondition passes--the function will return whether or not the element exists in the list (and will never return none) (b) Write--in code--the same precondition. You should consider using the len function in Python.

7. Consider the following function:

def f(l):
  if (len(l) == 1): return 2
  else: return 2 + f(l[1:])

(a) Write a precondition (in english) that--when true--will make this function return twice the length of the list l.

(b) Prove that this function returns twice the length of l, by induction.

• You want to prove forall l, P(l) (whenever l satisfies the precondition you write in part (a)). Write P(l) (the statement to br proven) in English

• Write the base case for your induction.

• State (but do not prove) the inductive hypothesis.

• Perform the proof that P(l) -> P([e] + l)

8. Consider the following function:

def f(l):
  i = 0
  while (i < len(l)):
    l[i] = l[i] * 2
    i = i + 1

• Assume x = [2,5,8] and f(x) is called. What is the value of x now?

9. Using a loop, write a function, gtzero(l), that calculates how many elements of a list are greater than zero. For example, gtzero([5,8,3,-1,0,5]) = 4.

10. What is the output of the following code:

x = [1,1,3]
y = [5,8,12]
z = x[0] + x[0]
x[z] = y
x[z-2+1] = 3
print(x[z][2] * x[z-1])

11. What does the following piece of code do to the list l?

def foo(l):
  x = 0
  while (x < len(l)):
    l[x] = l[len(l) - 1 - x]
    x = x+1