Resedagbok 5: Utanför Melbourne

Halva tiden på andra sidan jorden är nu över. Kan inte påstå att tiden skulle ha gått speciellt snabbt eller långsamt. Jag har definitivt inte tråkigt, men det känns nog som om det börjar vara en lång tid sen jag for från Helsingfors.

Den här veckan var troligtvis den roligaste veckan hittills under resan, jag arbeta lite (mycket) mindre än vanligt för att kunna umgås med Chride så mycket som möjligt. Dock så började veckan istället med min anda “date” med Fannys pappa på måndagen. Han hade nämligen lovat låna både bil för onsdag-torsdag samt campingsaker för uppkommande campingresan. Dessutom bjöd han på mat under båda gångerna som vi träffats för att diskutera detaljerna. Definitivt mycket mer generöst än vad jag förvänta mig, jag är mycket tacksam!

På tisdagen var vi och äta till Naked For Satan. Jag hade inte varit dit själv, men fåt rekommendationer av flatmates i  stil med “lite dyrt men super bra utsikt”. Det visade sig att kommentarerna om utsikten stämde och “lite dyr” betyder “ca finsk restaurangpris”. I allmänhet är att äta ute i Melbourne lite förmånligare än i Finland, men inte jättebilligt. En biff eller dagens fisk på en ganska trevlig restaurang kostar ca 20€ o för en 10a får man ganska bra asiatisk mat.

Onsdag-Torsdag var det dags sen för “veckans höjdpunkt”. Vi åkte iväg på onsdag eftermiddag mot Mornington Peninsula med Fannys pappas bil. Första gången någonsin som jag körde i vänstertrafik och dessutom med en manuellt växlad bil. Vetenskapsmannen i mig tyckte om att analysera vad exakt det var som var svårt med vänstertrafik + manuella växlar. Det kanske enskilt svåraste var att träna musklerna till att blinka med högra handen, det var fler än en gång som jag slog på vindrutetorkarna då jag mena blinka. I stora drag var det dock inga problem med körande, märkte dock att hastighetsbegränsningarna här borta är jättehöga. Det fanns väldigt många vägar där jag helt enkelt inte vågade köra enligt hastighetsbegränsningen, något som händer ganska sällan i Finland. På onsdagen körde vi ganska rakt till Mornington, sökte upp vår AirBnB och for sen och äta på lokala seafood stället. Det var på vägen hem från den middagen som vi bestämde oss att ordna bröllop på sensommarn/tidiga hösten 2020. Jag tänkte inte använda den här plattformen till att diskutera förlovningen destumer. Kan dock nämna att de (tillfälliga) ringarna som syns på bilden på fb har Star Wars tema. Den mest intresserade läsaren kan fundera på vad det står på min ring om det står “I love you” på Chrides.

