DM582: Avancerede algoritmer

• Have kendskab til basale algoritmer og datastrukturer såvel som implementering af disse i et imperativt programmeringssprog, herunder stakke, køer, søgetræer og prioritetskøer, såvel som sorteringsmetoder og basale grafalgoritmer.
• Have kendskab til algoritmedesignteknikker og være i stand til at analysere algoritmer ved hjælp af asymptotisk analyse og sammenligne asymptotiske resultater.
• Være i stand til at anvende basal matematisk argumentation, herunder logiske udtryk, beviser ved induktion, modstridsargumenter, tælleteknikker og diskret sandsynlighedsteori.

• Anvende emner fra diskret sandsynlighedsteori til at estimere den forventede køretid for algoritmer
• Udvikle og analysere basale randomiserede algoritmer
• Anvende teknikker fra universel hashing til at vælge hashfunktioner med god forventet opførsel
• Formulere en strømningsmodel for problemer, der ligner dem fra kurset
• Anvende teknikker fra kurset til at vurdere den amortiserede tidskompleksitet af operationer på en datastruktur

• Randomiserede algoritmer
• Probabilistiske analyser af algoritmer
• Den probabilistiske metode
• Universel og perfekt hashing
• Strømning i netværk
• Amortiseret analyse

• Introfase: 40 lektioner
• Træningsfase: 30 lektioner

I introfasen anvendes en modificeret variant af klassiske forelæsninger, hvor fundamentale begreber og metoder præsenteres teoretisk såvel som gennem eksampler på konkrete data. Der opmuntres til spørgsmål og diskussioner. Træningsfasen drejer sig om øvelser og diskussionsemner, der relaterer sig til det materiale, der er blevet introduceret i de forudgående introfase lektioner. I træningsfasen kan de studerende arbejde specifikt med de mere udfordrende emner. Spørgsmål, som opstår i studiefasen, kan bringes op under mødetiderne.