Algorithm算法代写代考

Announcements Announcements • Exam 3 Solutions Online • Final Exam March 19th Last Time • NP-Hard/Complete Problems are as hard as any other problems in NP. • It is believed that this means that there are no polynomial time algorithms for such problems. Dealing With NP-Completeness (Ch 9) • Backtracking/Branch and Bound • Heuristic Search […]

CSE 101 Final Exam Page 1 of 25 1. Knapsack problem [15 points] Consider the Knapsack Problem: a subset of the following 4 items are to be put into a knapsack of weight capacity 5 such that the value of the items in the knapsack is maximized: A B C D values 30 24 48

CSE 101 Final Exam Page 1 of 21 1. SSSP [12 points] A B C D E F 5 4 8 1 7 2 4 5 1 1.a. [4 points] Find the topological sorting of the vertices of the above graph using Kahn’s algorithm. Use the tabular method as we did in lecture. Solution: A

Question 1 (Shortest Paths, 30 points). Find the lengths of the shortest path from s to each other vertex in the graph below: We run Bellman-Ford on this graph and get the following output: k s A B C D E F G H 0 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1

CSE 101 Homework 0 Solutions Winter 2021 Question 1 (Program Runtimes, 20 points). Consider the following programs: Alg1(n): For i = 1 to n j = 1 while j < n j = j+1 Alg2(n): For i = 1 to n j = 1 while j < n j = j+i For each of these

Announcements Announcements Homework 2 Due on Friday Last Time Shortest Paths in Graph with Negative Edge Weights Negative weight cycles might mean no shortest paths Bellman-Ford Computes shortest path length with ≤ k edges for various k If no negative weight cycles, take k = |V|-1 to get correct distances. Algorithm Bellman-Ford(G,s,ℓ) dist0(v) ← ∞

Problem Sheet Exercises 8 Jim Laird April 12, 2021 1. Suppose Oscar receives the ciphertexts 83, 36 and 37, which he knows are the encryptions of the same plaintext using the exponent 3, and moduli 143, 119 and 95 respectively. Without factorizing, recover the plaintext. 2. How many primitive elements are there modulo p =