Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
No one likes working on homework assignments one day after you enjoyed your party time, you realize that you have missed n homework deadlines! All the instructors were very angry at this, and they told you that the penalty will be based on your late days. So, now, you have to start working on your assignments. You have n assignments to make up, from today. For assignment i, you know you need t; days to finish it. You can only work on one assignment at a time. If you finish an assignment on day d, you can submit it immediately, and your the number of late days for that assignment is d, which is the number of points you lose for that course. Your total penalty, therefore, is the total number of late days you finally need for finishing all assignments. For example, suppose you have 3 assignments to make up, and they take time 4 days, 6 days, and 3 days, respectively. If you work on them in order, you need 4 days to finish the first assignment, and can submit it on day 4 (need 4 late days). For the second assignment, you will finish it on day 10, and the late day you need is 10 for that assignment. For the last assignment, you will finish it on day 13, which means you used 13 late days for that assignment. In total, you used 4+10+13= 27 late days, so you lose 27 points in total. Of course, you want to lose as few points as possible! How should you work on the assignments to minimize the number of points lost? 1. 2. What is the optimal solution for the above example (e.g., three assignments that require 4, 6, and 3 days, respectively)? What is the least number of points you will lose? From your answer above, you probably guess that a greedy algorithm can do the trick you are right. Given n assignments with number of days t; you need to finish them, please describe a greedy algorithm that can help you lose the fewest number of points. 3. Please prove that your algorithm can give the optimal solution. (Hint: you can use greedy choice and optimal substructure as we introduced in class. Actually there are other simpler ways to prove this. As long as your proof is valid and correct, you can get the points.)

No one likes working on homework assignments one day after you enjoyed your party time, you realize that you have missed n homework deadlines! All the instructors were very angry at this, and they told you that the penalty will be based on your late days. So, now, you have to start working on your assignments. You have n assignments to make up, from today. For assignment i, you know you need t; days to finish it. You can only work on one assignment at a time. If you finish an assignment on day d, you can submit it immediately, and your the number of late days for that assignment is d, which is the number of points you lose for that course. Your total penalty, therefore, is the total number of late days you finally need for finishing all assignments. For example, suppose you have 3 assignments to make up, and they take time 4 days, 6 days, and 3 days, respectively. If you work on them in order, you need 4 days to finish the first assignment, and can submit it on day 4 (need 4 late days). For the second assignment, you will finish it on day 10, and the late day you need is 10 for that assignment. For the last assignment, you will finish it on day 13, which means you used 13 late days for that assignment. In total, you used 4+10+13= 27 late days, so you lose 27 points in total. Of course, you want to lose as few points as possible! How should you work on the assignments to minimize the number of points lost? 1. 2. What is the optimal solution for the above example (e.g., three assignments that require 4, 6, and 3 days, respectively)? What is the least number of points you will lose? From your answer above, you probably guess that a greedy algorithm can do the trick you are right. Given n assignments with number of days t; you need to finish them, please describe a greedy algorithm that can help you lose the fewest number of points. 3. Please prove that your algorithm can give the optimal solution. (Hint: you can use greedy choice and optimal substructure as we introduced in class. Actually there are other simpler ways to prove this. As long as your proof is valid and correct, you can get the points.)

Computer Networking: A Top-Down Approach (7th Edition)
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
See similar textbooks
icon
Related questions
Question
100%
No one likes working on homework assignments one day after you enjoyed your party time, you realize that you have missed n homework deadlines! All the instructors were very angry at this, and they told you that the penalty will be based on your late days. So, now, you have to start working on your assignments. You have n assignments to make up, from today. For assignment i, you know you need t; days to finish it. You can only work on one assignment at a time. If you finish an assignment on day d, you can submit it immediately, and your the number of late days for that assignment is d, which is the number of points you lose for that course. Your total penalty, therefore, is the total number of late days you finally need for finishing all assignments. For example, suppose you have 3 assignments to make up, and they take time 4 days, 6 days, and 3 days, respectively. If you work on them in order, you need 4 days to finish the first assignment, and can submit it on day 4 (need 4 late days). For the second assignment, you will finish it on day 10, and the late day you need is 10 for that assignment. For the last assignment, you will finish it on day 13, which means you used 13 late days for that assignment. In total, you used 4+10+ 13 = 27 late days, so you lose 27 points in total. Of course, you want to lose as few points as possible! How should you work on the assignments to minimize the number of points lost? 1. 2. What is the optimal solution for the above example (e.g., three assignments that require 4, 6, and 3 days, respectively)? What is the least number of points you will lose? From your answer above, you probably guess that a greedy algorithm can do the trick you are right. Given n assignments with number of days t; you need to finish them, please describe a greedy algorithm that can help you lose the fewest number of points. 3. Please prove that your algorithm can give the optimal solution. (Hint: you can use greedy choice and optimal substructure as we introduced in class. Actually there are other simpler ways to prove this. As long as your proof is valid and correct, you can get the points.)
Transcribed Image Text:No one likes working on homework assignments one day after you enjoyed your party time, you realize that you have missed n homework deadlines! All the instructors were very angry at this, and they told you that the penalty will be based on your late days. So, now, you have to start working on your assignments. You have n assignments to make up, from today. For assignment i, you know you need t; days to finish it. You can only work on one assignment at a time. If you finish an assignment on day d, you can submit it immediately, and your the number of late days for that assignment is d, which is the number of points you lose for that course. Your total penalty, therefore, is the total number of late days you finally need for finishing all assignments. For example, suppose you have 3 assignments to make up, and they take time 4 days, 6 days, and 3 days, respectively. If you work on them in order, you need 4 days to finish the first assignment, and can submit it on day 4 (need 4 late days). For the second assignment, you will finish it on day 10, and the late day you need is 10 for that assignment. For the last assignment, you will finish it on day 13, which means you used 13 late days for that assignment. In total, you used 4+10+ 13 = 27 late days, so you lose 27 points in total. Of course, you want to lose as few points as possible! How should you work on the assignments to minimize the number of points lost? 1. 2. What is the optimal solution for the above example (e.g., three assignments that require 4, 6, and 3 days, respectively)? What is the least number of points you will lose? From your answer above, you probably guess that a greedy algorithm can do the trick you are right. Given n assignments with number of days t; you need to finish them, please describe a greedy algorithm that can help you lose the fewest number of points. 3. Please prove that your algorithm can give the optimal solution. (Hint: you can use greedy choice and optimal substructure as we introduced in class. Actually there are other simpler ways to prove this. As long as your proof is valid and correct, you can get the points.)
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps with 2 images

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Similar questions
  • SEE MORE QUESTIONS
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS