Introduction to Algorithms - NPRG062
Title: Algoritmizace
Guaranteed by: Department of Software and Computer Science Education (32-KSVI)
Faculty: Faculty of Mathematics and Physics
Actual: from 2022
Semester: winter
E-Credits: 4
Hours per week, examination: winter s.:2/1, C+Ex [HT]
Capacity: unlimited
Min. number of students: unlimited
4EU+: no
Virtual mobility / capacity: no
State of the course: taught
Language: Czech, English
Teaching methods: full-time
Guarantor: doc. RNDr. Tomáš Dvořák, CSc.
doc. RNDr. Pavel Töpfer, CSc.
Adam Dingle, M.Sc.
Teacher(s): Mgr. Tomáš Bílý
Adam Dingle, M.Sc.
doc. RNDr. Tomáš Dvořák, CSc.
RNDr. Tomáš Holan, Ph.D.
Mgr. Martin Mareš, Ph.D.
Mgr. Jakub Mestek
RNDr. František Mráz, CSc.
RNDr. Martin Pergel, Ph.D.
Mgr. Klára Pešková, Ph.D.
Mgr. Vít Šefl
Mgr. Jiří Šejnoha
RNDr. Michal Töpfer
doc. RNDr. Pavel Töpfer, CSc.
Co-requisite : NPRG030
Incompatibility : NMIN102, NMIN112
Is co-requisite for: NPRG030
Is incompatible with: NMIN112
Opinion survey results   Examination dates   WS schedule   Noticeboard   
Annotation -
An introductory course on fundamental algorithms, algorithmic complexity and data structures for first-year students of computer science and computer science education.
Last update: Töpfer Pavel, doc. RNDr., CSc. (30.10.2019)
Course completion requirements -

The course is concluded with a credit and a final exam. Obtaining a credit is a necessary prerequisite for an enrollment for the final exam.

The credit is awarded upon successfully completing the following requirements:

  • active participation in tutorials
  • obtaining a required score from homework assignments submitted by the deadline specified by the instructor

Due to the nature of the requirements, a failed attempt cannot be repeated as is possible for exams. The instructor may specify conditions whereby a student can make up for missing homework assignments.

The final exam consists of a written and an oral part. A student has three chances to pass the exam.

The exam is organized separately for students attending the lectures in Czech and in English. A student who is registered for one of the lectures in Czech may not take the exam in English.

Cheating on an exam or a homework assignment may result in automatically failing the course.

Last update: Dingle Adam, M.Sc. (27.09.2024)
Literature -

Thomas H. Cormen,‎ Charles E. Leiserson,‎ Ronald L. Rivest,‎ Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, Cambridge, MA 2022

Last update: Dvořák Tomáš, doc. RNDr., CSc. (29.09.2022)
Syllabus -
Algorithms and their efficiency.

  • Algorithm - properties, correctness, efficiency comparison.
  • Time and space complexity, asymptotic complexity, Big O notation.
  • Worst case, best case and average case analysis.

Basic algorithms and techniques.

  • Divisibility - Euclid's algorithm, prime factorization.
  • Prime numbers - primality testing, the sieve of Eratosthenes.
  • Decomposing numbers into digits, numeral systems conversion.
  • Higher-precision arithmetic ("long numbers").
  • Horner's scheme, fast exponentiation.

Basic data structures.

  • Array searching - sequential, binary.
  • Abstract data types: stack, queue, priority queue, dictionary.
  • Hash tables - principle, resolving collisions.
  • Heap. Binary search tree, balancing principle.

Sorting.

  • Internal sorting - direct methods (SelectSort, InsertSort, BubbleSort).
  • HeapSort, QuickSort.
  • Lower bounds for sorting.
  • Sorting in linear time (CountingSort, BucketSort, RadixSort).
  • Note about external sorting.

Recursion.

  • Recursion - principle, examples, efficiency.
  • Binary tree - representation, searching, applications.
  • Representing arithmetic expressions through binary trees.
  • Infix, prefix and postfix notations - evaluation, conversion.
  • General trees - representation, traversal, applications.

State space search.

  • Backtracking.
  • Depth first search (DFS) and breadth first search (BFS) - principle, applications, implementation.
  • Improving performace through pruning and heuristics.
  • Game tree, minimax, alpha-beta pruning.

Basic graph algorithms.

  • Representation of graphs.
  • DFS, BFS and their applications.

General methods of algorithms design.

  • Speeding by precomputation.
  • Greedy algorithm.
  • Divide and conquer.
  • Memoization.
Last update: Dvořák Tomáš, doc. RNDr., CSc. (23.09.2019)