Oppgavesett 5 - Palindromer og Flettesortering

Oppgavene blir tema på øvingen fredag 2. mars. Innleveringen skal bestå av en pdf-fil med korte kommentarer og dokumentasjon (utskrifter etc.). Legg også ved godt dokumenterte java filer. Alt pakkes i en zipfil, med navn assignment05-*.zip der * er etternavnene til gruppemedlemmene. Javafilene skal tilhøre en pakke med navn package assignment05.

Fristen for innlevering er tirsdag 28.februar 09:00.

Oppgave 1

Et palindrom er en tegnstreng som er som kan "leses" både forfra og bakfra (symmetrisk om midten). Vi ser bort fra whitespace og tegn som punktum, komma etc., og regner store og små bokstaver som identiske. Her er endel eksempler:

• Regninger
• Teppet
• Agnes i senga
• Du har bra hud

Du skal nå implementere tre ulike metoder som sjekker om en tegnstreng er et palindrom eller ikke (returnerer true/false). Hver metode skal først beskrives med klartekst, deretter med presis pseudokode, og endelig programmeres. Dokumenter at metodene virker.

A)

Med løkke: public boolean palindromIterative(char[] arr)

B)

Med stack: public boolean palindromStack(char[] arr)

C)

Med rekursjon: public boolean palindromRec(char[] arr)

Oppgave 2

A)

Redegjør for hvordan flettesortering virker, og hvorfor det er så effektivt. Bruk illustrasjoner.

B)

Beskriv flettesortering med presis pseudokode.

C)

Implementer flettesortering med følgende driverfunksjon: public void mergeSort(int[] arr). Denne metoden skal kalle den rekursive funksjonen private void recSort(int[] arr, int first, int last) Koden skal være rikelig kommentert. Test metoden og dokumenter også at den virker.

D)

Flettesortering har såkalt loglineær orden. Hva betyr det? Verifiser dette med å kjøre og måle tiden på et antall sorteringer med stigende verdier på input, med tilhørende plotting av resultatet. Tell også gjennomsnittlig antall rekursive kall for hver kjøring. Plott disse verdiene og kommenter!

* Oppgave 3

Implementer Sierpinski trekanten.