Masteroppgaver i algoritmer

Den beste måten å finne en passende masteroppgave i algoritmer er å snakke med en av professorene eller forskerne i algoritmegruppen. Hver av oss har mange oppgaver og prosjekt på lager og vi liker også å komme frem til en oppgave sammen med masterkandidaten.

Det som kjennetegner våre masteroppgaver er at de alle har elementer av både teori og implementasjon i seg. Avhengig av kandidatens interesser, forutsetninger og bakgrunn, kan hver oppgave vris inn mot mer implementasjon eller mer teori. Mange oppgaver er rene implementasjonsoppgaver, eventuelt supplert med noen teoretiske resultater. Veldig få oppgaver ender opp som rene teorioppgaver, og da etter ønske fra kandidaten. Fordelingen av implementasjon versus teori i en masteroppgave kan også gå seg til underveis, gjennom dialog mellom kandidat og veileder.

De som har tatt mastergrad i algoritmer ved UiB har veldig raskt fått jobber ved software utviklingsbedrifter, bank og finansinstitusjoner, konsulentfirma og akademia. Noen eksempler på steder der våre nyutdannede mastere har fått jobber er: Knowit (Bergen), Webstep (Bergen), Bekk (Bergen), Fiskeridirektoratet (Bergen), Equinor (Bergen), Vizrt (Bergen), Reaktor (Bergen), Webstep (Bergen), PSWinCom (Bergen), Tobii (Bergen), Microsoft (Oslo), Pride (Stavanger), Accenture (Oslo), Nordea (Bergen), Tryg Forsikring (Bergen) og Universitetet i Bergen.

For mer detaljert liste over uteksaminerte kandidater og hvor de fikk sin første jobb kan du kikke i listene som Fredrik Manne og Pinar Heggernes oppdaterer.

Se også Group Members for nåværende og avsluttede mastergrader.

Comparing maximum flow algorithms

Student: Karina Elinborg Jonasdottir Strømmen
Veileder: Pål Grønås Drange

A faster algorithm for c-closure

Student: Tuva Kvalsøren
Veileder: Pål Grønås Drange

Parallel Community Detection in Incremental Graphs

Student: Magnus Tønnessen
Veileder: Fredrik Manne

An Algorithm for k-insertion into a Binary Heap

Veileder: Martin Vatshelle og Pål Grønås Drange
Student: Marie Natland Berg

Vaccination strategies based on graph centrality

Student: Haakon O. Benning
Veileder: Fredrik Manne

Overlapping Community Detection using Cluster Editing with Vertex Splitting

Student: Gard Askeland
Veileder: Pål Grønås Drange

Parameterized Complexity of Fair Graph Clustering

Student: Joakim H. Sunde
Veileder: Petr Golovach

Machine Teaching for Explainable AI: Proof of Concept

Student: Brigt A.T. Håvardstun
Veileder: Telle

Algorithms for rainbow vertex colouring diametral path graphs

Student: Jakob Dyrseth
Veileder: Paloma Lima

Hardness of Non-trivial Generalized Domination Problems Parameterized by Linear Mim-Width

Student: Brage I.K. Bakkane
Veileder: Lars Jaffke

Properties of locally checkable vertex partitioning problems in digraphs

Student: Petter Daae
Veileder: Telle

Analyzing Solidity smart contracts

Student: Sondre Aasemoen
Veileder: Telle

N/A

Student: Ingrid N. Johansen
Veileder: Vatshelle

Cutwidth

Cutwidth er en grafparameter som er NP-hard å beregne generelt. Det finnes til og med grafer med meget begrenset struktur hvor vi ikke vet om cutwidth kan beregnes i polynomisk tid. Vi har nylig publisert en algoritme for beregning av cutwidth i polynomisk tid dersom indata grafen er en "threshold" graf. Algoritmen er meget enkel mens korrekthetsbeviset på at den beregner cutwidth av "threshold" grafer er mer innviklet. Det er mulige veier å gå for en masteroppgave:

1. Ren implementering: implementer den enkle algoritmen og test hvordan den fungerer på andre grafer enn "threshold". Dette vil også kreve en implementering av en brute-force algoritme for cutwidth for å sammenligne resultatene. Så størrelsen på grafer man kan teste på vil avhenge hvor rask man kan få brute-force til å gå. Kan være interessante implementeringstekniske problemstillinger der.
2. Ren teori: kan vi finne kompleksiteten til cutwidth på grafklassene "trivially perfect", "interval", osv? Selv om man ikke klarer å avgjøre polynomisk vs NP-komplett, kan vi gi raskere eksponentiell-tids algoritmer for disse grafklasser enn rett-frem brute-force? Hvis dette går greit, kan man gå videre til større grafklasser også.
3. Implementering og teori blandet: man tar de elementene man liker eller får til fra 1 og 2. For eksempel: implementer algoritmen. Implementer en raskere ekponentiell-tids algoritme for intervalgrafer enn generelle grafer (det vil kreve bruk av egenskapene til intervalgrafer). Finn ut om algoritmen fra paperet kan brukes som en approksimasjonsalgoritme for cutwidth av intervallgrafer.

