(Solved): Csc 320 Design And Analysis Of Algorithms S21 Homework

CSC 320 S21 Homework 5 – Due by Monday April 12, 2021 Chapter 9 – a b e c 1 4 8 3 5 f 7 1 2 d 3 5 6 g 8 5 Note: This graph is used for some of the following problems. You can copy/paste it to your homework and work on it by highlighting vertices/edges to show each step of your work. 1. For coin-making problem, a. Write pseudocode of the greedy algorithm b. Implement in any programming language and submit a screenshot for your source code and running results with input and output. 2. Apply Prim’s algorithm to the above graph. Illustrate each step. 3. Job Scheduling: Consider a problem of scheduling n jobs of known durations t1, t2, ..., tn 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 the jobs in the system. (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.) (a) Design a greedy algorithm for this problem. (b) Does your algorithm always provide an optimal solution? (Yes/No). If your answer is “No”, present a counterexample. 4. Apply Kruskal’s algorithm to the above graph. Illustrate each step. 5. Solve the following instances of the single-source shortest-paths problems with a as the source -- using the above graph 6. Huffman code: Construct a Huffman code for the following data: symbol A B C D - frequency 0.4 0.1 0.2 0.15 0.15 7. The table below is from HW 4 Problem 8 with an instance of the knapsack problem. You solved it as the 0-1 version using dynamic programming. Now if items can be taken in fractional, use greedy technique to solve this fractional knapsack problem. Item Weight Value 1 2 25 2 1 20 3 3 15 4 2 40 5 5 50 Capacity W=6 8. Find a trivial lower-bound class for each of the following problems and indicate, if you can, whether this bound is tight. a. finding the largest element in an array b. checking completeness of a graph represented by its adjacency matrix c. generating all the subsets of an n-element set d. determining whether n given real numbers are all distinct 9. What is the minimum number of comparisons needed for a comparison-based sorting algorithm to merge any two sorted lists of the sizes n and n + 1 elements respectively? Prove the validity of your answer. Use adversary arguments and give your proof in detail. 10. Which of the following diagrams do not contradict the current state of our knowledge about the complexity classes P, NP, and NPC (NP-complete problems)

Csc 320 Design And Analysis Of Algorithms S21 Homework

Related Study Services

Post your Answer - free or at a fee

Answer Review

Csc 320 Design And Analysis Of Algorithms S21 Homework

Related Study Services

Post your Answer - free or at a fee

Login to your tutor account to post an answer