CS126 Design of Information Structures

CS126 15 CATS (7.5 ECTS) Term 2

Availability

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