Man behøver ikke å bestemme seg for 1, 2, eller 3 før man setter i gang; vi kan se det an etterhvert. Andre muligheter finnes også, så man er heller ikke begrenset til 1,2,3.

Relevante kurs: INF234, INF 235, INF 237, INF 334
Veileder: Pinar Heggernes
Student: Simen Lilleeng

Minimum sykelbryting

Anta at en politimann prøver å fange en røver. Begge har hver sin bil og kjører på et veinett som kan beskrives med en graf. Politimannen må holde fartsgrensen, mens røveren er fri til å kjøre så fort han vil. Politimannen har k veisperringer som kan plasseres i veikryss, og røveren kan ikke passere politimannen uten å bli fanget. Gitt grafen(veinettet) og antallet veisperringer politimannen har til rådighet, er det mulig for politimannen å fange røveren?

Problemet over kalles Feedback Vertex Set(FVS) og har vært intensivt studert av forskere de siste 4-5 årene. Som et resultat har flere nye algoritmer blitt publisert, men ingen av de raskeste algoritmene er implementert. Oppgaven vil bestå i å implementere og teste et utvalg av disse algoritmene. En slik implementasjon vil kunne gi svar på hvilke probleminstanser det er ønskelig å bruke disse nye algoritmene. Noen av algoritmene er også godt egnet til parallelisering.

Veilder: Yngve Villanger
Student: Arvid Soldal Sivertsen

Treespan

Treespan er en grafparameter som er NP-hard å beregne. Prosjektet går ut på å finne hvor kompleksitetsgrensene går for denne parameteren. Er den fixed-paramter tractable (FPT) generelt, eller i begrensede grafklasser? Kan den beregnes i polynomisk tid for intervalgrafer eller for trær med begrenset gradtall? Er treespan det samme som bandwidth for intervalgrafer? Kan vi gi en O(n^k) algoritme der n er antall noder og k er treespan? Kan vi gi en O(c^n) algoritme der c er en ikke for stor konstant?

Veilder: Pinar Heggernes
Student: Markus S Dregi

Computing minimum fill-inn

Given a graph G, the minimum fill-inn problem asks for the minimum number of edges that can be added to G such that every cycle of length four or more contains a chord (i.e. a short-cut). This problem shows up when ordering the computations in certain linear-algebra computations. The problem is hard to solve optimally as it is known to be NP-hard. However, recently a new algorithm with a sub-exponential running time has been suggested. We wish to implement this and to test what the largest problems are that it can solve. In particular, we wish to test the algorithm on grid-graphs as these are often used in practice. Initially it is desirable to develop a sequential algorithm but it might also be possible to use parallel computers to speed up the computation.

Veilder: Fredrik Manne / Yngve Villanger
Student: Bjarte Djuvik Næss

Heuristikker for å telle antall nabolag

For å løse NP-harde grafproblemer bruker vi ofte divide-and-conquer på en tre-dekomponering av grafen med lav 'bredde'. En ny bredde-parameter innført av forskere fra UiB heter boolean-bredde og baserer seg på å telle antall nabolag som finnes over et gitt kutt i grafen. I denne oppgaven er målet å finne gode heuristiske algoritmer som raskt hjelper til å beregne antall slike nabolag, implementere disse og teste dem ut på grafer tatt fra applikasjoner.  
Veilder: Jan Arne Telle.
Student: Vithya Ganeshan

Visualisering av tre-liknende grafer

Grafer med begrenset trebredde oppstår for eksempel som kontroll-flyt-grafer av GOTO-frie programmer. Denne oppgaven går ut på å finne algoritmer for visualisering, dvs innen konteksten satt av fagfeltet 'Graph Drawing', av denne type tre-liknende grafer.
Nødvendig bakgrunn: I234 og gode programmeringskunnskaper
Andre relevante kurs: I238
Veileder: Jan Arne Telle
Student: Kristian Andersen

Konstruksjonsvarianter av dynamisk programmering

