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!

Homework 4 -- Don't forget to put each problem on its own page!
Grading Session is the evening of March 19 at 7:00pm.

Could you give an example to explain what is meant by Ax <= b in the 0-1 Integer Programming problem?

Consider the following constraints: 
       x1 + 2 x2 + x3   <= 2

       -x1              <= 1

       2x1       - 3 x3 <= 0

            - x2        <= 0
So here the number of variables n=3, the number of constraints m=4. Then 

     the matrix A is      and    the vector b is

        1   2   1                    2
       -1   0   0                    1
        2   0  -3                    0
        0  -1   0                    0
Notice that requiring that Ax <= b is exactly saying that you want a value for x1, x2, x3 so that the given 4 constraints are satisfied. The decision problem is then, "Is a vector x of n bits such that Ax <= b?" That is, if the bits in the n-vector x give the values for x1, x2 and x3, is there a solution wheren the above 4 inequalities are satisfied.

Note that in the 3-CNF-SAT problem you are asked to find an assignment to the variables so that at least one literal in each of the clauses is true. In the 0-1 Integer Programming problem you are asked to find an assignment to the variables so that each of the constraints is satisifed.

Homework 3 -- Don't forget to put each problem on its own page!
(Problems 7 and 8 can be combined).

In Problem 2, how are we expected to intepret the statement "schedule so that each outlet has as many units needed based on the forecasting estimates"?

If you are selling widgets and the forecasting estimates are that as many as 100 people are going to come by a widget then if you want to have as many widgets as needed you had better have 100 widgets in stock.

What are the steps in showing that a problem is in NP?

1. You should describe what is to be used for a certificate.

2. Then briefly argue that there exists a polynomial time algorithm A that takes as inputs the graph G and a certificate C such that.

a) If G is 3-colorable then there is some certificate C, such that algorithm A on inputs G and C, A will output "yes", G is 3-colorable.

b) If G is not 3-colorable then for any certificate C, algorithm A on inputs G and C will output "no", G is not 3-colorable.

I'm having trouble understanding the definition of 3-colorable

The function f is just a function that associates one of 3 colors with each vertex of the graph. The graph is 3 colorable if there exists such a function (i.e. a color assignment to each vertex) such that the two endpoints for each edge in the graph are a different color.

Notice that you are only asked to prove that Graph-3-colorability is in NP (not that it is NP-complete).

In the HW 2 solution for matching the skis with skiers what should be done if i>0 and j=0?

The value of the optimal solution here should be infinite since there are more skiers than skis. As written, the given solutions would have set this to 0. To fix this, you can change the recursive solution to: 
                0                                 if i = 0   
c[i,j] =    infinity                              if i > j
            min{c[i-1,j-1]+|hi-sj|,c[i,j-1]}      otherwise
where c[i,j] is the optimal solution for pairing skiers h1,h2, ...,hi with skis s1,s2,...,sj for 0 <= i <= n and 0 <= j <= m.

What problems are available for grading?

Problems available for grading are 2,3,4,5 and 6. The grading session is on the evening of Thursday Feb 26.

What output should we provide for Problem 1?

Here is the test data for homework 3 with some annotation to explain it. You will want to remove the annotation. Also feel free to modify this file if you find some other form easier to work with.

You MUST your output for this data along with your code.

To make it easier for you to test your program, here is the input and output from what was used for the exam.

In C++ how do I allocate a n by m two-dimensional array where n and m's values are not known until runtime?

Here is a sample program that allocates an two-dimensional array A and then sets A[i][j] to i+j (just to demonstrate the use). It uses the same stdinc.h as for the last homework. 

#include "stdinc.h"

main(){
   int **A;
   int n, m;
   cin >> n;
   cin >> m;
   A = new int*[n];
   for (int i=0; i<=n-1; i++)
      A[i] = new int[m];

// You can now access an entry with A[i][j] as shown below
// Note that the above is all you need to do to allocate
// the array.  What is below is just to demonstrate the use.
// You shouldn't do anything like the below for your homework

   for (i=0; i<=n-1; i++)
      for (int j=0; j<=m-1; j++)
         A[i][j] = i+j;

   cout << "Here is the matrix " << endl;
   for (i=0; i<=n-1; i++){
      for (int j=0; j<=m-1; j++)
        cout << A[i][j] << " ";
      cout << endl;
   }
}
In Java how do I allocate a n by m two-dimensional array where n and m's values are not known until runtime?

