you have to do all the steps – it is 4 part homework and you need to do it all and submit each part in different file and name it as what part it is.
Part one:
Greedy algorithms: The principle of a greedy algorithm is to find a near best solution for local conditions. For instance, a cashier gives coin changes to a customer, the best way is to give the smallest number of coins to the customer. However, it is usually hard to make such an arrangement. The cashier usually gives the largest valued coins first until could not give more, then select the second largest valued coins to the customer. And so on so forth.
For instance, for 48 cents, the cashier usually give one “25c”, two “10c”, and three”1c” coins. This algorithm is called the cashier’s algorithm that is a greedy algorithm. According to the previous research, the cashier’s algorithm is already the optimum for the US coin change system. Meaning that the cashier’s algorithm will give the best solution for US coin changes.
If a coin system is randomly assigned, for instance, there is no “5c”–nickel. The cashier’s algorithm may not reach the optimum in some cases.
(1) Design the cashier’s algorithm for any coin-change systems. You can assume the single coin values up to 10 different coins (m<=10). You can assume that the changes are in between 1-99 cents (1<=n<=99). (2) What is the time complexity with respect to “m” and “n?”
(2) Write a C++ or Java program to implement the cashier’s algorithm. (You can just use the US coin changes as the example.)
(3) Write an essay about the greedy algorithm ( 2 pages).
Part two:
Write a program using Dynamic Programming for combination number
C(n,m) = n!/m!(n-m)! = C(n-1,m)+C(n-1,m-1)
Part three:
Basic Graphs
(1) Establish a graph: Using both the adjacency matrix and the adjacency-list to represent 10 cities in U.S. based on airline travels (for edges and their distance). (2) According to geometric locations of the cities, draw a map for this graph. (Hint: using Java/Python would be easier. If you use C++, you might need to use OpenGL)
Part four:
Implement the DFS or BFS algorithm for component identification.
0 comments