Well designed data structures and the efficient algorithms
for their processing are the very basis of computer science.
The goal of the course is to acquire the basic
principles of design and analysis of algorithms and basic and dynamic data
structures for problem solving. We will present the basic principles for
problem solving, the relation between iteration and recursion, the analysis of
time-complexity of algorithms, the concept of abstract data type and the
definition and implementation of basic abstract data types: list, set,
queue, stack, mapping, tree, dictionary, priority queue, disjunctive sets,
graph and directed graph, as well as basic algorithms for graph analysis:
searching for longest paths and searching for shortest paths in directed
graphs, and building the minimum spanning tree in undirected graphs. At the end we will present also the basic principles for proving the correctness of programs.
At the end we will present also the basic
principles for proving the correctness of programs.
Student's obligations: on time finished and
positively graded homeworks (web quizes and other reports), on time finished and positively graded two
seminar works, written exam. The exercises grade is
a joint grade for two seminar works. Each seminar work has to be finished on
time and graded positively. The precondition for positive exercises grade is
also that you achieve at least half of the points from homeworks (web quizes and
other reports). Exam is written (and optionally the oral part). The
precondition for the written exam is the positive grade from exercises. At the
written part of the exam, from the literature it is allowed to use an A4 sheet
of paper, hand written with an ordinary pencil (that can be rub out) and signed
with a ball-point pen (name, surname and the inscription student number)
(photocopies and prints are not allowed). At the end of the exam, this sheet of
paper has to be given to assistant together with the written exam. The
precondition for the (optional) oral exam is positive grade from written exam. Final
grade is combined from the exercise grade (50%) and the exam grade (50%). Both
parts need to be positive.
Recommended literature for foreign
students: Cormen et al: Introduction to Algorithms, MIT press.
- nosilec: Igor Kononenko