58131 Data Structures (8 cr), Spring 2009
Please remember to ask for questions in English one week before the exam, if questions in Finnish are not ok for you! You are allowed to bring to the exam an A4size sheet of paper of personal notes!
Separate exams (with English version of the questions) after the course: 11.8.2009, 15.9.2009, 10.11.2009 (question 3 is the same as the course Exam 1 question 3).
The results of the course are available at the Finnish page: look for "Tuloslista". You can discuss your exam results with the teachers on 27 May at 13.0013.30 in the space outside the lecturer's office A316.
This course is lectured in Finnish only (no lecture 2 April 2009) and the lecture material is in Finnish. You can still study in English in the following way:
 Read yourself the relevant parts of the book T.H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein: Introduction to Algorithms, 2nd ed., MIT Press, Cambridge, Massachusetts, 2001 and some additional material (see "Reading list" below).
 Then you have 2 alternatives: At the same time with the separate exam you can also repeat the course exam (max 48 points), i.e., you can have the points from your exercises included.
For passing the course you need about 30 points of the max 60; for getting the highest grade 5/5 you need about 50 points.
There are three types of exercises: normal exercises, group exercises and computerassisted exercises. The first normal exercises are already during the first lecture week of the course!
Note that if you choose the alternative with exercises included, you have to do a minimum of 25% of the exercises to pass the course. If you do 25%, you get 0 points from exercises; the maximum 12 points is reached by about 85% of the exercises.
Note that, if needed, there is an exercise group in English by Janne Korhonen on Wednesdays 1618 in CK111.
Email addresses of the teachers:
Patrik.Floreen (at) cs.Helsinki.FI
Janne.H.Korhonen (at) cs.Helsinki.FI
Antti.H.S.Laaksonen (at) cs.Helsinki.FI or Antti.H.Laaksonen (at) Helsinki.FI
Topi.Musto (at) cs.Helsinki.FI
Reading list
You need not read the whole book; only parts of the book is needed. However, some additional material is also needed. You can receive the handouts by contacting the lecturer.
Below is a summary of the relevant parts in the order they will appear on the course:
 Introduction and preliminaries
 general background (Chapter 1)
 analysis of algorithms: loop invariants and running time analysis (Chapter 2 except divideandconquer and recurrences which will be covered later)
 asymptotic notation, in particular bigO and bigTheta (Chapter 3)
 Elementary data structures
 dynamic sets (Introduction to Part III)
 stacks and queues (Section 10.1)
 linked lists (Section 10.2, Section 10.3 on a general level)
 Trees and search trees
 basic concepts of trees (Appendix B.5, Section 10.4)
 binary search trees (Sections 12.1 to 12.3)
 Balanced search trees
 AVLtrees (in a separate handout)
 B+trees (in a separate handout)
 More about trees
 representing rooted trees (Section 10.4)
 backtracking (separate handout)
 Hash tables
 Sections 11.111.4 except for the mathematical analysis (in Theorems 11.2, 11.3, 11.5, 11.6, 11.8).
 Priority queues, heaps, and heapsort (Chapter 6)

Sorting
 merge sort (Section 2.3)
 quick sort (Chapter 7) except the analysis of expected running time (Section 7.4.2)
 sorting in linear time (Chapter 8 except Section 8.4 (bucket sort))

Basics of graphs
 basic concepts of graphs (Section B.5)
 breathfirst and depthfirst search (Sections 22.122.3)

More graph algorithms
 topological sorting (Section 22.4)
 strongly connected components (Section 22.5)
 single source shortest paths (intro to Chapter 24)
 BellmanFord algorithm (Section 24.1)
 Dijkstra's algorithm (Section 24.3)
 shortest path properties (Section 24.5)
 allpairs shortest paths (intro to Chapter 25)
 FloydWarshall algorithm (Section 25.2)
 minimum spanning trees (Section 23.1)
 Kruskal's and Prim's algorithm for minimum spanning trees (Section 23.2)
Homework problems
Remember that the first homework session is already during the first lecture week!
Note that written answers to exercises are provided in Finnish only; please attend the English homework group for explanations in English.
Homework 2
Note: In exercise 5 we need the definition of limit value.
The limit of function f(x) in infinity is a, if for all real numbers e>0 there is a real number m, so that
f(x)  a < e, when x > m.
Homework 4
Note: In exercise 1, you can simply fill in the missing parts of
the following class.
Due to problems with the login, we have put forward the deadline for TRAKLA2 round 2 until Wed 11.2.
Homework 8 Note: There are now new Homework 8 excerises!
Homework 9 (Actually, there is an error in exercise 6: the time complexity should be log n, not n log n.)
Homework 10 Note: In exercise 3b, it should read print v, not return v.
TRAKLA2 problems
TRAKLA2 is a tool developed in TKK. The problems are grouped into "round", i.e., groups of problems with the same deadline. A correct answer to a problem is worth one homework point. You can try to do the same problem many times; the best result remains. You get into TRAKLA2 through Haka here with your own university account. You can choose the language of TRAKLA2 to Finnish or English.
Old exams
Year 2008 course exam 1 and course exam 2.
22.11.2009 Patrik Floréen