Thore Husfeldt

Archive for the ‘Uncategorized’ Category

Orthogonal Vectors to Perl Regex

leave a comment »

The Orthogonal Vectors problem is given two sets of d-dimensional 01-vectors to decide if there is an orthogonal pair: two vectors, one from each set, with zero dot product. Obviously, the problem can be decided in time O(n2d) by trying all pairs.

Here’s the a complete reduction from the Orthogonal Vectors problem to evaluation of Perl regular expressions.

chomp($_ = <STDIN>);
s/0/\\d/g;
tr/1 /0|/;
print !!(<STDIN> =~ /$_/)

This is fully functional Perl code. Save the script as ov.pl and run it. The process expects two lines on standard input, each describing a set of vectors (as 01-sequences, separated by space). The script returns “1” if and only if the two sets contain an orthogonal pair of vectors.

>perl ov.pl
1000 0100 0010 1001
1110 1101 1111 1100^D
1

This construction shows that matching an n-character string against an n-character regular expression requires quadratic time under the Strong Exponential Time Hypothesis. So, the obvious quadratic-time dynamic programming algorithm for regex matching is in some sense optimal.

As to the Perl code, the first line eats the trailing newline of standard input. The next two lines contain the main part of the reduction, replacing “0” by “\d” (any digit), “1” by “0”, and “ ” by “|” to build a regex. The last line of the code attempts to match the second line from standard input to the regex. Oh, the double exclamation points? They are a perlism to enforce Boolean context, so that the output is “1” (true) exactly if the regex matches. The reduction is so obviously linear that it hurts.

Tell me this isn’t cute.

The core of the construction underlies the celebrated recent results of Backus and Indyk, Bringmann and Künnemann, and Abboud et al. that show similar bounds for various string edit distances. This particular example is just very concrete version of the NFA-acceptance reduction that appears on Karl Bringmann and Sebastian Krinninger’s slides for an MPI course on Complexity Theory of Polynomial-Time Problems (Summer 2016), there attributed to Russell Impagliazzo. I find that reduction very teachable. The step from NFA acceptance to a concrete Perl script is minimal, but makes it even more concrete (executable code!).

  • Amir Abboud, Arturs Backurs, Virginia Vassilevska Williams: Tight Hardness Results for LCS and Other Sequence Similarity Measures. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pp. 59-78.
  • Arturs Backurs, Piotr Indyk: Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false). Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015. pp. 51-58.
  • Karl Bringmann, Marvin Künnemann: Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping. IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. pp. 79-97.

Written by thorehusfeldt

October 10, 2016 at 20:28

Posted in Uncategorized

Hard Problems and How To Figure Them Out

leave a comment »

Explained using only the ten hundred words people use most often.

What is a good way of figuring out a problem?

First: it must be so simple and clear that we can explain it to a computer. (Or a Human. That’s not so different.)

Second: it must be fast enough so that it is done before lunch. (Or before the sun burns out. that’s not so different.)

Since people started using computers, lots of people get paid to think about ways to figure out problems. that’s what i’m doing.  Today we understand that some problems are hard, and others are pretty easy.

I want to help us becoming better at talking about what makes a problem hard.

So far, most of the people who think about this stuff look only at the size of the problem.

But some of us feel that you can think more clearly about problems when you not only look at their size, but at some other things as well. Sometimes, this way of thinking even helps us to come up with better ways to figure out problems!

 

small1.png

small2.pngsmall3.png

Two other people and myself have come up with a way to finish the game for all five-letter words — as long as you are forced to visit only around ten words. Or maybe twenty. So we found out that the number of words all-in-all was not so important. instead, what makes the problem hard is how many you are forced to visit. We can even find the shortest such path!

small4.png

Read more here: Another man, myself, and a woman, ‘Shortest path through stuff you didn’t choose’, place where people who care about this kind of question meet each year (the name sounds like a soft drink),  year twenty-hundred and ten and two.


Appendix

The above is a summary of a poster I made for a research sharing day at ITU.

hard-problems-poster (draft) in pdf (designed for printing in A0)

I loathe poster sessions, partly because of the unclear concept of who the audience is, and mainly because the social interaction exhausts me.

But to motivate me I gave myself the challenge to design a poster in the style of  Randall Munroe’s Up-Goer Five: Use only the 1000 most used words of English, be concrete, whimsical, accessible, and informative. Munroe has since made a whole book in this style: Thing Explainer, which is quite lovely.

