Computer Science 1 — CSCI 1100 — Summer 2020 Exam 2
July 23, 2020
Honor pledge: On my honor I have neither given nor received aid on this test.
Instructions:
You have 90 minutes to complete this test.
Unless otherwise stated, you may use any valid Python technique to solve any problem.
If required, please state clearly any assumptions that you have to make in interpreting a question as comments.
There are 3 questions on this test worth a total of 100 points.
Before starting to work on the problems download the files exam2files.zip from Course Material Exams/Exam2 folder on Submitty.
You must submit a separate file for each question i.e. you should submit three .py files in all. All parts of each question must be put together in a single file. Name your files part1.py, part2.py and part3.py corresponding to each question.
When you are finished with this test please upload all of your .py files to the Submitty gradeable called Test 2. These are NOT auto-graded.
There is no limit to the number of submissions, but submissions will close on Submitty at 7:00 pm EDT. Please make sure you plan to submit before this time.
Any submissions after 7:00 pm will not be entertained. You are given double the time required to finish the exam (estimated finish time is 90 minutes ONLY) so that you can take care of submission related issues.
If you have multiple submissions, make sure to specify which version is your final one. By default, the latest one will be considered for grading.
We generally will not answer questions except when there is a glaring mistake or ambiguity in the statement of a question.
We understand that in a very rare situation you might run into disruptions despite all arrangements. In that scenario or in any case of other issues you must contact (DURING EXAM TIME):
1. Instructor: Uzma Mushtaque
email:mushtu@rpi.edu
Please do not ask questions like whether a print statement is required for a particular question or not. Do as indicated in the question. It is recommended you use as many print statements you want for your own convenience. If the question is not asking you to print something then you need not print it!
You should not contact anyone else (students,mentors or TA) during the exam time.
IGNORE any colors appearing for text anywhere in the document. It does not mean anything special.
You are free to write comments in your code as per your own convenience. There are NO POINTS allocated for comments or formatting. We are looking at correct solutions to given problems only.
1. (Question 1: 45 points) Encryption is a technique used to encode information or message in a way that only authorized people can access it. Decryption is to get the encrypted message back to its original form. In this problem you will write code to decrypt a message (that is already encrypted). Alternately, you need to find the “shift” for the encoded message. Once you have the shift, you know the mapping so you can decrypt the message.
Assumption throughout: Every input message is a string type that has characters from the alphabet and spaces.
Encryption demonstrated: You don’t have to write code for encryption
Shift the message:
If the shift is 3 then every letter of the input message gets shifted by 3. Therefore letter ’a’ becomes ’d’, ’b’ becomes ’e’ and so on. If the key is 10 then ’a’ becomes ’k’. When letters exceed the last letter i.e. ’z’ you should start counting from ’a’ again.
For example, here is an encryption using our shift-three cipher (case is ignored): Plaintext: the quick brown fox jumps over the lazy dog
Encrypted text: wkh txlfn eurzq ira mxpsv ryhu wkh odcb grj
Decrypting the message Your goal in this problem is to write a python script that can decrypt an already encrypted message. For this, we will use a simplified version of the technique that is actually used. English language has a known distribution for each letter. For example, the letter “E” is the most common letter in English making up 12.702 percent of the letters on average (ignoring case). The procedure begins by finding the most common letter. You can assume that the most common letter maps to “E.” You can now find the “shift” from the most common letter in the encrypted-text to the expected most common letter “E”. For example, if the most common letter in the encrypted-text is “H”, you know that the shift from “E” to “H” is 3. Once you know the shift, you can apply the shift to all the letters in the encrypted-text and get the original message. You need to ignore spaces when counting letters (if you forget to ignore them, beware that the space will be the most common character).
Follow the following steps to arrive at the decrypted message (Each step has points allocated to it). You do not need to output anything until the end of all the steps. if you wish to print anything for your convenience feel free to do that:
Step 1 (5 points): Read the cipher1.txt file (provided with the exam2files.zip) and create a string called words that has the exact same contents of the cipher1.txt file.
Step 2 (15 points):In this step create a list called charactercounts that will have the count of each character corresponding to the index of the list. For example have the count for letter ’a’ at index zero of the list, count for letter ’b’ at index 1 and so on. For example, the list for the file cipher1.txt will look like this:
>>>print(characterounts)
[4, 161, 195, 300, 90, 20, 91, 1, 63, 5, 270, 44, 72, 175, 413, 54, 76, 215, 220, 3, 33, 159,
87, 207, 234, 26]
OPTIONAL HINT: You are free to use any technique that you are comfortable with. However, one way is to use the ord() function. It generates the ASCII integer value of a character. For example type ord(‘a’) into Python shell and it will return the integer 97. If you create a list of counts—one count for each letter—you can use the ord() function to index into that list. For example, if letter = ‘c’ you can find it’s index using index = ord(letter) – ord(‘a’). Try it in the Python shell. The index for ‘a’ will be 0, for ‘b’ it will be 1, for ‘c’ it will be 2, and so on.
The inverse to the ord() function is the chr() function. You may or may not need the chr() function for this part of the problem but it can be useful so check its usage in the interpreter.
Step 3 (10 points): In this part find the shift (integer). First find the most common letter from the list charactercounts and then find the shift. Remember the most common letter represents the letter ’e’ so the shift can be found easily.
Step 4 (15 points): Use the shift (integer) found above to finally print the decrypted message. This should be a string type just like words and should be named decrypted.
2
OPTIONAL HINT: Each number in the charactercounts list corresponds to a letter once we found the shift. You can determine the letter and create a key that can be helpful in decrypting:
>>>print(chr((0 + shift)%26 + ord(‘a’))) k
>>>print (chr((1 + shift)%26 + ord(‘a’))) l
Once done with the decryption code, test your results as shown i.e. the decrypted message (print this part):
>>>print(words[:100])
drobo kbo cdbkxqo drsxqc nyxo sx dro wsnxsqrd cex li dro wox gry wysv pyb qyvn dro kbmdsm dbksvc
rkf
>>>print(decrypted[:100])
there are strange things done in the midnight sun by the men who moil for gold the arctic trails
hav
Finally save your code in a file named part1.py and submit it to Submitty.
3
2. (Question 2:35 points) In this problem you will work with a file books1.txt. Each line of the file has the following contents: Name of the book, Author, Publication, Year, Genre all separated by a pipe demiliter.
Part a: (15/35 points) In this part write a function called books_info that returns a list of tuples with first element as the name of the book and the second element as the year.
Your output for this part must be:
>>>info=books_info(‘books1.txt’) >>>print(info[0:5])
[(’61 Hours’, ‘2010’), (‘A Breath of Snow and Ashes’, ‘12005’), (‘A Common Life’, ‘2001’), (‘A Dance With Dragons’, ‘2011’), (‘A Day Late and a Dollar Short’, ‘2001’)]
Part b: (20/35 points)
In this part write a program that asks the user if they want to search for a title or not. If the user enters a Y, then the program should ask for the year they are searching for. Using the function from part a, a list of titles for that particular year should be printed. If the user enters N then the program should exit. As long as the user keeps entering Y, the program should keep asking for the year and return list of titles.Your program must handle, upper or lower case ’Y’ and ’N’. Assume the user will not enter any other letter. If the user enters a year that is not in the file then the program should print ’No titles found for this year’. A sample run is shown below:
Do you want to search for titles? Enter Y or N =>y
Which year titles are you looking at? 2000 The list of titles:
[‘Before I Say Goodbye’, ‘Drowning Ruth’]
Do you want to search for titles? Enter Y or N =>Y
Which year titles are you looking at? 2011
The list of titles:
[‘A Dance With Dragons’, ‘Against All Enemies’]
Do you want to search for titles? Enter Y or N =>y
Which year titles are you looking at? 2019
No titles found for this year
Do you want to search for titles? Enter Y or N =>n
Thank you!
Save both parts in a single file called part2.py and submit it to Submitty.
4
3. (Question 3: 20 points) You are given a list of non-negative integers (includes zero). Write a function called jump_index that returns the number of jumps you perform for the following task:
Assume you begin at the first integer in the list. Given that the number at position where you are is P, you need to jump P positions to the right in the list. For example, if you are at position 6 and the number at position 6 has the value 3, you need to jump to position 6+3=9. Repeat, this operation until you reach at the last element. If the size of any jump exceeds the size of the list then jump to the last element irrespective and count that move as a jump. Return the number of jumps. If you jump at a zero at any point in the list then you cannot jump any further therefore, return a -1. Also, if an empty list is your input, then return a -1. Some example runs are shown below:
>>>print(jump_index([3,4,1,2,5,6,9,0,1,2,3,1]))
4
>>>print(jump_index([1,9,2]))
2
>>>print(jump_index([1,3,2,9,0]))
-1
>>>print(jump_index([]))
-1
Finally save your solution in a file called part3.py and submit it to submitty.
5