NPRG062 Introduction to Algorithms (winter 2019-20)

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 Monday from 14:00 - 15:30 in room S11. The first lecture will be on Monday, October 7.
There is also a semi-weekly tutorial ("cvičení") every second Wednesday from 14:00 – 15:30 in room S10. In the tutorial sessions we will solve various exercises together. The first tutorial will be on Wednesday, October 2.

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.

Extra help

Two teachers (Martin Koutecký and Vašek Končický) will lead mentoring sessions in computer science and math on Thursdays from 15:40 - 18:50 in room S510 on the fifth floor.

Feel free to stop by my office hours (Fridays from 13:00 - 14:30 in room 405).

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:

October 3 (notes) (exercises): Course overview. Divisibility. Quotient and remainder. Converting to hours, minutes and seconds. Decimal representation. Splitting an integer into digits. Joining digits to form an integer.
October 7 (notes): Numbers in different bases. Converting between bases. Prime numbers. Primality testing using trial division. The fundamental theorem of arithmetic. Prime factorization.
October 14 (notes) (exercises): Time complexity, 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 (notes): The sieve of Eratosthenes. Sequential search in an array. Binary search for values. Binary search for a boundary. Bubble sort, insertion sort.
October 28 (exercises): No lecture (Czechoslovak Independence Day)
November 4 (notes): Recursion. The Tower of Hanoi. Divide and conquer. Merging sorted arrays. Mergesort.
November 11 (notes) (exercises): Quicksort. Abstract data types. Stacks. Queues. Linked lists.
November 18 (notes): Recursion on linked lists. Sets. Dictionaries (maps). Binary trees. Binary search trees. Balanced and imbalanced trees.
November 25 (notes) (exercises): Hash functions. Hash tables.
December 2 (notes): Priority queues. Heaps. Heapsort. Infix, prefix and postfix notations.
December 9 (notes) (exercises): Expression trees. Parsing arithmetic expressions. Graph representations. Depth-first search.
December 16 (notes) (exercises): Breadth-first search. Replacing recursion with iteration.
December 23, 30: No lecture (winter vacation).
January 6 (notes) (exercises): Lower bounds for sorting. Sorting in linear time: counting sort, radix sort. Exhaustive search via recursion. Generating permutations and combinations.