Torsdagen spenderade vi med att undersöka Mornington i mer detalj. Vi var till Arthur Seat, en naturpark med en gondola hiss som man kunde ta upp på berget. Där såg vi bl.a. en massa fåglar samt några kengurun. Efter noggranna (och ofrivilliga) undersökningar av Addo kom det dock fram att jag inte lyckades få någon vettig bild av kenguruna :(, kanske Chride har en som jag kan sätta me senare.  Efter Arthurs var vi och äta på en vingård samt och utforska Sorento, staden/byn som ligger längst ut på udden. Mycket roligt att komma lite ut från stan och se andra områden, speciellt som Fannys pappa kom och mötte oss vid utkanterna av Melbourne så jag slapp köra riktigt i centrum av “storstan”.

På fredagen for Chride tillbaka mot Helsingfors, något som nu kanske inte direkt var sådär jättekul. Efter en timme eller så av #chrideavskedsblues så var det dock dags för nästa äventyr. Detta veckoslut är det nämligen Melbourne Cup, en jättestor hästtävling som så gott som alla i Melbourne firar på något sätt. Eftersom de flesta tar långt veckoslut så bestämde jag mig också att ta tillfället i akt och åka till Kyoto för att hälsa på Iris. För tillfället sitter jag på tåget från Osaka till Kyoto (och redigerar texten lite en dag senare på hostellet). Fastän detta inlägg tekniskt sätt bara täcker må->fre så får ni höra om Japan först nästa vecka, denna text är väl nämligen ganska lång ren. (Men lite sneak peeks kan det finnas bland bilderna!)

 

Resedagbok 4: One down, one and a half to go

Första månaden i Melbourne är nu över och mittpunkten av hela resan närmar sig. Händelserna den här veckan går ganska naturligt att dela in i “dagarna före Chride” och “veckoslutet efter Chride”. Före Chrides ankomst på fredagen så hände det inte egentligen sådär värst mycket nytt. Jag förberedde och höll en till presentation om min egen forskning och jobbade på några artikelidéer. Den helt första idén vi hade fastna lite, men den nya verkar mer lovande.

På fredagsmorgonen landa Chride i Melbourne. Eftersom min airbnb lägenhet är lite trång för 5 människor så bor vi på hotell denna vecka, eller närmare sagt en tvåa i ett av höghusen i centrum. Lägenheten vi bor i är modernare än AirBnB:n och passar ganska bra att bo i om man är två, men jag skulle inte vilja bo här utan Chride.

På lördagen var vi till Pax, dvs. en av de största spelmässorna i världen. Det var definitivt en spännande upplevelse. För min del gick dagen ut på att gå runt, tränga sig bland folkmängderna och försöka se skymten av nya spel. Under tiden gick Chride på vettiga paneldiskussioner om  representationen av minoriteter i spel och annat dylikt. Fastän köerna för att spela något nytt var alla helt för långa, så var det ändå väldigt intressant att uppleva stämningen bland besökarna och förundra sig över satsningen på kostymerna. I slutet av dagen då köerna blivit lite kortare så kom vi åt att testa en switch och Pokken tournament (dvs. Tekken med Pokemon). Kan nog definitivt rekommendera Pax åt vem som helst som är intresserad av spel. Efter Pax gick vi en stund på min flatmates 30 årsfest och small talka med massor av olika typers läkare. Festen var trevlig, men p.g.a. en inkommande tidig morgon så stack vi iväg rätt så tidigt.

Igår (söndag) började Chrides konferens med en public event där vem som helst fick komma och se på hennes (och de andras) submissions. Tydligen så var Chrides spel ett av de få som folk kontinuerligt kom och pröva på under hela dagen, speciellt ca 10 åriga barn och deras föräldrar/morföräldrar. På kvällen for vi till St. Kilda för besöka pingvinerna.  För den som inte vet så bor den en stor koloni av dvärgpingviner ca 30 minuter från Melbournes centrum. Varje kväll kommer de in från sina jaktresor ute på havet för att mata ungarna. Att besöka kolonin är en rätt så populär turistattraktion. Biologerna som håller koll på turisterna pratade om tusentals besökare per kväll under sommaren. Det borde dock nämnas här att  80 procent av kolonin är avstängd från allmänheten och pingvinerna kan när som helst flytta sig från “turistsidan” till den lugna sidan. Sammanlagt såg vi allt från små pingvinungar som ramla ner för stenarna till äldre pingviner som… gjorde fler små pingviner. Allt som allt, en mycket lyckad kväll!

Tack vare Fannys pappas generositet så skall vi den här veckan  på en dagsresa till Mournington och Sorrento. Efter att Chride far hem på fredan så bär det för min del av till Kyoto för att träffa Iris och tydligen Fredi och Jesper också. Detta får ni höra om nästa vecka.

P.S jag har inte fått Chrides bilder ännu, kan alltså hända att det kommer några fler bilder till denna post.

Resedagbok 3: Sommaren börjar

Tredje veckan i Australien är så gott som över. Under veckan har jag märkt en viss vårfiilis på universitetet och runt omkring i stan. Åt min europeiska hjärna var det svårare än det borde vara att inse att studieåret här faktiskt håller på att ta slut. Första gången klarnade detta för mig på onsdag då vi var på lunch till en “Farmers market” vid universitet och någon sa att marketen skulle ta paus under sommarlovet, dvs. ända tills februari. Ganska synd eftersom maten var ganska god och det fanns en massa annat intressant som man skulle kunna bekanta sig med. Förutom första och sista besöket till farmers marketen innehåll veckan också andra tecken på den inkommande sommaren, på fredagen bjöd fakulteten på “end of year cocktails”. Tekniskt sett så tror jag att det handlade om ett tack åt föreläsare och andra som undervisat, men ingen verkade minda att jag var där :). Läsårets slut här fick mig att fundera på att jag på sätt och vis lever i en rytm som är olik till både Finland och Australien. O ena sidan så känns det definitivt inte som om läsåret “borde” vara slut, det var ju bara en dryg månad sen det var gulisintagning. O andra sidan så är det ju ljust o ganska varmt, så inte känns det precis som om det vore november heller. Så inte vet jag egentligen vad det är, kanske bäst att inte fundera så noggrant.

