Examination requirements on T-106.250/253 Data structures and algorithms T/Y

These exam requirements are valid for spring 2005 course. They are used in exams until 30-Apr-2006.

You can read the following books and chapters while preparing to the exam (all of the books cover most of the topics, however, none of the books cover all of the topics, thus typically one book is sufficient, but some additional material is necessary):

• M.A. Weiss: Data Structures and Algorithm Analysis Algorithms in Java, chapters 1-9 plus sections 10.1.2, 10.3.4 and 12.2. Sections 4.5, 6.5-6.8, 7.10, 8.6.1 and 9.4. are not part of the exam requirements. Same requirements apply for the C-version of the book, except section 7.11, which is not part of the exam requirements.
• Cormen-Leiserson-Rivest: Introduction to Algorithms (1st ed., 1990), chapters 1-5, 7-14, 17.3, 19, 22-25, 26.2, 36-36.3, excluding sections 4.4, 10.3, 22.4, 25.3, 25.5.
• Cormen-Leiserson-Rivest-Stein: Introduction to Algorithms (2nd ed., 2001), appendices A and B, chapters 2-4, 6-13, 16.3, 18, 21-24, 25.2, 34-34.2, excluding sections 4.4, 9.3, 21.4, 24.1, 24.4.
• Sahni: Data Structures, Algorithms, and Applications In Java, chapters 2-3, 4.5 (this section is only for T-course students), 5-13, 15-17, 18.3.3, 18.3.5-18.3.6, 19. Sections 6.5.3, 8.3-4, 11.4, 11.6, 13.5, 16.3 and 19.4 are not part of the exam requirements.
• Levitin: The Design and Analysis of Algorithms, chapters 1-7, 8.2, 9., 10.3 Sections 3.3 (convex hull), 3.4, 4.5-4.6, 5.4-4.5, 6.2 and 7.2 are not part of the exam requirements.

Pay attention to the following things

• Definitions of basic terminology.
• You must understand the basic functionality of data structures and algorithms and how to utilize them.
• The analysis of the algorithms' running-time and space requirements are part of the course.
• You must be able to follow simple imperative programming language (C, Java, Pascal) or similar pseudocode.
• Do not memorize the algorithm code - learn to read and produce algorithms at least for simple tasks. Pseudocode is sufficient in all exam questions.

The following items are part of the examination requirements and provide helpful additional material (although, some of them are only in Finnish)

• Discussion on the course (lectures, lecture notes, newsgroups, web pages, old examinations, etc.),
• exercises and the material provided with them.

Below are some typical exam questions.

Definitions

Define the following concepts:
a) Deque
b) Priority queue
c) Hash function

Comparing different algorithms and data structures

Data structures:
a) Give four important criteria for selecting a data structure for an application. You can assume that only one type of search keys is used.
b) Use these criteria to compare binary search tree, AVL-tree and double hashing

An overview of one main topic

Sorting:
You must select an algorithm for sorting a number of elements in main memory. What criteria do you use for selecting the algorithm and what algorithms do you recommend for different situations? Give a reasoning for your opinion. (maximum recommended length 1 page)

Algorithm and data structure description

Give a textual description of an algorithm used to make topological sort of a graph. What is the running-time of the algoritm on a graph with V vertices and E edges?

Application and selection of algorithms and data structures for specific problems

Write the following algorithms using C, Pascal, Java or similar pseudolanguage. Describe the important aspects of the algorithm in text.
a) An algorithm that calculates the height of a binary tree. What is the running-time (using big-Oh notation) of your algorithm on a tree that contains N elements?
b) An algorithm that compares two binary trees and tells if they are identical. What is the running-time (using big-Oh notation) of your algorithm on if both trees contain N elements?
c) An algorithm that takes two arrays and prints all elements that appear in both. You can assume that the arrays are sorted in increasing order. What is the running time of your algorithm if the arrays contain M and N elements, respectively.

Application of algorithms and data structures to simple problems

Heap:
a) Use the keys
P R I O R I T Y Q U E U E
to construct a binary heap using the build-heap algorithm. Heap property is parent >= children. Show intermediate phases.
b) Show the heap after one and two deletions.
c) Show the final heap in array format.

The first mid-term exam is on Friday, March 11th. Remember to register to all of the exams! Registration is through WebTOPI.

The last chance to take the examination is in the beginning of 2006 (probably in February or March).