58131 Data Structures (ohtk 25.8.2011)

Principal theme Prerequisite knowledge Approaches the learning objectives Reaches the learning objectives Deepens the learning objectives
Construction, correctness and complexity of algorithms
  • basics of set theory and logics; basic theorem proving techniques (Introduction to Discrete Mathematics)
  • basic properties of logarithmic and exponential functions; sums of arithmetic and geometric series (school mathematics)
  • programs simple algorithms applying data structures and solution models mentioned elsewhere in this matrix
  • determines the asymptotic time and space complexity of a simple algorithm
  • is familiar with the O-notation (order of magnitude)
  • identifies examples of algorithms employing more complex algorithm panning methods
  • explains the working of simple algorithms using invariants
  • uses invariants in normal programming
  • uses recurrences to analyse the resource requirements of an algorithm (Design and Analysis of Algorithms)
Basic data structures and deepening the programming skills
  • describes how a linked structure is implemented in computer memory (Advanced Course in Programming)
  • programs in Java a linked list and its simple variations 
  • writes simple recursive programs in Java
  • implements a priority queue as a heap
  • uses stack, queue, list and tree structures in normal programming
  • uses recursion in programming as appropriate
  • know Java tools and solutions for implementing data structures presented on the course
  • writes a Java program with non-trivial data structures (Project in Data Structures)
Search structures
  • describes how a linked structure is implemented in computer memory (Advanced Course in Programming)
  • programs basic operations on (non-balanced) binary search trees
  • understands the concept of hashing and implements some basic version of a hash table
  • understands the concept and consequences of balancing and knows some balancing methods
  • chooses a suitable search structure based on time complexity results
  • solves simple algoritmic problems by hashing and other search structure
  • knows dictionary structures for disk storage
  • analyses amortised time complexity of an algorithm (Design and Analysis of Algorithms)
  • lower bound Ω(n log n) of comparison based sorting (Introduction to Discrete Mathematics)
  • implements in Java some square time sorting algorithm (Advanced Course in Programming)
  • knows some sorting algorithms and programs at least one O(n log n) sorting algorithm
  • knows the time complexities and limitations of the basic sorting algorithms
  • analyses the average case time complexity of sorting algorithms (Design and Analysis of Algorithms)
  • knows basic graph definitions (Introduction to Discrete Mathematics)
  • programs breadth-first and depth-first traversals in graphs
  • explains (using pictures, words and examples) the basic algorithms for shortest paths and minimum spanning trees
  • solves various graph problems using traversals, path finding and spanning trees
  • justifies the correctness and time complexity of algorithms for shortest paths and minimum spanning trees
  • solves optimisation problems using network flow algorithms (Discrete Optimisation)
  • reconises several NP-complete graph problems and can explan the meaning of NP completeness (Design and Analysis of Algorithms)


22.01.2015 - 19:23 Patrik Floréen
14.03.2011 - 16:02 Webmaster