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).
  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).
  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.
  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.
  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)).
  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.

Answers