---

Basic information, updated April 26, 2006 (Hannu Laine)

---


Algorithms and Datastructures C0197  (CAP04)

You should register to the course using WinhaWille. The identification code of the course is C0197 and the implementation code is CAP04.

The most important issue of the course is to learn to understand the significance of abstraction, genericity and sw-components  and to learn to use them effectively in programming. A view of component developer and a view of component user are considered. The problematics of developing generic reusable software components is studied. The students learn to develop reusable software components using mainly C-language. The concept of abstract data type (ADT) is used. The concept of ADT is quite a powerfull method in achieving the genericity and reusability. The weaknesses of these kind of implemantations are analyzed and tools for improving them are found in C++. Then a class is used to implement ADTs. This is the way the students learn to understand thoroughly the essence of the object oriented approach. Features of C and C++ are compared to eachother considering the tools they offer for abstraction and generic programming. The classic ADT:s like lists, stacks, queues and trees are studied. Different implementations (with identical interfaces) are compared. Their use in applications is demonstrated and students learn to recognize the situations where to use these generic components rather than to start programming from scratch. Template classes, container classes and iterators are discussed because they are concepts closely connected to topics described above.

Recursion is also thoroughly studied. Recursion in definitions, in problem solving and as a programming technique is studied. How recursive function is executed in the processor is examined. The sorting and searching methods are studied as an example of algorithm analysis. The genericity aspects are consired also in this context.

---

[ General  |  Main topics  | Record  | Course material  |  Exercises  | Teamwork excercise  |  Exam ]

---

 General information

• The course is taught during third and fourth period of the third year
• The course is 4.5 study points ( ECTS)
• Lectures 2 h / week ( 28 hours together)
• Labs 2 h / week (28 hours together)
• One teamwork exercise (estimated effort for  student 30 hours)
• Self study (estimated effort for student 30 hours)
• Exam at the end of the course (3 hours)

Main topics

The preliminary list of main topics is below.
 
• Introduction, main topics, algorithm
• Abstraction, procedure abstraction / data abstraction
• Abstract Data Type (ADT)
• Using software components
• Implementation with C and C++ (class)
• List : Definition and use
• List : various implementions
• Stack: definition, usage, implementations
• Queue: definition, usage, implementations
• SW Component hierarchies
• Disadvantages of array implementation
• Dynamically allocated implementations for List, stack and queue
• Other linked structures (circularly linked list, double linked list, sparse matrix, ...)
• More about genericity
• Classes, operator overloading and templates
• More about C++ (comparisons to C)
• Container classes
• Iterators
• Summary of software components
• Recursion in defintions and in problem solving
• Recursive functions (comparison to reentrant functions)
• Sorting methods
• Comparison of sorting methods
• Searching methods
• Seqential, Binary, Hashing
• Trees
• Binary search tree

The history of topics of lectures

You can find the list of topic titles, which have been discussed each week on "theory" classes by clicking the following link.

List of topics discussed so far.

 Course material

• You can print out the handouts from the following links
• Handouts are supplemented with notes during lectures
• Supporting books 1)  Kruse, Leung, Tondo :  Data Structures and Program design in C

(or 2) Mark Allen Weiss : Data structures and algorithm analysis in C )

Handouts (Material is added here gradually when the course proceeds)

 

Example  1 (Array implementation of a stack, and a small test application),
Example 2 : (Separation of previous example into three files : application , header , implementation )
Example 3 (a different implementation, application does'nt need any modification)
Example 4 (Array implementation of a queue, and a small test application )
Example 5 : (ADT stack is used as a subcomponent when implementing a list as linked array:
A list as linked array  ,  a header of integer stack  ,  an implementaion of integer stack )
Example 6  (ADT queue as a subcomponent when implementing a priority queue)

Example 1 (Allocating space for dynamic arrays),
Example 2 (Stack implemention with a dynamic array as storage structure),

 Exercises

There are about fourteen lab excercises during the course. Some of them are voluntary additional tasks (marked with E, standing for extra)

Exercise 1

 Teamwork Exercise

 Exam

At the end of the course the exam is arranged in which the understanding of the topics and the ability to apply them is tested. The  final grade is based mainly to the exam. The activity in labs and in a teamwork excercise can have an effect of 20% in final grade (all compulsory lab excercises are required to be completed to get the course approved).  The problems to be solved in the exam have similarities in nature with the problems worked out in labs, but they don't give straight answers to questions in the exam. Some potential types of questions in the exam are as follows: Question type 1) Certain objects of real world are described with the following attributes ...and the following operations  are defined for them. Implement the abstract datatype for those objects (i.e. write datatype definitions and operation functions for it). Question type 2) The abstract datatype xxx is available. The operation functions of that datatype are as follows .... The interface description is in the file xxx.h and the compiled object file in the file xxx.obj. Write a program that completes the following task: .... using the abstract datatype xxx. Question type 3) The abstract datatype xxx is available. The operation functions of  that datatype are as follows .... The interface description is in the file xxx.h and the compiled object file in the file xxx.obj. Implement an abstract datatype yyy with the following operations.... using the abstract datatype xxx (i.e. the ADT xxx is a subcomponent of the ADT yyy). Question type 4) Write a program that solves the following problem using recursion. Question type 5) You can see a program below. What is the problem, the program solves. What is the maximum size of stack frame allocated for the function f and so on. Question type 6) You can see a function below which sorts an array of  integers in ascending order. What are the changes needed to make the function absolutely general sorting function, meaning that no modifications are needed to the source code when changing the itemtypes of the array (for example to sparepart structure) or when changing the sorting criteria (for example to the price / weight ratio of the spare part).

Here You can find some model questions and their answers by clicking links.