Questions related to the 1st assignment

This page contains questions from students and my answers to them. If a question is asked that has already been answered, then I will not post another answer. So if your questions seems to go unanswered, you should check over previous questions.

I was just wondering if its ok to work on the assignments with people from other sections?
Yes, you can work on the 1st assignment with students from any section, but the number of people in your team must be less than or equal to 3. If you work with someone else, submit only one copy of your assignment.

I was wondering where I can find copies of the transparencies you were using in class.
Take notes in class: write down the most important definitions and ideas. You can also use handouts provided by Michael Goodrich and Roberto Tamassia.

Which book we have to buy?
You have to buy the custom published book only (ask at the Ryerson bookstore). You can also borrow from Library Reserve some of the recommended books (but you are not required to buy anyone of them).

Which programming language we can use for coding in home work assignments?
Any common programming language is fine: C, Java, C++, Python, Prolog. But if you would like to use any other programming language outside of this list, talk to the instructor in advance and be prepared to explain your reasons. In any case, make sure you provide clear instructions to the TAs.

Where I can find definitions of Big-O, Big-Theta, Big-Omega?
Here is a link to Wikipedia. You can also read definitions given on transparencies or in the textbook: Section 2.2. Note that both function f(n) and function g(n) are functions from positive integers to positive real numbers. The statements that you are asked to prove follow from the definitions.

I found a program X provided at Y and would like to use it in my implementation of a greedy algorithm. Can I do this?
Yes, you can, but you have to acknowledge correctly who wrote that program X and mention from where you downloaded that program. You can do this in your results.txt file. If your implementation uses several programs from different places, mention all of them.

I had a question about Part 1a of the assignment. When sorting intervals from I, is it based on the number of total houses covered by the interval, or is it the number of houses covered by the interval that have not already been covered by a previous interval?

For example, I1 covers houses 1,2,3,4, and I2 covers houses 4,5,6. If the first choice is I1, it covers 4 points. Does that mean that if I2 is chosen next, it would only cover 2 points since house 4 is already covered by I1?
Or is it just the absolute number of points covered, regardless of previous choices?
Sorting is based on the number of houses covered by the interval that have not already been covered by previous intervals. This is a kind of sorting with adaptation: the first interval chosen determines which points remain uncovered, so that the greedy strategy chooses the next interval that covers most of the remaining points, and so on. In your example, if one chooses I1 that covers {1,2,3,4}, then when comparing I2 with other intervals, we have to count that I2 covers only 2 remaining houses {5,6} out of total number {4,5,6}.

I am not sure if i am on the right track proving part of question 2 in the assignment.   <... skip a line ...>   I proved this for k+1 but i dont know if this is actually proving the algorithm. Can you tell me if i am on the right track or should consider something else as the statement to prove..
First of all, do Part (a) of the 2nd question. According to the hint mentioned in the assignment, you can guess this function by tracing each line of the algorithm for small values of n. The value of x does not matter when you trace. Once you know what kind of function of x,n is answer when the while-loop terminates, you can proceed to (b). In Part (b), you have to prove by strong induction on n that for all n >= 1, upon termination of this algorithm, the value of answer will be exactly the function of x,n that you guessed in Part (a). Without this proof there is no gurantee that you guessed correctly, or that this algorithm computes answer correctly for all positive integer n >= 1 (i.e., not only for those which you traced by hand). In doing Part (a), you probably noticed that the algorithm behaves differently for n=1 and n=2, i.e., different sequences of steps (Lines) in the algorithm will be executed depending on whether n is odd or even. Use these observations in your proof by induction. In other words, you have to consider 2 base cases, and when you are doing inductive step, i.e., prove your statement for (n + 1), consider two cases: when (n + 1) is odd or when it is even. For each case, use one of the inductive hypothesis and trace what the algorithm does to prove your statement. The overal structure of your proof can be similar to a proof by induction from the example discussed in class: that any postage P >= 18 cents can be formed using just 4-cents stamps and 7-cents stamps. However, in this question, the difference is that you consider odd and even inputs separately. In addition, in Part (c), you have to argue why this while-loop always terminates and provide a reasonably tight upper bound O() on the running time of this algorithm.

