Q6: The array contains n numbers; not all numbers are distinct; there are
exactly k distinct numbers out of the total of n numbers; the sorted array should
be of size n (as the original array). (See question number 31 below for further detail.)
Q: Question 5
Should we provide pseudo code that produces an optimal Huffman code for Fibonacci numbers?
A:
No. You should only provide an optimal Huffman code. (To this end, we recommend that you use the algorithm that was taught in class.)
Q: Question 6
We believe we found a simpler way to sort the array in the required time order without using a smart array, is it possible?
Do you prefer a solution using smart array anyway?
A:
You do not have to use smartArray. You can use any data structure you like
as long as you meet the desired time requirement.
Q: Question 4
What exactly do you mean in the condition that all UNION operations appear before any of the FIND SET operations?
we are having trouble to comprehend it since UNION operation includes 2 FIND SET operations inside it.
A:
You raise a very good point.
When we say that all Union operations appear before all Find-Set operations, we mean
that any Union operation receives as input two "root" representitives.
In other words, Union(x,y) performs a Union of a set whose "root"-representitive
is x with a set whose "root"-representitive is y.
Even though Union(x,y) generally invokes the two following calls to Find-Set:
Find-Set(x) and Find-Set(y), under our assumption, we have x = Find-Set(x) and
y = Find-Set(y), and so we simply disregard these calls.
Q: Question 6
A. Can we assume that k is given?
B. If not, can we construct an array of size MAX+1, because this must increase
the running time to be O(MAX).
C. Can we assume that the running time needed to construct an array does not take any time?
D. Is k the maximal integer in the array?
A:
A. Yes.
B. You can construct an array of size MAX + 1 in time much less than Theta(MAX).
(Hint: you smartArray.)
C. No. (See the hint of the previous item.)
D. No.
Q: Question 2
Should we assume that there are m Insert operations and m Delete operations?
A:
No, there are m operations of Insert and Delete altogether.
(For example, it may be that all m operations are Insert operations, and so there are no Delete operations.)
Q: Question 2
May we assume that the integers in the set are distinct?
A:
You may assume this, but this really does not matter.
Q: Question 5
Should we construct a tree that represents an optimal Huffman code, as was shown in class?
A:
Such a tree is not an Huffman code itself, but rather an auxiliary tool for producing it.
I recommend that you first construct such a tree, and then use it to produce an optimal
Huffman code (as shown in class).
Q: Question 4
"sequence of m Make-Set, Find-Set, and Union operations" means m operations in total, or m operations of each one: m operations of MakeSet, m operations of Find-Set and m operations of Union?
A:
It means m operations in total, but this really does not matter.
Q: Question 2
In case I choose to store the elements of the set in an array, should I handle the case when the array becomes full?
A:
Yes, you should.
Q: Question 3
Should the answer be expressed in terms of both N and n?
A:
The answer should be expressed in terms of at least one of these parameters
(not necessarily the both of them).
Q: Question 3
Should we analyze the total cost of n operations or the amortized cost of a single
operation?
A:
You should analyze the total cost of n operations in the worst
case. (Dividing it by n would give you the amortized cost of a single operation.)
Q: Question 2
May we assume that no element is inserted to the set more than once?
A:
Yes.
Q: Question 6
We have a problem. In the hints you advice us to construct a smartArray of size MAX + 1.
The initialization of a smartArray involves constructing 3 arrays of size MAX + 1,
but in the FAQ it says that we may not assume that constructing an array of size MAX + 1
takes O(1) time.
A:
This is inaccurate. In the FAQ we only mention that the running time required to construct an array cannot be ignored. Specifically, it is O(1). (Notice that O(1) should not be regarded as zero.)
Q: Question 4
May we assume that no set exists at the beginning of the m operation?
A:
Yes.
Q: Question 3
May we assume that the capacity of the stack, N, is a constant?
A:
No.
Q: Question 6
We do not understand this question.
What does it mean "an array of size n that contains k distinct non-negative integers"?
A:
It means that the array contains n numbers and that the same number can
appear more than once. There are exactly k different numbers out of the total of n numbers.
Examples: a. if n equals 5 and k equals 1, then the array contains n numbers of the same value,
for instance [2,2,2,2,2]. b. if n equals 5 and k equals 5, then the array contains 5 numbers,
all of them are distinct, for instance [9,2,5,4,6].
Q: Question 3
What does the sign << mean?
A:
x << y means that x is much much smaller than y;
x >> y means that x is much much larger than y.
Q: Question 3
May we assume that the minimum among n and N is a constant?
A:
No.
Q: Question 3
In the case n << N (item c), may we assume that the stack cannot become full during
any n operations of the given four types?
A:
Yes.
Q: Question 3
A. What is |S|?
B. What is the maximal number of elements that we can push to S
in a single MultiPush operation?
A:
A. |S| is the number of elements currently stored in S.
B. No more than |S|, that is, no more
than the number of elements that are stored in S before the MultiPush operation is performed. (This means that the number of elements in S after a MultiPush operation
can be at most twice as large as it was before this operation.)
For example, if |S| equals 5 and N equals 20, then we can push at most 5 additional
elements. In addition, observe that we cannot push elements to a full stack,
that is, we cannot push more than N - |S| elements. For example, if |S| equals 5 and N equals 7, then we cannot push more than 2 elements.
Q: Question 3
You wrote in the FAQ (two questions above) that if n<<N, then we may assume that the stack cannot become full in any n operations.
Don't you mean if n<< logN?
A:
Notice that the notation "<<" is not the same as "<". When I write n<<N, I mean
that n is much much smaller than N, so that I can even assume that n is smaller than logN,
for example.