Utöver onödiga funderingar kring våren så spenderade jag veckan med  ganska mycket jobb. På tisdagen höll jag en seminariepresentation på universitet om min egen forskning. Det var ca 20 människor i publiken, lite mera än jag tänkte mig. Jag tror presentationen gick ganska bra, det var någon som skickade e-mail åt mig och bad om att få träffa mig nästa vecka för att diskutera forsknings ideér. Dessutom var det många som kom o prata under cocktailerna på fredag. Skall hålla en till presentation på Monash nästa fredag, måst bara göra sliderna först.

Det var ganska långt det jag har att säga om händelserna denna vecka. Tänkte avsluta med att berätta om resten av mina flatmates som jag nu har träffat. Förutom klättrande white hat hackern så bor jag med 3 andra människor: en läkare som jobbar med aborginaler samt ett par varav ena också är läkare och den andra studerar. Har inte egentligen stiftat närmare bekantskap med någon av dem. Läkaren som jobbar med aborginaler dök upp på en lördag och stack iväg på en till resa under 24h senare. Paret kom tillbaka från sin semester på tisdag och åkte iväg på ett bröllop på onsdagen. Nu är de dock tillbaka så kanske jag lär känna dem under nästa vecka.

Nästa vecka kommer Chride till Melbourne! Vi skall bl.a. på PAX och förhoppningsvis också ta en dagsresa utanför stan (om Fannys pappa är snäll). Förutom det så skall jag under de kommande veckorna till Kyoto för att hälsa på Iris samt på en klättrings/camppingresa till Grampians. Allt detta får ni höra om i kommande inlägg!

Resedagbok 2: Börjar bli varmt här

Andra veckan i Australien börjar närma sig sitt slut. Rubriken på posten syftar på vädret, idag var vi ute till stranden och njöt av det 28 grader varma vädret och den ca 3 km långa sandstranden. Man borde inte klaga, men måste medge att vädret idag var sådär på gränsen till för varmt. Förutom stranden så innehöll veckan jobb, klättring, flyttande, bordspel samt tuparen. Efter att ha besökt klättringsgymmet som ligger närmast universitetet (Hardrock) kunde jag avboka demonstrationen som var planerad för nästa vecka, på detta gym kan man nämligen säkra vänsterhänt också. Efter sammanlagt 3 besök under veckan så tror jag att Hardrock kommer att bli min Tapanila away from Tapanila.

