NPRG062 Introduction to Algorithms (winter 2026-7)

Instructors:

Adam Dingle (lecture)
Tomáš Bílý, Vít Šefl (tutorials)

This course is a fast-paced introduction to fundamental algorithms, algorithmic complexity, and data structures.

Lectures and other meetings

The weekly lecture for this class takes place every Monday from 10:40 - 12:10 in room S5.
There are two tutorial sessions:
- every Tuesday from 9:00 – 9:45 in room N11 (teacher: Vít Šefl)
- every Thursday from 11:30 – 12:15 in room N11 (teacher: Tomáš Bílý)
Danial Mohebbi will hold a programming mentoring session every Thursday at 15:40 in room N9.
Adam Dingle will hold office hours every Friday from 13:00 - 14:00 at his office (room 405), starting on Friday, October 9.

Requirements

This course includes both a pass/fail credit and a graded final exam.

To receive the credit, you must fulfill the following requirements by Friday, February 12, 2027 at the end of the exam period:

Complete a series of homework assignments through the semester. The tutorial teachers will assign these exercises weekly, and you can submit your solutions to the ReCodEx automated grading system. You must earn at least 70% of the total possible points.
Regularly attend the lectures and tutorials and participate in class.

You must complete the credit before you can enroll for the exam.

You may not use ChatGPT, Copilot or other AI tools to generate any code or documentation that you submit in any homework assignment in this course. Any use of such tools is considered cheating and may disqualify you from passing the class.

Textbooks

Bradley Miller et al, Problem Solving with Algorithms and Data Structures Using Python, Second Edition (Franklin, Beedle & Associates, 2011)
Thomas Cormen et al, Introduction to Algorithms, Fourth Edition (MIT Press, 2022)

The Miller text is available online (see the link above). There are many copies of the Cormen text in the MFF library on the first floor.

Syllabus

This is a rough map of the ground we plan to cover in this class. (It will probably evolve as the semester goes on.)

October 5 (notes) (exercises): Powers of two and ten. Logarithms. Divisibility. Quotient and remainder. Decimal representation. Numbers in different bases. Converting between bases.
October 12 (notes) (exercises): Prime numbers. Primality testing using trial division. The fundamental theorem of arithmetic. Prime factorization. Greatest common divisor. Euclid's algorithm. Least common multiple.
October 19 (notes) (exercises): Limits. Big-O notation. Analyzing a program's running time. Worst-case and best-case analysis. The sieve of Eratosthenes.
October 26: Sequential search in an array. Binary search for values. Binary search for a boundary. Bubble sort, selection sort.
November 2: Insertion sort. Running time of recursive functions. Merging sorted arrays. Mergesort.
November 9: Quicksort. Abstract data types. Stacks. Queues. Linked lists.
November 16: Implementing stacks and queues with linked lists. Sets. Binary trees. Binary search trees.
November 23: Removing from a binary tree. Balanced and imbalanced trees. Dictionaries (maps). Dynamic arrays.
November 30: Hash functions. Hash tables.
December 7: Priority queues. Binary heaps. Heapsort.
December 14: Graph representations. Depth-first search. Breadth-first search. Shortest paths in a graph. Searching in state spaces.
December 18: No lecture (winter vacation).
December 25: No lecture (winter vacation).
January 4: Infix, prefix and postfix notations. Expression trees. Parsing and evaluating arithmetic expressions. Stable sorts. Lower bounds for sorting. Sorting in linear time. Counting sort. Radix sort.