NPRG062 Introduction to Algorithms (winter 2023-4)

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 Tuesday from 10:40 - 12:10 in room S9.
There are three tutorial sessions:
- every Thursday from 10:40 – 11:30 in room SU2 (teacher: Vít Šefl)
- every Thursday from 13:10 – 14:00 in room SU2 (teacher: Tomáš Bílý)
- every Thursday from 14:00 - 14:50 in room SW2 (teacher: Vít Šefl)
Aryan Kumar holds a programming mentoring session every Thursday at 17:10 in room S11.
Adam Dingle holds office hours every Friday from 14:00 – 15:00 in room S8.

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 16, 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 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 3 (notes) (exercises): Powers of two and ten. Logarithms. Divisibility. Quotient and remainder. Decimal representation. Numbers in different bases. Converting between bases.
October 10 (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. Limits.
October 17 (notes) (exercises): Big-O notation. Analyzing a program's running time. Worst-case and best-case analysis. The sieve of Eratosthenes.
October 24 (notes) (exercises): Sequential search in an array. Binary search for values. Binary search for a boundary. Bubble sort, selection sort.
October 31 (notes) (exercises): Insertion sort. Running time of recursive functions. Merging sorted arrays. Mergesort.
November 7 (notes) (exercises): Quicksort. Abstract data types. Stacks. Queues. Linked lists.
November 14 (notes) (exercises): Sets. Binary search trees. Balanced and imbalanced trees.
November 21 (notes) (exercises): Dictionaries (maps). Dynamic arrays. Hash functions.
November 28 (notes) (exercises): Hash tables. Priority queues. Binary heaps. Heapsort.
December 5 (notes) (exercises): Lower bounds for sorting. Graph representations. Depth-first search.
December 12 (notes) (exercises): Breadth-first search. Shortest paths in a graph. Searching in state spaces. Infix, prefix and postfix notations.
December 19 (notes) (exercises): Expression trees. Parsing and evaluating arithmetic expressions. More state space searching.
December 26: No lecture (winter vacation).
January 2: No lecture (winter vacation).
January 9 (notes) (exercises): Stable sorts. Sorting in linear time. Counting sort. Radix sort.