CS8—Final Exam
E03, 10F, Phill Conrad, UC Santa Barbara
12/08/2010

Name: ___________________________________________________


Umail Address: ______________________________@ umail.ucsb.edu



Circle one:       9am   10am   11am   noon



Please write your name only on this page. That allows me to grade your exams without knowing whose exam I am grading.

This exam is closed book, closed notes, closed mouth, cell phone off,
except for:

There are 100 points worth of questions on the exam, and you have 180 minutes to complete the exam. However, the exam is designed for you to be able to complete it in 100 minutes (1 hour 40 minutes).

A hint for allocating your time—on your first pass through the exam:

If you do that, after you complete your first pass thorugh the exam in 50 minutes, you'll still have 1 hour 20 minutes to:


  1. AK
    AL
    AR
    AZ
    CA
    CO
    etc...
    

    (12 pts) The code below is intended to read data from a file that which contains up to 50 lines of text. Each line of that file contains exactly one state abbreviation, as shown in box at right. The code is supposed to read the data from that file into a list, and return that list as the result of the function. and produce a list containing all of the state abbr, and then close the file.

    The code below was tested, and then several lines of code were removed. Your job is to fill in the blanks, in a way consistent with the comments.

    The code should not depend on the fact that there are exactly 50 states—for any given run of the program, the file might contain ALL 50 states, or it might contains only some of them (e.g. all states west of the Mississippi, all states that border the Gulf of Mexico, etc.)

    code/readStates.py
    1# readStates.py
    2# read from a file containing up to 50 2-letter
    3# state abbreviations, one per line.
    4# return them as a list of strings
    5# Example call: abbrList = readStates('states.txt')
    6
    7def readStates(fname):
    8
    9 # (a) open file
    10
    11 infile = ____________________________________________________
    12
    13 # initialize stateList to empty list
    14
    15 stateList = []
    16
    17 # (b) read every line in the file
    18
    19 for ___________________________________________________
    20
    21 stateList.append(line.strip())
    22
    23 # close file
    24
    25 infile.close()
    26
    27 # (c) return the answer
    28
    29 ________________________________________________
    30
    31
  2. (20 pts) Continuing with idea of a list of states—here's the stub of a function, documented via its docstring—and some test cases it should pass. Cross out the return "stub" line and replace it with the coded needed to work properly (including passing all the test cases indicated below.)
    code/statesThatStartWith.py
    1def statesThatStartWith(listOfStates,letter):
    2 """
    3 listOfStates should be a list containing only
    4 strings of length 2 (or the empty list), and letter should
    5 be a string of length 1---if either of those conditions is violated,
    6 return "error"
    7
    8 otherwise:
    9 return a new list containing only the strings from
    10 listOfStates that start with letter. If listOfStates is the
    11 empty list, return empty list
    12 """
    13 return "stub"
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32def test_statesThatStartWith():
    33 """
    34 run test cases and return the number of failed tests (if any)
    35 """
    36 print("test_statesThatStartWith:")
    37 failed = 0
    38 states=['AK','AL','AR','AZ','CA','CO','CT','DE','FL','GA']
    39 failed+= check_expect("test1",statesThatStartWith([],'A'),[])
    40 failed+= check_expect("test2",statesThatStartWith(['PA','RI',],'R'),['RI'])
    41 failed+= check_expect("test3",statesThatStartWith(states,'D'),['DE'])
    42 failed+= check_expect("test4",statesThatStartWith(states,'A'),
    43 ['AK','AL','AR','AZ'])
    44 failed+= check_expect("test5",statesThatStartWith(states,"Z"),[])
    45 failed+= check_expect("test6",statesThatStartWith(states,'C'),
    46 ['CA','CO','CT'])
    47 failed+= check_expect("test7",statesThatStartWith(states,2),"error")
    48 failed+= check_expect("test8",statesThatStartWith(12,'A'),"error")
    49 failed+= check_expect("test9",statesThatStartWith(["UCSB","UCLA"],'U'),"error")
    50 failed+= check_expect("test9",statesThatStartWith(["CA",3],'C'),"error")
    51 return failed
  3. (9 pts) Below are four Python programs, with four possibilities for what the output might be.
    For each one, circle the correct output—or if none of them is correct, circle "none of these"

    Program Circle one of these outputs
    code/whatOutput01.py
    1def bar():
    2 print("A")
    3
    4def fum():
    5 print("B")
    6
    7def foo():
    8 fum()
    9 print("C")
    10 bar()
    11
    12def go():
    13 print("D")
    14 foo()
    15
    16go()
    A
    B
    C
    D
    
    D
    A
    B
    C
    
    D
    B
    C
    A
    
    D
    C
    B
    A
    
    None
    of
    these
    code/whatOutput02.py
    1def bar():
    2 print("A")
    3 fum()
    4
    5def fum():
    6 print("B")
    7
    8def foo():
    9 print("C")
    10
    11def go():
    12 bar()
    13 foo()
    14 print("D")
    15
    16go()
    A
    B
    C
    D
         
    D
    A
    B
    C
         
    D
    B
    C
    A
         
    D
    C
    B
    A
         
    None
    of
    these
    code/whatOutput03.py
    1def bar():
    2 print("A")
    3
    4def fum():
    5 foo()
    6 print("B")
    7 bar()
    8
    9def foo():
    10 print("C")
    11
    12def go():
    13 print("D")
    14 fum()
    15
    16go()
    A
    B
    C
    D
         
    D
    A
    B
    C
         
    D
    B
    C
    A
         
    D
    C
    B
    A
         
    None
    of
    these
  4. (10 pts) Fill in the table below, according to these instructions:
    • The first column contains a Python expression involving the not operator
    • Directly underneath each expression,
      fill in a Python expression that is equivalent to the first, without using the not operator.
    • In the second column, fill in the value of the expression, assuming that w, x, y and z have the values shown.

    The first row is done for you an an example

    under each expression,
    fill in an equivalent expression
    that doesn't use not
    Value of expression when
    w="uc"; x=7; y=3; z=[2,1]

     not type(z) == list

       type(z) != list           

    False

     not (y <= z[0])


     not ( type(w)!=str or len(w)>2)


     not (x<7) and not (y>=x)


                              

     not (z[0]<z[1] and z[1]<3)


     not (y!=3) and y > x


  5. Hint: In case it isn't obvious, DEC can be an abbreviation for both December, or Decimal, and OCT can be an abbreviation for both October and Octal.

    Cultural Note: If you are unfamiliar with American holidays:
    • Christmas is a holiday that takes place on December 25
    • Halloween is a holiday that takes place on October 31st.
    (5 pts) Now, its time for a lame joke about Computer Science:

    Q: Why do computer scientists have a hard time telling the difference between Christmas and Halloween?

    A: Because DEC 25 = OCT 31

    Use the binary representations of DEC 25 and OCT 31 to explain the mathematical basis of this joke.

  6. In the box below is a recursive function to find the sum of a list—but the comments have been removed.
    1. (3 pts) Circle the "base case" and write beside it the words
      base case
    2. (3 pts) Circle the "recursive call" (be very precise—circle only the function call) and write beside it the words
      recursive call
    code/recursiveSumList.py
    1def sumList(theList):
    2 if (theList==[]):
    3 return 0
    4 else:
    5 return theList[0] + sumList(theList[1:])
     
  7. (3 pts) In the figure below, you'll see an incorrect version of the same function from the previous problem—the difference between this and the correct version is indicated in bold and marked with a comment.

    Briefly describe what will happen on the run-time stack when this version of the function is called.

    (I don't want a full detailed story—just a couple of sentences that describe the big picture of what will take place.)

    code/recursiveSumListWrong.py
    1def sumList(theList):
    2 if (theList==[]):
    3 return 0
    4 else:
    5 return theList[0] + sumList(theList[0:]) # [0:] should be [1:]












  8. (3 pts) In lab10, we developed a "heuristic" for counting syllables.

    In your own words, what is a heuristic, and how does it differ from an "algorithm"?
  9. (12 pts) The code below is one correct solution to one of the functions from lab10—with several lines of code replaced by blanks. Your job is to fill in the blanks, in a way consistent with the comments, so that the test cases pass.

    The test cases are on a separate handout which you should have received with this exam.

    code/allVowelsA.py
    1
    2def allVowelsA(word):
    3 """
    4 allVowelsA is a function that changes all vowels to A.
    5 This function is a building block for a function that will count
    6 syllables by counting vowels. For that purpose, all vowels are equivalent.
    7 But, we want to remove consecutive duplicate vowels. Converting all
    8 vowels to the same vowel is a first step.
    9 word should be a string---otherwise return boolean value False
    10 when word is a string, return word with all vowels changed to the letter a
    11 examples:
    12 allVowelsA("by") produces "ba"
    13 allVowelsA("alien") produces "alaan"
    14 allVowelsA("boot") produces "baat"
    15 allVowelsA("fruition") produces "fraataan"
    16 Note: empty string is legal, and should return empty string
    17 """
    18
    19 # (a) make sure word is of the correct type
    20
    21 if (type(word)!=str):
    22
    23 ________________________________________
    24
    25 result=""
    26 vowels="aeiouyAEIOUY"
    27 for i in range(len(word)):
    28
    29 # (b,c) Use accumulator pattern on result,
    30 # replacing letter with a if its a vowel (two blanks below)
    31
    32 if word[i] in vowels:
    33
    34 ________________________________________
    35
    36 else:
    37
    38 __________________________________________________________
    39
    40 return result
    41
    42
  10. (20 pts) The code below is a different correct solution to the same function from lab10 described in the previous problem—again, with several lines of code replaced by blanks. Your job is to fill in the blanks, in a way consistent with the comments, so that the test cases pass.

    The test cases are on a separate handout which you should have received with this exam.

    code/allVowelsARecursive.py
    1def allVowelsA(word):
    2 """
    3 allVowelsA is a function that changes all vowels to A.
    4 This function is a building block for a function that will count
    5 syllables by counting vowels. For that purpose, all vowels are equivalent.
    6 But, we want to remove consecutive duplicate vowels. Converting all
    7 vowels to the same vowel is a first step.
    8 word should be a string---otherwise return boolean value False
    9 when word is a string, return word with all vowels changed to the letter a
    10 examples:
    11 allVowelsA("by") produces "ba"
    12 allVowelsA("alien") produces "alaan"
    13 allVowelsA("boot") produces "baat"
    14 allVowelsA("fruition") produces "fraataan"
    15 Note: empty string is legal, and should return empty string
    16 """
    17 # (a) make sure word is of the correct type
    18
    19 if (type(word)!=str):
    20
    21 ________________________________________
    22
    23 # (b) if word is empty string, return empty string
    24
    25 __________________________________________:
    26 return ""
    27
    28 # Now we know we have at least one letter in the word
    29 vowels="aeiouyAEIOUY"
    30
    31 # (c) If the first letter in the word is a vowel...
    32
    33 if ( _________________________ in vowels):
    34 # We'll replace it with an 'a'
    35 ch = 'a'
    36
    37 else:
    38
    39 # (d) Otherwise, keep the same letter
    40
    41 ch = _________________________
    42
    43 # (e) Combine the first letter with a recursive call on rest of word
    44
    45 return ch + _______________________________________________________________
    46

End of Exam

Total points: ?

HANDOUT for CS8—Final Exam
E03, 10F, Phill Conrad, UC Santa Barbara
12/08/2010

Test cases for allVowelsA (problems 9,10)

code/test_allVowelsA.py
1def test_allVowelsA():
2 failures = 0
3 failures += check_expect('allVowelsA("")',allVowelsA(""),"")
4 failures += check_expect('allVowelsA("pwn")',allVowelsA("pwn"),"pwn")
5 failures += check_expect('allVowelsA("pwned")',allVowelsA("pwned"),"pwnad")
6 failures += check_expect('allVowelsA("pone")',allVowelsA("pone"),"pana")
7 failures += check_expect('allVowelsA("We")',allVowelsA("We"),"Wa")
8 failures += check_expect('allVowelsA("hold")',allVowelsA("hold"),"hald")
9 failures += check_expect('allVowelsA("these")',allVowelsA("these"),"thasa")
10 failures += check_expect('allVowelsA("be")',allVowelsA("be"),"ba")
11 failures += check_expect('allVowelsA("self")',allVowelsA("self"),"salf")
12 failures += check_expect('allVowelsA("pone")',allVowelsA("pone"),"pana")
13 failures += check_expect('allVowelsA("defenestrate")',
14 allVowelsA("defenestrate"),
15 "dafanastrata")
16 failures += check_expect('allVowelsA("independence")',
17 allVowelsA("independence"),
18 "andapandanca")
19 failures += check_expect('allVowelsA("people")',
20 allVowelsA("people"),
21 "paapla")
22 failures += check_expect('allVowelsA("fruition")',
23 allVowelsA("fruition"),
24 "fraataan")
25
26 failures += check_expect("allVowelsA(0)",allVowelsA(0),False)
27 failures += check_expect("allVowelsA(['a'])",allVowelsA(['a']),False)
28
29 return failures