Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MISCADA 2023/24

Advanced Algorithms

You should submit (i) one PDF document containing your answers to all the theoretical/mathematical questions, and (ii) a zip file with the various Python files and SAT instances as requested in Question 1. Please note that for each of the theoretical/mathematical questions we expect you to provide con- cise & precise answers, none of which need to be significantly longer than just a few lines worth of arguments and/or mathematical expressions.

1. In a graph G  :=  (V(G), E(G)), the size k of the largest clique that is an induced subgraph of G is known as the clique number of G.  A proper colouring of G is an assignment of colours to the vertices of G so that, if (x, y)  ∈ E(G) then x and y have distinct colours.  The chromatic number of G is the smallest number of colours such that G admits a proper colouring with these colours.  The complement G of a graph G has the same vertex set as G and edge set E(G) := {(x, y) : x, y ∈ V(G), x y, (x, y) E(G)}.

Other variants of chromatic number can be defined. For example, an acyclic colouring of G is an assignment of colours to the vertices of G that is a proper colouring but also has the property that no two of the colours induce a graph with a cycle.  A star colouring of G is an assignment of colours to the vertices of G that is a proper colouring but also has the property that no two of the colours induce a path of length three (with four vertices) or a cycle on four vertices.  A proper injective colouring of G is an assignment of colours to the vertices of G that is a proper colouring but also has the property that no two of the colours induce a path of length two (with three vertices).

The acyclic chromatic number (respectively, star chromatic number, proper injective chromatic num- ber) of G is the smallest number of colours such that G admits an acyclic colouring (respectively, star colouring, proper injective colouring) with this many colours.

(a) Give the chromatic number, acyclic chromatic number, star chromatic number and clique number for the graphs in Figures 1-3. [10 marks]

(b) Look at the files GraphR1-2024.txt to GraphR5-2024.txt where in each a (undi-  rected) graph is specified by naming the two vertices of each edge, separated by a space,  on each line. Write some code that can load the 5 graphs to some internal representation  (data structure) of Python. Write some code that takes these graphs and creates from them DIMACS SAT-instances in order to calculate the chromatic number and clique number of  these five graphs. Solve these SAT-instances in a SAT-solver of your choice in order to find  the chromatic number and clique number of the graphs. [20 marks]

(c) The problem GRAPH ACYCLIC 2-COLOURING takes as input a graph and asks whether it admits an acyclic colouring with two colours. Give an efficient algorithm for this problem [5 marks] with a justification of its efficiency [2 marks]. [7 marks]

(d) The problem GRAPH  ACYCLIC 3-COLOURING takes as input a graph and asks whether  it admits an acyclic colouring with three colours.  Give an algorithm for this problem [4  marks]. Is it efficient? [3 marks] [7 marks]

(e) How would you modify your code from part (b) to find the independence number instead of the clique number? [6 marks]

2. Consider the experiment where you throw an unbiased twenty-faced die and take the value on the top face.

(a) Let A be the event that the die lands face up with 1 or 11 or 12. Let B be the event that the die lands face up with an even number. What is the probability P(A|B)? [4 marks] (b) Define two random variables X and Y as follows.  Let X take value 1 if the output is  {1, 2, 3, 4, 5}, 2 if the output is {6, 7, 8, 9, 10}, 3 if the output is {11, 12, 13, 14, 15}, and 4 if the output is {16, 17, 18, 19, 20}. Let Y take value 1 if the output is an even number and 2 if the output is an odd number. Are X and Y independent random variables or not? Justify your answer. [8 marks]

3. You discover a strange machine that was programmed to always pay out money whenever it is used. Each time you use it, it simulates the throwing of two unbiased six-faced dice and takes the values on their top faces.

(a) The payout of the machine is determined based on three “bets” .  First bet:  if both dice show even numbers, you get 10 pounds, else you get 1 pound. Second bet: if the first die shows one of {2, 4} and the second die shows one of {4, 6}, you get 40 pounds, else you get 2 pounds. Third bet: if the first die shows an even number and the second die shows an odd number, you get 3 pounds, else you get 7 pounds.  Let X be the random variable  that denotes the payout you get from the machine. What is E[X]? [8 marks] (b) For the random variable X defined in the previous part, prove that P(X ≥ 25) ≤ 0.7 using one of Markov’s inequality, Chebyshev’s inequality, and the generic Chernoff bound.  [6  marks] Which inequality/bound of Markov’s inequality, Chebyshev’s inequality, and the  generic Chernoff bound did you use to show this [2 marks] and explain for each of the  other two, why you did not use them [4 marks]? Prove that the conditions, if any, that are required to use the inequality/bound you used are satisfied. [6 marks] [18 marks]

4. You are given a deck of 52 unique playing cards that are stacked in some arbitrary manner. Now, the following process is performed on the stack of cards.  In every round, starting from round 1, the following two step process is performed. Step 1: one card is chosen uniformly at random from the (entire) deck and moved to the bottom of the deck. Step 2: the bottom card is moved to the top of the deck. Let Xi  be the permutation of cards taken from top to bottom at the beginning of round i and let the state space be every possible permutation of the cards in a stack. The states (Xi)i ∈Z+  represent a Markov chain.

(a) Is the Markov chain irreducible? Prove your answer. [6 marks]

(b) The following question depends on your answer to the previous one:

If the Markov chain is irreducible, then is the Markov chain aperiodic? Justify your answer. [6 marks]

If the Markov chain is not irreducible, then give the largest subset of the state space over which the chain is irreducible.  [2 marks] For this subset of the state space, is the Markov chain aperiodic? Justify your answer. [4 marks] [6 marks]

Total marks: 100