Avancerade algoritmer, avalg11

Senaste Nytt

2012-02-22

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

Tryck här för att hämta kursenkäten:

2012-02-12

The TSP report has now been graded and all results should be in "rapp". It may take a day or two before you see it in "Mina sidor".

Äldre nyheter.

Lärare

• Kursledare: Mikael Goldmann
• Assistenter: Cenny Wenner och Mateus de Oliveira Oliveira

Examination

Examinationen består av två projekt (som kan ge 100 poäng vardera) och fyra omgångar med inlämningsuppgifter (som kan ge 25 poäng vardera).

Lösningar behöver vara på engelska och du behöver vara beredd att redovisa på engelska då inte alla lärare på kursen kan svenska. Dessutom passar det 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.

A	236	-	300
B	200	-	235
C	180	-	199
D	160	-	179
E	140	-	159
F	0	-	139

Registrering

Registrera dig så fort kursen börjat i systemet rapp. Logga in med ditt KTH-id, markera "avalg11", och klicka "Jag går kursen".

Om avalg11 inte finns med bland dina kurser i rapp kan det bero på olika saker

1. Du har påbörjat kursen ett tidigare år och är registrerad på en tidigare kursomgång. Om du vill bli omregistrerad på den nya kursomgången kontaktar du studerandeexpeditionen på Osquars backe 2, plan 2. Dina resultat på tidigare kursomgång finns då i rapp eller res.
2. Du är inte antagen på kursen av din studievägledning. Gå till din studievägledning och be att få gå DD2458. Dagen efter att studievägledningen lagt in din kursanmälan i Ladok kommer kursen att komma upp i din lista i Rapp, så att du kan registrera dig.

Kompendium och annat material

• Johan Håstad, Notes for the course advanced algorithms (pdf), Jan 2000.
• Rivest, Shamir, and Adleman, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (pdf), 1978.
• Jakob Nordströms föreläsning om SAT-lösare. Slides till och med 15: DPLL and resolution svarar mot Jakobs föreläsning.
• 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 Granlunds presentation av GMP (pdf)
• The Traveling Salesman Problem: A Case Study in Local Optimization, D. S. Johnson and L. A. McGeoch
• Material om amorterad analys delas ut.
• Övrigt material kommer att läggas upp allt eftersom

Föreläsningsplan

F1 Unit cost, bit cost, Euclides extended algorithms, RSA

F2 SAT-solving and resolution

F3 Analysis of RSA. Modular exponentiation. Chineese remainder theorem.

F4 Primality testing. Sorting in O(n log log n) start.

F5 Sorting networks. Sorting in O(n log log n) concluded.

F6 Factoring. Pollard's and Fermat's methods.

F7 Factoring with quadratic sieve. Polynomial multiplication. Karatsuba.

F8 FFT and polynomial multiplication.

F9 GMP, efficient implementation of algorithms for multiple precision arithmetic (Torbjörn Granlund).

F18 Linear programming

F11 TSP

F12 matchings and flows

F13 matchings and flows

F14 Amortized analysis

F15 Buffer

Schema

Hämtat från schemageneratorn.

Timeout