For grafer som er partielle k-trær har vi velkjente dynamisk programmering-algoritmer som raskt finner verdien av en optimal løsning for mange problemer som ellers er NP-harde, dvs av typen 'Hva er størrelsen på største uavhengige mengde noder?'. Disse algoritmene baserer seg på å løse problemet ved rå kraft for delmengder av noder av størrelse opptil k+1, og samle slike løsninger i tabeller av størrelse eksponensiellt i k. For en praktisk rask implementering er det viktig å lagre få slike tabeller samtidig, og det har blitt vist at om grafen har en underliggende tre-struktur T så holder det å lagre et antall tabeller lik stibredden til T. Oppgaven går ut på å løse konstruksjonsvarianten av disse problemene, som for eksempel 'Finn en største uavhengig mengde av noder' under begrensningen at man kun lagrer få tabeller samtidig. Dette er problematisk da man ikke kan benytte standard-algoritmen for dette som nøster seg bakover i tabellen(e) fra en optimal løsning.
Nødvendig bakgrunn: I234 og gode programmeringskunnskaper
Andre relevante kurs: I238
Veileder: Jan Arne Telle
Student: Øyvind Neuman

Analyse av rutebusstilbudet i Bergen

Utfra eksisterende rutetabeller, skal man analysere deler av rutebusstilbudet i Bergen. Blant annet skal det implementeres et program som kan hjelpe busspassasjerer ved for eksempel å liste ut hvor og når man må bytte buss. Til analyseformål er det tenkt å ta i bruk en del grafteori. Det er også ønskelig å finne ut om busstilbudet kan gjøres mer brukervennlig uten å øke kostnadene. Oppgaven kan utvides, forandres, og diskuteres etter forslag fra studenten.
Nødvendig bakgrunn: I234. I tillegg er det en fordel om man har tatt I235 og/eller I273.
Veileder: Pinar Heggernes
Student: Rune A. Wallmark

VLSI-layout vha algoritmer for grafer med begrenset tre og stibredde 

Veileder: Jan Arne Telle
Student: Frode Johannesen

A framwork for parallel graph algorithm using edge partitioning

Veileder: Fredrik Manne
Student: Martin Tofteberg
Eksamen: 2011

Disjoint-set algorithms on shared memory computers

Veileder: Fredrik Manne
Student: Peder Refsnes
Eksamen: 2010

Parallel graph coloring on the Cell-processor

Veileder: Fredrik Manne
Student: Daniele Jesus
Eksamen: 2009

Self-stabilizing algorithms for distance-k coloring

Veileder: Fredrik Manne
Student: Shuang Wang
Eksamen: 2007

Selvstabiliserende algoritmer for å vedlikeholde et utspennende tre

Strukturen til datanettverk kan forandre seg over tid og man har ikke alltid full oversikt på ett bestemt sted over hvordan nettverket ser ut. For å håndtere slike situasjoner trenger man distribuerte algoritmer. Oppgaven består i å teste ut og studere ulike distribuerte algoritmer for å vedlikeholde et utspennende tre i et nettverk.
Veileder: Fredrik Manne
Student: Bjørn Even Wahlstrøm
Eksamen: 2007

Programmer for å oppdage plagiarism

Med utbredelsen av internett har plagiarism (eller kopiering) blitt et stadig større problem innenfor utdanning. Oppgaven består i å evaluere og teste ulike program utviklet spesielt med tanke på å oppdage plagiarism innenfor data-utdanning.
Veileder: Fredrik Manne
Student: Nhat Tran
Eksamen: 2007

Out of core algorithms for connected components

Veileder: Fredrik Manne
Student: Tone Hopsdal
Eksamen: 2007

Leksikografisk bredde-først og dybde-først søk

Leksikografisk bredde-først søk (LBFS) er en algoritme for gjenkjenning av kordale grafer. Den har ønskede egenskaper som gir effektiv implementering og kan også brukes til å gjenkjenne andre grafklasser i modifiserte former. Nylig har man også definert leksikografisk dybde-først søk (LDFS) og vist at denne algoritmen kan også brukes til å gjenkjenne kordale grafer.
Oppgaven går ut på å gjennomføre en studie av LBFS og LDFS, studere tidligere og nye resultater på LBFS, formalisere definisjonen og bevise korrektheten av LDFS, og implementere disse to algoritmene så effektivt som mulig og sammenligne deres kjøretider basert på forskjellige implementasjonsteknikker. I tillegg er vi interessert i LBFS og LDFS i komplementgrafen.
Nødvendig bakgrunn: INF234, INF334
Veileder: Pinar Heggernes
Student: Audun Hegranes
Eksamen: 19. juni 2006

Tools for online testing

Veileder: Fredrik Manne
Student: Nils Martin Sande
Eksamen: 2005

Augmented Reality

