CS算法课业代写 CSCI 3104代写

CSCI 3104 Problem Set 3

CS算法课业代写 1 Instructions The solutions must be typed, using proper mathematical notation. Wecannot accept hand-written solutions. Here’s a short intro to

1 Instructions

The solutions must be typed, using proper mathematical notation. Wecannot accept hand-written solutions. Here’s a short intro to LaTeX .
You should submit your work through the class Canvas page Pleasesubmit one PDF file, compiled using this LATEX template.
You may not need a full page for your solutions; pagebreaks are there to helpGradescope automatically find where each problem is. Even if you do not attempt every problem, please submit this document with no fewer pages than the blank template (or Gradescope has issues with it).
You are welcome and encouraged to collaborate with your classmates, as well as consult outside resources. You must cite your sources in this document. Copying from any source is an Honor Code violation. Furthermore, all submissions must be in your own words and reflect your understanding of the material. If there is any confusion about this policy, it is your responsibility to clarify before the due date.
Posting to any service including, but not limited to Chegg, Reddit, StackExchange, etc., for help on an assignment is a violation of the Honor Code.
You must virtually sign the Honor Code (see Section 2). Failure to do so will result in your assignment not being graded.

2 Honor Code CS算法课业代写

(Make Sure to Virtually Sign the Honor Pledge)

Problem 1. On my honor, my submission reflects the following:

My submission is in my own words and reflects my understanding of the material.
Any collaborations and external sources have been clearly cited in this document.
I have not posted to external services including, but not limited to Chegg, Reddit, StackExchange, etc.
I have neither copied nor provided others solutions they can copy.

In the specified region below, clearly indicate that you have upheld the Honor Code. Then type your name.

Honor Pledge.

3 Standard 3- Dijkstra’s Algorithm CS算法课业代写

3.1 Problem 2

Problem 2. Consider the weighted graph G(V, E, w) pictured below. Work through Dijkstra’s algorithm on the following graph, using the source vertex A.

Clearly include the contents of the priority queue, as well as the distance from A to each vertex at each iteration.
If you use a table to store the distances, clearly label the keys according to the vertex names rather than numeric indices (i.e., dist[’B’] is more descriptive than dist[’1’]).
You do not need to draw the graph at each iteration, though you are welcome to do so. [This may be helpful scratch work, which you do not need to include.]

3.2 Problem 3

Problem 3. Give an example of a simple, finite, weighted, and connected graph G(V, E, w) together with a specified source vertex v ∈ V (G), such that Dijkstra’s algorithm fails to find a shortest path from s to v for at least one vertex v ∈ V (G). Note that you will need to use negative edge weights. Carefully justify why your example works. [Hint: It may be worthwhile to look at the families of graphs from the Graph Theory notes and the corresponding recitation.]

You are welcome to hand-draw your diagrams and embed them as an image below, provided (i) your drawings are legible and (ii) the graders do not have to rotate their screens to grade your work. Your explanation must still be typed.

3.3.1 Problem 3(a) CS算法课业代写

(a) Rephrase this is as a graph problem. Give a precise definition of how to model this problem as a graph, and state the specific question about this graph that must be answered. [Note: While you are welcome to draw the graph, it is enough to provide 1-2 sentences clearly describing what the vertices are and when two vertices are adjacent. If the graph is weighted, clearly specify what the edge weights are.]

3.3.2 Problem 3(b)

(b) Clearly describe an algorithm to solve this problem. If you use an algorithm covered in class, it is enough to state that. If you modify an algorithm from class, clearly outline any modifications. Make sure to explicitly specify any parameters that need to be passed to the initial function call.

3.3.3 Problem 3(c)

(c) Apply that algorithm to the question. Report and justify your answer. Here, justification includes the sequences of vertices visited, the total cost, and the sequence of steps the algorithm took.

3.3 Problem 4 CS算法课业代写

Problem 4. You have three batteries, with 4200, 2700, and 1600 mAh (milli-Amp-hours), respectively. The 2700 and 1600-mAh batteries are fully charged (containing 2700 mAh and 1600 mAh, respectively), while the 4200-mAh battery is empty, with 0 mAh. You have a battery transfer device which has a “source” battery position and a “target” battery position. When you place two batteries in the device, it instantaneously transfers as many mAh from the source battery to the target battery as possible. Thus, this device stops the transfer either when the source battery has no mAh remaining or when the destination battery is fully charged (whichever comes first).

But battery transfers aren’t free! The battery device is also hooked up to your phone by bluetooth, and automatically charges you a number of cents equal to however many mAh it just transfered.

The goal in this problem is to determine whether there exists a sequence of transfers that leaves exactly 1200 mAh either in the 2700-mAh battery or the 1600-mAh battery, and if so, how little money you can spend to get this result.

合作平台：essay代写论文代写写手招聘英国留学生代写