CSE 441T/541T Frequently Asked Questions (FAQs)

CSE 441T/541T Frequently Asked Questions (FAQs)

The following list of FAQs is provided for your convenience. If your question isn't answered below, don't despair! We want to be sure that you get an answer! To seek out the answer you need, you can:

check the recent announcements for homework/lab hints and clarifications,
go to office hours,
read postings on the newsgroup (wu.cse.class.441),
send us mail.

And, of course, you can always ask questions in class. Don't be shy.
We want to help you!

Homework 3

For question 3, can the job lengths for MP-SCHED be negative?: No. The length of a job must be at least 0. However, in subset-sum each x_i is a natural number which means that it is a non-negative integer. In fact, if you look at the reduction from 3-CNF-SAT to Subset-Sum given in the text you will see that each x_i is a positive integer and so not suprisingly if you restrict each x_i to be a positive integer, subset-sum is NP-complete.
For question 3, can I do a reduction from Partition: Yes, but then you should prove that Partition is NP-hard by doing a reduction from Subset-Sum to Partition.
On question 3, does MP-SCHED return true only if the latest job completes at time d, or is it true if the latest job completes at or before time d?: It returns true if the latest job completes at or before time d. So if MP-SCHED is true for a given d then it is also true for any deadline greater than d.

Homework 2

Can you review the steps that should be in our solutions?

0. Mention any preprocessing (not always needed)
1. State the general subproblem form (include your notation and the semantics of what subproblem you are solving).
2. Give the recursive definition (using your notation from #1)
3. Say where the solution to the original problem is located (or how it can be computed).
4. Say (briefly) the bottom-up order or justify the use of memoization if you feel that would be best.
5. Prove the recursive definition is correct (argue that there exists some optimal solution that included one of the first steps of your recursive definition and for each possible first step, explain why your formula is correct in the recursive definition and argue that optimal substructure holds).
6. Analyze the asymptotic time complexity (this will include counting how many subproblems there are and the time complexity for each -- explain how you got what you put for both of these).

Look at the practice problem solutions (in postscript)/ (in pdf) to see samples. Also look at the text book since it generally includes all of these steps in giving the solutions to the problems in the book

Can you give me a sample output for problem 1c so I can check my output?

Here is my output with M=60. It is possible there are other optimal layouts. So if your layout has a cost of 95 then it is optimal. The row of periods above the text is a row of 60 periods to make it easier to see how much white space is at the end so you can confirm the cost is 95.

Cost with line length of 60 is 95, obtained by layout: 

............................................................
Fourscore and seven years ago our fathers brought forth 
on this continent a new nation, conceived in liberty and 
dedicated to the proposition that all men are created equal. 
Now we are engaged in a great civil war, testing whether 
that nation or any nation so conceived and so dedicated can 
long endure. We are met on a great battlefield of that war. 
We have come to dedicate a portion of it as a final resting 
place for those who died here that the nation might live. 
This we may, in all propriety do. But in a larger sense, we 
cannot dedicate, we cannot consecrate, we cannot hallow this 
ground. The brave men, living and dead who struggled here 
have hallowed it far above our poor power to add or detract. 
The world will little note nor long remember what we say 
here, but it can never forget what they did here.

For Problem 3, what affect do the negative edges have an the path?

If you follow a directed path from a node down toward the leaves and add up the edge weights as you go, then if there is a negative weight this sum goes down.

Homework 1

For the algorithm proposed in 3b, are all mn possible skier/ski pairings considered in making the greedy choice?: Yes, all mn possible pairings are considered and one that minimizes |h_i-s_j| among all mn choices for i and j is picked. That is for i and i' integers between 1 and n, and for j and j' integers between 1 and m, an i and j are selected so that
|h_i-s_j| <= |h_i'-s_j'| for any i', j'.
In 1a, shoud it read that "job i runs for 1 unit" instead of saying that "job i runs from 1 unit"?: Yes.
Return to the CSE 441T/541T Home Page