NPRG062 Introduction to Algorithms (winter 2025-6)

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 Thursday from 9:00 - 10:30 in room S9.
There are four tutorial sessions:
- every Tuesday from 12:20 – 13:05 in room N8 (teacher: Vít Šefl)
- every Tuesday from 15:40 – 16:25 in room N10 (teacher: Vít Šefl)
- every Tuesday from 15:40 – 16:25 in room N11 (teacher: Tomáš Bílý)
- every Wednesday from 14:00 - 14:45 in room N8 (teacher: Vít Šefl)
Aryan Kumar will hold a programming mentoring session every Thursday at 15:40 in room S7.
Adam Dingle will hold office hours every Friday from 13:00 - 14:00 at his office (room 405).

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