Lecture | Title | Date | Time | Room |
---|---|---|---|---|
1 | Introduction, Growth of Functions | 8h15-12h | B2-104 | |
2 | Representing and Manipulating Numbers | 8h15-12h | B2-104 | |
3 | Recurrences | 8h15-12h | B2-104 | |
4 | Probabilistic Analysis and Randomized Algorithms |
8h15-12h | B2-104 | |
5 | Extra Material, Sorting | 8h15-12h | B2-109 | |
6 | Extra Material, Sorting | 8h15-12h | B2-104 | |
7 | Sorting in Linear Time Data Structures |
8h15-12h | B2-104 | |
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
Matching, Solutions to implementation Exercises |
8h15-12h | B2-104 |
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 and exercises
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.
Material: Slides ps.gz/pdf and exercises ps.gz/pdf.
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.
Material: Slides ps.gz/pdf and exercises ps.gz/pdf.
Solution: suggested solutions ps.gz/pdf.
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.
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 and exercises
ps.gz/pdf.
C program
sort-exercise.c needed for the exercises.
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.
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.
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 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.
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.
Abstract: Extra material on string matching, finish red-black trees, presentation of solutions for the previous implementation exercises.
Reading: Wikipedia page on string searching.
Material: String matching slides ps.gz/pdf.
Solutions: suggested implementations for