### 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:
• Determine if f is 1-1.

Of course, f is 1-1, if whenever i< j, f(i) is not equal to f(j). That is, a_i is not equal to a_j. We need to look at each a_i and see if there is a j>i such that a_i=a_j. We might as well stop if this ever happens. Let me give two, they both have the same complexity. The first makes all comparisons hence there's no need to worry about worst case. I'll not analyse the second but you should (it might fool you since there's only one "while" loop and you might jump to the conclusion that it is O(n)).

Procedure 1-1 (a_1,...,a_n: integers)
value:=1 {switch this to 0 if it is not 1-1} for i:=1 to n-1
for j:=i+1 to n
if a_i = a_j then value:=0
{I don't think I needed "begin-end" here}

The complexity analysis: For each i, what do we do? We let j go from i+1 to n. This is (n-i) steps. Therefore, considering all i, we get the sum:
(n-1) + (n-2) + ... + (n-(n-1))= 1+2+...+(n-1)
SIGMA { k : k=1,...,n} = (n*(n+1))/2
This sum is (SIGMA {k: k=1,..., n} ) - n = n * (n+1)/2 -n = n ( (n+1)/2 - 1) = n( (n+1)/2 - 2/2) = n ( (n-1)/2)
We could certainly do (1+...+(n-1) = (n-1)( (n-1)+1)/2 directly but I wanted to give a little practice with SIGMA. Of course n*(n-1)/2 is O(n^2).

Here is the second:
i:=1
j:=2
While (i < n and a_i < > a_j){common symbol for not equal}
if j < n then j:=j+1
else
begin
i:=i+1
j:=i+1
end
{if i<n then it is not 1-1}

• Find if there is an x, such that the preimage of x has precisely 2 elements.
The preimage of x means f^{-1}(x), i.e., all those i such that f(i)=x.
We obviously only need to consider those x which are equal to f(i) = a_i for some i. So we let i run from 1 to n, for each i, see if there is exactly one j > i such that a_i=a_j. (I didn't bother fixing it but I realized later that there's an obvious flaw in this algorithm, j needs to start with 1 -- why?)

Procedure 2elements(a_1,...,a_n: integers)
value:=0
hits:=1
i:=1
while hits<> 2 {remember this mean not equal}
begin
hits:=1
j:=i+1 {oops first version started at i+1}
while (j<= n and hits< 3)
begin
if a_i=a_j then hits:=hits+1
j:=j+1
end
i:=i+1
end

• Takes as input, x and the list and computes Sigma f^{-1}(x). (Sigma means that summation sign and we want the sum of the pre-image of the value x).

Procedure Sum f^{-1}(x)(x,a_1,...,a_n: integers)
S:= 0 {initialize sum}
for i:=1 to n
if x=a_i then S:=S+i

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.