Förutom klättring har jag även kommit igång med arbetet lite bättre under veckan. Det jag säkert inte har pratat om ännu är att jag jobbar då för University of Melbourne som ligger ganska centralt i stan (men störande nog 2 hållplatser utanför gratis spårazonen). Baserat på mina två veckor där så verkar universitetet gammalt och prestigefyllt, vilket för med sig små obekvämligheter som mörka rum med små fönster, små kök utan kaffemaskiner osv. Tur i oturen så jobbar jag också en dag i veckan på Monash University. Tar lite längre att komma dit (50min vs. 20 till uni) men är betydligt trevligare: modernare hus, trevligare arbetsmiljö och bättre gemenskap. Till exempel så blev jag kvar på pizza, öl och bordspel i Monash efter jobbet på torsdag. Jag var sherif i Bang och visa åt Australienarna hur man spelar Bang i Finland. Rykten om att lagen vann p.g.a. att de enda som spelat förut var sheriffen, renegaden och vicen är sen bara lögner så ni vet.

På lördagen for jag med en jobbkompis till en annan jobbkompis inflyttningsfest. Det var väldigt intressant att märka hur många av gästerna på festen, speciellt kinesiska gästerna, var helt obsessed av Finland. T.ex. så fanns det en tjej från Hong Kong som, efter att ha hört varifrån jag var, spendera hela kvällen med att med jämna mellanrum fråga frågor av mig om Finland. Tydligen är hennes största dröm i livet att få träffa julgubben i Rovaniemi. Det fanns annars också många som kände behov att dela med sig sin kunskap om Finland, oberoende av om det passade in i diskussionen eller inte. Enligt gemenskapen borde jag inte få kalla mig finne eftersom jag: 1) aldrig har sett ordentligt norrsken, 2) aldrig har sett julgubben i Lappland 3) aldrig har deltagit i mobiltelefonskastning eller 4) aldrig har isfiskat (vilket jag skulle kalla för att pilcka, men det är väl inte riktigt svenska). Underligt nog så var det ingen som tyckte att man borde kunna kasta en bumerang och spela en didgeridoo för att få kalla sig australiensk.

Det var väl ungefär det viktigaste som hänt denna vecka. För nästa vecka har jag inte så noggranna planer. Vi får se vad Australien kastar fram!

 

 

MR: Measuring difficulty

This post is one in the series explaining my research. Even though the post should be self-contained, it does make more sense in the context of the other posts in the series. (Look for the “my_research” category).

In the last post we used the following travel plan problem to discuss the differences between decision and optimization problems.

Graph

Recall that the scenario we consider is one where you are planning a round trip to visit all of the northern capitals and come back to Helsinki. The decision problem in this setting asks whether or not there exist any route that is shorter than some given bound B. This problem has a yes or no answer. In contrast, the optimization problem asks for the shortest possible route, and does not have a yes or no answer, instead the answer is a number. In this post we will investigate, how difficult these problems are  to solve.

A reasonable question to ask at this point is, how do you measure difficulty in computer science? Is there a scale that assigns a difficulty value to a problem? Can we for example say that the decision problem has difficulty 5? The short answer is: no. The longer answer is: kind of. There are several well defined classes and hierarchies of problems that allow grouping “similar” problems together. Furthermore, most researchers in the field believe that a problem higher up in the hierarchy is more difficult to solve than one lower down. However, there are many open questions related to the relationship between problem classes and difficulties, the most well known one is probably the P vs. NP problem. We will look into the hierarchy of problems in more detail in later posts.

While saying anything concrete about the difficulty of a single problem is not easy, we do have another option. We can compare two problems with each other. Lets get back to our travel planning and ask, is the decision or the optimization problem more difficult? Another way of phrasing the same question is: If we had a solution to one problem, could we use that to get a solution to the other? Lets start by assuming that we have a magic box that can find us the shortest route visiting all cities in the graph. We do not know how it works (nor do we care), we just assume that it does. With this box it is fairly easy to solve any decision problem of form “is there a route that is at most of length K” for some positive number K. We simply use the magic box to figure out if the length of the shortest route is less than K. If it is, we know that there exists a route shorter than K. If it isn’t we know that there exists no route shorter than K (since the box gave us the shortest possible route). So in this sense, the optimization problem is indeed easier than the decision problem.