Veileder: Fredrik Manne
Student: Jean-Paul Balabanian
Eksamen: 2005

Parallell gjenkjenning av kordale grafer

Vi har tre metoder for gjenkjenning av kordale grafer. Den første og raskeste er å kjøre en linær tids algoritme (som MCS) som finner en perfekt eliminasjons ordning dersom grafen er kordal. Deretter må eliminasjonsspillet kjøres på grafen med denne ordningen for å se om det blir produsert noe fyll. Dette kan også gjøres i linær tid ved hjelp av en algoritme beskrevet av Tarjan og Yannakakis i 1984. Denne metoden er sterkt sekvelsiell siden både MCS og fyllberegning prosesserer en node i hvert steg, og hva som skal skje i de neste stegene er sterkt avhengig av dette steget. En annen metode for å gjenkjenne kordale grafer er å sjekke om grafen har simplicial noder, fjerne alle slike, og se om det finnes simplicial noder i neste steg, fjerne alle slike, og fortsette til grafen er tom (kordal) eller ingen simplicial noder finnes (ikke kordal). Denne metoden kan muligens parallelliseres til en viss grad, men vi kan få grafer der det er få simplicial noder i hvert steg som gjør at vi ikke kan eliminere mer en et fåtall noder parallellt i hvert steg. Hver node i en kordal graf trenger ikke å være simplicial (det må finnes mist to), men hver node i en kordal graf må være LB-simplicial. Dette gir oss den tredje metoden for å gjenkjenne kordale grafer. En node er LB-simplicial dersom hver minimal separator som er en delmengde av nodens nabomengde er en klikk. Å finne ut dette krever en dybdeførst grafsøk for hver node, så som en sekvensiell algoritme er denne metoden ikke bra. Men, siden ALLE noder må oppfylle dette kravet, kan alle noder sjekkes samtidig, hvilket gir gode muligheter til parallellisering. En slik parallell implementasjon vil selvsagt ikke være kostoptimal for generelle grafer, men vi vil se om den kan få bedre parallell kjøretid enn den raskeste sekvensiell metode for bestemte graftyper, for eksempel nesten komplette grafer, og hvilken speedup vi kan oppnå for disse tilfellene. Dersom tid er den viktigste faktoren, og man har tilgang til rikelig med regneressurser, vil en slik implementasjon være interessant. Oppgaven går ut på å implementere disse metodene sekvensielt, og de to sistnevnte metodene parallelt, og sammenligne kjøretidene.
Nødvendig bakgrunn: I234, I236, og gode programmeringskunnskaper
Andre relevante kurs: I238
Veileder: Pinar Heggernes
Student: Lars Tore Løvtangen
Eksamen: 21. oktober 2005

Optimal linear arrangements of interval graphs

Nødvendig bakgrunn: INF234 og gode programmeringskunnskaper
Anbefalte kurs: INF334
Veileder: Fedor Fomim
Student: Thomas Watnedal
Eksamen: August 2005

Domination and packing problems on AT-free graphs

Nødvendig bakgrunn: INF234 og gode programmeringskunnskaper
Anbefalte kurs: INF334
Veileder: Fedor Fomin
Student: Helge Skjellevik
Eksamen: 9.juni 2005

Bestemme trespenn av begrensede grafklasser

Trespenn er en ny grafparameter og en generalisering av grafparameteren bandbredde. Oppgaven går ut på å studere denne parameteren nærmere og prøve å finne ut om trespenn av enkelte begrensede grafklasser kan bestemmes i polynomisk tid. Allerede for en så begrenset klasse som trær som inneholder noder av gradtall høyst 4, er det uvisst trespenn kan bestemmes effektivt.
Nødvendig bakgrunn: INF234 og gode programmeringskunnskaper
Anbefalte kurs: INF334
Veileder: Pinar Heggernes
Student: Kjetil Watnedal
Eksamen: 10. august 2005

Minimum Degree og minimale trianguleringer

Minimum Degree er en enkel heuristikk for det NP-harde problemet av å finne trianguleringer med færrest kanter. I mange tilfeller har Minimum Degree blitt observert til å gi minimale trianguleringer, og et nytt resultat forklarer en del av grunnen til dette. I samme paper gir forfatterne en ny algoritme for å finne minimale trianguleringer med utgangspunkt i Minimum Degree.
Oppgaven går ut på å implementere den nye algoritmen og se nærmere på dens kjøretid, både i teori og i praksis. I tillegg vil vil bruke algoritmen til å teste enda flere egenskaper av Minimum Degree, som for eksempel hvilke minimale separatorer som blir oppdaget og fyllt underveis.
Nødvendig bakgrunn: INF234 og gode programmeringskunnskaper
Anbefalte kurs: INF334
Veileder: Pinar Heggernes
Student: Tore Nedretvedt
Eksamen: 10. august 2005

