Textbook: Michael T. Goodrich,
Roberto Tamassia. Data
Structures and Algorithms in Java.
John Wiley and
Learning objects from 2011
- Algorithms, properties of algorithms, time complexity
and space complexity, asymptotic behaviour of functions,
analysis of algorithms, main complexity classes.
- 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.
- Abstract data types. Stacks and queues. Reverse Polish
Notation (RPN). Linked lists and other pointer structures.
- 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.
- 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.
- Recursion: Hanoi towers, elimination of recursion, tail
recursion. Exhaustive search: 8 queens problem, knapsack
- Binary search trees, AVL trees, red-black trees,
binomial trees. B-trees. Heaps, heapsort.
- String algorithms: exact matching (linear,
Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp).
- Coding and compressing, coding schemes: Huffman,
Shannon-Fano. Greedy algoritms: Huffman encoding.
- Dynamic programming: longest common subsequence problem.
- Correctness of algorithms: preconditions,
postconditions, loop invariants, weakest precondition,
structural rules, total correctness and partial
correctness, halting problem.
- Introduction. Java. Java API, collections.
- Searching and sorting.
- Stack and Reverse Polish Notation.
- Abstract data types - implementation.
- Graphs (individual task, written report!).
Homeworks (every second week) and other materials reside in
Course password for Moodle is available through the student
information system: https://itcollege.ois.ee/
, also all "official" grades are there.
Homeworks 50%, Exam (written)
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.