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

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

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!