Algoritmid ja andmestruktuurid (I231)

Ainekava

Loengud

  1. Java (kordamine)
  1. Sissejuhatus. Algoritm, algoritmi omadused ja analüüs, keerukus ja selle hindamine
  2. Otsimine ja järjestamine
  3. Abstraktsed andmetüübid, magasin ja järjekord. Ahel
  4. Puu, puu kujutamine, puu läbimine
  5. Graaf
  6. Rekursioon
  7. Kahendpuu ja kuhi
  8. AVL-puu, B-puu jt.
  9. Sõnealgoritmid
  10. Ülesannete lahendamise strateegiad, dünaamiline kavandamine
  11. Algoritmi korrektsus
  12. Kokkuvõte, kordamisküsimused

2015 kevadsemestri loenguvideod
2015 kaugõppe videod
2015 sügissemestri loenguvideod
2016 kevadsemestri õhtuõppe loenguvideod
2016 kevadsemestri kaugõppe loenguvideod
2016 sügissemestri loenguvideod
2017 kevadsemestri õhtuõppe loenguvideod
2017 kevadsemestri kaugõppe loenguvideod
2017 sügissemestri loenguvideod

Ingliskeelsed raamatud

Wiki book 1    Wiki book 2

Algoritmide visualiseerimine    Visualiseerimine2

Lisamaterjal keerukuse teema kohta

MIT kursus

coursera1 coursera2

Lisamaterjalid lugemiseks eesti keeles

Tartu Ülikool
P.Laud
J. Vilo

Praktikumid: kasutame Moodle keskkonda (registreerumise võti on "Sorteeritud") ja bitbucket koodihoidlat

Tarkvara allalaadimiseks (jdk8 ja Idea)

Töökeskkonna seadistamine

Näited

Kodutööd leiate oma rühma materjalide juurest Moodle's (hilinemisel kaotate kuni 60% punktidest, vt. ainekava !)

Kodutööde tähtajad 2017/2018 õ-.a. sügissemestri päevaõppe õppevormis:
  Kõik kodutööd tuleb kaitsta tähtajale järgnevas praktikumis.

JUnit-testid, millega kodutöid kontrollitakse
bitbucket
Koodi vormistamisest
Individuaalse ülesande vormistamisest


Algorithms and Data Structures (Estonian)

*Course in English is I707

Syllabus

Textbook: Michael T. Goodrich, Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley and Sons, Inc.
Learning objects from 2011

Topics:

  1. Algorithms, properties of algorithms, time complexity and space complexity, asymptotic behaviour of functions, analysis of algorithms, main complexity classes.
  2. Searching and sorting. Linear search, binary search, hashing. Insertion sort, binary insertion sort, quicksort, merge sort, counting sort, radix sort, bucket sort. Complexity of different methods.
  3. Abstract data types. Stacks and queues. Reverse Polish Notation (RPN). Linked lists and other pointer structures.
  4. Trees. Examples of trees - arithmetic expression tree. Traversal of trees - preorder, postorder, in-order. Forms of expression for trees - parenthetic expressions, pointer structures, textual representation. Examples of "top-down" and "bottom-up" traversal.
  5. Graphs. Directed and undirected graphs, multigraphs. Cyclic and acyclic graphs. Connected components. Strongly connected  and weakly connected graphs. Paths and cycles. Simple graphs. Matrices related to graphs: adjacency matrix, matrix of shortest pathlengths. Operations on graphs: sum, multiplication, transitive closure. Representation and implementation of graphs. Algorithms on graphs: Floyd-Warshall (lengths of shortest paths), topological sort of vertices, depth-first and breadth-first traversal, Dijkstra (shortest path), finding connected components, minimal spanning tree.
  6. Recursion: Hanoi towers, elimination of recursion, tail recursion. Exhaustive search: 8 queens problem, knapsack problem.
  7. Binary search trees, AVL trees, red-black trees, binomial trees. B-trees. Heaps, heapsort.
  8. String algorithms: exact matching (linear, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp).
  9. Coding and compressing, coding schemes: Huffman, Shannon-Fano. Greedy algoritms: Huffman encoding.
  10. Dynamic programming: longest common subsequence problem.
  11. Correctness of algorithms: preconditions, postconditions, loop invariants, weakest precondition, structural rules, total correctness and partial correctness, halting problem.
  12. Exam.

Labs:

  1. Introduction. Java. Java API, collections.
  2. Searching and sorting.
  3. Stack and Reverse Polish Notation.
  4. Abstract data types - implementation.
  5. Trees.
  6. Graphs (individual task, written report!).
  7. Coding.
Homeworks (every second week) and other materials reside in Moodle: https://moodle.hitsa.ee/
Course password for Moodle is available through the student information system: https://itcollege.ois.ee/ , also all "official" grades are there.

Grading rules:
Homeworks 50%, Exam (written) 50%.
Homework deadlines are strict - penalty -25% for delay up to 1 week, -60% for delay more than 1 week.
Homeworks have to pass all automated tests without exceptions (if the tests are provided). Any form of plagiarism leads to failure and further sanctions.

Deadlines for homeworks are in Moodle.
All homeworks are defended by student personally during the next lab after corresponding deadline.

JUnit-tests for homeworks
Code conventions
 
Student has to collect at least 25 p. (50%) from homeworks AND to prepare a written report on homework 6 to get to the final exam.

Book about graphs and complexity
MIT course
MIT course on youtube
Stanford course
Complexity book

Jaanus Pöial

Jaanus Pöial