CMU 15-112: Fundamentals of Programming and Computer Science
Quiz 4 (35 minutes)

Quiz 4 frontmatter:

(This quiz was given in the CS Academy quiz proctoring app on 8/2)

You may do the questions in any order, and you may leave them incomplete and return to them later if you wish. HOWEVER, if you begin a free response question (where you can run python code) any viewed but unsubmitted CTs and multiple choice questions will automatically be submitted and locked (so that you cannot run the CT code in the free response editor).
You have a fixed time to answer all the questions.
- Watch the timer carefully!
If you are locked out due to a security error, exit the breakout room to speak with the TA or faculty member on duty

Quick Reminders:

Plug in your phone and computer
Turn on do-not-disturb on your phone and computer and make sure your phone won't go to sleep or remove you from the zoom call or turn off your camera.
Your phone must be properly positioned as described below
Other than your main monitor and your phone, you must not have any other computer monitors on, and no other phones/tablets/calculators/notes/other resources should be accessible.
Follow all proctoring instructions exactly. Failure to adhere to proctoring policy may result in a zero on the quiz, and possibly a deduction from your semester grade based on severity.
Any attempt to subvert, exploit, or misuse the testing environment (including attempts to access the raw content or investigate the underlying source code) will be considered a severe academic integrity violation, possibly leading to course failure or other significant penalties.

During the quiz

You may not ask questions during the quiz.
- If you are unsure how to interpret a problem, take your best guess.
You may not leave the quiz and return, and you may not interact with anyone else (remotely or in person) except for the TAs or faculty until the quiz is submitted.
You must not leave the full-screen testing environment at any time. If anything except the testing environment is visible on your screen, it will trigger a security error, and you will be locked out of your quiz / you may receive a deduction or a zero. Additionally, we will investigate whether this could be a matter of academic integrity.
All of these must be visible to your phone's camera at all times:
- All of your screen, and any other screens nearby
- Most of your desk
- Your mouse and keyboard
- Note: You must not block your screen with your head/arms/etc while taking the quiz
- You must not have any other computer monitors on, and no other phones/tablets/calculators/notes/other resources should be accessible.
If you are locked out due to a security error, exit the breakout room immediately to speak with the TA or faculty member on duty. At their discretion, they may unlock the quiz and allow you to continue.
When you finish a question, press the submit button to lock in your answer. You will not be able to return and change your answers after pressing submit. Once the allotted time elapses, the quiz will auto-submit with your current progress. See above for more details

You must use your phone to join the proctored Zoom meeting. If you cannot join Zoom on your phone:

You may receive a deduction if this is due to a lack of preparedness
Join Zoom on your computer instead.
You MUST still position your phone to see the items listed above, and you MUST record a video of the entire quiz until your proctor releases you.
We will not grade any section of the quiz that we did not receive full video for, and you may receive a zero.This is true even if your phone runs out of storage space.
After the quiz, immediately upload this to Google Drive or Box or Dropbox and then send us a link.You must use one of these three services. If you email the video directly or upload it to another source, you will receive a zero.
If we cannot access or view your video, or if you do not record one, we will give you a zero, so make sure your upload is successful. We must be able to view the video soon after the quiz, so please begin uploading immediately.
When your upload is complete, fill out the tech fail form and copy in the link to your video. Do not send it by email unless we request it.

After the quiz

If you submit your quiz before time is up, wait until everyone else finishes and your proctor gives you further instructions.
Wait until your proctor dismisses you, and then please exit Zoom. You are done! Rejoin the lecture Zoom session on your laptop.

For any tech fails (laptop or internet stops working, etc.):

If you are still in Zoom, exit the breakout room and speak with the TA/Faculty in the main room. Do not speak while in the breakout room.
If you cannot immediately speak with a TA or professor, stop taking the quiz and fill out the tech fail form linked from the course website's forms?page. (Note: A security error is not a tech fail, unless you are unable to return to the testing environment without triggering another one. We may be able to address accidental security errors in certain circumstances, but only if they are immediately brought to our attention.)
We will email you soon to resolve the issue.

1. True/False [2 points]

After running the code below, C[0] and C[1] are aliases of the same list.

import copy
A = [1, 2, 3]
B = [A, A]
C = copy.deepcopy(B)

2. Short Answer [2 points]

Fill in the blanks in the wordSearchFromCellInDirection below.


def wordSearchFromCellInDirection(board, word, startRow, startCol, drow, dcol):
    (rows, cols) = (len(board), len(board[0]))
    dirNames = [ ["up-left"  ,   "up", "up-right"],
                 ["left"     ,   ""  , "right"   ],
                 ["down-left", "down", "down-right" ] ]
    for i in range(len(word)):
        row = startRow + i*drow
        col = startCol + i*dcol
        if ((row < 0) or (row >= rows) or
            (col < 0) or (col >= cols) or
            (________)):   #<----First blank
            return None
    return (word, (startRow, startCol), dirNames[______][______]) #<--Second and Third blanks

3. Multiple Choice [2 points]

Which of the following statements are true? (Note: More than 1 may be true)

s = {} creates an empty set
d = {} creates an empty dictionary
If D is a dictionary, D.get(k, set()) does not crash even if k is not in D
Checking for membership in a set is no more efficient than checking in a list
Python internally uses a hash() function when adding a key-value pair to a dictionary

4. Short Answer [2 points]

Which is faster, merge sort or selection sort? What is the Big-O of the faster sort?

5. Code Tracing [10 points]

Indicate what the code below prints.