Implementasjon av algoritmer for "broadcast domination" på ulike grafklasser

Broadcast domination er en nyere introdusert variant av dominating set i grafer. Målet er å tildele hver node v en størrelse f(v) slik at alle noder u i grafen med f(u)=0 har distanse f(v) til en eller annen node v. Det vil si at noder v med f(v)>0 dominerer seg selv og de nodene som ligger i distanse f(v) fra v. Alle noder må bli dominert og målet er å minimere summen av f(v) for alle v.
Det er uvisst om broadcast domination er NP-hardt på generelle grafer. Det har blitt introdusert algoritmer på intervalgrafer, trær og serie-parallelle grafer.
Oppgaven går ut på å implementere disse algoritmene og å prøve å finne flere klasser av grafer som kan ha polynomisk tids broadcast domination algoritmer.
Nødvendig bakgrunn: I234 og gode programmeringskunnskaper
Anbefalte kurs: I238
Veileder: Pinar Heggernes
Student: Helge Holm
Eksamen: 31. januar 2005

Implementasjon av en ny algoritme for minimal triangulering

Et viktig og velstudert problem innen graftalgoritmer er å gjøre en gitt graf kordal ved å legge til nødvendige kanter. En graf er kordal dersom enhver sykel av lengde > 3 har en korde, dvs en kant som krysser over sykelen. Minimeringsproblemet, å finne en kordal overgraf av en gitt graf med færrest mulig kanter, er NP-hardt. Dette vanskelige problemet kalles også minimum triangulering. Et nært relatert problem er å finne en minimal triangulering, dvs en kordal overgraf som ikke inneholder en annen kordal overgraf av den gitte grafen. Det sistnevnte problemet kan løses i polynomisk tid og flere algoritmer finnes. Oppgaven går ut på å implementere en ny algoritme som ikke har blitt implementert enda. Kjøretiden og kvaliteten (mhp antall kanter) av produsert svar skal sammenlignes med en allerede etablert algoritme som løser samme problem. For en teoretisk interessert student er det flere spennende spørsmål å ta fatt i. Vi er interessert i å identifisere inndata grafklasser der de to algoritmene produserer samme svar, og generelt bevise forskjeller og likheter mellom de to algoritmene.
Nødvendig bakgrunn: I234 og gode programmeringskunnskaper
Anbefalte kurs: I238
Veileder: Pinar Heggernes
Student: Camilla Nesse Nilsen
Eksamen: 20. desember 2004

Speeding up parallel graph coloring

Veileder: Fredrik Manne
Student: Tom Christian Woods
Eksamen: 2004

Self-stabilizing algorithms for graph coloring

Veileder: Fredrik Manne
Student: Tom Solem
Eksamen: 2004

Self-stabilizing k-packing on trees

Veileder: Fredrik Manne
Student: Morten Mjelde
Eksamen: 2004

Monitoring the environment on a distressed submarine

Veileder: Fredrik Manne
Student: Torbjørn Svensson
Eksamen: 2003

Tools for online testing

Veileder: Fredrik Manne
Student: Sveinar Sæverud
Eksamen: 2003

Implementasjon av grafalgoritmer i LEDA

LEDA er et C++ bibliotek for kombinatoriske og geometriske datatyper og algoritmer og egner seg godt for implementering av relativt avanserte grafalgoritmer. Oppgaven går ut på å sette seg inn i LEDA og implementere algoritmer relatert til løsning av optimeringsproblemer på grafer med begrenset trebredde. Videre skal man utvikle/analysere/implementere diverse slike algoritmer og sammenlikne disse fra et praktisk standpunkt.
Nødvendig bakgrunn: I234 og gode programmeringskunnskaper
Andre relevante kurs: I238
Veileder: Jan Arne Telle
Student: Gunnar Horneland

Sammenlikning av parallelle beregningsmodeller

Oppgaven går ut på å sette seg inn i den grovkornede modellen for parallelitet, CGM (Coarse-Grained Multiprocessing), dens implementasjon sscrap, og implementere algoritmer for randomisert permutering i CGM-biblioteket sscrap. Deretter sammenlikne denne med liknende implementasjoner i andre modeller.
Bakgrunn: I234, I236
Veileder: Jan Arne Telle
Student: Kjell Kongsvik

Ordninger for minimalisering av antall fyll elementer

