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 A4-size sheet of paper of personal notes!
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.00-13.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:
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 computer-assisted 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 16-18 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
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 divide-and-conquer and recurrences which will be covered later)
- asymptotic notation, in particular big-O and big-Theta (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
- AVL-trees (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.1-11.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)
- 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)
- breath-first and depth-first search (Sections 22.1-22.3)
More graph algorithms
- topological sorting (Section 22.4)
- strongly connected components (Section 22.5)
- single source shortest paths (intro to Chapter 24)
- Bellman-Ford algorithm (Section 24.1)
- Dijkstra's algorithm (Section 24.3)
- shortest path properties (Section 24.5)
- all-pairs shortest paths (intro to Chapter 25)
- Floyd-Warshall algorithm (Section 25.2)
- minimum spanning trees (Section 23.1)
- Kruskal's and Prim's algorithm for minimum spanning trees (Section 23.2)
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 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 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.
22.11.2009 Patrik Floréen