Algorithms and Data Structures (INF1, Fall 2007)

Course Lecturer

Hua Lu (email: luhua AT cs.aau.dk, office: Selma 3.2.05)

Course Description

This is an introductory course on algorithms and data structures for informatics students. It will cover these correlated aspects: algorithm correctness and complexity analysis, algorimth design techniques, fundamental data structures and important algorithms over them. Relevant basic concepts and approaches will be introduced, with limited intermediate or deep contents. Through this course, students are supposed to well understand the basic computer science algorithms and data structures, and be able to reason about algorithm correctness and complexity. The course will be given in English.

Textbook and References

Main textbook: Algorithms and Data Structures: Design, Correctness and Analysis (2nd edition) by Jeffrey H. Kingston (available at the local bookstore).
Supplementary: Algorithmics: The Spirit of Computing by David Harel (available at the local bookstore).
Advanced readings:Algorithm Design by Jon Kleinberg and Éva Tardos; Introduction to Algorithms (2nd edition) by Thomas H. Cormen et al.
Slides: Lecture slides will be downloadable from this site, shortly before or after each lecture.
Others: How to write algorithms in latex - download here.

Course Structure

This course will have 15 sessions. The first session will be an introductory one, approximately lasting for 2 hours. Each of other sessions will last for about 4 hours. The first 2 hours will be devoted to exercises, which cover the knowledge taught in the previous session. While the other 2 hours will be focused on giving a lecture with specific topics. The questions in the exercises are similar to those that will be used in the final exam, in terms of both format and difficulty.

Syllabus

You can have a look at it here.

Lecture Schedule (tentative! Check the calendar for updates.)

Lecture 1: Introduction to the course, algorithmic problems and solutions, searching.
Date: 4.9.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Note: The first lecture will start at 13:30, as we do NOT have any exercises to solve this time.
Lecture 2: Correctness of algorithms.
Date: 11.9.2007 (Tue). Time: 12:30-16:15. Location: 0.2.12.
Outline, slides, exercises, solutions.
Note: The exercise class will start at 12:30 in the lecture room. Please try to start solving the exercises by yourselves before the lecturer comes.
Lecture 3: Complexity of algorithms.
Date: 18.9.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 4: Data abstraction, Linear structures (I).
Date: 25.9.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 5: Linear structures (II).
Date: 27.9.2007 (Thu). Time: 8:15-12:00. Location: 0.2.12.
Outline, slides, exercises, solutions.
Note: This lecture will be shorter than usual. We will spend the time left on exercise explanation.
Lecture 6: Sorting (I).
Date: 2.10.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Note: This lecture will be shorter than usual. We will have a quiz afterwards.
Lecture 7: Sorting (II).
Date: 4.10.2007 (Thu). Time: 12:30-16:15. Location: 0.2.13.
Outline, slides, exercises, solutions.
Lecture 8: Trees, Symbol tables (I).
Date: 9.10.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 9: Symbol tables (II).
Date: 23.10.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 10: Algorithm design techniques (I).
Date: 25.10.2007 (Tue). Time: 12:30-16:15. Location: 0.2.12.
Outline, slides, exercises, solutions.
Lecture 11: Algorithm design techniques (II).
Date: 30.10.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Note: This lecture will be shorter than usual. We will have our second quiz.
Lecture 12: Graphs (I).
Date: 20.11.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 13: Graphs (II).
Date: 22.11.2007 (Thu). Time: 12:30-16:15. Location: 0.2.12.
Outline, slides, exercises, solutions.
Lecture 14: Shortest paths in graphs.
Date: 27.11.2007 (Tue). Time: 12:30-16:15. Location: 0.2.90.
Outline, slides, exercises, solutions.
Lecture 15: Minimum spanning trees.
Date: 29.11.2007 (Thu). Time: 12:30-16:15. Location: 0.2.12.
Outline, slides.
Note: A conclusion on the whole course will be given at the end of this lecture. No exercises for this lecture.

Exam

Individual and written. Marks will be given according to the standard Danish scale. Any electronic devices like laptops and mobile phones are NOT allowed. But you can freely use copies of slides from the lectures, textbooks, and any other course material common to all students.

Totally there will be 3 questions in the exam. Question 1 consists of 6-8 sub-questions, all of which are objective ones. For such objective sub-questions, you just need to pick a correct choice or write down the final answers only, without any written reasoning. Neither question 2 nor 3 is that simple. Instead, you need to think actively, and write down your justification together with the solutions (e.g., algorithm design followed by correctness/complexity analysis). The full 100 points are allocated in this way: 50 points for question 1, 25 points for question 2, and 25 points for question 3.

All exam (sub-)questions will exhibit the similar format and hardness as those used in exercises. Therefore, students should digest all exercise questions in order to get good scores in the exam.

Exam questions and answers in previous years:
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.

Earlier exam questions: 2001 (re-exam), 2001, 2000 (re-exam), 2000.