CS 441/539 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: And, of course, you can always ask questions in class. Don't be shy.
We want to help you!

NOTE: Help Session on Tuesday 11:30am-1:00pm and 2:30-4:00pm in Jolley 542.

Homework 6

NOTE: In Problem 3, the last sentence should read "Assuming it is still needed, the algorithm must decide whether to buy the item for K dollars or rent it for another day."

Homework 4

For Problem 5, for the Set Partition problem can the input S be a multi-set (that is, can there be repetitions)?

Yes.

Homework 3

For Problem 7, what can B do besides calling A?

Nothing except for $O(1)$ time operations to decide what input to use for the next call where it can use it's input y or any of the outputs from earlier calls to A.

Homework 2

For Problem 2 (the alignment problem) are you allowed to align to non-matchin characters?

Yes! For the example, given another (and better) alignment is given by 

ctatg
ttaagc
which has cost 3. The example given was there to illustrate how the cost is affected by spaces.

How should I write-up my HW 2 solutions?

Here is the E-mail sent on how to write-up your homework 2 solutions.

Also a solution for practice problem 1 is included here so that you can see a sample solution write-up.

Homework 1
Are we expected to provide a proof of correctness for each of the algorithms we give?

As stated at the top of the assignment: In all problems that ask you to give an algorithm you must give a clear description of the algorithm, prove the algorithm outputs an optimal solution and show that the algorithm has the desired time complexity.

The only difference I see between Problem 4 and Problem 7 is that there is a nickel available in Problem 7. Does that really make any difference?

YES!

For problem 8 in Homework 1, do I need to prove my algorithm is correct (i.e. it uses the fewest lecture halls possible)?

Yes. Whenever you give an algorithm, I expect you to prove that it is correct.

If I prove the greedy choice property and optimal substructure property, do I still need to do the inductive proof?

No. However, you should see us if you do not understand the "generic" inductive proof given in class.

Do I have to do the correctness proof by showing that the greedy choice property and optimal substructure properties hold?

No. However, you should be sure that your proof shows that the solution output by your algorithm is an optimal solution.

Return to the CS 441/539 Home Page