Algoritmer med mere

Læringsmål

Efter første uge er det meningen at:

Efter anden uge er det meningen at:

Erhvervskompetencer

Efter disse to uger er det meningen at du skal kunne:

De algoritmiske ting bag ArrayList, HashMap og sortering vil I ikke komme til at skrive selv (de ligger i Java bibliotekerne). Men jeres chef og kollegaer forventer at man ved hvordan de virker.

Uge 1

Det er meningen I skal arbejde sammen selvstændigt med emnerne. Vi mødes mandag, onsdag og fredag.

Mandag er vigtig

og vil være “klassisk dag”, altså alle tilstæde i klassen med en blanding af oplæg, demo, og øvelser.

Denne dag er semesterets første dag, og vi vil prøve at give det overordnede billede af hvad der kommer til at ske resten af semesteret, og præsentere de to undervisere I kommer til at arbejde med i disse 2 uger.

Onsdag og Fredag vil vi mødes i grupperne af gangen så vi kan følge op på om der er problemer med opgaverne og læsestoffet.

Læsestof og opgaver til onsdag

Når vi mødes onsdag vil jeg gerne have en demo af at I kan sætte breakpoints og forklare hvordan debuggeren virker. Det betyder at I skal have lavet jeres ArrayList så I kan vise det til vejlederen.

Forventninger:

Niveau Demo
Grøn Det forventes at I har fået arraylist programmet op at køre i netbeans, og kan forklare mig hvordan vi i debuggeren kan se kaldsstak, this pointeren og parametere til metoden add når der er sat et breakpoint i linje 33 i Sem2ArrayList.java. Det forventes også at I ved hvad fejlen er i denne linje.
Gul Der skal laves en metode Coordinate removeLast() der fjerner det sidste element (og returnerer det). Hvis der ikke er noget element skal der returneres null. I kan eventuelt også lave det sådan at hvis kun 25% af elementerne i array bruges, så kopieres de resterende elementer over i et mindre array (halv størrelse af det gamle). I skal så vise et eksempel hvor der er et breakpoint som stopper ligefør arrayet gøres mindre.
Rød For de særligt nysgerrige vil jeg foreslå at I forbereder en forklaring på hvad der sker i konstruktøreren og hvorfor den mon hedder <init> i både pythontutor og i debuggeren. Hint - prøv at flytte noget af initialiseringen ud af konstruktøren og over i felterne.

Læsestof og opgaver til fredag

De næste par dage skal vi se på hvordan man i Java kan teste sine programmer. Det bliver først interessant hvis programmerne er lidt komplicerede, så vores eksempel vil være at lave vores egen udgave af et HashMap.

Når vi mødes fredag vil jeg gerne have en demo af jeres HashMap (eller det i er nået). Hvis I ikke er færdig til fredag, så skal I vise hvad I har og hvorfor I er gået i stå.

Forventninger:

Niveau Demo
Grøn Jeg forventer i kan demo et hashmap med tests. Det behøver ikke at håndtere kollisioner, men I skal have en test der viser at den ikke kan - altså en test der fejler pga. kollision.
Gul Jeg forventer at I kan håndtere kollisioner og at der er en test der viser at det kan I. Jeg forventer ikke at jeres HashMap kan udvides. Der skal være en test der fejler fordi den ikke kan udvides.
Rød Jeg forventer I har implementeret at jeres HashMap udvides når det begynder at blive fuldt. Der skal være tests der viser at det kan det.

Uge 2

Vi skal i denne uge kikke på et emne der kaldes “søgning og sortering”.

Vi kommer til at bruge den første del af ugen på det der kaldes et “binært søge træ”. Søgetræer er en klassisk måde at gemme data på. Søgetræer fungerer ligesom HashMap ved at man gemmer en værdi under en nøgle.

Dernæst skal vi kikke på en af de måder at sortere på som er mest udbredt, nemlig quicksort.

Endelig skal vi fredag se på hvordan man vælger hvilken type collection man skal bruge til hvilken opgave.

Mandag

Mandag bliver “klassisk dag”, altså alle tilstæde i klassen med en blanding af oplæg, demo, og øvelser. Jeg vil gennemgå ugens emner

Onsdag

Vi mødes vi i gruppen for at I kan give en demo af søgetræet I har implementeret.

Læsestof & opgaver

Forventninger:

Niveau Demo
Grøn Jeg regner med at I har kan demo løsningerne til opgaverne i Noten om søgetræer (dem der ikke er markeret avanceret)
Gul Jeg regner med at I selv har kikket på det med at fjerne elementer fra søgetræet, og hvis I ikke har fået det til at virke, at I så i det mindste har fået skrevet nogle tests der fejler men kan oversættes.
Rød Jeg regner med at I enten har fået det balancerede søgetræ til at virke, eller har nogle ret klare spørgsmål for at afklare jeres problemer.

Fredag

I skal demo jeres løsninger af quicksort algoritmen, og jeres løsninger på store O opgaverne og det at vælge en collection

Læsestof og opgaver

Forventninger:

Niveau Demo
Grøn Jeg regner med at I kan demo quicksort og har test at I kan sortere både nul, et og 10 elementer, og en test der viser at I kan sortere noget der allerede er sorteret, samt noget der er i omvendt rækkefølge. Desuden regner jeg med at vi kan snakke om løsningen på opgaverne omkring store O og det at vælge en datastruktur.
Gul Jeg regner med at I kan forklare hvorfor man får log2(n) opførsel på søgning i søgetræ, og hvorfor man får n·log2(n) opførsel på quicksort.
Rød Jeg vil foreslå at I kikker på den algoritme der hedder “MergeSort”, og prøver at implementere den (ja, vi forventer røde selv at kunne finde det der skal bruges på nettet). Hvis I ikke kommer igennem med det, så prøv at indkredse hvad ved algoritmen I ikke forstår.