How about the other way? Assume we have another magic box to which given any number K tells us if there exists a route that visits all cities and is shorter than K. Can we use this box to solve the optimization problem more efficiently? While it might at first glance seem like the answer should be no, there actually is a way. You first ask whether or not there is a route shorter than 1km. If the answer is yes, you know its the shortest possible route. If the answer is no, you then ask if there is a route of length at most 2km. Again, if the answer is yes, you know that has to be the shortest possible since you know there is no route of length 1 or shorter. You keep on going this way until your box answers yes, at which point you know you’ve found the shortest route. This is a very simple scheme, any readers familiar with computer science should have no problems coming up with improvements (and any readers not familiar with computer science that figure out improvements should consider a change of career).

So there we go. A solution to either problem can be used to solve the other one. So both are equally difficult, right? Not quite. The final point I want to consider in this post is how much extra work we needed in order to get the solution to the other problem. Given a solution to the optimization problem we do not have to do anything extra to solve the decision problems. Just use the solution method once and you can immediately solve all possible decision problems. On the other hand, given a solution method to any decision problem, you need to use it many times in order to solve the optimization problem. Even worse, the number of times you need to use your decision problem solver depends on the particular graph. For the simple scheme i described, you need to use your decision solver as many times as the length of the shortest route is. Even though the number can be decreased significantly, it will always depend on the particular graph. There is no constant number of calls that can be used to solve the optimization problem in any graph. So, as expected, the optimization problem is, in this sense, more difficult.

 

Resedagbok: Första veckan på andra sidan jorden

Innan jag for iväg på min resa var det en del av mina vänner som önska få se bilder och updates om hur resan går. Efter att ha funderat lite på hur jag skulle effektivast kunna dela med mig om upplevelserna på ett sätt som når de som är intresserade men inte behöver nå hela sociala median så bestämde jag mig för blogginlägg. Skall försöka skriva och lägga upp bilder ca 1 gång i veckan. Kommer att försöka hålla texterna ganska korta, vill man höra detaljer är det bara att fråga! Om man har berättelser från Finland så välkomnas dom också!

Nu är första veckan på andra sidan jorden över. Planet landade på tisdag morgon australiensisk tid. Min jetlaggade/trötta hjärna hade lyckats intala sig att addressen jag skulle till var 3 Eades Pl. så det blev lite fram och tillbaka yrande tills ovannämnda hjärnan gick med på att Eades Pl. inte har hus med udda siffror. Efter det dubbelkolla jag addressen, gick in i 6 Eades Pl. och hittade min säng. Jag bor på en övrevåning av en ganska stor lägenhet. Jag har en egen wc och en egen balkong. All in all, not too bad! Bor med 3 andra människor varav 2 e på semester. Han som inte är på semester är en “white hat hacker” som klättrar mycket. Stort emphasis på mycket; just nu känns det som att jag antingen kommer att bli jättebra på att klättra, eller sen typ dö innan jag kommer bort härifrån. Under veckan var jag en gång och bouldra, och en gång och top ropea, lyckades få två skavsår på högra handens lillfinger, mest p.g.a. man här måste säkra högerhänt, något mina händer inte är vana med.
Annars gick veckan åt till att bli bekant med omgivningen, ladda upp resekorte från ifjol, skaffa ett Australienskt sim kort, lösa ut arbetsrummets nyklar osv. Förutom det var jag på afterwork till en ölpub som Lasse hitta på untappd, till en biosalong som har tidsrest från 80-talet för att se en klättringsfilm, och på en bowling meetup. Under veckan hade jag t.o.m. tid o bli en del av en konstinstallation (se bilderna).

