|1||Introduction, Growth of Functions||8h15-12h||B2-104|
|2||Representing and Manipulating Numbers||8h15-12h||B2-104|
|4||Probabilistic Analysis and
|5||Extra Material, Sorting||8h15-12h||B2-109|
|6||Extra Material, Sorting||8h15-12h||B2-104|
|7||Sorting in Linear Time
|8||Extra Material, Hashing and Hash Tables||8h15-12h||B2-104|
|9||Binary Search Trees, Red-Black Trees||8h15-12h||B2-104|
|10||Red-Black Trees, String
Solutions to implementation Exercises
Abstract: Basic introduction to algorithm design, correctness of algorithms, analysis of algorithms, and asymptotic behaviours. Note: I will come back to chapter 2 when I treat sorting to avoid being redundant.
Reading: Chapters 1 and 3.
Abstract: Binary representation of integers and floats, implementation of basic operations (in processors), basic arithmetics on integers and some applications, limits of the representation (integers and floats), and optimization issues.
Reading: A chapter related to binary representation in any reasonable architecture book. The choosen course book for architecture, or one of the additional listed books is fine. Ask at the library or borrow one from me.
Solution: Suggested solution to the RGB exercise rgb.c.
Abstract: Introduction to recurrences and some techniques to solve them such as the substitution method, the recursion tree method, and the master method.
Reading: Chapter 4 and read again section 3.2.
Abstract: Introduction to counting, probabilities, and randomized algorithms.
Reading: Chapter 5 and appendices A and C.
Abstract: Some extra material on computing polynomials and sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quicksort).
Reading: Chapters 2 and 7.
Abstract: Heapsort, powering numbers, and Fibonacci revisited.
Reading: Chapter 6.
Material: same as lecture 5.
Abstract: Previous sorting algorithms were comparison sorts, here we study other kinds of sorts (counting, radix, and bucket sorts), and basic dynamic data structures such as stacks, queues, and linked lists.
Reading: Chapters 8 and 10.
Abstract: Introduction to hash functions and hash tables. The problem is to store or retrieve data in a dictionary data structure implemented efficiently as a hash table. Presentation of suggested solutions to the implementation of the different sorting algorithms. Extra material: the linux scheduling algorithm in O(1), doubly linked lists in practice, and suggested implementation for the sorting algorithms.
Reading: Chapter 11.
Slides on the Linux scheduler ps.gz/pdf.
on Linux process scheduler.
Slides on doubly linked lists ps.gz/pdf.
Slides on hashing and hash tables ps.gz/pdf and exercises ps.gz/pdf.
Also lecture 7 and lecture 8 from the MIT lecture notes related to hashing and hash tables.
Solution: almost C code for insertion and rehashing of a hash table whose size is a power of 2.
Abstract: Introduction to binary search trees that can be used as dictionary or priority queues, and a particular search tree structure (red-black tree) that has the property to keep the tree balanced. Suggested solution to the hash table pseudo-code exercise.
Reading: Chapters 12 and 13.
Abstract: Extra material on string matching, finish red-black trees, presentation of solutions for the previous implementation exercises.
Reading: Wikipedia page on string searching.
Solutions: suggested implementations for