代做c++ | Data structure代做 | Algorithm作业 | 数据结构代写 – CPSC 4100 Design & Analysis of Algorithms

2020-05-11

CPSC 4100 Design & Analysis of Algorithms

代做c++ | Data structure代做 | Algorithm作业 | 数据结构代写 – 这是一个关于Data structure的题目, 主要考察了关于Data structure的内容,是一个比较经典的算法题目, 包括了c++/Data structure/Algorithm等方面

数据结构代写 代写数据结构 Data structure代写 算法代写

Homework

Note: This is the last assignment. More problems will be added as the class

progresses. Please check the updates regularly!

Problems [xx points]

  1. [3 pt] Write the c++ Algorithm for the greedy algorithm for the change-making problem with
an amount C and a normal set of coin denominations D. The algorithm returns the
minimum number of coins for C. C is a non-negative integer and D is a vector of coin
denominations. The values in D are not sorted. Your C++ code should be compilable.
1) Write the C++ algorithm: int CoinChange(vector<int>& D, int C)
2) Give the time efficiency of your algorithm.
  1. [3 pts] Consider the problem of scheduling n jobs of known durations t0, t1, …, tn-1 for execution by a single processor. The jobs can be executed in any order, one job at a time. You want to find a schedule that minimizes the total time spent by all jobs in the system. Note that the time spent by one job in the system is the sum of the time spent by this job in waiting plus the time spent on its execution. The durations of n jobs are stored in a vector t. The values in t are not sorted. Write the C++ greedy algorithm which returns the minimal total time spent by all the n jobs. Your C++ code should be compilable.
    1. Write C++ algorithm: int MinTotalTime(vector& t)
    2. Give the time efficiency of your algorithm.
  2. [3 pts] Apply Prims algorithm to generate the minimum spanning tree (MST) for the following graph. You need to complete the table below when generating the MST. Assume MST generation starts with node a. As discussed in class, Parent[x] means the parent node of x on the resulting MST and Dist[x] is the minimum distance of x to the tree when x is added onto the MST. You also need to give the sum of edge weights on this MST.
Node Parent[Node] Dist[Node]
a - 1 0
b
c^
d

The MSTs sum of edge weight =?
  1. [3 pts] Design an algorithm to find, in linear time, whether there is a cycle containing vertex x in given directed graph G. ( From Final Exam 2014 @ Seattle U ). G contains n vertices, labeled as 0, 1, …, n-1.
    1. In order to achieve the linear time efficiency in your algorithm, what Data structure is used to represent the graph if the graph is a sparse graph? Please describe your data structure here and it will be used in 2).
    2. Write the C++ code: bool HasCycle(int x). Your C++ code should be compilable. HasCyle() returns true if a cycle containg x exists. Returns false otherwise.

More problems will be added as the class progresses!