NPRG062 Introduction to Algorithms (winter 2024-5)

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 Wednesday from 9:00 - 10:30 in room S9.
There are three tutorial sessions:
- every Tuesday from 9:50 – 10:35 in room N11 (teacher: Vít Šefl)
- every Thursday from 9:50 – 10:35 in room N11 (teacher: Vít Šefl)
- every Thursday from 11:30 - 12:15 in room N8 (teacher: Tomáš Bílý)
Aryan Kumar will hold a programming mentoring session every Wednesday from 15:40 - 17:10 in room S510
Adam Dingle will hold office hours every Friday from 14:00 - 15:00 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 14, 2024 at the end of the exam period:

Complete a number 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. Any points that you earn over 90% (up to a maximum of 10%) 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.

You may not use ChatGPT, Copilot or other AI tools to generate any code 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. Least common multiple.
October 16 (notes) (exercises): Limits. Big-O notation. Analyzing a program's running time. Worst-case and best-case analysis. The sieve of Eratosthenes.
October 23: No lecture (matriculation of first-year students)
October 30 (notes) (exercises): Sequential search in an array. Binary search for values. Binary search for a boundary. Bubble sort, selection sort. Insertion sort.
November 6 (notes) (exercises): Merging sorted arrays. Mergesort. Running time of recursive functions. Quicksort.
November 13 (notes) (exercises): Abstract data types. Stacks. Queues. Linked lists. Sets. Binary trees.
November 20 (notes) (exercises): Binary search trees. Balanced and imbalanced trees. Dictionaries (maps). Dynamic arrays. Hash functions.
November 27: Hash tables. Priority queues. Binary heaps. Heapsort. Lower bounds for sorting.
December 4: Graph representations. Depth-first search. Breadth-first search. Shortest paths in a graph.
December 11: Searching in state spaces. Infix, prefix and postfix notations.
December 18: Expression trees. Parsing and evaluating arithmetic expressions. More state space searching.
December 25: No lecture (winter vacation).
January 1: No lecture (winter vacation).
January 8: Stable sorts. Sorting in linear time. Counting sort. Radix sort.