Hire Experts For Answers
Order NowRelated Study Services
 Homework Answers
 Coursework writing help
 Term paper writing help
 Writing Help
 Paper Writing Help
 Research paper help
 Thesis Help
 Dissertation Help
 Case study writing service
 Capstone Project Writing Help
 Lab report Writing
 Take my online class
 Take my online exam
 Do my test for me
 Do my homework
 Do my math homework
 Online Assignment Help
 Do my assignment
 Essay Writing Help
 Write my college essay
 Write my essay for me
DESCRIPTION
Posted
Modified
Viewed
14
You may will need to draw diagrams to illustrate steps. You may use a tool like Word/Shapes or Paint to draw and copy/paste diagrams to your Word document, or you may draw by hand and take pictures to copy/paste to your Word document.
This order does not have tags, yet.
Attachments
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 coinmaking 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 singlesource shortestpaths 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 01 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 lowerbound 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 nelement set
d. determining whether n given real numbers are all distinct
9. What is the minimum number of comparisons needed for a comparisonbased 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 (NPcomplete problems)
Explanations and Answers
0
No answers posted
Post your Answer  free or at a fee
NB: Post a homework question for free and get answers  free or paid homework help.
Get answers to: Csc 320 Design And Analysis Of Algorithms S21 Homework or similar questions only at Tutlance.
Related Questions
 Semester Projects  Data Structures
 Creating An App: Fingerprint Base Atm
 Its An Assignment About Html..
 Operating Systems Concepts  Java Programming
 Artificial Intelligence  Assignment 2: Ai Survey Program
 Scheme Functions In R5Rs Using Drracket
 Questions About Algorithm Complexity That Must Be Answered In Detail.
 School Managment System.
 Excel Project Pivot Tables, Functions, Etc.
 Designing A Landscape Map And Use Cases
 Prioritized Queue Using A Binary Heap
 Prioritized Queue Using A Binary Heap In Java
 C Scheduler Program That Opens Win10 Processes For A Specificed Amount Of Time
 Wireshark Investigation Forensic Group Report
 Inventory Management System In Java Eclipse For Computer Science Project
 Implement Sieve Of Eratosthenes Using Two Data Types In C++
 C++ Programming Assignment For Operating Systems: Write Scheduling Program
 Python Programming For Defining Several Functions
 (C Programming) Computer Science Program With Files
 Programming And Compiling For A Java Assignment
 Implementing Two Classes Powers And Shiftutil.
 Passing Values Python Assignment
 C# Project With Gui Using Avalonia
 Use Ajax To Update Parts Of A Web Page.
 Memory Program In C That Plays A 2Player Memory Game.
 Hierarchical Agglomerative Clustering In Python
 Common Lisp Programming Project
 Programming, Assessment 10: Input, Processing, And Output
 Python Lab College Intro Course
 Python  Tree Data Structure Assignment
 C Programming Project About Files And Decoding Codes.
 Expression Binary Tree On Python
 Operating Systems Race Condition
 Using Basic Excel Functions (Formatting, Formulas, Etc.)
 Using Basic Excel Functions (Formatting, Formulas, Etc.)
 Program Budgeter. Must Be Coded In Java And Meet All Requirements Found In The Attached Doc.
 In C#, Create A Clock Class With Private Fields: "Int Hours" + "Int Minutes". Hours Is (0<X<23), Minutes Is (0<X<59)
 Sql Injection, Buffer Overflow Seed Lab
 I Need Comp1012 Python Programming Help
 A Computer Logic Working Clock Project
 I Need Python Programming Help On My Test
 I Need Someone To Code This Homework 4B: The 2048 Game. I Have Been Really Struggling On It
 Homework Coding.write And Test A Function To Draw A Box On The Bitmap Display
 Programming Project.for A Data Structures Class
 Writing A Program In Java That Meets The Requirements Stated On The Attached File
 Summative Lab Worksheet Using Mbed Online Complier And Simulator
 Java Scrabble Game Programming
 Python Coding Computer Science Fill In The Blank Homework Online Banking System
 Sql Injection, Buffer Overflow Seed Labs
 Computer Vision Homework, Computational Graphs And Backprop, Optimization And Fitting FullyConnected Neural Networks