CS126 15 CATS (7.5 ECTS) Term 2
Core - CS, CSE, CSBS, Discrete Mathematics and Data Science. Option - Mathematics and MORSE.
CS118 or MA117
- To gain familiarity with the specification, implementation and use of some standard abstract data types (ADTs) such as linked-lists, stacks, queues, graphs etc.
- To learn some standard algorithms for common tasks (such as searching and sorting) and some elementary methods of measuring the complexity, and of showing the correctness, of algorithms.
- To learn how to program with non-standard ADTs using an object-oriented language.
On completion of the module, a student will:
- Be familiar with a range of standard ADTs and how they can be used to accomplish common programming tasks;
- Be able to assess the complexity and correctness of simple algorithms, and choose appropriate algorithms for simple tasks; and
- Have practical experience of designing user-defined ADTs, and associated algorithms, for a non-standard application.
- Types and their properties: simple types in programming languages; relationship between familiar mathematical and program objects of given type. Using predicate logic to state properties of types and their operations in terms of pre- and post-conditions.
- Abstract data types: specification of familiar abstract objects (eg complex numbers, sets, sequences, matrices) and their operations, comparison with their implementation using a typical programming language. Specification and implementation of some important standard types (eg strings, stacks and queues).
- Algorithms: relationship between data structures and algorithms; some standard algorithms for searching, sorting and pattern matching. Elementary analysis of complexity. Reasoning about the correctness of the implementation of simple algorithms.
- Goodrich MT, Tamassia R and Goldwasser MH, Data Structures and Algorithms in Java (6/e), Wiley, 2015.
One and a half-hour examination (50%), programming assignment (40%), marked laboratory session (10%)
30 one-hour lectures and 8 two-hour practical sessions