Hi,

Problem 1 asks us to use MEDIAN to find the ith smallest element of a
list A in linear time. When they say "the ith smallest element of a
list", does that mean we should return the ith smallest element
including OR excluding duplication of elements?

Say for example, if we want the second smallest element of the list
[1;1;1;2;2;6;6;6;9;9;10], should it return '1' or should it return
'2'?

Thanks,

Vivien

In class it was mentioned that you should literally return the ith
smallest element of the sorted list.

In your example, the second smallest element would be 1. A[2] assuming
a 1-based array.