Algorithms

Question 1

Finding the maximum element in a finite sequence

complexity 0(n)

Answer 1

Procedure max(a1, a2…..an: integers)

max:= ai
for i= 2 to n
if max < a1 then max := ai
return max {max is the largest number}

Question 2

Linear Search

complexity 0(n)

Answer 2

Procedure linear search( x:integer a1,a2.....an: Distinct)
i := 1
while (i <= n and x! = ai)
        i:= i+1
if i <= n then location := i
else location := 0
return location

Question 3

Binary Search

complexity 0(logn)

Answer 3

Procedure Binary Search (X: integer, a1,a2…..an: increas)

i: = 1( i is left endpoint of search interval)
j: = n (j is right endpoint of search interval)

while i< j
m:= [(i+j)/2]
if x> am(small) then i:= m+1
else j:= m

if x = ai then location := i
else location := 0
return location

Question 4

Bubble sort

Answer 4

Procedure bubblesort (a1,a2,…an: real n with n>=2)

for i:= 1 to n-1
for j:= 1 to n-i
if aj >aj +1 then interchange aj and aj+1

Question 5

Insertion sort

complexity 0(n^2)

Answer 5

Procedure Insertion (a1,a2,...an: integers)
 for j = 2 to n
        i := 1
        while aj > ai
                 i:= i+1
        m:=aj
        for k= 0 to j-i-1
                  aj-k :=aj-k-1
         ai:=m

Question 6

Prove that if 2^p-1 is primer then p is prime

by contradiction

Answer 6

Suppose that 2^p-1 is prime and p is not prime
then let p=st

x^st -1 =(x^s -1)(x^s(t- 1)+ x^s(t-2+…..x^s+1)

Then if x=2 then 2^p-1 can be expressed as the product of two factor

then 2^p-1 is not prime —>contradiction (2^p-1 was stated as prime)

Question 7

Prove that every composite integer n is a product of prime numbers

(by contradiction)

Answer 7

Let N be the smallest positive number that is not a product of prime numbers.

Since N is a composite then ∃a,b ∈Z
Such that N=ab a,bcontradiction
(N was stated as not prime)

Question 8

Prove that there are infinite prime numbers

by contradiction

Answer 8

Suppose that there are only K prime numbers

Let n=p1p2p3…pk +1

Consider N/pi= p1p2…pi…pk/pi + 1/pi

then N is not divisible by pi

then N is prime

Question 9

e

Answer 9

pichea

Question 10

f

Answer 10

pichea