NPRG062 Introduction to Algorithms (winter 2021-2)

Instructors:

Adam Dingle (lecture, tutorials)
Tibor Rózsa (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 11:30 – 13:00 in room N2 in Troja. (SIS shows a different time and place, but we moved to N2 starting Dec 14.)
There are two tutorial sessions:
- every Wednesday from 9:00 – 9:45 in room N11 in Troja (teacher: Adam Dingle)
- every Thursday from 14:50 - 15:35 in room N11 in Troja (teacher: Tibor Rózsa)
All lectures and tutorials also take place simultaneously on Zoom. We will send Zoom login information to all students before classes start.
Adam Dingle holds office hours every Monday from 9:00 – 10:00 in room N207 in Troja.
Martin Koutecký holds programming mentoring sessions every Tuesday afternoon from 14:50 – 16:20 in room N207 in Troja.

Requirements

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

To receive the credit, you must fulfill the following requirements:

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. The final exam includes both a written part and an oral part. The grade for the exam is based on both parts.

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, Third Edition (MIT Press, 2009)

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.

To access any of the videos below, use our Zoom meeting ID and passcode (not your CAS login) as the username/password.

September 29 (Wed tutorial video) (notes) (exercises): Mathematical terminology. Powers of two and ten. Logarithms. Divisibility. Quotient and remainder.
October 5 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Decimal representation. Splitting an integer into digits. Joining digits to form an integer. Numbers in different bases. Converting between bases. Prime numbers. Primality testing using trial division. The fundamental theorem of arithmetic. Prime factorization.
October 12 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Limits. Big-O notation. Analyzing a program's running time. Worst-case and best-case analysis. Greatest common divisor. Euclid's algorithm.
October 19 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Least common multiple. The sieve of Eratosthenes. Sequential search in an array. Binary search for values.
October 26 (exercises): No lecture (matriculation ceremony)
November 2 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Binary search for a boundary. Bubble sort, selection sort, insertion sort.
November 9 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Running time of recursive functions. Merging sorted arrays. Mergesort. Quicksort.
November 16 (lecture video) (Thurs tutorial video) (notes) (exercises): Abstract data types. Stacks. Queues. Linked lists.
November 23 (Wed tutorial video) (Thurs tutorial video): No lecture (Doors Open Day)
November 30 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Sets. Binary trees. Binary search trees. Balanced and imbalanced trees. Dictionaries (maps).
December 7 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Hash functions. Hash tables. Priority queues.
December 14 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Binary heaps. Heapsort. Graph representations. Depth-first search.
December 21 (lecture video) (Wed tutorial video) (notes) (exercises): Breadth-first search. Searching in state spaces. Infix, prefix and postfix notations.
December 28: No lecture (winter vacation).
January 4 (lecture video) (Wed tutorial video) (Thurs tutorial video) (notes) (exercises): Expression trees. Parsing and evaluating arithmetic expressions. Lower bounds for sorting. Sorting in linear time.