Sale!

ve203 Assignment 7

$30.00

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)

Category:

Description

5/5 - (3 votes)

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