Data Structures, spring 2010

Exercises:

English Exercise group wednesdays 16-18 B119

Please note that exercises start at the first week of the course!

Besides normal exercises we also use TRAKLA2-system. Registration to TRAKLA2 here

It is also possible to earn exercise points by doing Project Euler programming problems. Please ask the course assistant how to proceed if you are interested in doing these.

Lecutures

Course is based on the following book
T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms, 3nd ed., MIT Press, 2009.

Also the 2nd edition ok. Some parts of the course are not covered in Cormen. Good material for AVL-trees is
M. A. Weiss: Data Structures and Algorithm Analysis in Java, 2nd ed., Pearson Addison-Wesley, 2007.

Material on B+-trees

Progress of the lectures and corresponding pages from Cormens both editions

19.1 correctness of algorithms, cormen2: 5-21, cormen3: 5-23
21.1 complexity of algorithms, cormen2: 23-27, 41-55, cormen3: 23-28, 43-59
26.1 more on complexity
28.1 Stack, Queue, cormen2: 197-203, cormen3: 229-235
2.2 Linked List, cormen2: 204-208, cormen3: 236-240
4.2 Tree, cormen2: 1087-1090, 214-215, 253-255, cormen3: 1176-1179, 246-247, 286-288
9.2 Binary search three, cormen2: 253-264, cormen3: 286-298
11.2 AVL-tree, not in Cormen
16.2 more on AVL-tree, not in Cormen
18.2 more on AVL-trees and trees, cormen2: 214-215, cormen3: 246-247
23.2 Trees in problem solving
25.2 Recap for the exam
1.3 first exam 16-19 A111
16.3 and 18.3 Hash Tables, cormen2: 221-245, cormen3: 253-277
23.3 Heap, cormen2: 127-132, 138-141, cormen3: 151-158, 162-168
25.3 Sorting algorithms, cormen2: 133-137, 27-36, cormen3: 156-161, 29-39
29.3 Sorting algorithms, cormen2: 145-173, cormen3: 170-199
30.3 Graphs, Breth-First search, cormen2: 1080-1085, 525-540, cormen3: 1168-1172, 587-603
13.4 Depth-First search and applications, cormen2: 540-560, cormen3: 603-623
15.4 Sortest paths, cormen2: 580-587, 595-613, 629-636, cormen3: 643-650, 658-680, 693-699
20.4 and 22.4 Minimum spanning trees, cormen2: 561-579, cormen3: 624-642
27.4 More on graphs
29.4 Recap for the exam
6.5 second exam 9-12 A111

Passing the course

Course has two exams both giving 24 points, 12 weekly exercises, TRAKLA2-exercises and possibility for Euler Project problems.

From exercises it is possible to get 12 points. 2/3 of the exercise points comes from "normal" weekly exercises and 1/3 from TRAKLA2-exervises.

Ask course assistant how the Project Euler problems effect the exercise point.

85% of exercises gives 12 exercise points. Minimum 25% of the exercises should be done.

Maximum total of exams is 24+24. To pass the course one should get at least 24 points form exams and at least half of the total 60 point. To pass the course, minumum of 25% of the exercises should be done.