Topic outline

  • General

  • Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike

    Andrej Brodnik

    Vsebina:

    1. Uvod
    2. Osnovne podatkovne strukture: sklad, vrsta, slovar, vrsta s prednostjo, množica
    3. Drevesa za okus
    4. Delo z nizi
    5. Veliki O in prijatelji
    6. Urejanje (sorting)
    7. Osnovne tehnike načrtovanja algoritmov
  • Torek: Najnujnejše o grafih

    Mitja Trampuš

    Vsebina:

    1. Kaj je graf
      • Cestna omrežja, prijateljstva
      • Drevo, cikel, usmerjen graf, utežen graf
    2. Predstavitve grafov
      • Matrika sosednosti
      • Seznam sosedov
      • Implicitna predstavitev (npr. premikanje po gridu)
    3. DFS (iskanje v globino) z rekurzijo
      • Pazi na cikle
    4. DFS z ročno vodenim stackom
    5. BFS (iskanje v širino)
    6. Povezanost v neusmerjenih grafih. Komponente za povezanost
    7. Dvodelnost in 2-obarvljivost
    8. Intermezzo: Lahki nalogi za začetnike
      • Facebook friend suggest
      • Height map grid, iz zgornjega levega vogala izvira voda. Bo pritekla v spodnji desni vogal?
    9. Premer drevesa
    10. DAG (usmerjen acikličen graf) in topološko urejanje
    11. Najmanjše vpeto drevo (Minimum spanning tree)
    12. Najkrajše poti
      • Bellman-Fordov algoritem
      • Dijkstrov algoritem
      • Warshall-Floydov algoritem (bo razložil Janez v četrtek)
    13. Eulerjev obhod
    14. Problem trgovskega potnika (Travelling salesperson problem). Hamiltonov obhod (opis problema, NP-težkost)
  • Sreda: Dinamično programiranje – 1. del

    Nino Bašić

    Vsebina:

    1. Trikotnik števil (The Triangle, IOI 1994)
    2. Računanje binomskega koeficienta in Stirlingovih števil 2. vrste
    3. Preštevanje particij naravnih števil
    4. Linearna razdelitev (UVa 714 - Copying Books)
    5. 0/1 nahrbtnik. Coin Change
    6. Problem trgovskega potnika. Maksimalno prirejanje v grafih
    7. UVa 108 - Maximum Sum
  • Četrtek: Dinamično programiranje – 2. del

    Janez Brank

    Vsebina:

    1. Množenje matrik. Oklepajski izrazi. Delitev daljice
    2. Najdaljše skupno podzaporedje (LCS). Urejevalniška razdalja
    3. Floyd-Warshallov algoritem
    4. Najdaljše naraščajoče podzaporedje (LIS)
  • Petek: Izkušnje s tekmovanj

    Žiga Ham

  • Petek: Tekma

  • Topic 7

    • Topic 8

      • Topic 9

        • Topic 10