VSFS:B_ADS Algorithms and Data Structures - Course Information

B_ADS Algorithms and Data Structures

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: Ing. Barbora Ptáčková

Timetable of Seminar Groups

B_ADS/cAPH: Mon 10:30–11:14 E129, Mon 11:15–12:00 E129, except Mon 7. 3., except Mon 18. 4., except Mon 25. 4. ; and Thu 18. 2. 10:30–12:00 E306, Thu 25. 2. 10:30–12:00 E007KC, Thu 3. 3. 10:30–12:00 E306, O. Čepek
B_ADS/pAPH: Mon 8:45–9:29 E129, Mon 9:30–10:15 E129, except Mon 7. 3., except Mon 18. 4., except Mon 25. 4. ; and Thu 18. 2. 8:45–10:15 E306, Thu 25. 2. 8:45–10:15 E007KC, Thu 3. 3. 8:45–10:15 E306, 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.

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

• Enrolment Statistics (Summer 2016, recent)
  
• Permalink: https://is.vsfs.cz/course/vsfs/summer2016/B_ADS