Is there any specific name that we should call some of the Greedy Algorithms in the book that are not given specific names?
I want to use the Minimize Lateness greedy algorithm as a black box, but I'm not sure what to call it since I couldn't find a specific name for the algorithm used in the book.
So on the last problem, I dont understand something. Are the paths all calculated before starting the trip or are they calculated, one-by-one, as a stopping point is reached?
The problem is a trip between two cities with intermediate stops along the way. The folks taking the trip have access to a website that determines travel times between cities and stopping points and the variable seems to be that the weather can change travel times at any point.
I guess what I am wondering is do the travellers plan the path completely before the trip or do they travel to a point and then check for the next path? (I am guessing the former or it doesnt matter)
Re problem 4.18, the travelers are supposed to plan their entire trip before leaving home. The way the problem is stated, it isn't the case that the website updates its forecasts as time goes by, but rather, the website has advance knowledge of how long crossing any road segment will take, given the start time as input.
Are we expected to include a proof of correctness and speed for our algorithm for 4.4? I ended up coding up a little program in Eclipse, and it seems pretty obvious that the code will have the correct output and the running time given, but I don't want to penalized for not including it.
It would be good to say at least a sentence or two about each of these aspects. If you think they may be obvious, try to briefly explain why you think so.
Using the greedy algorithms as a black box:
ReplyDeleteIs there any specific name that we should call some of the Greedy Algorithms in the book that are not given specific names?
I want to use the Minimize Lateness greedy algorithm as a black box, but I'm not sure what to call it since I couldn't find a specific name for the algorithm used in the book.
Just say "the Maximum Lateness minimizing scheduling algorithm," or words to that effect. I don't think there is any special name for it.
ReplyDeleteSo on the last problem, I dont understand something. Are the paths all calculated before starting the trip or are they calculated, one-by-one, as a stopping point is reached?
ReplyDeleteSorry, I don't have the problem statement with me here. Can you post it, or at least the relevant part, please?
ReplyDeleteThe problem is a trip between two cities with intermediate stops along the way. The folks taking the trip have access to a website that determines travel times between cities and stopping points and the variable seems to be that the weather can change travel times at any point.
ReplyDeleteI guess what I am wondering is do the travellers plan the path completely before the trip or do they travel to a point and then check for the next path? (I am guessing the former or it doesnt matter)
KS
Re problem 4.18, the travelers are supposed to plan their entire trip before leaving home. The way the problem is stated, it isn't the case that the website updates its forecasts as time goes by, but rather, the website has advance knowledge of how long crossing any road segment will take, given the start time as input.
ReplyDeleteAre we expected to include a proof of correctness and speed for our algorithm for 4.4? I ended up coding up a little program in Eclipse, and it seems pretty obvious that the code will have the correct output and the running time given, but I don't want to penalized for not including it.
ReplyDeleteIt would be good to say at least a sentence or two about each of these aspects. If you think they may be obvious, try to briefly explain why you think so.
ReplyDelete