Course Catalog 2009-2010 Basic Basic Pori International Postgraduate Open University |Degrees|     |Study blocks|     |Courses|

Person responsible

Imed Hammouda

Implementations

	Lecture times and places	Target group recommended to
Implementation 1	Per 4 : Friday 10 - 12, TB216 Per 4, 5 : Wednesday 12 - 14, TB216

Requirements

A compulsory computer exercise, programming assignments and a final exam.
Completion parts must belong to the same implementation

Principles and baselines related to teaching and learning

-

Learning outcomes

After completing the course, the student knows the commonly used sorting algorithms and their complexity. The student can implement basic data structures (lists and trees) independently, and knows how to apply relating algorithms to them. The student is able to analyze the complexity of simple programs and knows how to use the C++ standard library sensibly.

Content

Content	Core content	Complementary knowledge	Specialist knowledge
1.	Asymptotic efficiency and complexity notations.	Understanding the logarithmic complexity of divide and conquer algorithms	More advanced complexity analysis
2.	Sorting algorithms. The difference between quadratic and O(NlogN) sorting.	Different algorithms
3.	Lists, hash tables and the binary search tree	Red-Black tree	Not as widely used data structures
4.	C++ standard library: data structures and algorithms. Choosing the best alternative. Using the suitable data structure.	Using the STl algorithms, itrator categories, special containers.	Tha standard library and programmer defined data types.
5.	Graphs. The basic idea of graph algorithms.	Breadth first search, depth first search, Dijkstra's algorithm.	Other graph algorithms.

Evaluation criteria for the course

Passed homework assignments and the exam together define the final grade.

Assessment scale:

Numerical evaluation scale (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

Type	Name	Author	ISBN	URL	Edition, availability, ...	Examination material	Language
Book	Utilization of Data Structures	Minna Ruuska, Terhi Kilamo (compiled by)	1 84479 360 5		Available in the Juvenes bookstore		English
Lecture slides	Utilization of Data Structures						English

Prerequisites

Additional information about prerequisites
The course can be started while completing the course programming II. A good knowledge on the topics of programming II is required.

Correspondence of content

More precise information per implementation

	Description	Methods of instruction	Implementation
Implementation 1		Lectures Excercises Practical works	Contact teaching: 0 % Distance learning: 0 % Self-directed learning: 0 %

Last modified	03.03.2009
Modifier	Imed Hammouda