Avancerade algoritmer, avalg13

Hjälp oss förbättre utbildningen genom att fylla i kursenkäten. Tack.

Lärare

• Kursledare: Stefan Nilsson
• Assistenter: Musard Balliu, Mladen Mikša och Marc Vinyals

Föreläsningar

16/9

Introduktion. Unit-cost RAM. Radix sort. [valfri källa]

18/9

Undre gräns för jämförelsebaserad sortering [valfri källa]. Sortering på O(n log log n) tid. [The Fastest Sorting Algorithm?]

23/9

Mer om sortering på O(n log log n) tid. GCD, snabb exponentiering, enkel faktorisering. [Notes for the course advanced algorithms]

25/9

Faktorisering: Pollards rho-metod. [Notes for the course advanced algorithms]

30/9

Deadline: HW A Amorterad analys. [Amortized Analysis Explained by Rebecca Fiebrink]

2/10

Splayträd. [Self-Adjusting Binary Search Trees] Kvadratiska sållet. [Notes for the course advanced algorithms, Att implementera kvadratiska sållet ]

9/10

Kinesiska restsatsen. Miller-Rabins primtalstestning. [Notes for the course advanced algorithms]

4/11

Deadline: HW B Diskreta Fouriertransformen (DFT) och snabba Fouriertransformen (FFT).

6/11

Multiplikation av stora tal: naiv metod, Karatsuba, FFT.

11/11

Deadline: PRO 1 Elliptic curve cryptography.

• A (relatively easy to understand) primer on elliptic curve cryptography
• The Many Flaws of Dual_EC_DRBG
• Revealed: how US and UK spy agencies defeat internet privacy and security
• How to Remain Secure Against the NSA

13/11

GMP. [presentation av GMP uppdaterad 2013-11-13]

18/11

Euklidisk TSP: introduktion och Christofides undre gräns.

27/11

Deadline: HW C Euklidisk TSP: heuristiker, lokal sökning, 2-opt, 3-opt.

2/12

Faktorisering på polynomisk tid med FFT på kvantdator.

9/12

Deadline: PRO 2 Reserv.

Examination

Examinationen består av två projekt (som kan ge 100 poäng vardera) och tre omgångar med inlämningsuppgifter (som kan ge 25 poäng vardera). Inlämningsuppgifterna är individuella; projekten görs i tvåpersonersgrupper. Deadline för uppgifterna bestämmer vi tillsammans på första föreläsningen 16/9.

Lösningar behöver vara på engelska och du ska vara beredd att redovisa på engelska då inte alla lärare på kursen kan svenska. Det passar bra ihop med KTHs mål att civilingenjörer ska vara parallellspråkiga, dvs kunna tala och skriva om sitt område på både svenska och främmande språk.

Betyg delas ut baserat på hur många poäng man uppnår på projekt och hemtal.

Kompendium och annat material

• Cormen, Leiserson, et al., Introduction to Algorithms.
• Johan Håstad, Notes for the course advanced algorithms, Jan 2000.
• Rivest, Shamir, and Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, 1978.
• Stefan Nilsson: The Fastest Sorting Algorithm?
• Greg Plaxton: Parallel Recursion: Batcher s Bitonic Sort. Bra material om sorteringsnätverk som kan kompletteras med wikipedia-artiklar nedan (wikipedia-artiklarna har illustrationer som hjälper en förstå denna presentation).
• Wikipedia: Sorting networks, Bitonic sorting
• Torbjörn Granlund: presentation av GMP
• D. S. Johnson and L. A. McGeoch: The Traveling Salesman Problem: A Case Study in Local Optimization
• Material om amorterad analys och Splayträd delas ut.
• Torbjörn Granlund: Att implementera kvadratiska sållet
• Lars Engebretsen: Faktorisering med hjälp av kvantberäkningar
• Övrigt material kommer att läggas upp allt eftersom.