Topic outline

  • General

  • Ponedeljek: Osnovne podatkovne strukture, algoritmi in tehnike

    Matevž Jekovec

    Vsebina:

    • Uvod
    • Osnovne podatkovne strukture: sklad, vrsta, slovar, vrsta s prednostjo, množica
    • Drevesa za okus
    • Delo z nizi
    • Veliki O in prijatelji
    • Urejanje (sorting)
    • Osnovne tehnike načrtovanja algoritmov
  • Torek: Algoritmi na grafih, 1. del

    Nino Bašić

    Vsebina:

    • Kaj je graf?
    • Stopnja vozlišča, sprehodi, poti. Lema o rokovanju
    • Predstavitve grafov
      • Matrika sosednosti
      • Seznam sosedov
    • Eulerjev graf (Problem königsberških mostov)
    • Iskanje v globino (DFS)
    • Iskanje v širino (BFS)
    • Povezanost, povezane komponente
    • Dvodelni grafi
    • Usmerjeni grafi
    • Topološko urejanje
  • Sreda: Algoritmi na grafih, 2. del

    Mitja Trampuš

    Vsebina:

    • Najkrajše poti
      • Floyd-Warshallov algoritem
      • Dijkstrov algoritem
      • Bellman-Fordov algoritem, detekcija neg. ciklov
    • Strongly connected components (krepko povezane komponente)
    • Link hopping (lowest common ancestor problem)
    • Ford-Fulkerson - max pretok, min prerez
    • Min cost max flow, dvodelno prirejanje
      • "Successive shortest path" algoritem
      • Prevod problema prirejanja na min cost max flow problem

  • Četrtek: Dinamično programiranje

    Janez Brank

    Vsebina:

    • Množenje matrik. Oklepajski izrazi. Delitev daljice
    • Najdaljše skupno podzaporedje (LCS). Urejevalna razdalja
    • Razdelitev na podzaporedja z najmanjšo vsoto (problem pisarjev)
    • Floyd-Warshallov algoritem
    • Najdaljše naraščajoče podzaporedje (LIS)
    • 0/1-nahbrtnik
    • Trgovski potnik
  • Petek: Tekmovanje

    Žiga Ham

    Tekmovanje dostopno v okolju UVa na naslovu:
    http://umt.boocode.com/viewcontest.php?id=1283