I did the whole thing in Omnigraffle Professional 5, which is hard pressed to handle a document with almost 6000 elements. Drawings are free-hand in Keynote (basically because I don’t have a good way of digitising my free-hand drawings — I am a competent artist, but Munroe’s style is sufficiently simple.) The font is xkcd-font from the iPython project, licensed under CCANC 3.0.

As a starting point I used a 2012 paper of Andreas, Nina, and myself that presents an efficient FPT-algorithm for shortest Steiner cycle. That’s as accessible a result as I have. The big drawing at the end shows a path from TEARS to SMILE passing through seven intervening emotions (WORRY, SPITE, etc.) This is a highly nontrivial result and a cute story that I’m insanely happy with, I haven’t found a good way of expressing this fact in only 1000 words.

Andreas Björklund, Thore Husfeldt, and Nina Taslaman, Shortest cycle through specified elements, Proceedings of the twenty-third annual ACM-SIAM symposium on Discrete Algorithms (SODA 2012),  January 17–19, 2012, Kyoto, Japan, SIAM, pages 1747-1753. [PDF].

Written by thorehusfeldt

October 9, 2016 at 10:11

Posted in Uncategorized

Løsning til nr. 32

leave a comment »

Løsning til min danske kryptokryds nr. 32

Definitioner er understregede.
* angiver omkastning, < angiver omvending.

Vandret

2 Retsforfølge og lede efter vrøvl igen. (7)
SAGSØGE. SØGE (=lede) efter GAS (vrøvl) retur (=igen)

7 Lyd fra endetarm i avlssvin. (4)
MIAV. Gemt i endetarMIAVlssvin

10 Anret sumak-arrangement fra vestafrikansk land. (10)
MAURETANSK. ANRETSUMAK*

11 To kilo i vinen gør beruset. (7)
DRUKKET. KK (to kilo) i DRUEN

13 Afsætning af glas går tilbage. (4)
SALG. GLAS<

14 Propagere for EU? Bed DR om skrivelse. (7)
UDBREDE. EUBEDDR*

15 Stagnation i Liechtenstein er tidsbegrænset. (6)
INTERTI. liechtensteINERTIdsbregrænset

16 Lige fra regnvejr til robåd. (4)
ENER. Hvert andet bogstav fra REGNVEJR

17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
SKABELSEN. S(vovl) + KABEL + SEN

21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
PIRATERI. VIPIRATER*

25 Storme fra gale aser. (4)
RASE. ASER*.

27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
RUBATO. TUBA* i (afbryder) RO (stilhed).

29 Gøre hastværk når man restaurerer voliere. (7)
OVERILE. VOLIERE*

30 Dyr fadæse leverer indhold. (4)
ÆSEL. fadÆSELeverer

31 Var fx Finland under den kolde krig et område med god akustik? (7)
LYDLAND. Kryptisk definition, indikeret ved “?”.

32 Besvær i knoglerne, de er slemt betændte! (10)
LEDSMERTER. DEERSLEMT*

33 Klokken er forkert. (4)
URET. Dobbelt definition.

34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)
ANKENDE. DEKANEN*.

Lodret

1 Gid prishop skaber en vred kunde, fx. (10)
HIDSIGPROP. GIDPRISHOP*

2 Svagt fra sangerinder fra sjællandsk akademi. (7)
SORANER. SOPRANER uden P (“svagt”).

3 At mule over magisk smykke. (6)
AMULET. ATMULE*.

4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
SUKAT. SU + KAT.

5 Finde på nyt navn til agenda: køber flås. (7)
GENDØBE. aGENDa kØBEr flået (dvs. uden det yderste lag.)

6 Opret selvstændighedsbevægelse og Belgien griner. (7)
ETABLER. ETA + B + LER.

7 Malker forbløffende fisk. (6)
MAKREL. MALKER*

8 Medrivende og ophidsende tennis. (6)
INTENS. TENNIS*.

9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
ASEDE. AEDE omkring S.

12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
JERNHOLDIG. DEJLIG* omkring HORN*

18 Hinduistisk princip om kulde og udstråling. (7)
KARISMA. KARMA om IS.

19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
ATOLLEN. ALEN omkring LOT<

20 To gange en tønde efter aftale. (7)
ENTENTE. EN T(ønde) (to gange) E(efter)

22 Denise, efter et par øl, forbliver meget kølig. (6)
ISENDE. DENISE*

23 Vitser om Puccini, fx. (6)
VERIST. VITSER*.

24 Hård på den gamle måde, indeholder lille risiko. (6)
HASARD. HAARD omkring S (small)

26 Fiskerihavn erhverver delvist skaller. (5)
AVNER. fiskerihAVNERhverver

