Each week of the course, there are two exercise sessions:
During these sessions, a teacher will solve exercises from the book on the blackboard and you will be able to discuss problems related to the course. If you have problems related to the current topics in the course, we often solve them together on the blackboard. Attendance is not mandatory, but strongly recommended.
The exercises marked with *, we intend to go through in the exercise sessions, but the plan is preliminary, and we don't always have time for all of them, especially if we need to discuss many other problems.
| Week | Topic | Exam problems | Problems from book (2nd ed.) | Problems from book (3rd ed.) |
|---|---|---|---|---|
| 1 | Induction | 1.11a*b1, 1.12 | 1.11a*b, 1.12 | |
| Time Complexity | P1 | 2.1*, 2.2*, 2.4-5, 2.7a, 2.10*, 2.11-12, 2.15*, 2.26, 2.31 | 2.2*, 2.7a, 2.10*, 2.11-12, 2.15*, 2.26, 2.31 | |
| Lists, Stacks, Queues | 12/08:1*, 12/08:5, 12/04:3*, 13/04:6 | 3.2, 3.6, 3.11, 3.15, 3.21-22, 3.24, 3.25a*, 3.27-28, 3.29*, 3.31-32 | 3.2, 3.6, 3.11, 3.15, 3.21-22, 3.25a, 3.27, 3.28, 3.29*, 3.31-32 | |
| 2 | Lists, Stacks, Queues | 12/12:5, 13/04:5*, 12/08:62 | 3.7, 3.33*, 3.34-35, 3.37 | 3.33*, 3.34 |
| Sorting | 7.1-2, 7.15, 7.17 | 7.13, 7.2, 7.15, 7.17 | ||
| Trees | 12/11:2* | 4.1-5, 4.8, 4.41 | 4.1-3, 4.5, 4.8, 4.41 | |
| Priority queues | 12/04:4 (för trea), 13/04:3, 13/08:4, 12/11:1*, 13/08:2, 12/04:54 | 6.2*, 6.3*, 6.10ab, 6.37b*, 6.38-39 | 6.2*, 6.3*, 6.10ab, 6.37b*, 6.38 | |
| 3 | Hash Tables, Sets, Maps | P3*, 12/08:2*, 11/12:1*, 12/11:3, 13/08:3, 13/08:6, 13/04:4 | 5.1a-c, 5.4, 5.13b, 5.14, 5.18 | 5.1a-c, 5.15b, 5.17 |
| Graphs | P4, 12/12:2, P5*, P6*, 12/08:4*, 13/08:5 | 9.1-3, 9.5, 9.38b, 9.41 | 9.1-2, 9.5, 9.38b, 9.41 | |
| 4 | Graphs | P7*, 12/04:6*, P8, 11/12:4, 12/12:6*, 11/12:6 | 9.7a, 9.10b, 9.15-16, 9.18, 9.20*, 9.26-27, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53 | 9.7a, 9.10b, 9.15-16, 9.18, 9.20*, 9.26, 9.31, 9.42*, 9.44-45, 9.51*, 9.52-53 |
| 5 | Search Trees | 12/12:1*, 13/04:1*, P9*, P10*, P11, 12/08:3*, 11/12:2, 12/04:1,2, 11/12:3 (för trea), 12/12:4* | 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c*, 4.19, 4.24-25, 4.35 | 4.9, 4.11-12, 4.16, 4.37, 4.49, 6.37c*, 4.19, 4.35, 4.25b |
| Splayträd | 13/08:1, 11/12:3 med splayträd*, P12 | 4.27-28 | 4.27 | |
| Skip Lists | 11/12:3 with skip lists* | 10.36, 10.38 | 10.37, 10.39 | |
| 6 | Sorting | P13, P14*, P15*, 12/04:4* (för fyra), 12/12:3* | 7.11-12, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.39-41, 7.48ab* | 7.11, 7.19-20, 7.21a-c, 7.22a, 7.27b, 7.31, 7.33, 7.44-46, 7.53ab* |
| 7 | Repetition |
This exercise is not correctly formulated. Part of your task is to correct the formulations.↩
Use the book-keeping method.↩
Use insertion sort, not radix sort.↩
Use the book-keeping method.↩
Remember that this is not a programming course: while the programming labs give practical experience, you will need to know your theory in order to pass the exam. These exercise sessions are an excellent opportunity for you to sharpen your theoretical skills.
The "work on your own" exercises have been cancelled due to lack of student participation. To compensate for this, if you need extra help with a particular exercise and the blackboard sessions don't fill your needs, you can make an appointment with either Ramona or Anton to discuss your problem. To do this, please send an email stating your problems as clearly as possible, and we will get back to you to agree on a time to meet.
This course covers the implementation of data structures in functional programming languages as well as object oriented. As some of you may not have used functional programming in a while, or even at all, there will be a two lecture crash course on Haskell, our recommended functional programming language, at the beginning of the course:
Everyone is welcome to these lectures, and we especially recommend students from TM and anyone else without prior functional programming experience to attend.
The lectures will cover the basics of functional programming, control structures, recursion, types, higher order functions and basic I/O. This is a lot of material to cover in two lectures, so you may find it helpful to prepare by having a look at Learn You a Haskell For Great Good before the first lecture.