I mange lineær algebra operasjoner på matriser er arbeidet man må utføre proposjonalt med antall ikke-null elementer i matrisene. For matriser med få ikke-null element er det derfor viktig å utnytte denne egenskapen for å lage  effektive algoritmer. I Gauss eliminasjon kan man på forhånd permutere matrisen slik at man får lite ekstra nuller (fyll elementer) under selve løsingspro sessen. Dette er et vanskelig problem (NP-komplett) og det er derfor utviklet en rekke heuristi kker som skal gi permutasjoner med relativt sett lite fyll.
Oppgaven består i å først utvikle algoritmer som søker etter den best mulige permutasjonen for en del bestemte matrise typer.  Matrisen representeres som en graf slik at dette blir egentlig et søkeproblem på grafer. Søkerommet er i utgangspunkt så stort at man må analysere problemet for å finne muligheter for å begrense tidsbruken. Det kan også være ønskelig å bruke parallelle datamaskiner for å søke raskere. Steg to i oppgaven vil være å se om man kan trekke konklusjoner fra søket til hvordan man permuterer mer generelle matriser (grafer) for å få minst mulig fyll.
Relevante kurs: I234,I236 (kan leses som hovedfagspensum)
Veileder: Fredrik Manne
Student: Eivind Samdal
Eksamen: 2003

Gjenkjenning av "weakly chordal graphs"

Kordale grafer er en viktig grafklasse som dukker opp i mange sammenhenger, blant annet i forbindelse med løsningen av glisne ligningssystem. Weakly chordal graphs, eller svakt kordale grafer, er en overmengde av kordale grafer, og det har i årevis blitt forsket på å etablere sammenhenger mellom disse to grafklassene. Et nylig presentert resultat viser at kordale grafer og svakt kordale grafer kan gjenkjennes med lignende algoritmer.
Oppgaven går ut på å implementere en gjenkjenningsalgoritme for svakt kordale grafer. Denne algoritmen omfatter grafsøk, og egner seg godt til å paralleliseres. Vi vil implementere algoritmen både sekvensielt og parallelt, og måle hvor bra effekten av parallelisering er. I tillegg mistenker vi at den sekvensielle algoritmen egentlig har en bedre kjøretid i praksis enn dens beviste tidskompleksitet. Vi vil med gjentatte tester på store grafer vise algoritmens egentlige kjøretid i praksis. I tillegg til implementeringsdelen er det rikelig plass for teoretiske utfordringer i oppgaven dersom dette skulle være ønskelig for studenten.
Bakgrunn: I234, 236. I tillegg er det ønskelig med gode programmeringskunnskaper.
Veileder: Pinar Heggernes
Student: Lars Skeide
Avsluttende presentasjon: 17 desember 2002.

A Multilevel Scheme For The Traveling Salesman Problem

The traveling salesman problem is one of the most famous combinatorial problems of all time. A salesman visits n cities with given positions and returns finally to his city of origin. Each city is to be visited only once, and the problem is to find the shortest possible route. This problem belongs to a class known as NP-complete problems.
In this thesis, we aim at introducing a multilevel scheme for finding good solutions for very large graphs. The multilevel scheme we intend to develop works as follows: A sequence of smaller graphs are obtained from the original graphs using a coarsening procedure. Thereafter, an approximate solution to the problem is computed on the coarse graph. This solution is then projected back towards the original graph, by periodically proceeding with an improvement phase using combinatorial optimization techniques such as the simulated annealing method.
The objective of the project is to study the impact of different coarsening schemes on the quality of the final solution and to compare the proposed scheme with other existing algorithms.
Bakgrunn: I234
Veiledere: Fredrik Manne og Noureddine Bouhmala, Høyskolen i Vestfold
Student: Øystein Hjertnes
Eksamen: 2002

Image analysis of fish fillets

Veileder: Fredrik Manne
Student: Lars Helge Stien
Eksamen: 2002

Teoretisk kjøretid og effektiv implementering av en algoritme for minimale trianguleringer

En ny algoritme for minimale trianguleringer av grafer ble lansert i 1999. Kjøretiden var foreslått til å være O(nm) der n er antall noder og m er antall kanter i grafen. Men denne kjøretiden har ikke blitt bevist. I denne oppgaven vises det hvordan den nevnte algoritmen kan implementeres ved hjelp av en tredekomponering datastruktur, og kjøretiden O(nm) bevises for denne implementasjonen. Praktiske testresultater gis for å dokumentere reell kjøretid.
Veileder: Pinar Heggernes
Student: Yngve Villanger
Eksamen: 20 juni 2002.

Evaluering av trebredden til kontroll-flyt-grafen til Java-programmer

