Skip to main content

CS126 Design of Information Structures

CS126 15 CATS (7.5 ECTS) Term 2

Availability

Core - CS, CSE, CSBS, Discrete Mathematic sand Data Science. Option - Mathematics and MORSE.

Prerequisites

CS118

Academic Aims

  • 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.

Learning Outcomes

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.

Content

  • 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.

Books

  • Goodrich MT, Tamassia R and Goldwasser MH, Data Structures and Algorithms in Java (6/e), Wiley, 2015.

Assessment

One and a half-hour examination (50%), programming assignment (40%), marked laboratory session (10%)

Teaching

30 one-hour lectures and 8 two-hour practical sessions