| 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)
|