Computer Science 1 — CSci 1100 — Fall 2020 Exam 2
October 29, 2020
Honor pledge: On my honor I have neither given nor received aid on this exam.
By submitting your test files for grading, you are signifying that you understand and agree with the honor pledge.
Instructions:
• Submitty will open for a 90 minute submission period beginning at the start of the testing block time at 6:55 pm ET and will remain open until 8:25 pm ET. You must complete your test within this time window.
• Your test began when you either:
– Downloaded the unencrypted test file from Submitty, or
– Accessed the decryption key and opened the encrypted test file.
Your time stops when you submit your answers. Tests submitted beyond their allotted time limit will incur a
penalty.
• If you run over your allotted time please submit as soon as possible. Do not wait to contact us to get permission. The later your submission, the greater the penalty. If you run into a technical issue that prevents you from submitting, immediately email the instructors at cs1instructors@cs.lists.rpi.edu. Attach your exam to the email and briefly but thoroughly explain the issue. Depending on when you email us and the issue, we will decide whether or not to apply a penalty.
• There are 3 questions on this test. The allocated points are specified with each problem. Each question should be answered in a separate .py file and submitted to the correct submission box in the Exam 2 gradeable on Submitty. These will not be auto-graded like your homeworks. Therefore, you will not see any points once you submit. There is no limit to the number of submissions.
• During exam, if you are doubtful/confused about a problem, simply state your assumptions and/or interpretation as comments right before your code and write your solution accordingly.
• During exam time, you should NOT contact any of the TAs or mentors either via email or on the discussion fo-
rum. In case of an extremely urgent situation please email the instructors at: cs1instructors@cs.lists.rpi.edu.
• This is an open book, open notes and open reference material exam.
• Also NOTE THE FOLLOWING:
– We give you a lot of sample output. We know that the Spyder IDE inserts an extra blank line before every input statement. We will not penalize you for those extra blank lines.
1. (Social Network: 37 points) In this problem we will work with a given text file (social_network.txt) from a social network (like LinkedIn) that has details of connections between users. Each line of the file has 2 user ids that are connected with each other (user ids are separated by a pipe delimiter). A sample file might look like
0|1
0|2
0 |3
1|4
1 |6
1 |7
1 |9
2 |3
2|6
2|8
2 |9
3 |8
3 |9
4 |6
4 |7
4 |8
5 |9
6 |8
7 |8
We will create a simple system that analyzes this social network. The problem is divided into 3 parts. All three parts must be saved in the same python file. You cannot use Sets or Dictionaries in this problem.
Part a:(15 points) Given a file like social_networks.txt. Write a function called init_network(file,user) that takes input as the file name and a user id and returns the list of connections for that particular user. You may assume that the id is valid. As an example, given the test file above, user 9 should result in the list [1,2,3,5] and for user 0 it should be [1,2,3].
Once you have written the function init_network(file,user) write code to ask the user for a userid and print the list of connections returned by init_network(file,user) for that userid on the file social_networks.txt as shown below: A few sample runs for this part of the program are shown.
Enter the user Id =>8
[2, 3, 4, 6, 7]
Enter the user Id =>9
[1, 2, 3, 5]
Part b (7 points) In this part write a function called complete_network(file,n). that returns a list of lists such that the index of every sub-list corresponds to a user id and the sub-list has the connections for that particular user. For example the first sub-list is at position zero so the list must have [1,2,3]. These are the connections of user id 0. Your code in this part must involve calling the init_network(file,usr) function that you created in part a.
Once you have written the function complete_network(file,n) write code to call the function on the file social_networks.txtand print the network as shown below. You can assume the number of user ids (n) is 10 in your call to complete_network(file,n).
2
Complete Network
0 : [1, 2, 3]
1 : [0, 4, 6, 7, 9]
2 : [0, 3, 6, 8, 9]
3 : [0, 2, 8, 9]
4 : [1, 6, 7, 8]
5 : [9]
6 : [1, 2, 4, 8]
7 : [1, 4, 8]
8 : [2, 3, 4, 6, 7]
9 : [1, 2, 3, 5]
Part c (15 points) We will continue writing code in the same script for this part. Using the userid input in part a and the complete network from part b find the user in the complete network that shares the most connections in common with user userid. In the case of a tie, choose the user with the lowest id. Then print the common connections.
A complete run of your entire python program including this final piece is shown in the sample output below.
Enter the user Id =>6
[1, 2, 4, 8]
Complete Network
0 : [1, 2, 3]
1 : [0, 4, 6, 7, 9]
2 : [0, 3, 6, 8, 9]
3 : [0, 2, 8, 9]
4 : [1, 6, 7, 8]
5 : [9]
6 : [1, 2, 4, 8]
7 : [1, 4, 8]
8 : [2, 3, 4, 6, 7]
9 : [1, 2, 3, 5]
User whose connections match the most => 7 Matching connections are:
148
Write your code for all three parts as a single Python file and submit it to the upload area below. Make sure you hit Submit after submitting
3
Solution:
# -*- coding: utf-8 -*-
“””
Created on Fri Oct 23 09:17:19 2020
@author: mushtu
“””
“””In this problem we will work with a .txt file from a
social network (like LinkedIn) that has
details of connections between users. We will create a
simple system that analyzes this social network.
The problem is divided into 3 parts.
Part a:(15 points) You are given a file called social_networks.txt.
Each line of the file
has 2 user ids that are connected with each other (user ids are separated by a pipe delimiter).
Write a function called init_network(file,usr);that takes input as the file name and a valid
user id
(this is the assumption) and returns the list of connections for that particular user. For
example, for user 9
the list returned should be [1,2,3,5] and for user 0 it should be [1,2,3].
“””
def init_network(filename, usr_id):
network=[]
for i in open(filename):
line=i.split(“|”)
network.append([int(line[0]),int(line[1])])
final=[]
for j in network:
if usr_id in j:
if usr_id==j[0]:
final.append(j[1])
else:
final.append(j[0])
return final
user=int(input(“Enter the user Id =>”)) print(init_network(‘social_network.txt’, user))
“””Part b (7 points) In this part write a function called complete_network(file,n).
Assume you are given the total number of users for this file = 10.
The function must return a list of lists such that the index of
every sub-list corresponds to a user_id and the sub-list has the
connections for that particular user. For example the first sub-list
is at position zero so the list must have [1,2,3]. These are the friends
of user id 0.
This must involve calling the init_network(file,user) function that
you created in part a.
Using the list of lists print the following:
0 : [1, 2, 3]
1 : [0, 4, 6, 7, 9]
2 : [0, 3, 6, 8, 9]
3 : [0, 2, 8, 9]
4 : [1, 6, 7, 8]
5 : [9]
6 : [1, 2, 4, 8]
7 : [1, 4, 8]
8 : [2, 3, 4, 6, 7]
9 : [1, 2, 3, 5]”””
4
def complete_network(file,n):
network=[]
for i in range(n):
network.append(init_network(file, i))
return network
net=complete_network(‘social_network.txt’,10) print(‘Complete Network’)
for i in range(len(net)):
print(i,’:’,net[i])
“””Part c: Using the output from part b find the connection nearest to a given user.
More the number of common connections, nearer is the user. Write code that uses the
list of lists generated in part b to find the user that is nearest to the user id earlier
taken as input(part a).
Finally print the common connections as shown in the sample output below. If there is
a tie between multiple users that have the same number of common connections (For example for
user 5 there are common connections (equal to 1) with many users) then pick the smallest
user id which in this case would be user 1.”””
user_id=user
l=net[user_id]
score=[]
for k in net:
common=[]
for m in l:
if m in k:
common.append(m)
score.append(len(common))
score[user_id]=-1
n=max(score)
match=score.index(n)
print(‘User whose connections match the most with you =>’,match) list1=net[match]
list2=net[user_id]
final=[]
for i in list1:
if i in list2:
final.append(i)
print(‘Matching connections are: ‘) for k in final:
print(k, end=’ ‘)
Or
def init_network(filename, user):
L = []
for line in open(filename):
connection = line.split(‘|’)
first = int(connection[0].strip()) second = int(connection[1].strip()) if first == user:
L.append(second)
elif second == user:
L.append(first)
return L
user = int(input(“Enter the user Id =>”).strip()) print(init_network(‘social_networks.txt’, user))
def complete_network(filename, n):
L = []
5
for ctr in range(n):
L.append(init_network(filename, ctr))
return L
L = complete_network(“social_networks.txt”, 10)
ctr = 0
print(“Complete Network”)
for l in L:
print(“{} : {}”.format(ctr, l))
ctr += 1
test = L[user]
best = -1
matches = []
for ctr in range(len(L)):
if ctr != user:
target = L[ctr]
common = []
for t in target:
if t in test:
common.append(t)
length = len(common)
if length > len(matches):
best = ctr
matches = common
print(“User whose connections match the most =>”, best)
print(“Matching commections are:”)
for m in matches:
print(m, end=” “)
print()
6
2. (Number Triangle: 25 points) In this problem we will generate a triangle of numbers using the list of lists data structure. Your program must ask the user for the number of rows (h) to be generated. You may assume the user will always enter a positive number. Now, begin by creating a list with a single sub-list containing the value 1 in it. At this point, your list of lists will be [[1]]. This is your initialization part. Your program should make this list grow based on the input number of rows i.e. the final output must have h number of sub-lists. The content of each sub-list will be based on the following rules:
(a) Each sub-list must have the first and the last element equal to 1. This implies that a list of size 1 or 2 will have only ones.
(b) The index of each sub-list decides the number of elements in it. For example, the first sublist has 1 element, the 2nd sublist has 2 elements and so on.
(c) The value of an element in a sub-list (except the ones on each end) are the sum of the elements at its own position and one position before it in the previous sub-list. So for example, the 2 in position [1] of the third sub-list is the sum of the two 1s in positions [0] and [1] in the second sub-list.
A few sample runs that print this sub-list are shown here:
Sample run 1: Here the user enters number 4, so number of sub-lists should be 4.
Please input the number of sub-lists: 4
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1]]
Sample run 2:
Please input the number of sub-lists: 7
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1], [1, 5, 10, 10, 5, 1], [1, 6, 15, 20, 15, 6, 1]]
Once you have the triangle generated correctly, print the triangle using the following pattern:
1
11
121
1331 14641
1 5 10 10 5 1
1 6 15 20 15 6 1
To clarify, when you run the entire script all together, this is how the output should appear:
Please input the number of sub-lists: 5
[[1], [1, 1], [1, 2, 1], [1, 3, 3, 1], [1, 4, 6, 4, 1]]
1
11
121 1331 14641
Write your code as a single Python file and submit it to the upload area below. Make sure you hit Submit after uploading
7
Solution:
# -*- coding: utf-8 -*-
“””
Created on Sat Oct 24 20:21:37 2020
@author: mushtu
“””
”’In this problem we will generate a pattern of numbers using
the list of list data structure. Your program must ask the user
for the number of rows that should be printed (h).Assume the user
will always enter a positive number. Once you have
the number, begin by creating a list that has a sub-list with number 1 in it. This is your initialization part. This list will grow based
on the input number of rows i.e. the final output must have h number of sub-lists. The content of each sub-list will be based on the following rules:
1. Each sub-list must have the first and the last element equal to 1. This implies that a list of size 1 or 2 will have ones only.
2. The index of each sub-list decides the number of elements in it. For example, first sublist has 1 element, 2nd sublist has 2 elements and so on.
3. The value of an element (except the ones on each end) is a sum
of 2 elements from the previous sub-list. For example in the third sub-list number 2 at position 1 is a sum of 1 and 1 from the second sub-list. In summary, each new element is a sum of the element at its own position and one position below in the previous sub-list”’
h = int(input(“Please input the number of sub-lists: “))
final = [] # create a list representing the triangle
final.append([1]) # append the first row into the triangle
if h > 1:
final.append([1,1]) # append the second row into the triangle
for i in range(3, h+1):
new_row = [] # this is the new row we will generate
last_row = final[-1] # the new row is based on the last row of current triangle
new_row.append(1) # the leftmost number is 1
for j in range(i-2):
new_row.append(last_row[j]+last_row[j+1])
new_row.append(1) # the rightmost number is 1
final.append(new_row) # add the new row into the triangle
print(final)
print()
for i in final:
for k in i:
print(k,sep=” “,end=’ ‘)
print() Or
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
“””
Created on Wed Oct 28 23:04:53 2020
@author: wes
“””
levels = int(input(“Please input the number of sub-lists: “))
8
L = []
L.append([1])
for ctr in range(1, levels):
layer = [1, 1]
for col in range(1, ctr):
value = L[ctr-1][col] + L[ctr-1][col-1]
layer.insert(col, value)
L.append(layer)
print(L)
print()
for row in L:
string = “”
for col in row:
string = string + str(col) + ” ”
print(string.strip())
9
3. (Truth Table: 38 points)
This problem will test using modules, booleans, and truth tables. Assume there is a module named evaluate with a single function triple_bool(bool1, bool2, bool3).triple_bool takes three boolean values and re- turns a single boolean as the result. There are eight possible combinations of the three input values. You need to write a program that calls triple_bool with all possible combinations of True and False for the three input arguments and creates a list of 4-tuples of the form
(bool1, bool2, bool3, triple_bool(bool1, bool2, bool3)).
For example, if triple_bool(bool1, bool2, bool3) returns (bool1 and bool2) or bool3, then you would generate the list
[(True, True, True, True),
(True, True, False, True),
(True, False, True, True),
(True, False, False, False),
(False, True, True, True),
(False, True, False, False),
(False, False, True, True),
(False, False, False, False)]
Once you have generated the list, print out the values as a truth table. For the above example, you would print:
bool1 bool2
—– —–
True True
True True
True False
True False
False True
False True
False False
False False
bool3 Result
—– ——
True True
False True
True True
False False
True True
False False
True True
False False
Note that there is a single tab character between every column. We realize that this may not display correctly in Spyder.
There are some restrictions.
(a) You must import evaluate and use the module correctly. Do not assume you know what triple_bool returns as output and do not embed it in your file. For testing, you can assume that the file evaluate.py contains:
def triple_bool(b1, b2, b3):
return (b1 and b2) or b3
(b) You must accomplish all steps including first generating the entire list of 4-tuples first before printing.
(c) There are only eight possible combinations of three boolean variables and they are all shown in the example, so it may be tempting to give a brute force solution. To get full credit, you must use nested loops and a single call to triple_bool. Solutions that try to ‘brute force’ the solution by making multiple calls to triple_bool or that hardcode the arguments to triple_bool will lose substantial credit.
Write your code as a single Python file and submit it to the upload area below. Do not submit any code for evaluate.py. Make sure you hit Submit after uploading
10
Solution:
import evaluate
bools = [True, False]
L = []
for b1 in bools:
for b2 in bools:
for b3 in bools:
L.append((b1, b2, b3, evaluate.triple_bool(b1, b2, b3)))
print(‘{}\t{}\t{}\t{}’.format(“bool1”, “bool2”, “bool3”, “Result”)) print(‘{}\t{}\t{}\t{}’.format(“—–“, “—–“, “—–“, “——“)) for l in L:
print(‘{}\t{}\t{}\t{}’.format(l[0], l[1], l[2], l[3]))
11