B_ADS Algorithms and Data Structures

University of Finance and Administration
Summer 2014
Extent and Intensity
2/2. 6 credit(s). Type of Completion: zk (examination).
Teacher(s)
prof. RNDr. Ondřej Čepek, 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: Dagmar Medová, DiS.
Timetable of Seminar Groups
B_ADS/cAPH: Tue 10:30–11:14 E129, Tue 11:15–12:00 E129, O. Čepek
B_ADS/pAPH: Tue 8:45–9:29 E129, Tue 9:30–10:15 E129, O. Čepek
B_ADS/vAPH: Fri 7. 3. 17:15–18:45 E126, Sat 8. 3. 14:00–15:30 E126, 15:45–17:15 E126, Fri 21. 3. 15:30–17:00 E126, 17:15–18:45 E126, Fri 4. 4. 12:00–13:30 E126, O. Čepek
Prerequisites (in Czech)
Úvod do programování.
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.
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 2015, Summer 2016, Summer 2017, Summer 2018, Summer 2019, Summer 2020, Summer 2021, Summer 2022, Summer 2023, Summer 2024, Summer 2025.
  • Enrolment Statistics (Summer 2014, recent)
  • Permalink: https://is.vsfs.cz/course/vsfs/summer2014/B_ADS