Math 2415 assignment Help - Online Assignment Help

Marking scheme out of 100 points. For each question, the vector (K,M,P,E) represents the points allocated for each of the 4 criteria, as exposed in the corresponding rubric in Canvas. Please indicate your name and student number on the top of your answer sheet, number the questions and give your answer without copying the question.

For any finite alphabet A (finite set of symbols), A∗ denotes the set of finite strings (or finite words) on A. Note that A∗ includes the empty string, denoted ε.

[(K,M,P,E)=(1,0,0,2)] We consider two alphabets A, B and define a code as a function from A∗ to B∗. The code is used to transmit a message. Explain in your own words why it is essential for the code to be

We consider the following binary code:

C : {0, 1}∗ −→ {0, 1}∗

ω ›→ ωωω

For instance, C(101) = 101101101.

[(K,M,P,E)=(1,0,1,0)] Justify that C defines a well defined
[(K,M,P,E)=(2,0,3,0)] Is C injective? Surjective? Justify your
We use C to transmit binary messages through a network subject to some transmission An error in transmission corresponds to a digit set to 0 in the code while it should be 1 or set to 1 while it should be 0.
- [(K,M,P,E)=(0,2,3,1)] Justify that the recipient can detect errors with the infor- mation that no more than two errors may occur. Can they always detect errors if more than two errors may occur? Give a convincing
- [(K,M,P,E)=(0,2,3,1)] Justify that the recipient can correct errors with the in- formation that no more than one error may Can they always correct errors if two errors may occur? Give a convincing argument.

A usual way to encrypt messages written in English is to define a permutation on letters, e., a bijection φ from {a, . . . , z} onto {a, . . . , z} and then, encrypt a word a₁ . . . a_p with φ(a₁) . . . φ(a_p).
- [(K,M,P,E)=(1,0,2,1)] Justify that, if φ is a bijection, then this encryption defines a bijection from {a, . . . , z}∗ onto {a, . . . , z}∗.

A usual way to define φ is to number letters from 0 to 25 (0 for a, 25 for z) and use a bijection ϕ : {0, . . . , 25} −→ {0, . . . , 25} so that we can use operations between numbers. Then, the image of the ith letter is the letter number ϕ(i).

We remind that, for two integers, a, b, b > 0, a mod b is the reminder of the division of

a by b defined by the two following conditions:

c = a mod b 0 ≤ c ≤ b − 1

a ≡ c(mod b)

(b) [(K,M,P,E)=(2,2,2,0)] We define ϕ : {0, . . . , 25} −→ {0, . . . , 25}

x ›→ 17x + 9 mod 26

Let x, y ∈ {0, . . . , 25} such that ϕ(x) = ϕ(y). Show, using Gauss’ Theorem (See exercice 2, practical Week 2) that 26 is a factor of |x − y| and conclude that ϕ is injective.

[(K,M,P,E)=(1,0,2,0)] Deduce from the previous question that ϕ is
This question aims at determining the inverse of ϕ, which will give us the a method for decoding a
- [(K,M,P,E)=(2,2,0,0)] Determine gcd(17, 26) using the Euclidean algorithm and determine two integers (λ, µ) such that λ × 17 + µ × 26 = 1 and deduce that

17 × λ ≡ 1(mod 26) Show all steps of your working on your answer sheet.

(ii) [(K,M,P,E)=(2,2,2,0)] Show that

ψ : {0, . . . , 25} −→ {0, . . . , 25}

y λ (y 9) mod 26 is the inverse of ϕ

We recall you need to show ϕ ◦ ψ = ψ ◦ ϕ = Id, where Id denotes the identity on

{0, . . . , 25} −→ {0, . . . , 25}. We recommend using the result of Exercise 5, practical Week 2.

(iii) [(K,M,P,E)=(0,3,0,1)] Use ψ to decode the message “ipdrmzuz fjuy pd ldzqlo qnm rmbeun”.

You can use a computer program, Excel or by hand calculation. In all cases, please explain your method, show your working and upload the related file if you use a computer bases tool.

(a) [(K,M,P,E)=(1,1,0,0)]Write down the set Cyber of letters in the word “cybersecurity” and the set Crypto of letters in the word “cryptography” as lists of elements separated by commas and enclosed by braces {. . .}.

[(K,M,P,E)=(2,1,0,0)] Write down the symmetric difference Cyber∆Crypto as a list of elements separated by commas and enclosed by
[(K,M,P,E)=(1,0,0,1)]In which sense can we say that these two words have the same number of letters? Answer with a full

In what follows, an (non-directed) graph has at most one edge between every two vertices (no multi-edge) while an (undirected) multigraph may have several edges between two vertices (multi-edge). A loop is an edge between one vertex and itself (both extremities are identical). A simple graph is a graph without loop. For the following questions, you can use for instance https://graphonline.ru/en/ to draw graphs or multigraphs.

Consider the following degree sequence: {6, 5, 4, 2, 2, 2, 1}.
- [(K,M,P,E)=(1,2,2,1)] Is it possible to sketch a simple graph that has this degree sequence? If yes, sketch the graph. If not, give a convincing argument it is not possible. We recommend to first establish the number of vertices and edges of such a graph, if it
- [(K,M,P,E)=(1,2,2,1)] Is it possible to sketch a multigraph without loop that has this degree sequence? If yes, sketch the multigraph. If not, give a convincing argument it is not

For any subset A ⊂ {1, . . . , 17}, we define N_A the simple graph on vertices {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} such that two different vertices are linked by an edge if the sum of their labels belongs to
A. When drawing the graph N_A, we label/weight each edge with the sum of the labels of its

[(K,M,P,E)=(1,2,0,1)]Draw the graphs N{9} and then N{9,13}. How many connected components do they have?
[(K,M,P,E)=(1,2,2,1)] Draw the graph N{8,9,13}; is it Eulerian? Provide a convincing argument and if it is Eulerian, then describe an Eulerian walk as a list of

[(K,M,P,E)=(2,2,0,2)] Draw the graphs N{8,9,13,15}; is it Eulerian? Provide a convinc- ing argument and if it is Eulerian, then describe an Eulerian walk as a list of vertices.
[(K,M,P,E)=(1,1,2,0)] Find a set A ⊂ {1, . . . , 17} such that N_A is the complete graph on {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
[(K,M,P,E)=(1,2,2,1)] Draw the graph N{4,8,10} and give a convincing argument whether it is bipartite or not (see Exercise 6, practical Week 7 for details about bi- partite graphs).