Diskret matematik, algoritmer og datastrukturer

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. 

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.
• Anvende algoritmerne fra kurset på konkrete problemer.
• 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.