28 Syntes at nogen fortjente grundtemaets kerne. (5)
UNDTE. grUNDTEmaets.

Written by thorehusfeldt

May 27, 2016 at 18:37

Posted in Uncategorized

Lyd fra endetarm i avlssvin (4)

leave a comment »

no28

Mit fjerde forsøg på en dansk kryptisk krydsogtværs i den engelske »bjælkede« stil. Nogle nøgler er udmærkede, andre lidt kluntede.

Som PDF: no32.  Løsning til nr. 32

Vandret
2 Retsforfølge og lede efter vrøvl igen. (7)
7 Lyd fra endetarm i avlssvin. (4)
10 Anret sumak-arrangement fra vestafrikansk land. (10)
11 To kilo i vinen gør beruset. (7)
13 Afsætning af glas går tilbage. (4)
14 Propagere for EU? Bed DR om skrivelse. (7)
15 Stagnation i Liechtenstein er tidsbegrænset. (6)
16 Lige fra regnvejr til robåd. (4)
17 Svovl-ledning har forskinket hvad der blev afsat seks dage til. (9)
21 Vi pirater til søs, hvor offentlighed er uønsket. (9)
25 Storme fra gale aser. (4)
27 Skinger tuba afbryder stilhed uden at holde tempoet. (6)
29 Gøre hastværk når man restaurerer voliere. (7)
30 Dyr fadæse leverer indhold. (4)
31 Var fx Finland under den kolde krig et område med god akustik? (7)
32 Besvær i knoglerne, de er slemt betændte! (10)
33 Klokken er forkert. (4)
34 Dekanen, efter omorganisation, er den, der genoptager sagen. (7)

Lodret
1 Gid prishop skaber en vred kunde, fx. (10)
2 Svagt fra sangerinder fra sjællandsk akademi. (7)
3 At mule over magisk smykke. (6)
4 Overførselsindkomst til husdyr i form af tørret frugt. (5)
5 Finde på nyt navn til agenda: køber flås. (7)
6 Opret selvstændighedsbevægelse og Belgien griner. (7)
7 Malker forbløffende fisk. (6)
8 Medrivende og ophidsende tennis. (6)
9 Gav kærtegn, omkring et sekund, men anstrengte sig. (5)
12 Dejlig forvirret om skingert horn er lavet stål, fx. (10)
18 Hinduistisk princip om kulde og udstråling. (7)
19 Lot vendte sig godt en halv meter omkring for at se øen. (7)
20 To gange en tønde efter aftale. (7)
22 Denise, efter et par øl, forbliver meget kølig. (6)
23 Vitser om Puccini, fx. (6)
24 Hård på den gamle måde, indeholder lille risiko. (6)
26 Fiskerihavn erhverver delvist skaller. (5)
28 Syntes at nogen fortjente grundtemaets kerne. (5)

Written by thorehusfeldt

May 27, 2016 at 18:14

Posted in Uncategorized

English statistician is positive to a degree (5)

leave a comment »

The occasion of this cryptic crossword was the workshop Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms (Nov. 2 – Nov. 6, 2015, Simons Institute for the Theory of Computing, Berkeley, California, United States) that I had the pleasure of co-organising.

The grid is a bit more difficult than usual, with several entries less than 50% checked, and two 15-letter words. Some of the clues (and jokes) make little sense if you’re not the in target group of theoretical computer scientists.

no33

Across

9 School on a graph isomorphism base. (9)
10 Who does the grading in Greek? (5)
11 Maybe a forest is better. (7)
12 Bizarre airlines ignoring N. Alon, say. (7)
13 Indian author of assumption about finding 14 across fast. (4)
14 Idiot workers take gin cocktail to first job. (10)
16 They fight to restore Rosamond’s section. (7)
17 Matrix transform vanishes when v → 0. (7)
19 Circuit complexity, typically, sounds like a religious habit (10)
22 Father of parameterised and polynomial-space algorithms, originally. (4)
24 Two-player game about encrypted mail token. (7)
25 Free variable turns leading proof assistant around. (7)
26 Additional seconds of Keynote experiments stymie brilliant talk. (5)
27 Compute |AB| as |A| + |B| like Dracula’s former girlfriend? (9)

Down

