Write algorithms as described and analyse the complexity

    A list means a list, a_1,..., a_n of integers.
  1. Find the 10th largest element in an ordered list (with and without repetitions). One is O(n) and one is O(1).

    For the list without repetitions of course the pseudocode is trivial:

    Procedure 10th(a_1,...,a_n:integers in increasing order)
    x:= a_(10)
    {output x}

    It doesn't matter how large n is it still takes the same number of steps. Hence this is O(1).

    For a list with repetitions, we will have to have the algorithm that potentially has to look at each element.

    Procedure 10th again(a_1,...,a_n:integers)
    t:=0 {a counter for "clock ticks"}
    i:=1
    e:=0 { a counter representing numbers less than a_i in list}
    while ( e<10 and i<n)
    begin
    if a_i < a_(i+1) then e:=e+1
    i:=i+1
    end

    if e=10 then x:=i
    else x:=0
    {x=0 means do not have 10 distinct elements}

  2. Find an algorithm that is O(n^2) which will find the middle element of a list (middle means the [n/2] element when the list is ordered).

    If we input a_1, ..., a_n, we could let i run from 1 to n and test each a_i to see if it is the middle element. So given a_i, how will we test that? We just let j run from 1 through n and count how many of the a_j are less than and how many are equal to a_i. Think about which condition on these two numbers guarantees that the middle number of the ordered list will equal a_i. This algorithm is O(n^2).

    Procedure this question(a_1,...,a_n: integers)
    value:=0 {this will be the middle element}
    for i:= 1 to n
    begin
    Less :=0 {number of elements less than a_i}
    Equal := 0 {number of elements equal a_i}
    for j:=1 to n
    begin
    if a_j< a_i then Less:=Less +1
    if a_j=a_i then Equal := Equal +1
    end
    if (Less , Equal are right) then value:=a_i
    end

  3. Treat the assignment i sent to a_i as a function f, i.e. f(i)=a_i. Write algorithms which:
  4. Your computer cannot multiply or divide, write an algorithm which will compute a mod m and discuss the complexity in terms of a and or m.

    Procedure remainder (a,m: integers)
    while a< 0
    a:= a+m
    while a> (m-1)
    a:=a-m
    {that's it, a now has value a mod m}

    The complexity is O(a/m). Only one of the while loops is actually performed. It takes roughly a/m steps to complete.

  5. Write an algorithm which is O(m log(m)) which will list all those a from 0 to m which are relatively prime with m.

    Actually, all I had in mind here is that you remember that the Euclidean algorithm to compute gcd(a,b) is O(log(min(a,b))). So all we do is have an algorithm written, call it Euclid, which does this. Then here is the simple algorithm:

    Procedure List (m: integer)
    if m=1 then stop {there's no point}
    for i:=1 to m-1 {we know m is not relatively prime}
    begin
    d:= Euclid(i,m)
    if d=1 then Print(i)
    end

  6. With input a< m, list all b between 0 and m such that ax= b (mod m) has a solution. O(m^2) is easy, try also for O(m log(m)).

    For O(m^2), test each b between 0 and m, one by one. For each such b what do we have to do? Just let x run from 0 to m-1 to see if a*x=b (mod m). This is just an m loop in an m loop, so O(m^2). We are assuming that we can multiply or else finding if a*x=b (mod m) would add an additional power to the complexity.

    For O(m log(m)): use our theory. It's actually easier than what I was thinking. We know that there is a solution just if b is a multiple of gcd(a,m). In O(log(m)) steps we've computed d =gcd(a,m). Then we just list the multiples of d that are less than m. This second loop is not inside the first loop (finding the gcd), it comes after. Hence this algorithm is O(log(m)+m), and so just O(m) (even O(log(m)+m/d), since all we've got to do is compute d, d+d, d+d+d, ...

  7. In a list, we are told to ignore all occurrences of the largest and smallest elements because they are viewed as anomalous. Find the number which is in the 10th smallest position of those that remain.

    Method 1: First compute the largest and smallest elements. Then, let i run from 1 to n. Set two counters, Less and Equal to 0. For each i, we have an inner loop j running from 1 to n. If a_j < a_i, increment Less by 1. If a_j = a_i, increment Equal by 1. This ends the j loop. Think of a test using Less and Equal to determine if a_i is (or something equal to it is) the 10-th largest in the list. We neglected to ignore the smallest and largest elements so fix that up in the "IF" statements. Then go to the next value of i.

    Method 2: Again compute the largest and smallest elements. Now just run through the list at most 10 times, each time finding the next smallest element (counting repetitions).

    Method 3: Again compute the largest and smallest elements. This time, set b_1, b_2, ..., b_10 equal to a_1, ..., a_10. The idea is that b_1, ..., b_10 should end up as the first 10 elements of that final list mentioned in the question. Starting with i = 11, run through the list just once. If a_i is more likely to belong in that list than some b_k, then b_k:= a_i.

    Compare the complexities of the methods.

    I won't write pseudocode but here's the complexities:
    Method 1: n + n + n^2, hence O(n^2) {I realize there was no need to compute the largest}

    Method 2: n + n + (n+n+n+(7 more)) is O(n)

    Method 3: n + n+ 10n

    The difference between 2 and 3 is that 2 does a loop 10 times, while 3 does one loop n times but does 10 things in each loop.