Curriculum Page >> COMP225
Curriculum - COMP225 - Algorithms and Data Structures
| Handbook Entry | Unit Home Page |
Short Description
COMP225 studies algorithms, data structures and programming techniques emphasising the role of data abstraction and correctness proofs.
Assumed knowledge
- Ability to write non-trivial programs in a procedural language using structured programming techniques including recursion. Knowledge of testing and debugging techniques suitable for these programs. (COMP125)
- Knowledge of simple data structures - arrays, records, files, lists, stacks, queues, strings. Pointers and linked list implementations for these data structures. (COMP125)
- Ability to specify pre- and post-conditions. (COMP125)
- Basic mathematical knowledge - logarithms, exponents, mathematical induction. (3 credit points from MATH131-MATH136)
- Ability to program in an object-oriented language using classes. (COMP125)
Learning outcomes
- Ability to prove the correctness of algorithms, particularly partial correctness and termination of iterative and recursive algorithms.
- Ability to analyse algorithms, particularly their asymptotic behaviour.
- Understanding of the design of specific algorithms including ones based on incremental approaches, divide and conquer, and dynamic programming.
- Understanding of the definition, implementation and applications of common abstract data types such as priority queues, binary trees, and binary search trees.
- Understanding of graph data structures and graph algorithms.
- Understanding of a variety of sorting techniques including mergesort, quicksort, and heapsort.
- An understanding of the limits of computation.
Comments to: Steve Cassidy