# 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)
Sorting
• 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)
Graphs
• 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 14.03.2011 - 16:02