Algorithms and Data Structures (INF1, Autumn'06)

Lecturer: Jiri Srba (email: srba@cs.aau.dk, office: B2-204)

Course Description: This is an introductory course on algorithms and data structures. We will introduce the basic concept of algorithm design and analyze the correctness and complexity of the algorithms. Our aim will be to understand the basic algorithms and reason about their complexity. We will also focus on the most useful data structures of computer science. The working language of the course will be English.

Textbook: The main textbook will be Algorithms and Data Structures: Design, Correctness and Analysis 2nd edition by Jeffrey H. Kingston (available at the local bookstore). As a supplementary reading material I recommend the book Algorithmics: The Spirit of Computing by David Harel. Other reading material including the copies of slides will be provided for photocopying in the course folder.

Lectures and Exercises: The course will run in four-hour blocks. Each block will consist of combined activities: lecturing and supervised solving of exercises. These two activities can be interleaved several times during one block. Each week a list of exercises will be released. Students are supposed to print out the list and bring it to the lecture. Occasionally, some of the exercises will be marked as hand-in. Students are expected to solve them individually and the solutions will be corrected by the lecturer. Solutions to all exercises will be available on the web-page with a certain delay after the tutorials. The exercises are directly aimed at preparing the students for questions of category 1 of the written exam.

Exam: Individual and written. Marks will be given according to the standard Danish scale. The exam will consist of two categories of questions. Questions from category 1 (approximately one question per lecture) will be very concrete questions, possibly with multiple answers. The students are supposed to write/select the correct answer without providing any written justification. The questions of category 1 will closely follow the exercises released after each lecture (not necessarily only the hand-in ones). In order to pass the exam, a sufficient number of category 1 questions have to be answered correctly. Questions of category 2 will consist of two or three problems which require creative thinking and a written justification of the solutions is a necessary part of the answer (e.g. a design of an algorithm and its complexity analysis).

Syllabus: The syllabus of the course is essentially the same as the content of the lectures. Recommended reading is summarized at every lecture on the respective page and also here. A brief overview of the main focus areas is available on the slides from the last lecture (in the course folder).

Course web-page from the year 2003 including scanned copies of lecture slides is here.

How to write algorithms in latex - download here.

Inspiration for exam questions of category 2: here, here, here, here, and possibly also here (exams for DAT1 students).

Exam questions from 21.1.2004 are here and correct answers are here.
Exam questions from 30.8.2004 are here and correct answers are here.
Exam questions from 28.1.2005 are here and correct answers are here.
Exam questions from 31.8.2005 are here and correct answers are here.
Exam questions from 30.1.2006 are here and correct answers are here.
Exam questions from 30.1.2007 are here and correct answers are here.


Anonymous Feedback Form (can be accessed only from the domain cs.aau.dk)
(The students are very encouraged to notify the lecturer about any problem as soon as possible and to send suggestions for improvements. Positive feedback is also welcome.)

Lecture Plan (calendar is available here):

Date
 Time
 Place
 Link
 Exercises
 Remark
5.9.2006 (Tue) 12:30-14:30 B2-104 Lecture 1 No exercises. slides
12.9.2006 (Tue) 12:30-16:15 B2-104 Lecture 2 Tutorial 1 slides Solutions to set 1: ps, pdf, latex
14.9.2006 (Thu) 12:30-16:15 A4-106 Lecture 3 Tutorial 2 slides Solutions to set 2: ps, pdf, latex
19.9.2006 (Tue) 12:30-16:15 B2-104 Lecture 4 Tutorial 3 slides Solutions to set 3: ps, pdf, latex
21.9.2006 (Thu) 12:30-16:15 A4-106 Lecture 5 Tutorial 4 slides Solutions to set 4: ps, pdf, latex
3.10.2006 (Tue) 12:30-16:15 B2-104 Lecture 6 Tutorial 5 slides Solutions to set 5: ps, pdf, latex
5.10.2006 (Thu) 12:30-16:15 A4-106 Lecture 7 Tutorial 6 slides Solutions to set 6: ps, pdf, latex
12.10.2006 (Thu) 12:30-16:15 A4-106 Lecture 8 Tutorial 7 slides Solutions to set 7: ps, pdf, latex
31.10.2006 (Tue) 12:30-16:15 B2-104 Lecture 9 Tutorial 8 slides Solutions to set 8: ps, pdf, latex
2.11.2006 (Thu) 12:30-16:15 A4-106 Lecture 10 Tutorial 9 slides Solutions to set 9: ps, pdf, latex
7.11.2006 (Tue) 12:30-16:15 B2-104 Lecture 11 Tutorial 10 slides Solutions to set 10: ps, pdf, latex
9.11.2006 (Thu) 12:30-16:15 A4-106 Lecture 12 Tutorial 11 slides Solutions to set 11: ps, pdf, latex
14.11.2006 (Tue) 12:30-16:15 B2-104 Lecture 13 Tutorial 12 slides Solutions to set 12: ps, pdf, latex
16.11.2006 (Thu) 12:30-16:15 B2-104 Lecture 14 Tutorial 13 slides Solutions to set 13: ps, pdf, latex
21.11.2006 (Tue) 12:30-16:15 B2-104 Lecture 15 Tutorial 14 slides Solutions to set 14: ps, pdf, latex
26.1.2006 (Fri) 15:00-? A4-106 Spørgetime Please, send questions via email 24 hours before the meeting.