Algorithms and Data Structures 2

Topic outline

• General
  

  General

  • Novice Forum

    Restricted Not available unless: Your Email address is not empty
  • Pogovori o snovi, domačih nalogah, izpitu, ... Forum

    Restricted Not available unless: Your Email address is not empty
  • Izvajanje predmeta Page
  • Literatura in povezave Page
  • Vaje - Microsoft Teams URL
  • ---

  • Izziv - Množenje velikih števil Assignment
  • ---

  • Primer izpitnih nalog File Uploaded 1/06/20, 17:48
• 2. izpitni rok - 1. 7. 2020 ob 11.30
  

  2. izpitni rok - 1. 7. 2020 ob 11.30

  • Izpit z rešitvami File Uploaded 4/07/20, 11:12
• 1. izpitni rok - 10. 6. 2020 ob 11.30
  

  1. izpitni rok - 10. 6. 2020 ob 11.30

  • Izpit z rešitvami File Uploaded 11/06/20, 08:11
• Predavanja
  

  Predavanja

  • Uravnotežena iskalna drevesa File
  • Večsmerna drevesa File
  • Predavanja 23. 3. 2020 (Večsmerna drevesa 1/2) BigBlueButtonBN
  • Predavanja 30. 3. 2020 (Večsmerna drevesa 2/2) BigBlueButtonBN
  • Predavanja 6. 4. 2020 (Zgoščena tabela) BigBlueButtonBN
  • Predavanja 20. 4. 2020 (Razredi časovne zahtevnosti) BigBlueButtonBN
  • Predavanja 4. 5. 2020 (Dinamično programiranje 1/3) BigBlueButtonBN
  • Predavanja 11. 5. 2020 (Dinamično programiranje 2/3) BigBlueButtonBN
  • Predavanja 18. 5. 2020 (Dinamično programiranje 3/3) BigBlueButtonBN
  • Predavanja 25. 5. 2020 (Linearno programiranje) BigBlueButtonBN
  • Predavanje 1. 6. 2020 (Zunanje urejanje) BigBlueButtonBN
• 1. vaje (2.3. - 9.3.)
  

  1. vaje (2.3. - 9.3.)

  V prvem tednu vaj ponovimo določene izbrane vsebine iz APS1. O, Ω in Θ notacija, asimptotična časovna zahtevnost algoritmov, urejanje z vstavljanjem, mojstrski izrek, dvojiška kopica, rekurzija.
  

  • Vaje 1. teden File Uploaded 19/03/20, 10:00
• 2. vaje (10.3. - 16.3.)
  

  2. vaje (10.3. - 16.3.)

  Nekatere pogoste podatkovne strukture v standardni knjižnici programskega jezika Java: seznam, sklad, vrsta in dvojna vrsta. Ogledali smo si predpisane metode vmesnikov List, Stack, Queue in Deque ter nekaj preprostih primerov uporabe. Pri seznamu smo uporabili implementacijo s tabelo in dvojno povezanim seznamom. Sklad in vrsto lahko nadomestimo s splošnejšo podatkovno strukturo dvojna vrsta, ki implementira operacije obeh podatkovnih struktur.
  

  Domača naloga obravnava iskanje dolžine najkrajšega intervala v seznamu, katerega vsota elementov dosega ali presega podano ciljno vsoto. Možna implementacija z uporabo predponske/kumulativne vsote in dvojne vrste, ki ima linearno prostorsko in časovno zahtevnost. Naivna implementacija ima kubično časovno zahtevnost, ki pa jo je mogoče enostavno izboljšati na kvadratično.
  

  • Vaje 2. teden File Uploaded 12/03/20, 08:08
  • Naloga 1 - dvojna vrsta Assignment
• 3. vaje (17. 3. - 23. 3.)
  

  3. vaje (17. 3. - 23. 3.)

  Amortizirana analiza. Razlaga metode potenciala. Vaje iz treh metod amortizirane analize: metoda vsote, metoda kopičenja in metoda potenciala.
  

  • Vaje 3. teden File Uploaded 21/05/20, 17:15
  • Posnetek vaj 3. tedna URL
