C200留学生编程代写、代做Java，c++程序语言、Python程序代写

日期：2020-12-14 10:51

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 >>> <A Python expression you create>

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