Search the whole station

# 算法课业作业代写 CSCI 3104代写 LATEX代写 算法作业代写

378

## CSCI 3104 Problem set

### Instructions

• The solutions should be typed, using proper mathematical notation. We cannot accept hand-written solutions. Here’s a short intro to LATEX.
• You should submit your work through the class Canvas page only. Please submit one PDF file, compiled using this LATEX template.
• You may not need a full page for your solutions; pagebreaks are there to help Gradescope 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 may not collaborate with other students. 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, Discord, Reddit,StackExchange, etc., for help on an assignment is a violation of the Honor Code.

### Problem 1

Consider the undirected, unweighted graph G = (V, E) with V = {s, u, v, w, x} and E = {su, sv, sw, uw, ux, vw}, and let T ⊆ E be T = {sv, sw, uw, ux}. This is pictured below with T represented by wide edges.

Carefully explain why T cannot be output by BFS with start vertex s for any choices of iteration order over neighborhoods in the algorithm.

### Problem 2. 算法课业作业代写

Suppose we are given a finite, simple, connected, and weighted graph G(V, E, w), where the edge weights are non-negative. Suppose that the length of a path P is the product of the edge weights along P. Fix vertices s, t. Our goal remains to find a shortest path from s to t.

(a) Suppose we construct a new graph H(V, E, w) that is identical to G, with the exception that w({x, y}) = log(w({x, y})). That is, V (H) = V (G) and E(H) = E(G). So we have the same underlying graph, with the only difference being the edge weights. You may take as fact that P is a shortest s to t path in G if and only if P is a shortest s to t path in H.

Suppose now that we run Dijkstra’s algorithm on H, in order to fifind a shortest path from s to t in G. Is this approach valid? Justify your reasoning.

(b) Suppose now that the edge weights of G are all positive. That is, w({x, y}) > 0 for all edges {x, y} ∈ E(G). Let H(V, E, w) be the graph corresponding to G, as defined in part (a). Is it now a valid approach to run Dijkstra’s algorithm on H, in order to find a shortest path from s to t in G? Justify your reasoning.

(c) Give conditions on the edge weights of G, so that it suffices to run Dijkstra’s algorithm on H, in order to find a shortest path from s to t in G. Clearly explain why your conditions are correct.

### Problem 3.算法课业作业代写

Suppose you want to drive from Town A to Town B along some fixed route of distance d, and you have a gas tank whose capacity will take you at most m miles along the route. Let 0 < d1 < d2 < … < dn< d be the distances of each gas station along the route from Town A. (So the distance from A to gas station 2 is d2; the distance between the first two gas stations is d2 − d1.) Your goal is to get from A to B (equivalently, distance 0 to distance d) (a) without running out of gas, and (b) stopping as few times as possible.

The natural strategy most people use is a greedy one: go as far as you can, but refuel at gas station i if you don’t have enough to get you to gas station i+ 1. This strategy indeed minimizes the number of stops you need to make.

Consider a different greedy strategy, in which you stop at the nearest available gas station. Give an example (specify d, m, and the distances between the gas stations) showing that this strategy is not optimal. Show what this greedy algorithm does on your example, which subset of gas stations it outputs, and exhibit a strictly smaller set of gas stations that would still allow you to successfully complete the trip.

The prev: The next:

### Related recommendations

• #### 算法课业代做 CS 170代写 算法作业代写 高效算法作业代写

115

CS 170 Efficient Algorithms and Intractable Problems Project 算法课业代做 Problem Statement Penguins are the last remaining species on Earth and they must figure out how to defend themselve...

View details
• #### 高效算法与难题代写 Efficient Algorithms and Intractable代写

654

CS 170 Efficient Algorithms and Intractable Problems Homework 4 高效算法与难题代写 Design an efficient algorithm that given a directed graph G determines whether there is a vertex v from wh...

View details
• #### 数据分析工具代写 MAT 170代写 MATLAB代写 LATEX代写

420

MAT 170 FINAL PROJECT 数据分析工具代写 All Final Projects need to be done individually. No teams are allowed. We will refer all suspected acts of collaboration to student judicial All Final ...

View details
• #### 计算理论导论代写 CSC236H代写 LaTeX代写 计算机作业代写

226

CSC236H-Assignment 1 计算理论导论代写 • For this assignment, you must work individually, produce a PDF file named a1.pdf, and submit it to MarkUs. Submissions must be typed. • For this ass...

View details
1