NPRG062 Introduction to Algorithms (winter 2022-3)

Instructors:

Adam Dingle (lecture)
Tomáš Bílý, Nese Günes, Jiří Šejnoha (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 Tuesday from 9:00 - 10:30 in room S5.
There are three tutorial sessions:
- every Monday from 14:00 – 14:50 in room SU2 (teacher: Tomáš Bílý)
- every Tuesday from 15:40 – 16:30 in room SW2 (teacher: Nese Günes)
- every Wednesday from 9:50 - 10:40 in room SW2 (teacher: Jiří Šejnoha)
Martin Koutecký and Ilia Zavidnyi will hold programming mentoring sessions every Thursday at 17:20 in room S11.
Adam Dingle will hold office hours every Friday from 15:30 – 16:30 in room S510.

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, 2023 at the end of the exam period:

Complete a number of homework assignments through the semester. You must earn at least 70% of the total possible points. Any points that you earn over 85% (up to a maximum of 15%) will be applied as bonus points to your exam score when you take the exam.
Regularly attend the lectures and tutorials and participate in class.

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

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