• Non ci sono risultati.

Algorithm Engineering 12 June 2020 – time 30 minutes

N/A
N/A
Info
Scarica
Protected

Academic year: 2021

Condividi "Algorithm Engineering 12 June 2020 – time 30 minutes"

Copied!
1
0
0

Caricamento.... (Visualizza il testo completo ora)

Scarica adesso ( 1 pagine )

Testo completo

(1)

Algorithm Engineering

12 June 2020 – time 30 minutes

Question #1. Let us be given the following symbols and probabilities: p(a) = 1/4, p(b)=1/4, p(c) = 1/2. Compress the text “AC” via Arithmetic coding, using ratios to make computations, and emitting the final sequence of bits.

Question #2. You are given the graph below, in which the bold edges {(A,B), (A,C)}

are the ones already inserted in the MST under construction.

• Which is the next edge inserted in the MST by Kruskal’s algorithm

• Which is the next edge inserted in the MST by Prim’s algorithm Please motivate the two answers.

Question #3. Given the suffix tree of a string T[1,n], how do you compute the longest substring of T which occurs at least L times? What is the time complexity of the proposed algorithm in function of n?

Question #4. Show the first 3 codewords of the (s,c)-code with s=1 and c=3, hence s+c = 4 = 22 (comment your calculations).

Riferimenti

Scarica adesso ( PDF - 1 pagine - 74.93 KB )

Documenti correlati

RCP steady state operating configurations are given in the following of the paragraph.

when temperature is lower than **** some of the RIS/RRA trains are called in operation and correspondingly reactor primary pumps **** are shutdown; when temperature is lower

Let a(n, k) be the number of walks which start at the origin and on step n are, for the first time, k steps below its maximum-so-far

Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit` a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy. Let a(n, k) be the number

Determine the combined total Fnof the number of (nondegenerate) triangles and rectangles for which all edges are subsets of Gn

Let G n be the union of all closed line segments joining any two elements of [n] × [n] along a vertical or horizontal line, or along a line with

The better you know, the better you make your choice. The need for a scientific citizenship in the era of knowledge

An extremely naïve assumption has crumbled before our eyes: some used to believe science communication was a transfer of information between those who know (scientists) and those

The better you know, the better you make your choice. The need for a scientific citizenship in the era of knowledge

La scienza – e la tecnologia che della scienza è, insieme, figlia e madre – sono sempre più elementi essenziali della nostra vita, in ogni e ciascuna delle sue

The following text is a post-print (ie final draft post-refereeing) version of the article which differs from the publisher’s version.

7b, we notice that the data of energy spacing between replicas in the 1.71 eV sideband of different samples (from the analysis of spectra in Fig. 5) show differences that follow

The following text is a post-print (ie final draft post-refereeing) version of the article which differs from the publisher’s version.

(c) Example of decay fitting measured in correspondence of the valley visible in (a) and (b) at an excitation wavelength of 254 nm and emission wavelength at 460 nm.

Two applications of the results are given

Moreover, the Monge–Amp`ere equations, written under the form of first order systems of PDE’s, can be reduced to linear form by means of invertible point transformations suggested