• 4. vaje (24. 3. - 30. 3.)
  

  4. vaje (24. 3. - 30. 3.)

  Pri vajah v četrtem tednu obravnavamo še amortizirano analizo na primeru dinamične tabele z operacijama vstavljanja in brisanja. Nato se osredotočimo na podatkovno strukturo seznam, ki je lahko glede na sosledje elementov neurejen ali urejen. Primerjamo časovne zahtevnosti implementacije seznama s tabelo in kazalčnim/povezovalnim seznamom. Nekoliko podrobneje obravnavamo preskočni seznam, kjer se osredotočimo na verjetnostno analizo časovne in prostorske zahtevnosti.
  

  • Vaje 4. teden File Uploaded 15/04/20, 17:43
  • Seminarska naloga 1 File Uploaded 8/04/20, 17:17

    Tematika 1. seminarske naloge je igra IQ Fit, pri kateri je za podane like potrebno poiskati njihove postavitve in orientacije tako, da jih lahko vložimo na igralno ploščo pravokotne oblike.

  • Seminarska naloga 1 Assignment
  • Posnetek vaj 4. tedna URL
• 5. vaje (31. 3. - 6. 4.)
  

  5. vaje (31. 3. - 6. 4.)

  V 5. tednu pri vajah obravnavamo drevo, urejena dvojiška iskalna drevesa, in rotacije.

  
  

  • Vaje 5.teden File Uploaded 1/04/20, 09:03
  • Posnetek vaj 5. tedna URL
• 6. vaje (7. 4 - 13. 4)
  

  6. vaje (7. 4 - 13. 4)

  V 6. tednu pri vajah obravnavamo AVL drevo in rdeče-črno drevo. Implementiramo obe vrsti dreves za operacije iskanja, vstavljanja in brisanja elementa.

  
  

  • Vaje 6.teden File Uploaded 7/04/20, 09:48
  • Posnetek vaj 6. tedna URL
• 7. vaje (14. 4 - 20. 4)
  

  7. vaje (14. 4 - 20. 4)

  V 7. tednu pri vajah obravnavamo B, B+, in TTF drevesa.
  

  • Vaje 7.teden File Uploaded 13/04/20, 22:56
  • Posnetek vaj 7. tedna - prvi del URL
  • Posnetek vaj 7. tedna - drugi del URL
  • Posnetek vaj 7. tedna - tretji del URL
• 8. vaje (20. 4 - 27. 4)
  

  8. vaje (20. 4 - 27. 4)

  V 8. tednu pri vajah obravnavamo prioritetno vrsto in zgoščeno tabelo.
  

  • Vaje 8.teden File Uploaded 20/04/20, 16:31
  • Posnetek vaj 8. tedna - prvi del URL
  • Posnetek vaj 8. tedna - drugi del URL
• Seminarska naloga 2
  

  Seminarska naloga 2

  • Testni primeri File Uploaded 28/04/20, 07:54
  • Posnetek predstavitve druge seminarske naloge URL
  • Seminarska naloga (angl.) File Uploaded 6/05/20, 10:33
  • Naloga File Uploaded 7/05/20, 11:38
  • Seminarska naloga 2 Assignment
• 9. vaje (5. 5. - 11. 5.)
  

  9. vaje (5. 5. - 11. 5.)

  NP-polni problemi: Hamiltonov cikel, problem izpolnjivosti, barvanje grafov, problem razdelitve množice, problem vsote podmnožice. Primeri navidez podobnih problemov, kjer so eni lahki, drugi pa težki. Prevedbe. Osnovna algoritma za reševanje NP problemov.
  

  • Vaje 9. teden File Uploaded 21/05/20, 10:09
  • Posnetek vaj 9. tedna URL
• 10. vaje (12. 5 - 18. 5)
  

  10. vaje (12. 5 - 18. 5)

  Dinamično programiranje
  

  • Vaje 10.teden File Uploaded 12/05/20, 08:34
  • Posnetek vaj 10. tedna - prvi del URL
  • Posnetek vaj 10. tedna - drugi del URL
• Seminarska naloga 3
  

  Seminarska naloga 3

  Tema seminarske naloge je polnjenje baterije telefona na potovanju. Ugotoviti je treba najmanjše število polnjenj, da baterija vzdrži skozi celotno potovanje. Rešitev je mogoče implementirati z dinamičnim programiranjem, a to ni edini, in tudi ne nujno najučinkovitejši pristop.
  

  • Opis seminarske naloge 3 File Uploaded 19/05/20, 10:29
  • Seminarska naloga 3 Assignment
• 12. vaje (26 . 5 - 1. 6)
  

  12. vaje (26 . 5 - 1. 6)

  • Vaje 12. teden File Uploaded 26/05/20, 08:26
  • Vaje 12.teden predstavitev File Uploaded 28/05/20, 13:36
  • Posnetek vaj 12. tedna - prvi del URL
  • Posnetek vaj 12. tedna - drugi del URL