Begrepet trebredde kan knyttes til flere bruksområder i den virkelige verden, f.eks har kontroll-flyt grafen til et GOTO-fritt C program trebredde 5.
Veileder: Jan Arne Telle
Student: Ole Aleksander Mæhle

Fixed Parameter Kompleksitet

Mange kombinatoriske problemer, f.eks. Vertex Cover: 'Gitt en graf G med n noder og et heltall k, har G en delmengde av k noder som dekker alle kanter?' er NP-komplette, dvs at vi ikke kjenner noen algoritme for å løse problemet som for alle input har kjøretid O(n^c) for en konstant c. Istedet får vi en kombinatorisk eksplosjon som gir algoritmer med kjøretid O(c^n). De siste årene har det utviklet seg en mer raffinert måte å se på slike problemer, kallt fixed parameter kompleksitet, som har vist seg å være nyttig. Ideen er kort sagt å inngå en avtale med 'eksplosjonsdjevelen' ved å skille ut en parameter k i input, og lage en algoritme hvor eksplosjonen går utover kun k, med håp om at k i visse applikasjoner ikke vokser for mye. For vertex cover er det f.eks. utviklet algoritmer med kjøretid O(n (1.3)^k), k definert som over, og implementeringer viser at denne algoritmen er praktisk nyttig for k opptil 60, bortimot uavhengig av grafstørrelsen. Oppgaven vil bestå i å først sette seg inn i den teoretiske bakgrunnen for dette feltet, og skrive et første kapittel over denne. Deretter kan man enten konsentrere seg om å utvikle egne 'fixed parameter' algoritmer for et utvalgt problem (eventuellt vise negative resultater av typen: 'problemet er komplett for denne kompleksitetsklassen') eller arbeide med implementering og testing av allerede eksisterende algoritmer.
Bakgrunn: I234, I235. Det er ønskelig at studenten har en god teoretisk bakgrunn.
Veileder: Jan Arne Telle
Student: Christian Sloper

Visualisering ved hjelp av L-systemer

L-systemer, eller Lindenmayer-systemer, er en måte å konstruere kompliserte strenger ved hjelp av grammatikker. De ble først tatt i bruk som en matematisk modell for plantevekst, men brukes også som et rent visualiseringsverktøy. Teorien bak L-systemer er relatert både til formelle språk og fraktalgeometri.
Veileder: Jan Arne Telle
Student: Knut Erstad

Grafalgoritmer for glisne matriser og klikktrær

Symmetriske glisne matriser egner seg godt til å tolkes som grafer. En rekke viktige operasjoner på glisne matriser innen lineær algebra kan derfor oversettes til grafalgoritmer. Dette gjør at grafteoretiske metoder kan t as i bruk for løsning av problem som oppstår når man vil behandle glisne matriser mest mulig effektivt. Et slikt kjent problem er minimering av antall fyll-elementer under faktorisering.
I denne oppgaven tar vi utgangspunkt i en allerede implementert algoritme relatert til fyll-problemet. Vi ønsker å forandre deler av denne implementasjonen og gjøre tester for å se effekten av forandringene. For å kunne gjøre de ønskede forandringene må studenten først implementere en kjent struktur som kalles "klikktrær". Nylig har det blitt definert operasjoner på klikktrær som vi ønsker å bruke i vår modifisering. Disse operasjonene skal erstatte noen av de metodene som brukes i den eksisterende implementasjonen. Oppgaven går ut på å implementere en modul for klikktrær med de ønskede operasjonene, og deretter integrere disse operasjonene i koden som vi ønsker å forandre. Avslutningsvis skal studenten utføre tester for å se effekten av forandringene.
Nødvendig bakgrunn: I234 (I tillegg fordel med I235 og/eller I260).
Veileder: Pinar Heggernes
Student: Jan Storenes
Eksamen: 5 desember 2001
Oppgavetittel: Implementation and application of a fully dynamic algorithm for chordal graphs.

Lastbalansering på parallelle datamaskiner (Sekvensielle algoritmer)

I parallell prosessering er det vesentlig at man klarer å fordele det tilgjengelige arbeidet mest mulig likt mellom de ulike prosessorene. Dette problemet kan i enkelte tilfeller modelleres ved at man deler opp en tallsekvens i like mange deler som man har prosessorer under forutsetning av at hver del får omtrent samme vekt. Det finnes en rekke sekvensielle algoritmer av ulik teoretisk kompleksitet som løser dette problemet.
Oppgaven består i å implementere, analysere og videreutvikle disse algoritmene med et spesiellt øye for hva som er effektivt.
Relevante kurs: I235, I236
Veiledere: Fredrik Manne  (og Tor Sørevik)
Student: Thomas Haukland
Påbegynt: V99
Avsluttet: V01

