Diskret matematik, algoritmer og datastrukturer

Studerende, der følger kurset, forventes at:

• Besidde matematisk modenhed, som f.eks. opnået gennem kurset Calculus og Lineær Algebra.
• Kunne programmere i Java.

• Definere og beskrive relevante koncepter indenfor diskret matematik, algoritmer og datastrukturer 

• Arbejde med logiske udsagn, relationer og bevisteknikker, herunder induktion.
• Argumentere præcist for en algoritmes korrekthed eller mangel på samme.
• Bestemme en algoritmes asymptotiske køretid.
• Tilpasse kendte algoritmer og datastrukturer til specialtilfælde af kendte problemer og til nye problemer.
• Designe nye algoritmer til at løse problemer, som i natur minder om problemer fra kurset. Herunder give en præcis beskrivelse af algoritmen, f.eks. vha. pseudokode.
• Foretage formålstjenlige valg af datastruktur.
• Designe nye datastrukturer baseret på kendte datastrukturer.
• Designe og implementere et større program, som anvender algoritmer og datastrukturer fra kurset.
• Argumentere præcist for de valg, der foretages i forbindelse med de foregående fire punkter. 

Kurset indeholder følgende faglige hovedområder:

• Diskret matematik: bevisteknikker (herunder induktion), logik, relationer, rekursionsligninger, invarianter. 
• Algoritmer: korrekthed og kompleksitetsanalyse, del-og-hersk algoritmer (master teorem, Strassens algoritme), grådige algoritmer, dynamisk programmering, graf-algoritmer (BFS, DFS, topologisk sortering af DAGs, sammenhængskomponenter, stærke sammenhængskomponenter, minimum udspændende træ, korteste veje), Huffman-kodning. 
• Datastrukturer: ordbøger (binære søgetræer, rødsorte træer, hashing), prioritetskøer, disjunkte mængder.