Q1
I was just wondering if its ok to work on the assignments with people from
other sections?
A1
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.
Q2
I was wondering where I can find copies of the transparencies
you were using in class.
A2
Take notes in class: write down the most important
definitions and ideas. You can also use
handouts provided by Michael Goodrich and Roberto Tamassia.
Q3
Which book we have to buy?
A3
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).
Q4
Which programming language we can use for coding in home work assignments?
A4
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.
Q5
Where I can find definitions of Big-O, Big-Theta, Big-Omega?
A5
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.
Q6
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?
A6
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.
Q7
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?
A7
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}.
Q8
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..
A8
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.
Q9
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?
A9
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.
Q10
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?
A10
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.
Q11
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.
A11
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.
Q12
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 Heap.java is with DynamicSetElement line (208). As well many
more errors. Can you please provide us with additional files to make these
classes work.
A12
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
Heapsort.java DynamicSetElement.java
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:
http://algs4.cs.princeton.edu/code/
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.
Q13
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"?
A13
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.
Q14
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?
A14
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.
Q15
A15
Q16
A16
Q24
A24
Q25
A25
CPS616