Algorithms and Data Structures (INF1, Autumn'05)

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

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 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 scale 00 - 13. 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.


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
6.9.2005 (Tue) 12:30-14:30 C2-209 Lecture 1 No exercises.
13.9.2005 (Tue) 12:30-16:15 Kroghstraede 3-2.119 Lecture 2 Tutorial 1 Solutions to set 1: ps, pdf, latex
15.9.2005 (Thu) 8:15-12:00 C2-209 Lecture 3 Tutorial 2 Solutions to set 2: ps, pdf, latex
20.9.2005 (Tue) 12:30-16:15 C2-209 Lecture 4 Tutorial 3 Solutions to set 3: ps, pdf, latex
27.9.2005 (Tue) 12:30-16:15 C2-209 Lecture 5 Tutorial 4 Solutions to set 4: ps, pdf, latex
29.9.2005 (Thu) 8:15-12:00 C2-209 Lecture 6 Tutorial 5 Solutions to set 5: ps, pdf, latex
4.10.2005 (Tue) 12:30-16:15 C2-209 Lecture 7 Tutorial 6 Solutions to set 6: ps, pdf, latex
11.10.2005 (Tue) 12:30-16:15 C2-209 Lecture 8 Tutorial 7 Solutions to set 7: ps, pdf, latex
13.10.2005 (Thu) 8:15-12:00 FB3 2.103 Lecture 9 Tutorial 8 Solutions to set 8: ps, pdf, latex
25.10.2005 (Tue) 12:30-16:15 C2-209 Lecture 10 Tutorial 9 Solutions to set 9: ps, pdf, latex
27.10.2005 (Thu) 8:15-12:00 FB3 2-103 Lecture 11 Tutorial 10 Solutions to set 10: ps, pdf, latex
1.11.2005 (Tue) 12:30-16:15 C2-209 Lecture 12 Tutorial 11 Solutions to set 11: ps, pdf, latex
8.11.2005 (Tue) 12:30-16:15 C2-209 Lecture 13 Tutorial 12 Solutions to set 12: ps, pdf, latex
10.11.2005 (Thu) 8:15-12:00 FB3 2-103 Lecture 14 Tutorial 13 Solutions to set 13: ps, pdf, latex
15.11.2005 (Tue) 12:30-16:15 C2-209 Lecture 15 Tutorial 14 Solutions to set 14: ps, pdf, latex
26.1.2006 (Thu) 13:00-? C2-209 Spørgetime Questions should be sent by email 24 hours before the meeting.