Please clarify Part 4 from the 1st assignment. Is it necessary to read all programs stored on the tape before the program X if we want to read the program X only? Also, can programs be temporarary stored elsewhere? Finally, how can I justify my greedy strategy before I prove that it is correct?
Yes, because programs are stored on the tape consecutively, you can read the program X only after going through all intermediate programs. Note that the only input to your algorithm will be lengths of the programs. Programs cannot be moved anywhere, they can be only stored on this tape. Imagine that this is a tape used for backup purposes: it might happen that programs from this tape accessed rarely, and there is no point in moving them elsewhere. Consider a few simple numerical examples to show how did you decide that your greedy strategy is optimal. Of course, you have to prove also by induction that your greedy algorithm is correct.

I have a question about assignment 1 Q4. As you had mentioned in Q&A9 above the programs are stored on the tape and cannot be moved anywhere. I suppose the greedy algorithm is to sort the programs on the tape. I believe the sorting can only be achieved if we have another tape or any temporary storage for the program to do the sorting. Can we assume this operation can be done somehow?
There is no need for your greedy algorithm to use the tape. Assume that you have sorted lengths somehow in RAM, and now your algorithm computes an optimal sequence of programs. There is no need to use tape for these purposes. Once an optimal sequence has been computed by the algorithm, programs from this sequence will be stored on the tape somehow. Your algorithm just produces an optimal sequence in which programs will be subsequently stored on the tape. There is no need for your algorithm to copy programs physically to the tape. Similarly, the greedy algorithm for interval scheduling (for scheduling talks in a single lecture hall) that has been discussed in class does not put people in the hall, it just computes an optimal schedule according to which classes will go in the lecture hall.

Which proof by induction should I follow when proving correctness of my greedy algorithm in Part 4? I know a proof from class, but the textbook has a proof with a different style.
Follow proofs from class. Read all handouts (posted on Blackboard) on proving correctness of greedy algorithms by induction. Your proof for Part 4 is expected to be similar to what we did in class.

I am trying to do question 1 c) the one where I have to write a program. The problem is that my IDE is complaining about almost every file provided on Blackboard and its not the package error. An example of an error I am having in is with DynamicSetElement line (208). As well many more errors. Can you please provide us with additional files to make these classes work. 
There are many solutions to this. First, the CD with all Java programs to Cormen's book is available from the library. Ask at the short term loan or at the circulation desk. Second, I added the programs to ZIP archive posted on Blackboard. Third, search on the Web for an implementation of priorities queues in your favorite programming language. For example, you can find this Web site:   Of course, there are many others. Fourth, write your own implementation: you know all pseudo-code for algorithms from class. If you use someone's else code, you have to cite the source: acknowledge in your assignment all external resources you are using. Read Q6/A6 above.

In Part 4, my question is that when we input the original array of unsorted program lengths into our greedy algorithm to find an optimal sequence, are we allowed to look at the lengths of all the programs from the onset, or are we restricted to only being able to see the length of the next program in the sequence (i+1) and not be able to "see into the future"?
The numbers L1, ..., L_n representing lengths are given as an input. Your algorithm can do whatever it likes with these numbers, e.g., it can start with sorting them, as usually greedy algorithms do: they sort input. Each greedy algorithm sorts its input according to some greedy rule, and then it processes elements from the sorted sequence one-by-one. Of course, to sort a sequence of numbers you have to know all these numbers in advance. But once you have sorted them, you can process them one-by-one in the sorted order, and you never need to backtrack. Read both handouts posted on the Blackboard. Also, read all examples of greedy algorithms discussed in class. Note you have to write a proof by induction of corretness for your greedy algorithm.

For question 1d how do we calculate the counter for j? Below is the pseudo code that you have given:
if item > last /* item is not covered, check if it can be covered */
then I_j = [s_j,f_j] <-- HEAP-MAXIMUM(Cover) /* this keeps an interval Ij in the heap */
for this code we assign the values of cover into I_j, but where is j coming from?
j is just a notation used in pseudocode and in explanations before the given greedy algorithm. We call I_j whatever interval that on the current iteration of the while-loop happened to be the root of the Max-heap (called "Cover") for intervals. The index j somewhat indicates that this interval might be considered as j-th interval in a sorted sequence (1=< j =< m), but you can ignore it, if it confuses you. There is no need to implement "j" as a counter.