Links to this web page
1 Goal of the course
2 Requirements for passing the course
3 The seminars
4 The programming project
5 The project document
6 Course material
7 Prerequisites
8 Correspondence of content
Closely related elsewhere
This course in TUT Course Catalogue
Software studies at TUT
Supplementary material
Find an error in this program!
Preprint scientific paper behind Topic 4
Original scientific paper behind Topic 5
This web page contains long-term information that is not likely to change often.
[ To Course main page ] [ To General Instructions for the Project ]
In this course, theory learnt in earlier courses is put into practice, to learn to write efficient reliable programs for challenging tasks. Emphasis is on the use of good data structures and algorithms.
The course consists of four components:
The project, its document, and giving seminar talks are obligatory. Listening to seminar talks by others is voluntary, but may affect the mark. Participating the lectures is voluntary but, of course, highly recommended.
If the student's seminar talks, project, and its document satisfy minimal requirements but not more, then the student gets the mark 1. The student may earn extra points as described on these web pages. Every extra point increases the mark by 1, except that the highest possible mark is (of course) 5.
Each student must give two seminar talks, referred below as talk-A and talk-B.
Talk-A is held on period 1 and it is on a topic other than the student's programming project. The student must agree on the topic with the teacher. The design of data structures or algorithms must be in important role in the talk. The topic may, but need not, be related to a program that the student has made at some earlier time. The topic must not be about a programming project of another TUT data structures and algorithms course.
The ACM and other similar programming contest problems are excellent topics. The student may give a seminar talk on such a problem even if the solution is described on the net, provided that the student understands the solution well and presents it with her/his own words and slides at a level suitable for other students of the course.
Talk-B is held on period 2 and it is about the student's programming project. The student tells about the main principles of the program that (s)he is writing, and will get feedback from others in the seminar room. The goal is that the feedback helps in continuing the work. In particular, if another student has the same topic, (s)he is likely to both give useful feedback and benefit from the talk.
The talk may be given at an early or late stage of the project, or any time in between. However, the talk must not be given before the student has at least a design of the program that covers the most important data structure and algorithm choices.
The length of each talk should be 30 to 35 minutes, plus some time for the discussion so that the total time is 45 minutes. If the number of participants exceeds expectations, the total time will be reduced to 30 minutes.
The student may reserve any free lecture/seminar times for giving his/her talks excluding the last day of each period. There can be at most two talks in each day. Reserving takes place by sending email to the teacher. A reservation cannot be made more than three weeks in advance. This is because in earlier years some students had the tendency to reserve as late a time as possible and then not use it.
Please notice that if you do not give your talk early enough, there is the risk that there are no free times available when you want to give the talk! In an emergency, the last day of the period can be used, at the penalty of ½ points.
A common error in this kind of talks is to only tell what the speaker finds essential and interesting, and fail to tell sufficiently about the context, so that the audience cannot follow the talk. It is often the case that the speaker has been thinking about the problem so much that the statement of the problem, the overall plan of the solution, and so on are so familiar to him/her that it does not even come to her/his mind to start to tell about them. However, they are new to the audience. The audience cannot understand the core message of the talk, if the background and the context have not been told. You will not get useful feedback, if others do not understand your talk.
On the other hand, others cannot give useful feedback also if you only tell about the background and context, or discuss the solution at a very abstract level. You must present some ideas at such a level that others can think about them, comment on how well they would work, and so on.
In the case of talk-B, you may assume that everyone has read the problem description.
You can give your talk from your own laptop, bring it on a USB memory and present from the teacher's laptop, or email it to the teacher in advance. In the latter two cases the talk must be in PDF form. Five minutes before the start of the talk is not counted as “in advance”.
Very good talks and/or active constructive participation in the discussion on others' talks can earn ½ or 1 or in exceptional cases up to 2 points.
The project consist of writing an efficient C++ program on some topic where the use of good algorithms and data structures is essential for the performance of the program. The topics are such that C++ standard library algorithms and data structures do not immediately yield good solutions.
The project is done personally (that is, not in groups). However, more than one student may choose the same topic, and they may freely discuss and exchange design ideas with each other. They may also exchange test data. Exchanging program code or document text is not allowed.
Please read General instructions for the project.
Please do not underestimate the difficulty of the project. It is easy to write a program that often computes well, but much more difficult to write a program that always computes well. Experience from earlier years has been that in almost every case, the first submission has delivered a wrong result for some input, and sometimes four or more submissions were needed before the program started to work correctly. Furthermore, in those cases where the teacher wrote a solution of his own, it was almost always far more efficient than any of the students' solutions.
This is not a software engineering project. This is a data structure and algorithm project, where theoretical material from earlier courses is put into practice.
The document describes the algorithm and data structure design of the program. It must be written in the scientific and not in the industrial project document style. That is, it concentrates on the key ideas and does not list all trivial details. The document must be readable without looking at the code. Like with seminar talks, please pay attention to giving the readers sufficient information on what is obvious to you but not to them.
Please read General instructions for the project.
Lecture slides will be available via the course web pages. The teacher dreams of replacing some slides by better material. Until the new material is ready, the web page contains old material so that you have at least something.
Purchasing this book is highly recommended:
Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Cliff Stein. Publisher MIT Press or McGraw-Hill.
TUT library has 9 copies of the following book at the disposal of the students of this course. Also the teacher has one copy for quick needs (not to be removed from his office):
Algorithms and Theory of Computation Handbook. Edited by Mikhail J. Atallah.
The material of earlier data structure and algorithm courses is also useful.
OHJ-2156 Analysis of Algorithms is an obligatory pre-requisite of this course. It, in turn, has OHJ-2016 Utilization of Data Structures as an obligatory pre-requisite.
Doing the project will most likely be next to impossible if the student does not master the main issues in these two courses. This includes understanding the practical significance of the O-notation, being able to reason about the operation of algorithms, and knowing the basic principles of the most fundamental algorithms and data structures.
This course replaces all courses whose codes are of the form OHJ-220x and vice versa.