COMP1201 Algorithmics
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.
Aims and Objectives
Learning Outcomes
Knowledge and Understanding
Having successfully completed this module, you will be able to demonstrate knowledge and understanding of:
- Knowledge of common data structures and algorithms
- Understanding of time complexity
- Understanding of how to code data structures using object oriented methods
Subject Specific Intellectual and Research Skills
Having successfully completed this module you will be able to:
- Choose the most appropriate data structure for a particular problem
- Understand the operation of a number of important computer algorithms using those structures
- Understand how to evaluate an algorithm for efficiency
- Choose an appropriate algorithmic strategy to solve a problem
Transferable and Generic Skills
Having successfully completed this module you will be able to:
- Be able to solve problems algorithmically
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 |
---|---|
Lecture | 36 |
Preparation for scheduled sessions | 40 |
Revision | 10 |
Tutorial | 12 |
Wider reading or practice | 34 |
Follow-up work | 18 |
Total study time | 150 |
Resources & Reading list
Robert Sedgewick and Kevin Wayne (2011). Algorithms.
Weiss MA (2006). Data Structures and Algorithm Analysis in Java.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein (2009). Introduction to Algorithms.
Assessment
Formative
Assignment
Summative
Method | Percentage contribution |
---|---|
Final Assessment | 100% |
Repeat
Method | Percentage contribution |
---|---|
Set Task | 100% |
Referral
Method | Percentage contribution |
---|---|
Set Task | 100% |
Repeat Information
Repeat type: Internal & External
Linked modules
Pre-requisite: COMP1202