1 Maybe 20 down is a hammer made of carbon fibre? (9,6)
2 Beethoven wrote one functor in homological algebra; maybe addition. (8)
3 English statistician is positive to a degree. (5)
4 Introduces P.I.T. problem in linearly independent sets. (8)
5 Family of degree |C|. (6)
6 Tree decompostion of Sat is near. (4,5)
7 Letters from Nerode let Erdös blank out. (6)
8 Laugh at an optimal hint solving a problem. (11,4)
15 Maybe a2 + b2 + c2 challenge keeps Naor up. (9)
17 Optimal scheduler spent day and performed many tasks. (8)
18 Where identity is unique, altogether. (2,1,5)
20 More than 64 kilobyte Nintendo retro characters. (6)
21 Neglected flow algorithm starts confusingly. (6)
23 Threaten unruly spy with hierarchy. (5)

Annotated solution

Written by thorehusfeldt

January 11, 2016 at 20:05

Posted in Uncategorized

Løsning til nr. 31

leave a comment »

Løsning til kryptokryds nr. 31.

Vandret

2 Småfed kvinde, travlt besat.
KVABSET (=småfed)
Ordspil: KV (fork. for kvinde), anagram (travlt) av BESAT

7 Drej knækket krus. (4)
SKRU (= drej)
Ordspil: anagram (drej) af KRUS

10 Tilpasning af dato: Patina ændres. (10)
ADAPTATION ( = tilpasning)
Ordspil: anagram (ændring) af DATOPATINA

11 Anarkistisk junta tilbageholder strøm d. 24. december. (7)
JULENAT (= d. 24. december)
Ordspil: Anagram (anarkistisk) af JUNTA  omkring LE (strøm “el”, omvendt)

13 Atter skjult i lykkelig ensomhed. (4)
IGEN (= atter)
Ordspil: Skjult i lykkelIGENsomhed

14 Ungt rådyr går frem og tilbage efter plante. (7)
KIDDIKE (en plante i korsblomstfamiljen)
Ordspil: KID (ungt rådyr) + DIK (KID baglæns, ordet “går frem og tilbage”) + E (“efter”)

15 Nu ses vrede efter Cæsars første folketælling. (6)
CENSUS (= folketælling)
C (Cæsars første bogstaf) + anagram (vrede) af NU SES

16 Eremit vaskede spejlet. (4)
ENER (= eremit)
Ordspil: RENE (= vaskede, adj.) baglæns

17 Omorganiseret natolager bruges til kommunikation. (9)
TALEORGAN (bruges til kommunikation)
Anagram (omorganiseret) af NATOLAGER

21 Oprørt generer de dem, der bestemmer. (9)
REGERENDE (= dem, der bestemmer)
Anagram af (oprørt) GENERER DE

25 En klovn tilbage til landet. (4)
IRAN (et land)
I (en) + NAR (= klovn) baglæns

27 Handles kort efter dyrket mark. (6)
AGERES ( = handles)
AGER (dyrket mark) + ES (et kort)

29 Betragt i fuglekæbe en del af skelettet. (7)
NÆSEBEN (del af skelettet)
SE (betragt) indeholdt i NÆB (fuglekæbe) + EN

30 Hvor man kan mødes omkring sagnvæsen. (4)
CAFE (hvor man kan mødes)
CA (omkring) + FE (et sagnvæsen)

31 Hvad siger det lille lam i skrift til europæer. (7)
RUMÆNER (europæer)
MÆ (hvad det lille lam siger) i RUNER (skrift)

32 Omdanne sær, opdyrket jordart. (10)
MORÆNESAND (jordart)
Anagram (opdyrket) af OMDANNESÆR

33 Angrib rent ud. (4)
ENTR (angrib)
Anagram (ud) af RENT

34 Tømt glas for hastig dukkert. (7)
DRUKKET (tømt glas)
Anagram (hastig) af DUKKERT

Lodret

1 Afvisning af smykke efter skaldyr på tog. (10)
REJICERING (= afvisning)
RING (smykke) efter IC (tog) i REJE (skaldyr)

2 Tænk nu gedens indvolde klemte. (7)
KNUGEDE (=klemte)
Indeholdt (“indvolde” af) tænKNUGEDEn

3 Slagmarken tabes i begyndelsen passivt. (6)
VALENT (= passiv)
VALEN (asernes slagmark) + T (første bogstav af “tabes”)

4 Fx zulu, beta, alfa, november, tango, uniform. (5)
BANTU (en gruppe af sprog som indeholder zulu)
B + A + N + T + U (ifølge i det internationale flyveralfabet)

5 Måske Gråbøl returnerer en frokost. (7)
ETTIDEN (frokost)
DITTE (Gråbøl) bagfra (“returnerer”) + EN

6 Julemad i kristendommen fx, den sidder fast i munden. (7)
TANDROD (sidder fast i munden)
AND (julemad) i TRO (kristendommen, fx) + D (den, fork.)

