## Description

ve203 Assignment 7

Q1. Let m ∈ N with m > 1. Prove that if ac ≡ bc (mod m), then

a ≡ b

mod

m

gcd(c, m)

(2 marks)

Q2. Find a solution to the linear congruence 36x ≡ 75 (mod 1309).

(2 marks)

Q3. Find all solutions to the system:

2x ≡ 4 (mod 5)

3x ≡ 5 (mod 7)

7x ≡ 2 (mod 13)

(2 marks)

Q4. Find all, if any, solutions to the system:

x ≡ 5 (mod 6)

x ≡ 3 (mod 10)

x ≡ 8 (mod 15)

(2 marks)

Q5. Find all, if any, solutions to the system:

x ≡ 5 (mod 5)

x ≡ 3 (mod 7)

x ≡ 8 (mod 11)

x ≡ 2 (mod 17)

(2 marks)

Q6. Show that n log2

(n) is not O(log2

(n)).

(1 mark)

Q7. Show that log2

(n), log10(n) and ln(n) all have the same order.

(1 mark)

Q8. Show that bx

3 − 4c is order x

3

.

(1 mark)

Q9. Let k > 1. Do n

n and n

n−k have the same order?

(2 marks)

1

Q10. For all n ∈ N\{0} define

H(n) =

nX−1

k=0

1

n − k

(i) Show that

Xn

j=2

1

j

<

Z n

1

1

x

dx

(ii) Prove that H(n) is O(ln(n)).

(4 marks)

Q11. The Binary Insertion Sort Algorithm is a variation of the Insertion Sort

Algorithm that uses a binary search technique rather than a linear search technique to

insert the i

th element in the correct place among the previously sorted elements.

(i) Express the Binary Insertion Sort Algorithm in pseudocode.

(ii) Compare the number of comparisons of elements used by the Insertion Sort Algorithm and the Binary Insertion Sort Algorithm when sorting the list (7, 4, 3, 8, 1, 5, 4, 2).

(iii) Show that the Insertion Sort Algorithm uses O(n

2

) comparisons of elements.

(iv) Find the complexity of the Binary Insertion Sort Algorithm. Is it significantly

faster than Insertion Sort?

(8 marks)

2