Algorithms & Architecture I

Home

› Welcome !
› Prerequisites
› Course Topic
› Course Objectives
› Text Books
› Additional Material
› Fun Challenges
› Course Grading
› Contact
Course

› Schedule
› Lecture 1
› Lecture 2
› Lecture 3
› Lecture 4
› Lecture 5
› Lecture 6
› Lecture 7
› Lecture 8
› Lecture 9
› Lecture 10
This page is presenting the course of Algorithms & Architecture I (2005). 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:

- Analysis and design of algorithms,
- Growth of functions and asymptotic notations,
- Recurrences and techniques to solve them,
- Basics on probabilities and analysis of random algorithms,
- Different sorting algorithms (bubble sort, selection sort, insertion sort, merge sort, quicksort, heap sort),
- Elementary data structures (stacks, queues, linked lists),
- Hashing and hash tables,
- Binary search trees and red-black trees,
- Other topics relevant to an introduction to algorithms and semester projects such as string matching, computing polynomials, computing powers of numbers, binary search...

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
this book. The teacher for the 2nd part will inform you of
his/her choice for the architecture book.The
algorithm book has been ordered at the department book
store.

**Reading** directives will refer to the
*Introduction and Algorithms* book.

Introduction to AlgorithmsHomepage 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.

Structured Computer Organization -- 5th Edition |
Computer Organization and Design |
Computer Systems |
Computer Organization and Architecture |
Computer Algorithms |
Algorithm Design |

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):

- Lecture 2: recurrences.
- Lecture 1: sorting, merge sort, and asymptotic notation.
- Lecture 3: merge sort, binary search, Fibonacci numbers, powering numbers, and matrix multiplication.
- Lecture 4: quicksort.
- Lecture 5: sorting in linear time, decision tree sorting.
- Lecture 7 and lecture 8: hashing and hash tables.
- Lecture 9: binary-search-tree sort.
- Lecture 10: red-black trees.
- Lecture 20: interesting reading on lists and trees.

**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.