Course Catalog 2007-2008

OHJ-2016 UTILIZATION OF DATA STRUCTURES, 5 cr
Utilization of Data Structures

Courses persons responsible
Mika Siikarla

Lecturers
Mika Siikarla

Language of Instruction
The course is given entirely in English.

Lecturetimes and places
Per IV,V: Wednesday 12 - 14, TB216
Per IV: Friday 10 - 12, TB216

Implementations
  Period 1 Period 2 Period 3 Period 4 Period 5 Summer
Lecture - - - 4 h/week 2 h/week -
Exam  
(Timetable for academic year 2007-2008)

Objectives
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. 

Requirements for completing the course
A compulsory computer exercise, programming assignments and a final exam.

Evaluation criteria for the course

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

  • Used assessment scale is numeric (1-5)

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

    Prerequisites
    Code Course Credits M/R
    OHJ-1106 OHJ-1106 Programming I 4 Mandatory
    OHJ-1156 OHJ-1156 Programming II 5 Recommendable

    Prequisite relations (Sign up to TUT Intranet required)

    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.

    Remarks

  • Partial passing of course must be in connection with the same round of implementation.

  • Distance learning

  • ITC utilized during the course

  • - In information distribution via homepage, newsgroups or mailing lists, e.g. current issues, timetables
    - In compiling exercise, group or laboratory work
    - In distributing and/or returning exercise work, material etc
    - In the visualization of objects and phenomena, e.g. animations, demonstrations, simulations, video clips

  • Estimate as a percentage of the implementation of the course
  • - Contact teaching: 30 %
    - Distance learning: 0 %
    - Proportion of a student's independent study: 70 %

  • Description of the course implementation from ICT point of view
  • Written exam
    One compulsory computer exercise
    Compulsory programming assignments

    Scaling
    Methods of instructionHours
    Lectures 54
    Exercises 4
    Assignments 71

    Other scaledHours
    New tools and study methods 1
    Exam/midterm exam 3
    Total sum 133

    Correspondence of content
    8100300 Utilization of Data Structures

    Course homepage

    Last modified 14.02.2008
    Modified byMika Siikarla