Datateknik D3-2004
Aalborg University| Computer Science Dpt.| Control Engineering Dpt.
Home| Course
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

Welcome !

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.

Prerequisites

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.

Course Topic

This course is about efficient data structures and efficient arithmetics.

Course Objectives

After completing the course the students should have some knowledge in the following topics:

Text Books

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.

Introduction to Algorithms

Homepage of the book: check the errata!
Computer Organization and Design

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.

Computer Systems
Computer Organization and Architecture
Computer Algorithms

Additional Material

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

Fun Challenges

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.

Course Grading

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.

Contact

Any question or remark relative to the course is welcome. Personal contact information.