C200 Final Fall 2020
School of Informatics, Computing, and Engineering
Contents
Introduction 1
Problem 1: Pagerank 3
Starting Code for Problem 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Output for Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
Problem 2: Reverse Polish Notation 5
Starting Code to Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
Output for Problem 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
Problem 3: Database Queries 8
Output to Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Starting Code to Problem 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
Final Fall 2020 Page 1
Introduction
This is your final. You are required to work on this by yourself. You must implement the programs
on your own–do not copy any existing programs (if they, indeed, do exist).
We will not be answering questions on Piazza that will lead to an answer. If the files are not
in your repository, please let us know on Piazza.
For grading purposes (as you have seen in the previous assignments), there will be additional
tests that we will run. These parameters we pass in will not be edge cases, just a variation in
values (that logically fit with the problem).
There will be no grade request for this Final. Please ensure the file is in GitHub and is
pushed before the due date and there are no syntax errors.
For all problems, we will be giving partial credit based on the correctness of logic. Each
problem will be looked over, however syntax errors that prevent the file or function from running
will significantly reduce the partial credit. It is better to have a function that gives back incorrect
values versus a function that does not let the program run.
You will complete this before 11pm, Sunday, December 13th 2020.
Final Fall 2020 Page 2
Problem 1: PageRank
Read the accompanying lecture notes from Cornell University on the pagerank algorithm (which
we will try to attach to the Canvas Assignment). While it is somewhat old, it still forms, more or
less, the foundation for internet search. Your task is to implement the algorithm shown in the
Dynamical systems point of view. We will add a little to help you.
The algorithm does not give a way to converge. We will describe it here. Suppose you have
a sequence of vectors v0, v1, v2, . . . and are interested in observing how vi+1 changes from vi
. If
the change decreases monotonically (as we’ve discussed in class), then we can write a bound.
How can we measure a change? We use Euclidean distance (which we’ve seen):
We show this is correct using the console:
We can simplify using the linear algebra from numpy to find the norm:
You will, therefore, we comparing the last vector with the current vector and continue with
matrix multiplication while the norm of the difference is greater than tau.
1 def convergence(matrix, vector, tau):
Problem 2: Reverse Polish Notation
Please read the notes Reverse Polish Notation to understand how RPN (Reverse Polish Notation)
works. These also describe the algorithm. To simplify the problem, we’ll assume the
numbers are integers, not floats. The only additional modifications you have to address are:
• negative numbers
• a new operator abs
You can use .isdigit() to discover whether a string is a non-negative number:
1 >>> "0".isdigit()
2 True
3 >>> "1".isdigit()
4 True
5 >>> "*".isdigit()
6 False
7 >>> "-2".isdigit()
8 False
We can determine if a string is a negative number by using in. We’ll let you read about this
function (we covered this early on). We assume that a negative number has only one negative
value, i.e., -1, -2, -3, . . .. You can use string functions to remove the negation and change the
sign of the number. For example,
1 >>> x = "-2"
2 >>>
3 -2
4 >>>
Here are the expressions, and intermediate values, for the RPN:
1 3, 1, 2, +, * evaluates:
2 3,1,2,+
3 3,3,*
4 9
5
6 4, 2, 5, *, +, 1, 3, 2, *, +, / evaluates:
7 4, 2, 5, *
8 4,10,+
9 14
10 14,1,2,3,*
11 14,1,6,+
12 14,7,/
13 2
Final Fall 2020 Page 5
14
15 3 4 + 5 2 - * evaluates:
16 3,4,+
17 7,5,2,-
18 7,3,*
19 21
20
21 -2, -2, * evaluates
22 -2, -2, *
23 4
24
25 -200 abs 2 / evaluates:
26 -200 abs
27 200, 2, /
28 100
A hint on simplifying the problem. We can envision a dictionary that maps strings to functions.
For example,
1 >>> d = {"**":lambda x,y: x**y}
2 >>> s = "**"
3 >>> d[s](2,3) == 2**3
4 True
Lastly, we assume the input is a string where values and operators are separated by spaces.
For example, 3 4 + would be the string “3 4 +”. You know several ways to turn this string into a
list (another hint).
RPN
1 class stack:
2 """
3 DO NOT MODIFY, only use this class
4 """
5 # Code omitted for space in PDF
6
7 class RPS_calculator:
8 def __init__(self, exp):
9 """
10 TODO: complete the constructor
11
12 Parameter: A string representing RPN
13 No return statement
14 """
15 pass
16
Final Fall 2020 Page 6
17
18 def run(self):
19 """
20 TODO: complete the function
21
22 Parameter: No parameters
23 Returns: A numberical value from the expression
24 """
25 pass
26
27
28 def __str__(self):
29 """
30 DO NOT MODIFY
31 """
32 return str(self.calc)
33
34
35 if __name__=="__main__":
36 print("\n"*3)
37 print("Problem 2")
38 RPSlist = ["3 1 2 + *", "4 2 5 * + 1 3 2 * + /", \
39 "3 4 + 5 2 - *", "-2 -2 *", "-200 abs 2 /"]
40 for rpn in RPSlist:
41 x = RPS_calculator(rpn)
42 print("RPN:", rpn, "\t Run:", x.run())
Program Output
Problem 2
RPN: 3 1 2 + * Run: 9.0
RPN: 4 2 5 * + 1 3 2 * + / Run: 2.0
RPN: 3 4 + 5 2 - * Run: 21.0
RPN: -2 -2 * Run: 4.0
RPN: -200 abs 2 / Run: 100.0
Programming Problem 2
• Complete the RPN class
Final Fall 2020 Page 7
Problem 3: Queries
In class we were introduced to SQL and the relational model. Create a relation G with the data
shown in Table 1 that describes the distance traveling from destination X to destinate Y in miles.
Table 1: Relation G and distances from X to Y in miles.
Once you’ve created and populated your table, write the following queries:
1. Select all the tuples
2. Select all the tuples whose edges are greater than 2
3. Select all the paths of length 2
4. Select the path of length 2 that has the greatest sum and display the sum–a hint, you can
add values in the SELECT clause – investigate this on your own.
5. Give the average of the edge weights
6. Give the edges whose values are greater than the average weight
The average of the edge weights is:
ave(edges) = (1 + 3 + 5 + 5 + 2)/5 = 3.2
In Python:
1 >>> edge = [1,3,5,5,2]
2 >>> sum(edge)/len(edge)
3 3.2
Final Fall 2020 Page 8
Output
Problem 3
Query 1
(’A’, ’B’, 1.0)
(’A’, ’C’, 2.0)
(’A’, ’D’, 5.0)
(’B’, ’D’, 3.0)
(’C’, ’D’, 5.0)
******************************
Query 2
(’A’, ’D’, 5.0)
(’B’, ’D’, 3.0)
(’C’, ’D’, 5.0)
******************************
Query 3
(’A’, ’B’, ’D’)
(’A’, ’C’, ’D’)
******************************
Query 4
(’A’, ’C’, ’D’, 7.0)
******************************
Query 5
(3.2,)
******************************
Query 6
(’A’, ’D’)
(’C’, ’D’)
Final Fall 2020 Page 9
Programming Problem 3
• Finish the SQL queries for the functions in the assignment document
• All of the functions return strings and do not use any functions from sqlite3
• We created the table (createTable), all you have to do is insert and query.
• Insert the rows into the data
– insert1
– insert2
– insert3
– insert4
– insert5
• Queries listed in the problem statement
– query1
– query2
– query3
– query4
– query5
– query6
• There are no test cases in the test file
SQL Queries
1 import sqlite3
2 def createTable():
3 """
4 THIS FUNCTION ONLY RETURNS A STRING.
5 Do NOT call any ‘sqlite3‘ functions here
6
7 EXAMPLE: Complete the creating of a table
8 """
9 return "CREATE TABLE G (X text, Y text, Value real)"
10
11
12 def insert1():
13 # Comment omitted in PDF for space
14 return ""
15
16 def insert2():
Final Fall 2020 Page 10
17 # Comment omitted in PDF for space
18 return ""
19
20 def insert3():
21 # Comment omitted in PDF for space
22 return ""
23
24 def insert4():
25 # Comment omitted in PDF for space
26 return ""
27
28 def insert5():
29 # Comment omitted in PDF for space
30 return ""
31
32
33 def query1():
34 """
35 THIS FUNCTION ONLY RETURNS A STRING.
36 Do NOT call any ‘sqlite3‘ functions here
37
38 TODO: Complete the QUERY 1
39 """
40 return ""
41
42 def query2():
43 # Comment omitted in PDF for space
44 return ""
45
46 def query3():
47 # Comment omitted in PDF for space
48 return ""
49
50 def query4():
51 # Comment omitted in PDF for space
52 return ""
53
54 def query5():
55 # Comment omitted in PDF for space
56 return ""
57
58 def query6():
59 # Comment omitted in PDF for space
60 return ""
61
62
63 if __name__=="__main__":
Final Fall 2020 Page 11
64 ####
65 # DO NOT MODIFY CODE IN THIS SECTION
66 # No code will be graded in this section
67 #
68 # All code must be answered in the functions above
69 ####
70 print("\n"*3)
71 print("Problem 3")
72 connection = sqlite3.connect("final.db")
73 my_cursor = connection.cursor()
74 my_cursor.execute("DROP TABLE IF EXISTS G")
75 my_cursor.execute(createTable())
76
77 my_cursor.execute(insert1())
78 my_cursor.execute(insert2())
79 my_cursor.execute(insert3())
80 my_cursor.execute(insert4())
81 my_cursor.execute(insert5())
82 connection.commit()
83
84
85 #QUERY 1 Select All the tuples
86 print("Query 1")
87 for i in my_cursor.execute(query1()):
88 print(i)
89
90 print("*"*30)
91 #QUERY 2 Select All the edges greater than 2
92 print("Query 2")
93 for i in my_cursor.execute(query2()):
94 print(i)
95
96 print("*"*30)
97 #QUERY 3 Select All the paths of length 2
98 print("Query 3")
99 for i in my_cursor.execute(query3()):
100 print(i)
101
102 print("*"*30)
103 #QUERY 4 Select the path of length
104 # 2 that has the greatest sum and display the sum
105 print("Query 4")
106 for i in my_cursor.execute(query4()):
107 print(i)
108
109 print("*"*30)
110 #QUERY 5 Give the average of the edge weights
Final Fall 2020 Page 12
111 print("Query 5")
112 for i in my_cursor.execute(query5()):
113 print(i)
114
115
116 print("*"*30)
117 #QUERY 6 Give the edges whose values are greater than the average ←-
weight
118 print("Query 6")
119 for i in my_cursor.execute(query6()):
120 print(i)
121 connection.close()
Final Fall 2020 Page 13