import copy
def ct2(L):
    a = L
    b = copy.copy(L)
    c = copy.deepcopy(L)
    a[1][0] += 2
    b[0] = a[1] * 2
    a[0][0] += a.pop()[0]
    b[1] = c[0]
    print(f'a = {a}')
    print(f'b = {b}')
    return c

L = [[1],[2, 3]]
print(f'c = {ct2(L)}')
print(f'L = {L}')

6. Free Response 1: Book and Chapter Classes [26 points]

Write the classes Book and Chapter so that the following test code passes. Do not hardcode the test cases, but you may assume that the parameters are always legal (so, for example, chapter indexes are always in bounds).

def testBookAndChapterClasses():
    print("\tTesting Book and Chapter classes...", end="")
    chapterA = Chapter('I love CS!', 30) # chapter title, # of pages
    chapterB = Chapter('So do I!', 15)
    book1 = Book('CS is Fun!', [chapterA, chapterB]) # book title, chapters
    book2 = Book('The Short Book', [ Chapter('Quick Read!', 5) ])

    assert(book1.chapterCount == 2)
    assert(book1.getPageCount() == 45)
    assert(book2.chapterCount == 1)
    assert(book2.getPageCount() == 5)
    assert(book1.getChapter(0).title == 'I love CS!')
    assert(book1.getChapter(1).title == 'So do I!')
    assert(book2.getChapter(0).title == 'Quick Read!')

    # Move chapter 0 from book1 to the end of book2
    # so moveChapter always moves to the end of the target book.
    book1.moveChapter(0, book2)

    assert(book1.chapterCount == 1)
    assert(book1.getPageCount() == 15)
    assert(book1.getChapter(0).title == 'So do I!')
    assert(book2.chapterCount == 2)
    assert(book2.getPageCount() == 35)
    assert(book2.getChapter(0).title == 'Quick Read!')
    assert(book2.getChapter(1).title == 'I love CS!')
    print("Passed!")


testBookAndChapterClasses()

7. Free Response 2: maxRowColSum(L) [26 points]

Write the function maxRowColSum(L) which takes in a rectangular 2D list of integers and returns the largest possible sum of integers from any row or column.

For example, given the following input:


L = [[0, 1],
     [7, 8],
     [3, 4]]

maxRowColSum(L) returns 15, because 7+8 is 15 and no other row or col has a greater sum. And for the following input:


L = [[ 1,  2,  3,  -4],
     [ 2,  3,  4,  -5],
     [ 1,  1,  5,  -6]]

maxRowColSum(L) returns 12, because 3+4+5 is 12. Your solution must be non-destructive, and as always, we may grade using additional test cases. Note the test cases, which show that an empty list sums to 0, but a non-empty list could sum to a negative value.

def maxRowColSum(L):
    return 42


def testMaxRowColSum():
    import copy
    print("\tTesting maxRowColSum...", end="")
    L = [[0, 1],
         [7, 8],
         [3, 4]]
    assert(maxRowColSum(L) == 15)

    L = [[ 1,  2,  3,  -4],
         [ 2,  3,  4,  -5],
         [ 1,  1,  5,  -6]]
    assert(maxRowColSum(L) == 12)

    L = [[]]
    assert(maxRowColSum(L) == 0)

    L = [[-10]]
    assert(maxRowColSum(L) == -10)
    print("Passed!")


testMaxRowColSum()

8. Free Response 3: makeSpeciesDictionary(animalData) [30 points]

Say we are given the following 2D list of animalData, where each row contains exactly three elements (a species, a breed, and a name):

animalData = [['dog','labrador','fred'],
                   ['cat','persian', 'betty'],
                   ['dog','shepherd','barney'],
                   ['dog','labrador','fred'],
                   ['dog','labrador','wilma']]

Write the function makeSpeciesDictionary(animalData) that takes data formatted like this, and returns a dictionary mapping each species to another dictionary that maps each breed of that species to a set of the names in that table for that species.

For example, for the animalData given above, makeSpeciesDictionary(animalData) returns this:

{
  'dog':
        { 'labrador' : { 'fred', 'wilma' },
          'shepherd' : { 'barney' }
        },
  'cat':
        {  'persian' : { 'betty' }
        }
}

We may use other test cases, including species and breeds not given here, so do not hardcode!

def makeSpeciesDictionary(animalData):
    return 42


def testMakeSpeciesDictionary():
    print("Testing makeSpeciesDictionary...", end="")
    animalData = [['dog','labrador','fred'],
                  ['cat','persian', 'betty'],
                  ['dog','shepherd','barney'],
                  ['dog','labrador','fred'],
                  ['dog','labrador','wilma']]
    assert(makeSpeciesDictionary(animalData) == {
                  'dog':
                        { 'labrador' : { 'fred', 'wilma' },
                          'shepherd' : { 'barney' }
                        },
                  'cat':
                        {  'persian' : { 'betty' }
                        }
                })

    animalData = [['dog','golden','Boo'],
                  ['cat','chonk', 'Kitty'],
                  ['axolotl','wildType','Chee'],
                  ['axolotl','leucistic','Meep'],
                  ['dog','unknown','Chee']]
    assert(makeSpeciesDictionary(animalData) == {
                    'dog':
                        {'golden': {'Boo'},
                         'unknown': {'Chee'}
                        },
                    'cat':
                        {'chonk': {'Kitty'}
                        },
                    'axolotl':
                        {'wildType': {'Chee'},
                         'leucistic': {'Meep'}
                        }
                })
    print("Passed!")


testMakeSpeciesDictionary()

CMU 15-112: Fundamentals of Programming and Computer Science Quiz 4 (35 minutes)

CMU 15-112: Fundamentals of Programming and Computer Science
Quiz 4 (35 minutes)