This page is presenting the course of Algorithms & Architecture I (2004). You can find here all the information relative to this course and some material linked to the course. This course will be given in english and will last 10 lectures of two times 45 minutes (with a break in-between) and will be followed by some exercices in the project group rooms.
Students are expected to know C language, the basic GNU tools (emacs, gcc, ...), have access to a Unix system, and have access to a C compiler on their PCs.
This course is about efficient data structures and efficient arithmetics.
After completing the course the students should have some knowledge in the following topics:
The first part of this course (D3) is based on
Introduction to Algorithms from the MIT Press. The
following parts of this course (D4 and D5) will continue to use
the algorithms book and will also be based on Computer
Organization and Design for the architecture part. The
algorithm book has been ordered at the department book
store. The architecture book has not been ordered yet but you
may safely buy it if you can because we will use it later and it
is also useful for the first part of the course.
Reading directives will refer to the
Introduction and Algorithms book.
Homepage of the book: check the errata! |
Additional litterature: material for the
course will be picked up from different sources and books. There
are some books that are particularly relevant for this
course. You should be able to find them at the library.
The FXT Library: fast transforms and low level algorithms.
Article on the Linux process scheduler.
Good page on hash functions.
Demo of red-black trees.
Page on balanced trees.
Lecture notes from the MIT (homepage):
The N queens problems: given a chess board of size N by N, place N queens so that they do not threaten each other. You can check on this page for a more detailed problem description and analysis. There exists a straight-forward solution that does not require searching at all, but this is no fun ;). It is easy to get a solution for N less than 30, but try to get one 1000 or 1000000 with a search approach. I'll give you a solution that can solve this problem for 20000000.
Maximal pair of strings: find the maximal pair of strings in a text in the sense that they are the longest two strings that are repeated. Test it on a reasonably long text like the bible.
The course grading is done through your project. But it doesn't mean that you do not have to come to the lectures and skip the exercises. The goal of the course is to teach you something useful about algorithms applicable to your projects. You are welcome to ask for specific topics to be treated.
Any question or remark relative to the course is welcome. Personal contact information.