# Module ICP-2027:Data Structures and Algorithms

### Module Facts

Run by School of Computer Science and Electronic Engineering

10 Credits or 5 ECTS Credits

Semester 2

Organiser: Dr Ik Soo Lim

### Overall aims and purpose

To allow students to use, select, implement and analyse a range of common abstract data types and algorithms.

### Course content

• Data Types, Abstract Data Types, Theory, implementations and uses of stacks, queues, lists, trees, graphs, hash tables, binary search trees. Constraints and Trade offs (time vs. space). • Criteria for algorithms. Recursive algorithms: Towers of Hanoi. Data processing algorithms: sorting and searching. Graph theoretic algorithms: traversal, shortest path. • Efficiency measures for time and space: rates of growth; asymptotic behaviour, big-O notation. Algorithm complexity classes (P, NP, NP-complete).
• New versions of algorithms, moral problems and dilemmas of updating an algorithm, moral responsibility of correctness. And understanding how to result ethical problems of algorithm and data structure development.

### Learning outcomes mapped to assessment criteria

threshold

40%

good

60%

excellent

70%

Show an understanding of a selection of common Abstract Data Types (ADTs) by appropriate selection and manipulation.

Can state basic definitions of DT and ADT. Can describe the structures of the given ADTs and their basic uses. Knows the difference between static and dynamic implementations. Can select an appropriate ADT and implementation for a given problem taking into account the trade offs involved. Can implement the given data structures. Can design and implement new data structures based on the given ones.

Show an understanding of the design and implementation of a selection of common algorithms.

Can describe the basic operation of the given algorithms. Can select and implement an appropriate algorithm for a problem. Can design and implement new algorithms based on the given ones.

Use complexity analysis to assist in the selection and design of algorithms.

Can rank big-O complexity classes correctly. Can state the complexity of basic algorithms. Can select algorithms appropriately. Can calculate complexity for simple cases. Understands the nature of NP-complete and computationally impossible problems. Can calculate complexity for complex cases (divide and conquer).

Understand the ethical issues of algorithms and the responsibility of the developer.

Explain areas where moral dilemmas may occur, such as updating an underlying data structure or locating an error in a current algorithm. Able to discuss various issues and provide realistic solutions and well formed argument. Able to discuss various ethical issues, where they may occur.

### Assessment Methods

Type Name Description Weight
EXAM Examination 60
COURSEWORK Assignment 1

A programming assignment.

20
COURSEWORK Assignment 2

A programming assignment.

20

### Teaching and Learning Strategy

Hours
Lecture

20
Private study 40

ASSESSED assignments, including tutorial questions, problems, essays etc.

40

### Transferable skills

• Numeracy - Proficiency in using numbers at appropriate levels of accuracy
• Computer Literacy - Proficiency in using a varied range of computer software
• Self-Management - Able to work unsupervised in an efficient, punctual and structured manner. To examine the outcomes of tasks and events, and judge levels of quality and importance
• Exploring - Able to investigate, research and consider alternatives
• Critical analysis & Problem Solving - Able to deconstruct and analyse problems or complex situations. To find solutions to problems through analyses and exploration of all possibilities using appropriate methods, rescources and creativity.
• Presentation - Able to clearly present information and explanations to an audience. Through the written or oral mode of communication accurately and concisely.
• Argument - Able to put forward, debate and justify an opinion or a course of action, with an individual or in a wider group setting
• Self-awareness & Reflectivity - Having an awareness of your own strengths, weaknesses, aims and objectives. Able to regularly review, evaluate and reflect upon the performance of yourself and others

### Resources

#### Resource implications for students

Hard copies of the main course text are available at the library. On-line access to the highly recommended book is available.

Main Course text: Java collections: an introduction to abstract data types, data structures, and algorithms - David A. Watt, Deryck F. Brown c2001

Highly Recommended: Introduction to algorithms - Thomas H. Cormen 2010, c2009

Recommended: Probability and Computing, by Michael Mitzenmacher and Eli Upfal, Cambridge University Press.