DM02 - Algoritmer og Datastrukturer

Efterår 2003
Lene Monrad Favrholdt

Ugesedler

Tid og sted

Litteratur

Eksamen

Officiel kursusbeskrivelse

Obligatorisk opgave - første del: ps-format pdf-format

OBS:
I opgaven står der, at pladsforbruget skal være O(min(m,n)).
Det er i orden at have pladsforbrug O(m+n).

Obligatorisk opgave - anden del: ps-format pdf-format

OBS:
Man må gerne bruge (n^2) plads til at opbevare afstandene mellem de n strenge.

Aflevering:
Den elektroniske aflevering af programmet skal foretages inden mandag d. 1. december kl. 10:00.
Rapporten skal afleveres på sekretariatet senest tirsdag d. 2. december kl 10:00, eller til forelæsningen mandag d. 1. december (sekretariatet er lukket d. 1. december).

Lidt hjælp:
Man må gerne antage, at der ikke er nogen tomme strenge.
Man kan indlæse streng-filen på følgende måde:

        LinkedList strenge = new LinkedList();
        FileReader fr = new FileReader(pathname);
        BufferedReader in = new BufferedReader(fr);
        String s = in.readLine();
        while(s != null) {
            if (!s.equals("")) strenge.add(s);
            s = in.readLine();
        }