Lecture | Title | Date | Time | Room |
---|---|---|---|---|
1 | Introduction, Growth of Functions | 8h15-12h | B2-109 | |
2 | Representing and Manipulating Numbers | 8h15-12h | E3-209 | |
3 | Recurrences | 8h15-12h | B2-109 | |
4 | Probabilistic Analysis and Randomized Algorithms |
8h15-12h | B2-109 | |
5 | Extra Material, Sorting | 8h15-12h | NJ6a 1.44 | |
6 | Extra Material, Sorting | 8h15-12h | B2-109 | |
7 | Sorting in Linear Time Data Structures |
8h15-12h | B2-109 | |
8 | Extra Material, Hashing and Hash Tables | 8h15-12h | C2-209 | |
9 | Binary Search Trees, Red-Black Trees | 8h15-12h | B2-109 | |
10 | Red-Black Trees, String
Matching, Solutions to implementation Exercises |
8h15-12h | B2-109 |
This is a preliminary schedule based on the previous instance of the course. It is subject to changes. Since this course is supposed to help you for your projects, you are highly encouraged to ask for specific subjects you want to learn about, as long as they are in the scope of this course :). Concerning the solutions to the exercises: You are supposed to find them and I will help you during the exercise sessions. Only some solutions will be provided on this web page.
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.
Material:
Introduction slides
ps.gz/pdf and exercises
ps.gz/pdf.
Growth of Functions slides
ps.gz/pdf.
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.
Exercises:
Solution: suggested solutions ps.gz/pdf.
Abstract: Introduction to counting, probabilities, and randomized algorithms.
Reading: Chapter 5 and appendices A and C.
Exercises:
Abstract: Some extra material on computing polynomials and sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quicksort).
Reading: Chapters 2 and 7.
Material:
Polynomials slide
ps.gz/pdf.
Sorting slides
ps.gz/pdf.
Exercises (many but short and simple):
Solution: suggested solution for 7-2.b ps.gz/pdf.
Abstract: Heapsort, powering numbers, and Fibonacci revisited.
Reading: Chapter 6.
Material: same as lecture 5.
Exercises (many but short and simple):
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.
Material:
Sorting slides
ps.gz/pdf.
Data structure slides
ps.gz/pdf.
Exercises:
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.
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.
Also
lecture 7 and
lecture 8 from the MIT
lecture
notes related to hashing and hash tables.
Exercises:
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.
Material:
Binary search tree slides
ps.gz/pdf.
Red-black tree slides
ps.gz/pdf.
Wikipedia
on red-black trees.
Exercises:
Abstract: Extra material on string matching, finish red-black trees, presentation of solutions for the previous implementation exercises.
Reading: Wikipedia, page on string searching. Chapter 32.
Material: String matching slides ps.gz/pdf.
Solutions: suggested implementations for