B_ADS Algorithms and Data Structures

University of Finance and Administration
Summer 2020
Extent and Intensity
2/2. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
RNDr. Petr Tesař, Ph.D. (seminar tutor)
Guaranteed by
prof. RNDr. Ondřej Čepek, Ph.D.
Department of Computer Science and Mathematics – Departments – University of Finance and Administration
Contact Person: Ivana Plačková
Timetable of Seminar Groups
B_ADS/cAPH: Mon 17:30–18:14 E223, Mon 18:15–19:00 E223, P. Tesař
B_ADS/pAPH: Mon 15:45–16:29 E223, Mon 16:30–17:15 E223, P. Tesař
B_ADS/vAPH: Fri 13. 3. 15:45–17:15 E227, Fri 27. 3. 14:00–15:30 E128, 15:45–17:15 E128, Sat 18. 4. 14:00–15:30 E228, 15:45–17:15 E228, Fri 24. 4. 14:00–15:30 E228, 15:45–17:15 E228, P. Tesař
Prerequisites
There are no prerequisites for this course.
Course Enrolment Limitations
The course is offered to students of any study field.
Course objectives
The objective of the course is to give students an overview of common types of algorithms and to familiarize them with the theory of computational complexity.
The students will understand different types of algorithms (sequential and parallel, deterministic and probabilistic, optimization and approximation). Each type is explained with examples of specific algorithms. An emphasis is given to an analysis of their time complexity. The lecture also covers an introduction to computational complexity: classes P and NP are introduced, polynomial reducibility for decision problems defined, and the methodology of NP-completeness proofs explained.
Learning outcomes
After finishing this course students will be capable of:
- designing and efficient implementation of simple polynomial time algorithms
- designing data structures for an efficient implementation of simple polynomial time algorithms
- analyzing the time and space complexity of concrete algorithms with polynomial complexity;
- recognizing computationally intractable problems.
Syllabus
  • This curriculum is designed for full-time study, course of instruction for part-time study is given in the study material in the form of methodological sheets (ML).
  • 1st. lecture Overview of definitions of terms, data structures, means for describing complexity of algorithms, example of complexity calculation.
  • 2nd. lecture Sets - definition, graphs - definition.
  • 3rd. lecture Complexity of arithmetic operations, simple sorting algorithms, complex sorting algorithms not based on divide and conquer principle.
  • 4th. lecture Divide and rule algorithms, solution of recurrent equations, divide and rule algorithms for searching, sorting and arithmetic, Strassen algorithm for matrix multiplication.
  • 5th. lecture Text search using finite automata - Aho-Corasick algorithm and its analysis.
  • 6th. lecture Graph algorithms BFS (scan in width), graph algorithms DFS (scan in depth), graph connection testing., Graph algorithms - search for continuous components of undirected graph.
  • 7th. lecture Graph algorithms (cont.): Topological sorting, detection of strongly connected components of oriented graph.
  • 8th. lecture Graph algorithms - extreme problems
  • 9th. lecture Parallel algorithms - multiplication of matrices on abstract parallel machine PRAM, testing of reachability in a graph.
  • 10th. lecture Parallel algorithms (continued): transposition and sorting networks. Graph algorithms - minimum spanning tree
  • 11th. lecture Problems solvable deterministically in polynomial time (class P), problems solvable nondeterministically in polynomial time (class NP), NP-complete problems. polynomial transferability.
  • 12th. lecture Approximation algorithms.
Literature
  • Povinná literatura
  • A.Koubková, J.Pavelka: Úvod do teoretické informatiky, Matfyzpress 1998 (aktualizované vydání 2003), ISBN: 80-85863-33-2
  • Doporučená literatura
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 2nd. Ed., MIT Press/McGraw Hill, 2001. ISBN: 0-262-03293-7
  • Další zdroje
  • www.vsfs.cz/knihovna
  • www.knihovna.vsfs.cz/info/volne_eiz.html
Teaching methods
Type of teaching: Teaching consists of lectures and exercises in   full time and managed through group consultations in   combined studies.
The scope of compulsory participation in education: Minimum mandatory participation in exercises in full-time is   75%, the controlled group consultations in   50% of the combined studies. Students who fail to meet mandatory scope of participation, may be given during the semester   additional study obligations (to the extent that will demonstrate academic achievement and acquired competencies necessary for successful completion of course).
Assessment methods
Course completion: The course is concluded with a credit and examination. The test is in written form and the writing is available for   90 minutes. Credit certifying fulfillment of the course requirements.
Language of instruction
Czech
Further comments (probably available only in Czech)
The course can also be completed outside the examination period.
Information on the extent and intensity of the course: 14 hodin KS/semestr.
Teacher's information
http://kti.mff.cuni.cz/~cepek/vyuka.html
The course is also listed under the following terms Winter 2007, Summer 2008, Winter 2008, Summer 2009, Summer 2010, Summer 2011, summer 2012, Summer 2013, Summer 2014, Summer 2015, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2021, Summer 2022, Summer 2023, Summer 2024, Summer 2025.
  • Enrolment Statistics (Summer 2020, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/summer2020/B_ADS