Subject Program: "Algorithms and Data Structures"
Name in Estonian: "Algoritmid ja andmestruktuurid"
Subject code: I707
Study language: English
Credit points: 5 ECTS
Grading method: Exam
Academician: PhD Jaanus Pöial
Required subjects: I700 Basic Programming

Aim of the subject
Role of the course in curricula is to develop algorithmic thinking and programming skills of students, also to deepen their understanding of methods to analyse and solve algorithmic problems.

Abstract
This course provides an introduction to algorithms and data structures, also their analysis and implementation in the Java programming language. It covers techniques for solving common algorithmic problems – searching, sorting, data organization, using recursion, backtracking, dynamic programming, exhaustive search, text algorithms, etc. Classical data structures are presented: linked list, stack, queue, hash table, tree, binary tree, heap, graph, etc.

Learning outcomes
1. Student is familiar with basic data structures (linked list, stack, queue, hash table, tree, binary tree, heap, graph), knows their properties, appropriate terminology and algorithms or techniques related to these structures (traversal methods, path finding, searching, sorting, “greedy” algorithms, recursion, dynamic programming, backtracking, etc.). Student is familiar with basic classical algorithms covered in lectures. Student is able to analyse and estimate the time and space complexity of algorithms.
Threshold: Test result > 50% 	 
2. Student knows the Java programming language and appropriate development tools on the level that allows implementing algorithms and data structures efficiently. Student is able to develop and analyse algorithms for solving problems covered in the course. Student can write a technical report about her individual programming task, knows the coding conventions and principles of documentation.
Threshold: Summary result from all homeworks >50% and individual programming task (written report compulsory) passed.

Schedule	 
Lecture – 24h; Practice – 16h (every 2nd week); E-study – 10h; Individual work – 80h

Homeworks (programming task every second week):
1) Introduction, Java API, collections - 2h;
2) Searching and sorting - 6h;
3) Stack, queue, reverse Polish notation - 4h;
4) Abstract data types - implementation - 4h;
5) Trees - 8h;
6) Graphs (individual task, written report) - 16h;
7) Advanced programming techniques - 10h.
Homeworks are defended by students during the labs.

Mandatory literature
Michael T. Goodrich, Roberto Tamassia. Data Structures and Algorithms in Java. John Wiley and Sons.

Course homepage: http://enos.itcollege.ee/%7ejpoial/algorithms/

Assessment methods
Grading rules: homeworks 50%, final exam (written) 50%.
Homework no 6 (individual task) is compulsory and a proper written report has to be provided.
At least 25 points from the homeworks in total is needed to pass.
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. All homeworks are defended by student personally during the next lab after corresponding deadline.

Final exam consists of theoretical part (test) and small programming tasks, Moodle learning environment is used, time 150 min.
Final exam is arranged in computer classroom (Moodle environment) and takes 3 hours.

Equipment and software needed: Computer classroom with Java SE, development tools familiar to students (e.g. Eclipse, IntelliJ), Junit, git.

Topics
1. Algorithms, properties of algorithms, time complexity and space complexity, asymptotic behaviour of functions, analysis of algorithms, complexity classes. 6h
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. 14h
3. Abstract data types. Stacks and queues. Reverse Polish notation (RPN). Linked lists and other pointer structures. 12h
4. Trees. Examples of trees - arithmetic expression tree. Traversal of trees – pre-order, post-order, in-order. Forms of expression for trees - parenthetic expressions, pointer structures, textual representation. Examples of "top-down" and "bottom-up" traversal. 12h
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. 30h
6. Recursion: Hanoi towers, elimination of recursion, tail recursion. Exhaustive search: 8 queens problem, knapsack problem, branch and bound method. 14h
7. Binary search trees, AVL trees, red-black trees, binomial trees. B-trees. Heaps, heapsort. 16h
8. String algorithms: exact matching (linear, Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp). 8h
9. Coding and compressing, coding schemes: Huffman, Shannon-Fano. Greedy algoritms: Huffman encoding. 6h
10. Dynamic programming: longest common subsequence problem. 4h
11. Correctness of algorithms: preconditions, postconditions, loop invariants, weakest precondition, structural rules, total correctness and partial correctness, halting problem. 6h
12. Reflection of the course, final remarks. 2h