Module overview
This is a core module for computer science and software engineers. It teaches the basic data structures and algorithms which underpins modern software engineering. Without these algorithms most software would be hopelessly slow to the point of unusability. The course also teaches the principles behind the algorithms and data structures and the software engineering lessons which data structures and algorithms teach us.
Linked modules
Pre-requisite: COMP1202
Aims and Objectives
Learning Outcomes
Transferable and Generic Skills
Having successfully completed this module you will be able to:
- Be able to solve problems algorithmically
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Understanding of time complexity
- Understanding of how to code data structures using object oriented methods
- Knowledge of common data structures and algorithms
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Understand how to evaluate an algorithm for efficiency
- Choose an appropriate algorithmic strategy to solve a problem
- Understand the operation of a number of important computer algorithms using those structures
- Choose the most appropriate data structure for a particular problem
Syllabus
Introduction
- Data Objects, Data Structures, Complex Data Structures
Algorithm Analysis
- Time Complexity
Algorithm Design and Strategies
- Brute Force, Depth-First, Breadth-First, DFID, Best-first, Greedy Divide and Conquer,
- Dynamic Programming, Branch and Bound
Simple Data Structures
- List, Stack, Queue, Tree, Tree traversal
Sorting
- Selection Sort, Insertion Sort, MergeSort, QuickSort, Radix sort
Searching
- Sequential Search, Binary Search, Binary Tree Search
Advanced Tree Structures
- AVL Trees, Red-black Trees, B-trees
Hash tables
- Hash table size, Collision resolution, Separate chaining
- Open addressing, Re-hashing
Priority Queues (Heaps)
- Simple implementations, Binary heaps, Heap sort
Graphs
- Adjacency Matrix and List, Connectivity, Breadth vs Depth first search
- Shortest path algorithms
- Minimum Spanning Tree, Prim's algorithm
Learning and Teaching
| Type | Hours |
|---|---|
| Tutorial | 12 |
| Follow-up work | 18 |
| Wider reading or practice | 34 |
| Revision | 10 |
| Lecture | 36 |
| Preparation for scheduled sessions | 40 |
| Total study time | 150 |
Resources & Reading list
Textbooks
Robert Sedgewick and Kevin Wayne (2011). Algorithms. Addison-Wesley.
Weiss MA (2006). Data Structures and Algorithm Analysis in Java. Addison-Wesley.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). Introduction to Algorithms. MIT Press.
Assessment
Formative
This is how we’ll give you feedback as you are learning. It is not a formal test or exam.
Blackboard quizzes
- Assessment Type: Formative
- Feedback:
- Final Assessment: No
- Group Work: No
Summative
This is how we’ll formally assess what you have learned in this module.
| Method | Percentage contribution |
|---|---|
| Examination | 100% |
Referral
This is how we’ll assess you if you don’t meet the criteria to pass this module.
| Method | Percentage contribution |
|---|---|
| Examination | 100% |
Repeat
An internal repeat is where you take all of your modules again, including any you passed. An external repeat is where you only re-take the modules you failed.
| Method | Percentage contribution |
|---|---|
| Examination | 100% |
Repeat Information
Repeat type: Internal & External