Evolusjonstrær

Evolusjonstrær representerer hvordan arter har utviklet seg fra felles forfedre. Gitt to ulike evolusjonsteorier (trær), trenger man algoritmer som beregner en størst mulig delteori der teoriene stemmer overens. Felles prosjekt mellom gruppene for algoritmer og bioinformatikk.
Bakgrunn: I234, I282
Veiledere: Jan Arne Telle, Magnús M. Halldórsson og Inge Jonassen
Student: Cato Ervik

Informasjonssøking på World Wide Web

Web-eksplosjonen utgjør en gullgruve av nye algoritmiske problemer. Informasjonssøking på WWW er et av feltene som krever tildels nye metoder og teknikker. Denne teoretisk orienterte oppgaven vil innledningsvis bestå i å få en oversikt over disse nye problemstillingene og dernest i å velge ett eller flere av dem for nærmere analyse. De utvalgte problemer skal ha tilknytning til grafteori eller datastrukturer.
Det kreves god bakgrunn i algoritmer og kombinatorikk (I234 og M132).
Veileder: Jan Arne Telle
Student: Sidsel Horvei

Grafalgoritmer for glisne matriser

Symmetriske glisne matriser kan tolkes som grafer, og algoritmer for faktorisering av slike matriser kan uttrykkes som grafalgoritmer. Relatert til faktorisering finnes det mange problem som er vanskelige å løse, som minimering av antall ikke-null elementene i faktorene, og pivotering for å oppnå bedre egenskaper for parallel faktorisering. I denne oppgaven skal man implementere en del allerede eksisterende teoretiske resultater. Søkelyset skal spesielt rettes mot minimale ordninger, og eksperimenter med antall ikke-null elementer skal utføres.
Nødvendig bakgrunn: I234 of I260
Veileder: Pinar Heggernes
Student: Ole-Martin Kvinge
Eksamen: 18 november 1999
Oppgaventittel: Practical aspects of fill reduction on sparse matrices and graphs

Parallell graf-fargelegging

Fargeleggings problemet består i å fargelegge nodene i en graf med så få farger som mulig slik at ingen nabo-noder får samme farge. Dette er et meget sentralt problem innenfor databehandling og det eksisterer en rekke algoritmer for å løse det. Oppgaven består i å implementere/utvikle/analysere ulike parallelle algoritmer for dette problemet.
Relevante kurs: I234, I236
Veileder: Fredrik Manne
Student: Assefaw Hadish Gebremedhin
Eksamen: 11 mai 1999

Bestemming av bil-priser

En rekke dagsaviser legger idag ut sine rubrikk annonser på Internett. En rubrikk annonse kjennetegnes ved at den er kort og inneholder et relativt begrenset sett av strukturer og ord. I oppgaven skal det utvikles en grammatikk som kan tolke rubrikk annonser for bruktbiler. Hennsikten med dette er å bestemme ting som merke, pris, årsmodell, kjørelengde osv. Dette skal igjen brukes for å generere en database over biler som har vært til salgs. Utifra verdiene i databasen skal det ved hjelp av multivariat data-analyse lages statistikk over hvilke komponenter som er vesentlig ved fastsetting av prisen til en bruktbil.
Relevante kurs: I122, I125 og I231 + noe statistikk
Veileder: Fredrik Manne
Student: Pierre Pad
Eksamen: 18 november 1998

Støtteverktøy for programutviklere

Utvikling av store programsystemer foregår ofte inkrementelt og over lang tid. Dersom det skulle oppstå en feil i programkoden er man da i den situasjonen at man har to versjoner av programet, et som gir rett resultat og et (nytt) som gir feil resultat. Dersom programmet først regner feil på lange kjøringer vil det ta for lang tid å kjøre programet i en debugger for å finne feilen.
Oppgaven består i å utvikle et vertøy som kan hjelpe programutvikleren å finne hvor feilen har oppstått. Dette verktøyet skal kunne kjøre begge versjonene av programmet parallelt samtidig som det overvåker utviklingen av et par utvalgte variabler. Denne overvåkingen skal foregå automatisk og rapportere når eventuelle feil først oppstår.
Bakgrunn: Gode programmeringsevner. Interesse for grafiske brukergrensesnitt, distribuert prosessering og algoritmer.
Relevante kurs: I122, I234 og I236
Veileder: Fredrik Manne
Student: Svein Olav Andersen
Eksamen: 27 mars 1998

Implementing and Testing of Algorithms for Tree-like Graphs

Veileder: Jan Arne Telle
Student: Bjørn Hiim
Eksamen: november 1997