当前位置:天才代写 > CS代写 > 算法问题集代写 CSCI 3104代写

算法问题集代写 CSCI 3104代写

2022-09-20 11:46 星期二 所属: CS代写 浏览:38

CSCI 3104 problem set

算法问题集代写 Problem 1. Consider the interval scheduling problem from class. You are given a set of intervals I, where each interval has a start and end time

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.

 

Problem 1.  算法问题集代写

Consider the interval scheduling problem from class. You are given a set of intervals I, where each interval has a start and end time [si , fi ]. Your goal is to select a subset S of the given intervals such that (i) no two intervals in S overlap, and (ii) S contains as many intervals as possible subject to condition (i).

Suppose we have two intervals with the same start time but different end times. That is, let I1 = [s, f1] and I2 = [s, f2] with f2 > f1.

(a) Let overlap([s, f]) denote the number of intervals of I (excluding [s, f]) with which [s, f] overlaps. Explain carefully why overlap(I1) overlap(I2).

(b) Suppose that overlap(I1) < overlap(I2). Explain carefully why I2 can safely be exchanged for I1.

 

Problem 2.

Consider the following graph G(V, E, w). Suppose we have the intermediate spanning forest F (indicated using thick edges) consisting of the edges {A, B}, {B, C}, and {C, D}. Clearly identify the safe, useless, and undecided edges. Justify your reasoning. [Hint: You may find Corollary 61 on page 42 of the typed lecture notes to be helpful.]

 

算法问题集代写
算法问题集代写

 

Problem 3.

Consider the following graph G(V, E, w). Clearly indicate the order in which Kruskal’s algorithm adds the edges to the minimum-weight spanning tree. You may simply list the order of the edges; it is not necessary to exhibit the state of the algorithm (i.e., the disjoint-set data structure) at each iteration.

 

 

Problem 4.  算法问题集代写

Consider the following graph G(V, E, w). Clearly indicate the order in which Prim’s algorithm adds the edges to the minimum-weight spanning tree using H as the source vertex. You may simply list the order of the edges; it is not necessary to exhibit the state of the algorithm at each iteration.

 

 

Problem 5.   算法问题集代写

We say that two i ~→ j paths are edge-disjoint if they do not share any common edges. Note however, these paths can (and in fact, often do) share common vertices (aside from i and j). As an example, consider the following graph.

  • Observe that 0 1 3 5 6 and 0 2 3 6 are edge-disjoint paths, as they do not share any directed edges. It is fine that they share the common vertex 3.
  • Note however that 0 2 4 6 and 0 2 3 6 are not edge-disjoint paths, as they both share the (0, 2) edge.

 

算法问题集代写
算法问题集代写

 

Consider the following problem.

  • Input: A directed graph G(V, E), as well as a start node i and an end node j.
  • Solution: We seek to find a set P of i j paths such that any two distinct paths P1, P2∈ P are edge-disjoint, and |P| is maximum. That is, we seek to find a maximum set of edge-disjoint i j paths.

(a) Describe how to reduce the above problem to the (one-source, one-sink) max-flow problem from class. Your description should be general, and not tied to a specific example.

(b) Using your reduction, find a maximum set of edge-disjoint paths from 0 ~→ 6 in the graph above. Show your work, as well as your final answer. Note that there may be multiple maximum-size sets P in the graph above; you need only find one such set P of edge-disjoint paths, as long as it has the largest number of paths possible.

 

Problem 6.  算法问题集代写

Let f(n) = 23n and g(n) = n2 . Determine the relationship that best applies: f(n) o(g(n)), f(n) O(g(n)), f(n) Θ(g(n)), f(n) ω(g(n)), or f(n) Ω(g(n)). Prove your answer.

 

Problem 7.

Let f(n) = n2 and g(n) = n!. Determine the relationship that best applies: f(n) o(g(n)), f(n) O(g(n)), f(n) Θ(g(n)), f(n) ω(g(n)), or f(n) Ω(g(n)). Prove your answer.

算法问题集代写
算法问题集代写

 

更多代写:html程序代写  托业成绩作弊  英国Announcement代写   apa格式论文代写  article代写summary  个人陈述范文代写

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

 

天才代写-代写联系方式