Schedule

Lecture Title Date Time Room
1 Introduction, Growth of Functions 13/10/2004 8h15-12h B2-104
2 Representing and Manipulating Numbers 15/10/2004 8h15-12h B2-104
3 Recurrences 20/10/2004 8h15-12h B2-104
4 Probabilistic Analysis and
Randomized Algorithms
22/10/2004 8h15-12h B2-104
5 Extra Material, Sorting 27/10/2004 8h15-12h B2-109
6 Extra Material, Sorting 29/10/2004 8h15-12h B2-104
7 Sorting in Linear Time
Data Structures
3/11/2004 8h15-12h B2-104
8 Extra Material, Hashing and Hash Tables 5/11/2004 8h15-12h B2-104
9 Binary Search Trees, Red-Black Trees 10/11/2004 8h15-12h B2-104
10 Red-Black Trees, String Matching,
Solutions to implementation Exercises
12/11/2004 8h15-12h B2-104

Lecture 1 : Introduction, Growth of Functions

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.

Material: Introduction slides ps.gz/pdf and exercises ps.gz/pdf.
Growth of Functions slides ps.gz/pdf and exercises ps.gz/pdf.

Lecture 2 : Representing and Manipulating Numbers

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.

Material: Slides ps.gz/pdf and exercises ps.gz/pdf.

Solution: Suggested solution to the RGB exercise rgb.c.

Lecture 3 : Recurrences

Abstract: Introduction to recurrences and some techniques to solve them such as the substitution method, the recursion tree method, and the master method.

Material: Slides ps.gz/pdf and exercises ps.gz/pdf.

Solution: suggested solutions ps.gz/pdf.

Lecture 4 : Probabilistic Analysis and Randomized Algorithms

Abstract: Introduction to counting, probabilities, and randomized algorithms.

Reading: Chapter 5 and appendices A and C.

Material: Slides ps.gz/pdf and exercises ps.gz/pdf.

Lecture 5 : Extra Material, Sorting

Abstract: Some extra material on computing polynomials and sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quicksort).

Material: Polynomials slide ps.gz/pdf.
Sorting slides ps.gz/pdf and exercises ps.gz/pdf.
C program sort-exercise.c needed for the exercises.

Lecture 6 : Extra Material, Sorting

Abstract: Heapsort, powering numbers, and Fibonacci revisited.

Material: same as lecture 5.

Lecture 7 : Sorting in Linear Time, Data Structures

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.

Material: Sorting slides ps.gz/pdf and exercises ps.gz/pdf.
Data structure slides ps.gz/pdf and exercises ps.gz/pdf.
Needed C-file for the implementation exercise: stack-queue-exos.c.

Lecture 8 : Extra Material, Hashing and Hash Tables

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.

Material: Slides on the Linux scheduler ps.gz/pdf. Article 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.

Lecture 9 : Binary Search Trees, Red-Black Trees

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.

Material: Binary search tree slides ps.gz/pdf and exercises ps.gz/pdf.
Red-black tree slides ps.gz/pdf and exercises ps.gz/pdf.
Wikipedia on red-black trees.

Lecture 10 : Red-Black Trees, String Matching, Solutions to Implementation Exercises.

Abstract: Extra material on string matching, finish red-black trees, presentation of solutions for the previous implementation exercises.

Material: String matching slides ps.gz/pdf.

Solutions: suggested implementations for