Datateknik D3-2005
Aalborg University| Computer Science Dpt.| Control Engineering Dpt.
Home| Course
Course
› Schedule › Lecture 1 › Lecture 2 › Lecture 3 › Lecture 4 › Lecture 5 › Lecture 6 › Lecture 7 › Lecture 8 › Lecture 9 › Lecture 10
Home
› Welcome ! › Prerequisites › Course Topic › Course Ojectives › Text Books › Additional Material › Fun Challenges › Course Grading › Contact

Schedule

Lecture Title Date Time Room
1 Introduction, Growth of Functions 12/10 8h15-12h B2-109
2 Representing and Manipulating Numbers 13/10 8h15-12h E3-209
3 Recurrences 14/10 8h15-12h B2-109
4 Probabilistic Analysis and
Randomized Algorithms
26/10 8h15-12h B2-109
5 Extra Material, Sorting 1/11 8h15-12h NJ6a 1.44
6 Extra Material, Sorting 2/11 8h15-12h B2-109
7 Sorting in Linear Time
Data Structures
4/11 8h15-12h B2-109
8 Extra Material, Hashing and Hash Tables 8/11 8h15-12h C2-209
9 Binary Search Trees, Red-Black Trees 9/11 8h15-12h B2-109
10 Red-Black Trees, String Matching,
Solutions to implementation Exercises
11/11 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.

Lecture 1 : Introduction, Growth of Functions

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.

Exercises: ps.gz/pdf.

Lecture 2 : Representing and Manipulating Numbers

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.

Exercises: ps.gz/pdf.

Solution: Suggested solution to the RGB exercise rgb.c.

Lecture 3 : Recurrences

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.

Exercises:

Solution: suggested solutions ps.gz/pdf.

Lecture 4 : Probabilistic Analysis and Randomized Algorithms

Abstract: Introduction to counting, probabilities, and randomized algorithms.

Reading: Chapter 5 and appendices A and C.

Material: Slides ps.gz/pdf.

Exercises:

Lecture 5 : Extra Material, Sorting

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.

Lecture 6 : Extra Material, Sorting

Abstract: Heapsort, powering numbers, and Fibonacci revisited.

Reading: Chapter 6.

Material: same as lecture 5.

Exercises (many but short and simple):

Lecture 7 : Sorting in Linear Time, Data Structures

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:

Lecture 8 : Extra Material, Hashing and Hash Tables

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.

Lecture 9 : Binary Search Trees, Red-Black Trees

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:

Lecture 10 : Red-Black Trees, String Matching, Solutions to Implementation 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