CSC 263 Assignment # 1

• The PDF file that you submit must be clearly legible. To this end, we encourage you to learn
and use the LaTex typesetting system, which is designed to produce high-quality documents
that contain mathematical notation. You can find a latex template in Piazza under resources.
You can use other typesetting systems if you prefer. Handwritten documents are acceptable
but not recommended. The submitted documents with low quality that are not clearly legible,
will not be marked.
• You may not include extra descriptions in your provided solution. The maximum space limit
for each question is 2 pages. (using a reasonable font size and page margin)
• For any question, you may use data structures and algorithms previously described in class,
or in prerequisites of this course, without describing them. You may also use any result that
we covered in class, or is in the assigned sections of the official course textbook, by referring
to it.
• Unless we explicitly state otherwise, you should justify your answers. Your paper will be
marked based on the correctness and completeness of your answers, and the clarity, precision,
and conciseness of your presentation.
• For describing algorithms, you may not use a specific programming language. Describe your
algorithms clearly and precisely in plain English or write pseudo-code.

1. (20 marks) In the following procedure, the input is an array A of size n ≥ 2 which contains arbitrary
integers.
1: procedure Odd-or-Even(A,n)
2: for i = 2 to n do
3: x = (i mod 2) . (i mod 2) is one if i is odd; it is zero, otherwise.
4: if (A[i] + A[i − 1]) mod 2 , x then
5: for j = i to n do
6: A[j] + +
7: end for
8: else
9: return . Returns from the procedure call.
10: end if
11: end for
12: end procedure
Let T (n) be the worst case time complexity of executing procedure Odd-or-Even on an array of
size n ≥ 2. Assume that assignments, comparisons and arithmetic operations, like additions take a
constant time each.
(a) (5 marks) State whether T (n) is O(n
2
) and justify your answer.
(b) (15 marks) State whether T (n) is Ω(n
2
) and justify your answer. Any answer without a sound
and clear justification will receive no credit.
2. (35 marks) Considering the following algorithm which searches for the last appearance of value k
in an array A of length n. The index of the array starts from 0.
FindLast(A,k) :
1 for i ← n − 1,n − 2,...,0 :
2 if A[i] = k :
3 return i
4 return −1
The input array A is generated in the following specific way: for A[0] we pick an integer from {0,1}
uniformly at random; for A[1] we pick an integer from {0,1,2} uniformly at random; for A[2] we
pick an integer from {0,1,2,3} uniformly at random, etc. That is, for A[i] we pick an integer from
{0,..., i + 1} uniformly at random. All choices are independent from each other. Now, let’s analyse
the complexity of FindLast by answering the following questions. All your answers should be in
exact form, i.e., not in asymptotic notations.
Note: For simplicity, we assume that k is an integer whose values satisfies 1 6 k 6 n.
(a) (5 marks) In the best case, for input (A,k), how many times is Line #2 (“if A[i] = k”) executed?
Justify your answer.
(b) (5 marks) What is the probability that the best case occurs? Justify carefully: show your work
and explain your calculation.
(c) (5 marks) In the worst case, for input (A,k), how many times is Line #2 executed? Justify your
answer.

(d) (10 marks) What is the probability that the worst case occurs? Justify carefully: show your
work and explain your calculation.
(e) (10 marks) In the average case, for input (A,k), how many times is Line #2 expected to be
executed? Justify your answer carefully: show your work and explain your calculation.
Hint: Your answers should be in terms of both n and k. Thinking about the number of comparisons
needed to find a given k, which values are possible, which values are not?
3. (20 marks) Given an integer array of n elements, write an algorithm that finds the k smallest elements
of the array where k and n are two integers such that k < n. You need to give the most efficient
algorithm for this question. Analyze the time complexity of your algorithm.
4. (25 marks) Given an input stream of n integers, we want an efficient algorithm that finds the median
of elements that have been read so far. The algorithm must perform the following task for each i
th
integer:
• Add the integer to a running list of i
th integers and find the median of the updated list.
• Print the list’s updated median after reading each element.
For example, let us consider the stream 5,15,1,3
• After reading the first element of the stream 5 → median: 5
• After reading the 2nd element of the stream 5,15 → median: 10
• After reading the 3rd element of the stream 5,15,1 → median: 5
• After reading the 4th element of the stream 5,15,1,3 → median: 4
So, the algorithm output will be 5,10,5,4.
The worst case running time of your algorithm must be less than Θ(n
2
). Algorithms with time
complexity of Θ(n
2
) and higher will receive no credit.
Hint: : You need to use the heap data structure for an efficient algorithm.
(a) (20 marks) Describe your algorithm clearly and precisely in plain English.
(b) (5 marks) Analyze the worst case running time of your algorithm.
Remark: The median is the value separating the higher half of a data set from the lower half. For a
sorted data set,
• if a dataset contains an odd number of elements, the median is the middle element of the
sorted sample.
• if the dataset contains an even number of elements, the median is the average of the two
middle elements of the sorted sample.