NPRG062 Introduction to Algorithms (winter 2020-21)

Instructor: Adam Dingle

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 10:40 - 12:10. The first lecture will be on Wednesday, September 30.
There is also a tutorial every Wednesday from 13:10 – 14:10. In the tutorial sessions we will solve various exercises together. The first tutorial will be on Wednesday, September 30.

For at least the month of October, all lectures and tutorials will take place on Zoom.

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 30 (lecture video) (notes) (exercises): Course overview. Mathematical terminology. Powers of two and ten. Logarithms. Divisibility. Quotient and remainder. Converting to hours, minutes and seconds.
October 7 (lecture 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.
October 14 (lecture video) (notes) (exercises): The fundamental theorem of arithmetic. Prime factorization. Limits. 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 21 (lecture video) (notes) (exercises): The sieve of Eratosthenes. Sequential search in an array. Binary search for values.
October 28 (review sesson video): No lecture (Czechoslovak Independence Day)
November 4 (lecture video) (notes) (exercises): Binary search for a boundary. Bubble sort, selection sort, insertion sort. Merging sorted arrays. Mergesort.
November 11 (lecture video) (notes) (exercises): Quicksort. Linked lists.
November 18 (lecture video) (notes) (exercises): Abstract data types. Stacks. Queues. Binary trees.
November 25 (lecture video) (notes) (exercises): Sets. Binary search trees. Balanced and imbalanced trees. Hash functions.
December 2 (lecture video) (notes) (exercises): Dictionaries (maps). Hash tables. Priority queues. Heaps.
December 9 (lecture video) (notes) (exercises): Heapsort. Graph representations.
December 16 (lecture video) (notes) (exercises): Depth-first search. Breadth-first search.
December 23, 30: No lecture (winter vacation).
January 6 (lecture video) (notes) (exercises): Searching in a state space. Infix, prefix and postfix notations. Expression trees. Parsing arithmetic expressions.