Here is a sample program that allocates an two-dimensional array A and then sets A[i][j] to i+j (just to demonstrate the use). It uses the same Terminal class as in the last homework. 
public class Test {

   public static void main(String args[]){
      int n = Terminal.readInt();
      int m = Terminal.readInt();
      int A[][] = new int[n][m];

// You can now access an entry with A[i][j] as shown below.
// Note that the above is all you need to do to allocate
// the array.  What is below is just to demonstrate the use.
// You shouldn't do anything like the below for your homework

      for (int i=0; i<=n-1; i++)
         for (int j=0; j<=m-1; j++)
            A[i][j] = i+j;

     Terminal.println("Here is the matrix");
      for (int i=0; i<=n-1; i++){
         for (int j=0; j<=m-1; j++)
           Terminal.print(A[i][j] + " ");
         Terminal.println("");
      }
   }   
}

Homework 2 -- Don't forget to put each problem on its own page!

Problem 2 is still available for grading. (The grading session will be on Thursday night.)

For problem 4, do we get to decide where to place the integers?

NO! Below is an example input -- The numbers are already fixed to a square. The choice of pebble placements shown (a non-optimal choice) has a value of 778.

Is the following alignment legal for the example provided?

ctatg
ttaagc
Yes, its cost is 3 (mismatches in positions 1,4,6). So this is a better alignment than the one given in the homework.

What are the steps expected when writing up my dynamic programming solution?

Be sure that each of the below steps is clearly labeled.

  1. You should clearly state the subproblems and your notation.

    For example in the matrix multiply example we had: For 

     1 <= i <= j <= n,  m[i,j]
    held the number of scalar multiplies for the optimal way to parenthesize 
     A_i .... A_j

    As one more example for the LCS problem the subproblem was to find the LCS for the first i chars of X and the first j chars of Y. We used c[i,j] for the length of the LCS between the first i chars of X and the first j chars of Y.

    This step is VERY important for your solution to be easily read and understood.

  2. Describe the recursive solution.

    You can do this, as we've done in class by just giving a recursive definition for the solution for each subproblem in terms of the solutions to smaller subproblems or if you prefer to express it has a recursive procedure that is also fine.

  3. Prove that the solution defined by your recursive solution is correct.

    Generally this involves the following steps (which can be combined in your write-up):

    • For an optimal solution S, argue that S must have fit into one of the cases you considered.

    • Prove that you have the optimal substructure property. That is you must prove that the optimal solution to the original problem includes within it the optimal solution to the subproblems. The key here is typically to show that cost associated with a solution to the subproblem(s) and the cost associated with the first step are independent of each other.

  4. Describe the order in which the subproblems are solved.

    This step can be very brief

  5. Time complexity analysis.

    Along with stated the time complexity be sure to briefly explain your answer.

When will the test data be available?

Here it is.

Homework 1

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 1 should we show the tree used for decoding?

If the codeword you give for each character is correct then you will receive full credit. However, by showing the tree that is created during the algorithm (which is the tree used for decoding), you will enable us to give you partial credit if you make some silly error in going from the tree to the codewords. Thus I recommend that you go ahead and put the final tree in your solutions (please do NOT show the intermediate steps).

In Problem 2 are d_1, ..., d_n sorted?

The intention was for them to be sorted. (You can think of them as the value on the "mile markers" with mile marker 0 at St. Louis.) So d_1 <= d_2 <= ... <= d_n. Please write your solution under this assumption. Also it is assumed that you begin in St. Louis with a full tank of gas.

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 two problems are very similar, do I need to repeat portions of my solution that are the same in both?

No. Just explain which portions can be re-used and then in your solution for the later problem just refer back to the first one.

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.

Do I need to use dynamic programming for any problem in Homework 1?

No.

Return to the CS 441/539 Home Page