Informatik 2 – General information

Summer 08 - Schmiedecke

 

Course start is on Thursday, April 3, 12:00 a.m.

 

Overview

Informatik 2 features algorithms and data structures, which can be considered the stem cells of computer science, orbiting around the question: How can I make my computer solve my problem?

So we are turning our backs to interactive systems, and combining ready-cut objects to form a composite program, which is often called programming-in-the-large, and dive into details of loops, recursions and optimizations, called programming-in-the-small. Together with this change of perspective, we will change our working  platform from Windows to Linux, the more competent – and before all – open source operating system. We will still be using Eclipse, so that the change will not really feel grave.

Whereas beforehand, we happily made use of Java's  Vectors and Array Lists and their sorting and searching methods, it is now our term to implement them from scratch –and do so well. there is also quite some math involved – and hopefully, some of you will find math useful and even fun afterwards. And of course we will ask the big questions: Is this problem at all solvable? How long does the computation take? Is there a better solution to this problem? Even though in a programmer's everyday life, we do not often deal with these matters, they are obviously important to understand!

Organisation and Communication:

The course consists of a double lecture per week and a double lab session every other week.
All course materials (slides, exercises, memos) are published in the Moodle e-learning environment. (If Moodle is down, you will find most of the materials also on my homepage.) Exercises are handed in by uploading them in Moodle.

Exercises:

There is a lab every other week, which you are asked to work on in groups of two students. This is a preparation for the well known pair programming technique, in which all code has to be written and modified by pairs of programmers. It has been shown that this improves both the structure and the quality of the code! Once again, you hand in reports (one per group!), but this time preferably as html pages, or rather links to your home page. And you will need to present at least 50% of your labs to me during lab time.

All labs contain prep work, which this time is compulsory, so you need to report on it to receive full points.

There will be no (or only few)  online tests this term, sorry L

Lab exercises are worth 20 points and loose 4 points per week of delay (20%). 

 

Grading:

In order to pass the course, you must have done all exercises with at least 50% of the points and passed the final exam.  To be admitted to the final exam, you must have handed in at least labs 1-5, the last lab may be handed in after the exam. The final grade will be a 50/50 combination of exercise and exam.

Exercises are graded as follows:

·       All labs are worth 20 points – X6 is worth 30 points..

·       This corresponds to a full solution without extras.

·       If you do not reach the full solution, points will be deduced – but not, if you lab report shows that in spite of good preparation, you have come across unexpected difficulties.

·       If you have done extras or worked particularly well, you will receive 1-5 extra points.

·       Full grading (20 points) on all exercises corresponds to  a final marking of 2,0.

The final exam will contain questions both on the lab exercises and on the lecture. There will be 2 preparatoy lectures before the exam. In addition, you can try out last year's exam and a mock exam.

 

Literature:

 

Most of the relevant literature is published with titles like "Algorithms and Data Structures"  - and there is a host of it. Here is a list of my favourite references, the first two of them can be considered immediate course text books.  Number 5 is another favourite of mine and both worth and fun reading, too. Most books are in German – I am positive that you can cope with it J

 

1.     Hans-Werner Lang, "Algorithmen", Oldenbourg 2006
Detailed algorithm explanations and understandable mathematics, mathematical basics in the appendix. Additional modern approaches: network and cluster sorting.

Online resources under  http://www.iti.fh-flensburg.de/lang/lehrver.htm

 

2.     Gunter Saake, Kai-Uwe Sattler, "Algorithmen und Datenstrukturen" (3.Aufl.), d-punkt Heidelberg, 2006
 - a very good balance between theoretical concepts, classical approaches and modern concepts. All sample programs in Java
Online resources under
http://www.dpunkt.de/buch/alg_dat.html

3.     Andreas Solymosi, Ulrich Grude, "Grundkurs Algorithmen und Datenstrukturen", Vieweg Wiesbaden 2000
- very concise, non-pretentious and down-to-earth, but a little academic in its examples. All in Java

Online resources under http://www.tfh-berlin.de/~oo-plug/Ad

 

4.     Sedgewick, "Algorithms" (2nd Ed.) Addison-Wesley Reading MA, 1989
- 650 pages full of very detailed and careful explanations! Using Pascal.
German version available.

5.     Duane Bailey, "Java Structures" (2nd Ed.) , Mc Graw-Hill New York, 2003
- all from the data structure perspective, very disciplined approach, many fine examples – all Java
Online resources at
http://www.mhhe.com/javastructures

6.     Thomas Ottmann, Peter Widmayer, "Algorithmen und Datenstrukturen"(4.Aufl), Spektrum Heidelberg, 2002
- a classical approach with very many examples, all in Java
Online resources under
http://ad.informatik.uni-freiburg.de/bibliothek/books/ad-buch

7.     Nicolas Wirth, "Algorithmen und Datenstrukturen – Pascal-Version"(5.Aufl.), Teubner Stuttgart, 2000 (Original ca. 1975)
- one of the first text books covering this material in a more practical way

 

8.     Manfred Bretz, "Algorithmen und Berechenbarkeit",  Vieweg Wiesbaden 1992
- mathematics revisited and digested for non math addicts, still very theoretical

 

9.     D.E.Knuth, "The Art of Computer Programming Vol 1-3", Addison-Wesley Reading MA, 1998
- THE STANDARD VOLUME ON ALGORITHMS – every computer scientist should at least have glanced through it….

 

Further literature on more specialized topics will be mentioned during the lectures.