CS 4310-5310: Greedy Algorithm Design Paradigm and Adv Data Structures - IT Assignment Help

Assignment Task:

Task:

General Comments: Read questions carefully and answer ALL parts of the question. Show all your work, otherwise no partial credit. No credit without proper justifications. State all your assumptions. No Algorithm is complete without its time and space complexity. When presenting an algorithm, first indicate if it is like a well-known algorithm, second describe intuitively how the algorithm works (which may be supported by examples), third give its pseudo code and finally analyze its time and space complexity. Always describe general idea of the algorithm before giving its pseudo-code. Do not reinvent the wheel, i.e., if a well-known algorithm can be modified to solve a problem efficiently, use that solution and clearly indicate the changes required. Do not unnecessarily complicate a solution, i.e., if a simple but efficient solution exists then we should use it. Finally, if you just write pseudo-code of a well-known algorithm without indicating how it applies or modified to the problem at hand, no credit will be given.

1. Let S = {a, b, c, d, e, f, g} be a collection of objects with benefit-weight values, a: (12,4), b: (10,6), c: (8,5), d: (11,7), e: (14,3), f: (7,1), g: (9,6). What is an optimal solution to the fractional knapsack problem for S assuming we have a sack that can hold objects with total weight 16? Show your work.

2. Provide an example instance of the fractional knapsack problem where a greedy strategy based on repeatedly choosing as much of the smallest-weight item as possible results in a suboptimal solution.

3. Suppose you are given an instance of the fractional knapsack problem in which all the items have an equal weight of 4. Show that you can solve the fractional knapsack problem in this case in O(n) time.

4. Sue says that she ran the Huffman coding algorithm for the four characters, A, C, G, and T, and it gave her the code words, 0, 10, 101, 110, respectively. Give examples of four frequencies for these characters that could have resulted in these code words or argue why these code words could not possibly have been output by the Huffman coding algorithm.

5. In a side-scrolling video game, a character moves through an environment from, say, left-to-right, while encountering obstacles, attackers, and prizes. The goal is to avoid or destroy the obstacles, defeat or avoid the attackers, and collect as many prizes as possible while moving from a starting position to an ending position. We can model such a game with a graph, G, where each vertex is a game position, given as an (x, y) point in the plane, and two such vertices, v and w, are connected by an edge, given as a straight line segment, if there is a single movement that connects v and w. Furthermore, we can define the cost, c(e), of an edge to be a combination of the time, health points, prizes, etc., that it costs our character to move along the edge e (where earning a prize on this edge would be modeled as a negative term in this cost). A path, P , in G is monotone if traversing P involves a continuous sequence of left-to-right movements, with no right-to- left moves. Thus, we can model an optimal solution to such a side- scrolling computer game in terms of finding a minimum-cost monotone path in the graph, G, that represents this game. Describe and analyze an efficient algorithm for finding a minimum-cost monotone path in such a graph, G.

6. Draw a (simple) directed weighted graph G with 9 vertices and 18 edges, such that G contains a minimum-weight cycle with at least 4 edges. Show that the Bellman-Ford algorithm will find this cycle.

7. Give an example of a weighted directed graph, G , with negative-weight edges, but no negative-weight cycle, such that Dijkstra’s algorithm incorrectly computes the shortest-path distances from some start vertex v.

8. Describe the meaning of the graphical conventions used in Figures 15.9 and 15.10, illustrating Prim-Jarnik algorithm. What do thick lines and dashed lines signify?
9. Show all the steps of Kruskal''s minimum cost spanning tree algorithm for a complete graph of 7 vertices where the weight of the edge between the distinct vertices i and j is |i-j|+1, for 1 <= i, j <= 7.

10. Describe an efficient greedy algorithm for making change for a specified value using a minimum number of coins, assuming there are four denominations of coins (called quarters, dimes, nickels, and pennies), with values 25, 10, 5, and 1, respectively. Argue why your algorithm is correct. Now, give an example set of denominations of coins so that a greedy change making algorithm will not use the minimum number of coins.

This CS 4310-5310:   IT Assignment has been solved by our IT Experts at My Uni Paper. Our Assignment Writing Experts are efficient to provide a fresh solution to this question. We are serving more than 10000+ Students in Australia, UK & US by helping them to score HD in their academics. Our Experts are well trained to follow all marking rubrics & referencing style.

Be it a used or new solution, the quality of the work submitted by our assignment experts remains unhampered. You may continue to expect the same or even better quality with the used and new assignment solution files respectively. There’s one thing to be noticed that you could choose one between the two and acquire an HD either way. You could choose a new assignment solution file to get yourself an exclusive, plagiarism (with free Turnitin file), expert quality assignment or order an old solution file that was considered worthy of the highest distinction.