Arvutiteaduse instituut
  1. Kursused
  2. 2018/19 sügis
  3. Algoritmika (MTAT.03.238)
EN
Logi sisse

Algoritmika 2018/19 sügis

  • Home
  • Lectures
  • Homeworks
    • Information
    • Submit
    • Plagiarism
  • Essays
  • Projects
  • Links
  • Exam

Exam in Algoritmics (MTAT.03.238)

Exam Date I - January 3rd (Thursday) @ 14-18 L2-405

Exam Date II - January 14th (Monday) @ 10-14 L2-122

For the exam you only need a pen and possibly a cheat sheet. A single one-sided A4 “cheat-sheet” is allowed. Submit it with your exam.

For repeating the material please make sure to understand the basic concepts from every set of lecture materials.

  • Complexity - the O, o, Theta, Omega, omega relations between functions, and how to prove that relationship holds.
  • Recurrences (e.g. T(n)= 2*T(n/2) + n) and use of the master theorem
  • Theoretical and practical considerations about sorting algorithms (remember the pre-course questionnaire?)
  • Binary search, array-based linear structure, linked list, skip-list
  • Binary search tree BST, balanced BST, B-tree
  • Hashing, hash functions, universal hashing, Bloom filters
  • Binary heap, binomial heap
  • Tree traversal orders and recursive and non-recursive traversal algorithms
  • Graph traversal orders (BFS, DFS, random, prioritised order) and algorithms (recursive, queue, priority queue based)
  • Shortest path, Dijkstra, A* algorithms
  • Topological sorting, maximum flow, transitive closure by matrix multiplications
  • Succinct data structures concept
  • Optimisation - finding the best "instance" or value or configuration
  • Heuristic search concepts - greedy, local search,
  • Meta-heuristics: simulated annealing, tabu-, genetic and evolutionary algorithms, differential evolution, ACO, swarm
  • Dynamic programming

Exam questions will be mostly descriptive - 4-5 "larger" questions

  • discuss the main principle of (e.g. Bloom filters, meta-heuristics, etc)
  • examples add numbers like 2,5,7,1,9,3 into BST,
  • given a graph provide the output for some algorithm,
  • prove the complexity class relation for a function;
  • etc.
  • Arvutiteaduse instituut
  • Loodus- ja täppisteaduste valdkond
  • Tartu Ülikool
Tehniliste probleemide või küsimuste korral kirjuta:

Kursuse sisu ja korralduslike küsimustega pöörduge kursuse korraldajate poole.
Õppematerjalide varalised autoriõigused kuuluvad Tartu Ülikoolile. Õppematerjalide kasutamine on lubatud autoriõiguse seaduses ettenähtud teose vaba kasutamise eesmärkidel ja tingimustel. Õppematerjalide kasutamisel on kasutaja kohustatud viitama õppematerjalide autorile.
Õppematerjalide kasutamine muudel eesmärkidel on lubatud ainult Tartu Ülikooli eelneval kirjalikul nõusolekul.
Tartu Ülikooli arvutiteaduse instituudi kursuste läbiviimist toetavad järgmised programmid:
euroopa sotsiaalfondi logo