7 Station lever af større byer. (6)
STÆDER (større byer)
ST (station, fork.) + ÆDER (= lever af)

8 Se rundt om min horisont. (6)
KIMING (= horisont)
KIG (= se) omkring MIN

9 Flytte bruskfisk. (5)
ROKKE (= flytte) (en bruskfisk)

12 Åbner udstilling: Firserne er misforstået. (10)
FERNISERER = åbner udstilling
Anagram (misforstået) af FIRSERNE ER

18 Bredt stykke stof gør din barm gyngende. (7)
ARMBIND (bredt stykke stof)
Anagram (gyngende) af DINBARM

19 Organ findes og yder. (7)
LEVERER (= yder)
LEVER (organ) + ER (findes)

20 Lincoln, mellem venner, pruttede til vildt gilde. (7)
ABEFEST (vildt gilde)
ABE (Abraham Lincoln) + FES (pruttede) + T (til, fork.)

22 Gammelt ømtåleligt helium fx. (6)
GASART (helium, fx)
GA (gammelt, fork.) + SART (= ømtåleligt)

23 Bære en rådden frugt. (6)
ENEBÆR (frugt)
Anagram (rådden) af BÆRE EN

24 Promovere dansk kulturradikal uden ende. (6)
BRANDE (= promovere)
(Georg) BRANDES (dansk kulturradikal) uden sidste bogstav

26 Fornuft er mærkelig baglæns på engelsk. (5)
RÆSON (= fornuft)
SÆR (= mærkelig) baglæns + ON (på, engelsk)

28 Mesterskaber i vanvid i soveværelse fx. (5)
GEMAK (soveværelse, fx)
EM (mesterskaber) i GAK (vanvid)

Written by thorehusfeldt

July 18, 2015 at 21:07

Posted in Uncategorized

Hearthstone Algorithms Design Exercises

with 2 comments

Exam time again. I’ve tried to produce exam questions for my current algorithms design class themed after Blizzard’s collectible card game Hearthstone. For a variety of reasons I decided to abandon the idea for the exam, but the ideas are cute enough for a blog post. Here are the first three. The target audience are algorithms design students struggling with Chapters 1–8 of Kleinberg and Tardos’s Algorithms Design book (so: graph traversal, greedy, divide and conquer, dynamic programming, network flow, NP-hardness). Enjoy!

Hearthstone Basics

Each card in the game Hearthstone depicts a minion. Each minion has 3 values: Attack, Health and Cost, given as integers a, h, and c. Here’s a minion with Attack 3, Health 2, and Cost 4:

xMBCWkKf

For the purpose of these exercises, these values are unbounded, positive integers. During the game, both players have a number of minions in play. In a turn of Heartstone, the player assigns his minions to fight enemy minions. Each minion gets to target a single enemy minion, initiating a fight between the two minions. When a minion with Attack A fights a minion with Health H, the other minion’s Health is reduced to max{0,H-A}. Note that both minions fight, and each deals damage to the other, regardless of who initiated the fight. Also note that an enemy minion can be involved in many fights each turn, when it is repeatedly targeted. When a minion’s Health is reduced to 0, it is removed from play.

For each of the problems below, state which algorithmic design technique should be used, or if the problem is NP-hard. Also give the best asymptotic worst-case running time.

Cleanup

You and ZombieMage02 both have the same number of minions in play. It is your turn. Can you take them all the enemy minions in one sweep?

Input:
The enemy minions (a1,h1),…,(an,hn) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes,” if your minions can take out all enemy minions this turn. “No,” otherwise.

Tanks

TwoOrcsOneCup has two minions in play. Both completely overpowered and powerful enough to wipe out your hero when it becomes TwoOrcsOneCup’s turn again. You have n minions in play. Can you take out both minions this turn?

EPfTXn7N FmSMUX1Z

Input: The enemy minions (a1,h1),(a2,h2) ∈ N2 and your minions (a1′,h1′),…,(an′,hn′) ∈ N2

Output: “Yes” if your minions can take out both enemy minions this turn.

Charge!

Showdown time. Your hero has almost no Health left and OprahWindfury’s mage keeps pummeling you with fireballs. This has been going on for hours—time to end this! Luckily your hand is full of high-powered cards with Charge, which can attack immediately.
Get out as many of these guys as you can afford!

Input Your available mana K. The minions with Charge on your hand, (a1,h1,c1),…,(an,hn,cn) ∈ N2.

Output: The total number of Attack points you can play this round.


Cards generated using achievementgen.com

Written by thorehusfeldt

May 18, 2015 at 20:24

Posted in Uncategorized