B_ADS Algorithms and Data Structures

University of Finance and Administration
Summer 2019
Extent and Intensity
2/2/0. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ondřej Čepek, Ph.D. (seminar tutor), RNDr. Petr Tesař, Ph.D. (deputy)
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 10:30–11:14 E129, Mon 11:15–12:00 E129, except Mon 18. 2. ; and Wed 27. 2. 10:30–12:00 E127, O. Čepek
B_ADS/pAPH: Mon 8:45–9:29 E129, Mon 9:30–10:15 E129, except Mon 18. 2. ; and Wed 27. 2. 8:45–10:15 E127, O. Čepek
B_ADS/vAPH: Fri 15. 2. 15:45–17:15 E223, 17:30–19:00 E223, Fri 15. 3. 14:00–15:30 E223, 15:45–17:15 E223, Fri 12. 4. 14:00–15:30 E223, 15:45–17:15 E223, O. Čepek
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).
  • 1.přednáška Means for the description of algorithms and operations on data structures (asymptotic notation), examples of asymptotic notation. Repetition of simple sorting algorithms. Exercise: Examples of analyzing the complexity of specific (sorting) algorithms.
  • 2.přednáška Divide-and-conquer algorithms and their analysis by solving recurrences. Exercise: Analysis of specific algorithms: binary search, mergesort and quicksort.
  • 3.přednáška Divide-and-conquer algorithms and their analysis (continued): search in median   linear time, Strassen algorithm for matrix multiplication. Exercise: The particular recurrence equations, using Strassenova algorithm for rectangular matrices.
  • 4.přednáška Lower bounds sequential algorithms, decision trees (applications: lower bound for sorting by comparison) Exercise: Design of decision trees for specific algorithms.
  • 5.přednáška Graph algorithms: BFS (breadth search) and DFS (depth-first search), version for undirected and directed graphs, test connection graph. Exercise: Using the BFS and DFS for a particular graph problems (testing bipartitnosti chart, the decision on the existence of     confluence in the graph).
  • 6.přednáška Graph Algorithms (continued): search dvousouvislých components undirected graph. Exercise: Use the memorized graph algorithms for solving other problems in undirected and directed graphs.
  • 7.přednáška Graph Algorithms (continued): topological sorting, detection of strongly connected components of directed graph. Exercise: Use the memorized graph algorithms for solving other problems in undirected and directed graphs.
  • 8.přednáška Search in   text using finite automata: Aho-Corasick algorithm and its analysis. Exercise: Design of specific search machines for different sets of search samples (words).
  • 9.přednáška Parallel Algorithms (continued): transposition and sorting networks. Exercise: Design of concrete sorting network.
  • 10.přednáška Problems solved deterministically in polynomial time   (Class P), problems solvable nondeterministically in polynomial time   (Class NP), polynomial. Exercise: Examples of specific polynomial transformation between problems.
  • 11.přednáška NP-completeness. Definitions, proof procedures, examples of NP-complete problems. Exercise: Other examples of NP-complete problems and evidence of NP-completeness.
  • 12.přednáška Approximation algorithms. Exercise: Design simple 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
  • IS VŠFS → osobní administrativa → ProQuest
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: 12 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 2020, Summer 2021, Summer 2022, Summer 2023, Summer 2024, Summer 2025.
  • Enrolment Statistics (Summer 2019, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/summer2019/B_ADS