• Ei tuloksia

582421 Randomised algorithms (Autumn 2005) Course examination, 12 December, 9:00{12:00, lecture hall B123

N/A
N/A
Info
Lataa
Protected

Academic year: 2022

Jaa "582421 Randomised algorithms (Autumn 2005) Course examination, 12 December, 9:00{12:00, lecture hall B123"

Copied!
1
0
0

Ladataan.... (näytä koko teksti nyt)

Lataa nyt ( 1 sivua )

Kokoteksti

(1)

582421 Randomised algorithms (Autumn 2005)

Course examination, 12 December, 9:00{12:00, lecture hall B123

1. Let C(n) be the probability that a random graph Gn;p includes a triangle (a clique of size 3), when p = f(n).

(a) Show that if f(n) = o(1=n), then limn!1C(n) = 0.

(b) Show that if f(n) = !(1=n), then limn!1C(n) = 1.

2. A process sends two service requests simultaneously, one to server A and one to server B. The reply time of server A is exponentially distributed with parameter and the reply time of server B exponentially distributed with parameter , and the reply times are independent. What is the expected time until both A and B have replied?

3. Remember that a vertex cover of a graph G = (V; E) is any set I V such that f u; v g \ I 6= ; for all (u; v) 2 E. Construct a Markov chain that has as its unique stationary distribution the uniform distribution over all the vertex covers of a given graph. Use results known from the course to demonstrate that your chain does have the desired property.

Maximum score 8 + 8 + 8 = 24.

P.S. Please remember to ll in the course feedback questionnaire on the web!

(Sama suomeksi kaantopuolella.)

Viittaukset

Lataa nyt ( PDF - 1 sivua - 57.61 KB )

LIITTYVÄT TIEDOSTOT

582691 Randomized Algorithms I

The purpose of all this is that combined with a random input graph, at any given time each vertex v ∈ V has the same probability of becoming the... Additionally, we assume that

582421 Satunnaisalgoritmit (syksy 2005) 1. välikoe 17.10. kello 9-12 sali B123

Tarkastellaan tuttua tilannetta, jossa n palloa sijoitetaan n lokeroon toisistaan riippumatta siten, että kunkin pallon todennäköisyys tulla kuhunkin lokeroon on sama.. Ajatellaan

582421 Randomised algorithms (Autumn 2005) Midterm examination, 17 October, 9:00{12:00, lecture hall B123

Consider the familiar situation where n balls are distributed independently and uniformly at random into n bins.. Suppose now that each bin can hold only

582421 Satunnaisalgoritmit (syksy 2005) 2. välikoe 12.12. kello 9-12 sali B123

Muodosta Markovin ketju, jonka yksikäsitteinen tasapainojakauma on tasainen ja- kauma annetun verkon kaikkien solmupeitteiden joukossa3. Muistathan

Bayesian Inference for Retrospective Population Genetics Models Using Markov Chain Monte Carlo Methods

The posterior distribution of the unobserved history of the individuals is studied conditionally on the observed marker data by using a Markov chain Monte Carlo algorithm (MCMC)..

Examination 15.12.2020 (remote examination using My Course)

A precondition for the participation in the examination is the fulfilment of compulsory parts of the course in the autumn 2020 or earlier?. The unbonded tendon along the centerline

1t of

(c) It has been shown in the course that if K is a nonempty convex and closed subset of a Hilbert space, then for every given point there exists a unique closest point in

ON APPROXIMATIONS OF DIFFUSIONS WITH EQUILIBRIUM

The top- ics of the course are: ”simple” Markov diffusions in R d with equilibrium or stationary measures; recurrence properties and convergence to a stationary measure; ”strong”