The first mid-term exam will take place on Monday, October 28. A couple
of older exam: autumn -00 (ps),
autumn -00 (pdf),
autumn -01 (ps),
autumn -01 (pdf).
Contents
The course consists of the following sections:
1. Introduction to algorithms
1.1. Presentation of algorithms
CLR 1-10
1.2. Growth of functions
CLR 23-31
2. The class Vector
See Lewis, Loftus, Java Software Solutions, Addison Wesley 1998, pp.
825-827 and
CP, pp. 158-159.
2. Linear lists
CLR 204-212.
See also examples of list implementations in Java, for example Carrano's
book, chapter 4. Pay attention on how the delete operation is implemented.
It should take only a constant time, but in many books it takes
a linear time. Here are the examples in the lectures: List_1, List_2 and testing a list.
3. Stacks and Queues
CLR 200-203 or K 87-98 for a general description.
Read about the implementation of recursive procedures using a stack,
for example Aho, Hopcrof, Ullman, Data Structures and Algorithms,
Addison Wesley -83, pp. 200-203. A very thorough description of
stacks and queues with implementations can be found in CP, pp. 247-324.
4. Trees
CLR 91-97, CLR 213-215, CLR 244-246, BB implicit trees and minimax
algorithm 306, 317-319 (there are at least two versions of Brassard's
and Bratley's book; these page numbers refer to the 1996 edition).
For the Java implementations of trees, CP pp. 421-482.
5. Sorting: quicksort, mergesort, heapsort, priority queues with heaps.
All in CLR (13, 140-150, 153-160).
6. Lower bound for sorting using decision trees: CLR 172.
7. Linear sorting algorithms: counting sort, bucket sort, CLR 175-183.
8. Hashing, CLR 219-236.
9. Search trees, CLR 244-254.
10. Red-black trees, CLR 263-279.
11. Representation of graphs, breadth-first and depth-first search,
CLR 463-484.
12. Topological sort, CLR 485-487.
13. Dijkstra's algorithm to find the shortest paths, CLR 527-531.
14. Minimum spanning trees, Bertsekas and Callager, CLR 498-510.
15. Relations and transitive closure, CLR 81-83, 562-563.
16. Disjoint-set forests, CLR 446-449.
17. Amortized analysis, especially potential method, CLR 363-370.
Exercises
Exercises are compulsory, if the course is passed with two mid-term
exams. It is necessary to make 40% of all the exercises. That amount
produces one extra point, 80% produces 6 extra points.
The exercise group Tuesday 14-16 will be in English. If there a lot
of foreigners, it is possible that a new group will be set up.
- Exercise 1, in ps-form, in
pdf-form.
- Exercise 2, in ps-form, in
pdf-form.
-
Exercise 3, in ps-form, in
pdf-form.
-
Exercise 4, in ps-form, in
pdf-form.
-
Exercise 5, in ps-form, in
pdf-form. You will need some tree classes in Java programming.
-
Exercise 6, in ps-form, in
pdf-form.
-
Exercise 7, in ps-form, in
pdf-form.
-
Exercise 8, in ps-form, in
pdf-form.
-
Exercise 9, in ps-form, in
pdf-form.
-
Exercise 10, in ps-form, in
pdf-form.
-
Exercise 11, in ps-form, in
pdf-form.
-
Exercise 12, in ps-form, in
pdf-form.