CSE 101 (Section 01): Introduction to Computational and Algorithmic Thinking Lab #5
Spring 2019
Assignment Due: Saturday, April 13, 2019, by 11:59 PM
Assignment Objectives
By the end of this assignment you should be able to design, code, run and test original Python functions that solve simple programming problems involving dictionaries and file input.
Getting Started
The assignments in this course require you to write Python code to solve computational problems. To help you get started on each assignment, we will give you a basic starter file for each problem. These files will contain function stubs1 and a few tests you can try out to see if your code seems to be correct (note that the test cases we give you in the starter files are just examples; we will use different test inputs to grade your work!). You need to complete (fill in the bodies of) these functions for the assignments. Do not, under any circumstance, change the names of the functions or their parameter lists. The automated grading system will be looking for functions with those exact names and parameter lists; if you change anything related to the header of a function, the grading program will reject your solution and mark it as incorrect.
Directions
Solve each of the following problems to the best of your ability. The automated grading system will execute your solution to each problem several times, using different input values each time. Each test that produces the correct/expected output will earn 1 or more points. This assignment contains 4 problems; you must earn at least 15 out of 20 points for a passing score. Note that not every problem may be worth the same number of points!
Each starter file has a comment block at the top with various important information. Be sure to add your information (name, ID number, and NetID) to the first three comment lines, so that we can easily identify your work. If you leave this information out, you may not receive credit for your work!
Submit your work as a set of individual Python files (one per problem). DO NOT zip or otherwise compress your files, and DO NOT place all of your functions in a single file. If you do so, the automated grading system will not be able to process your work and you will receive a failing grade for this assignment!
Each of your functions MUST use the names and parameter lists indicated in the starter code file. Submissions that have the wrong function names (or whose functions contain the wrong number of parameters) can’t be graded by our automated grading system, and may receive a grading penalty (or may not be graded at all).
Eachofyourfunctionsmustexplicitlyreturnitsfinalanswer;thegradingprogramwillignoreanythingthatyourcode prints out. Along those lines, do NOT use input() anywhere within your functions (or anywhere before the
if __name__ == “__main__”:statement);yourfunctionsshouldgetalloftheirinputfromtheirparameters.
Blackboard will provide information on how to submit this particular assignment. Be sure to submit your final work as directed by the indicated due date and time. Late work will not be accepted for grading. Work is considered late if it is submitted after the due date and time. If you wish to use a token to extend the submission deadline for 24 hours from the original date, you must notify the instructor (via e-mail) BEFORE the original assignment deadline has passed.
Programs that crash will likely receive a failing grade, so make sure you thoroughly test your work before submitting it.
1Stubs are functions that have no bodies, or have very minimal, bodies
CSE 101 (Section 01) – Spring 2019 Lab #5 Page 1
Part I: Multiple Madness (5 points)
(Place your answer to this problem in the “multiples.py” file)
Complete the multiples() function, which takes two arguments: a string representing the name of a (plain text) data file and a positive integer. Each line in the data file consists of one or more positive integers, each separated by a single space. The function returns an integer corresponding to the total number of lines in the data file whose contents add up to a multiple of the second argument. For example, multiples(“data.txt”, 3) would return the number of lines in “data.txt”thatadduptoamultipleof3(meaningthatalinelike”4 12 2″,whichaddsupto18,wouldbecounted, but”5 4 2”,whichaddsupto11,wouldnot).
The easiest way to do this is to open the data file using a for loop, as shown in the lecture slides: forvariable-namein open(name-of-data-file):
For each line, use the strip() method to get rid of any extra newline characters, then call split() to turn it into a list of numbers (in string format; you’ll need to convert them to integers before you add them up).
In (rough) pseudocode:
set count to 0
for each line in the data file:
call strip() on the line
call split() on the line and save the resulting list into a new variable
set total to 0
for each value in the list:
convert the value to an integer and add it to total
if total modulo the target value is 0:
add 1 to count
NOTE: Make sure that your data files are in the same folder/directory as “multiples.py”! Otherwise, the predefined test cases in the starter code (which call our sample data files) won’t work.
Examples: Function Call
multiples(“mult1.txt”, 2)
multiples(“mult1.txt”, 6)
multiples(“mult2.txt”, 3)
multiples(“mult2.txt”, 4)
multiples(“mult3.txt”, 2)
multiples(“mult3.txt”, 8)
Return Value (Number of Matches)
5 3 2 1 4 0
CSE 101 (Section 01) – Spring 2019
Lab #5
Page 2
Part II: The Great Dictionary Escape (5 points)
(Place your answer to this problem in the “escape.py” file)
Complete the escape() function, which takes a Python dictionary and an integer value as its arguments and returns an integer. The dictionary exclusively contains integer key-value pairs (meaning that every key and every value is an integer, like 3:2). The integer argument is guaranteed to be a key within the dictionary. Starting with the integer argument, find the dictionary value for that key. Use that value as a new dictionary key; its value will become the next dictionary key, and so on. Eventually, you will find a value which is not a valid key in the dictionary. At that point, the function ends and returns the total number of steps that were required to reach an invalid key.
For example, consider the dictionary {1: 3, 8: 4, 7: 9, 2: 7, 9: 4, 6: 2} and the starting key 6:
1. The key 6 corresponds to the value 2, which becomes our new key.
2. The key 2 corresponds to the value 7, which becomes our new key.
3. The key 7 corresponds to the value 9, which becomes our new key.
4. The key 9 corresponds to the value 4, which becomes our new key.
5. 4 is not a valid key in the dictionary, so the function ends after performing a total of 4 steps: (6 → 2, 2 → 7, 7 → 9, and 9 → 4)
Examples: Function Call
escape({1:3, 8:4, 7:9, 2:7, 9:4, 6:2}, 6)
escape({2:-1, 7:1, 9:4, 8:2, 5:4, 3:3, 1:-1}, 7)
escape({3:11, 9:9, 12:1, 5:12, 10:14, 13:2, 11:4, 15:5, 1:14, 7:3, 6:15,
8:6}, 8)
escape({13:14, 17:9, 11:15, 8:5, 15:10, 6:18, 1:2, 3:15, 7:2, 12:9, 14:17,
18:8, 16:7, 5:14, 10:19, 19:13, 4:16, 2:6}, 4)
Return Value
4 2 6
10
CSE 101 (Section 01) – Spring 2019 Lab #5
Page 3
Part III: The Heaviest Dictionary Key (5 points)
(Place your answer to this problem in the “heaviest.py” file)
Assume that the “weight” of a dictionary key is determined by its value. That means that the “heaviest” key in a Python dictionary is the one that has the largest value. For example, in the dictionary {11:5, 7:8, 19:9, 1:15, 5:2}, the heaviest key is 1, since it maps to the largest value (15).
Complete the heaviest() function, which takes one argument: a Python dictionary whose values are integers (the keys may be of any valid type). The function returns the key that corresponds to the largest value (if two or more values are tied for the largest, the function can return any one of the keys that correspond to that value).
There are several ways to solve this problem. One way (which may not be the most efficient, but that doesn’t matter here) is to use a loop that examines each key in turn, keeping track of the key that has the largest value seen so far:
set heaviest key to the first key in the dictionary
for each key in the dictionary:
if the current key’s value is greater than the heaviest key’s value:
set the heaviest key to the current key
NOTE: The Python dictionary method keys() returns something called a view, not a regular list. If you want to use the [ ] operator to retrieve the value at a particular position in the set of keys, you need to convert the view to a list using the list() function first:
keys = list(myDictionary.keys())
thirdKey = keys[2] # etc.
Examples: Function Call
heaviest({11:5, 7:8, 19:9, 1:15, 5:2})
heaviest({1:3, 8:4, 7:9, 2:7, 9:4, 6:2})
heaviest({“Saturn V”:6262500, “Atlas V”:46678, “Delta II”:511190})
Return Value
1
7
Saturn V
CSE 101 (Section 01) – Spring 2019 Lab #5
Page 4
Part IV: Recovering Garbled Text (5 points)
(Place your answer to this problem in the “recover.py” file)
In a computer network, data must be transmitted between different nodes (devices). Unfortunately, this is not an error-proof process. Transmission problems can garble a message, leading to errors in the data that is received. Luckily, the errors are (usually) randomly distributed, so they will occur in different places each time a message is transmitted. By transmitting the same message multiple times and comparing the results, we can gather data that will help us to reconstruct the original message. To do this, we examine each position of each message copy. The value that occurs most frequently in a specific position is (usually) the correct value for that position.
For example, consider the following repeated/retransmitted message (in this example, spaces have been inserted between each letter for clarity):
felnowowld hejwoaprod gelqhwkbpy hprseworld hellbmorld hegloxlrhd hhllowerku htlkqwxsld
In the first column/position, we have 1 f, 1 g, and 6 h’s. Since “h” is the most common value for the first letter, we can guess that the first letter of the original message was most likely “h”. The second position has 5 e’s, 1 h, 1 p, and 1 t, so “e” is the most likely second character. Repeat this process for each position in the message copies. In this case, the original message turns out to be “helloworld”.
Complete the recover() function, which takes a list of equal-length strings as its single argument (each string ONLY contains lowercase letters). recover() returns a single string whose length is equal to that of any one of the source strings. This function works as follows:
1. Create a dictionary to hold the frequency of each letter (you can either pre-populate this with all 26 letters, or just create an empty dictionary and use setdefault() to add new letters as you find them).
2. Create a variable to hold the recovered string (this will initially be the empty string).
3. For each index value:
(a) Examine the letter at that index in each source string. Update the dictionary’s count for that letter (i.e., if you see “b”, add 1 to the integer value associated with the key “b” in your dictionary).
(b) When you have evaluated all of the source strings at the given index, determine which dictionary key (letter) has the largest value associated with it (for each key in your dictionary, examine its value and compare it to the largest value that you’ve seen so far). Here is pseudocode for one possible sub-algorithm:
most_common = value of index 0 from your dictionary’s list of keys
for each key k in your dictionary:
if k’s value is greater than the value associated with most_common:
set most_common to k
Append that letter to your “recovered string” variable. For example, given the dictionary {“a”:3, “b”:5, “c”:4}, your code would return “b” as the most frequent letter. If two or more letters tie for the highest frequency in
CSE 101 (Section 01) – Spring 2019 Lab #5 Page 5
a given position, you may select any one of them as the “winner”; we will ultimately use context and human intuition to determine what the correct letter should have been.
(c) Clear or reset the contents of the dictionary in preparation for the next round of your loop. 4. When the outermost loop ends, return the value of your recovered string.
Examples: Function Call
recover([“edferfthm”, “aqvorithm”, “algbridnn”, “glgoxirhm”,
“iogleielb”, “alwxuithj”, “wlaobifhm”])
recover([“hqsokhoepmlyhn”, “seoqaipodllbmu”,
“sjeqfqplwatjao”, “sssxydzudauioo”, “klexuijypclivx”,
“sesquiyzbnjypc”, “dwsxuiptgzlini”, “dmscoipedaxryn”,
“afquujzeotcuap”, “hziqedeqiploan”, “xesljzaeorlian”])
Recovered String
algorithm
sesquipedalian
recover([“ellfpbicuurveurxpuosyster”, “exligticqurvedrbpnbsezyem”,
“eveiptiecuppecryptuspythd”, “eliiptmcburvecbzpyosysthm”,
“eyvchtdhgxrvecryetnsyqlem”, “qcoipgrcxyrvaqdypmewpgtem”,
“elgiptdceuyvefaypjoyzsttw”, “ellibcvcltrvejfvgbowystty”,
“awlhphiccnrvwcrdktbsytzee”, “erlicpyuwtrkcckymtopnwtcm”])
ellipticcurvecryptosystem
CSE 101 (Section 01) – Spring 2019 Lab #5 Page 6