Nu börjar vecka två, planen är att jobba lite mer och testa en intressant idé som förhoppningsvis leder till publikationer. Dessutom blir det house warming party på lördag. Det får ni höra om nästa vecka!

 

 

 

MR: Deciding vs. Optimizing

For an explanation of the my_research category, please see Introducing: Explaining my research.

Having established how all problems can be solved at once I next want to discuss the limitations of this idea. To recap the last post, assume we are interested in solving a problem A but have no idea how to do so. However, we do know that there exists a fairly similar problem B to which there are many known good solution approaches. Then instead of spending time and effort on developing a solution to problem A, we instead probably should try to find an reduction from problem A to problem B. A reduction is a function that allows us to: i) see an instance of problem A as an instance of problem B and ii) use the solution to problem B to obtain a solution to problem A. In the next few posts I want to go into some more detail on reductions. Specifically I wish to discuss criteria under which we can expect reductions from A to be to exist. Not every problem can be reduced to any other problem. In my opinion there are two main factors that affect the existence of reductions, the types and complexities of the problems A and B. In this post I will discuss the main two types of problems encountered in computer science research: decision problems and optimization problems.

Consider a scenario in which you own a plane and you are planning a flying trip to visit all the northern capitals (Helsinki, Stockholm, Oslo, Copenhagen, and Reykjavik). To help you in the planning you look up the pairwise distances between the cities and construct the following “map” to help in your planning.

Graph.png

As we can see, even for a relatively small number of cities like this, the order in which you visit them can affect the length of your trip considerably. For example, travelling Helsinki -> Stockholm -> Copenhagen -> Reykjavik -> Oslo -> Helsinki results in a route that is 7399km while going Helsinki -> Copenhagen -> Oslo -> Stockholm -> Reykjavik -> Helsinki requires 8740km, that is over a thousand kilometers more travelled.

Imagine now that your plane only has enough fuel to travel 7300km. At first glance it is not clear whether or not you can visit all four other cities and get back to Helsinki while only travelling 7300km. Figuring out if you can is a decision problem, i.e. a problem with an yes or no answer. Notice that in the general case, an instance of the decision problem consists of both a graph and a bound, i.e. we are asking whether or not there exists a route in the graph that is shorter than the bound. For this instance, the answer to the decision problem: is there a route that visits all the northern capitals and is at most 7300km long?, is no. This can be verified by enumerating all 4! = 24 different routes.

Having learnt that 7300km worth of fuel will not cut it you go out and get some more. As you are cheap, you would however want to get away with using as little fuel as possible. Hence you are interested in figuring out the shortest possible route that visits all cities and returns to Helsinki. This is an optimization problem. In contrast to the decision problem, an optimization problem does not ask for an yes or no answer. Instead the answer is the length of the shortest possible route. The interested reader can use this tool to verify that the 7399km long route Helsinki -> Stockholm -> Copenhagen -> Reykjavik -> Oslo -> Helsinki is the shortest possible route.

To summarize,  a decision problem is one with an “yes or no” answer while an optimization problem asks for “the best” answer. Before ending this post I want to highlight another important difference between deciding and optimizing. Consider a situation in which you have a candidate solution to either the decision problem (is there a route shorter than some bound?) or the optimization (how long is the shortest route?). If I am looking for a route that is shorter than 7500km and you give me one, I can easily use the map to verify that the route you’ve given me is indeed shorter than 7500km. Specifically, I do not need to be able to solve the problem myself in order to verify that the solution you give me is correct.  However, if I am looking for the shortest possible route and you give me one that is 7421km long, I have no way of verifying that it is indeed the shortest one, except for solving the problem on my own (or taking your word for it). For the interested reader I will mention that the property of solutions to decision problems being easily verifiable holds even if the answer is “no”. If I am looking for a route shorter than 6000km there exists standard forms of “proof” that you could present to me in order to convince me that there does not. If you are interested in learning more you can start here.