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

Module Aims

This module aims to teach the basic data structures and algorithms which underpins modern software engineering, the principles behind the algorithms and data structures, and the software engineering lessons which data structures and algorithms teach us.

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

Transferable and Generic Skills

Having successfully completed this module you will be able to:

Be able to solve problems algorithmically

Subject Specific Practical Skills

Having successfully completed this module you will be able to:

Have a greater confidence to write programs in Java
Be able to code a simple data structure
Be able to use data structures to build complex algorithms

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

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, Shellsort, MergeSort, QuickSort, Bucket Sort, Radix sort, - External sorting Searching - Sequential Search, Handling Failure, Binary Search, Binary Tree Search, Advanced Tree Structures - AVL Trees, Retaining Balance, Single Rotation, Double Rotation - Splay Trees, Red-black Trees, B-trees Hash tables - Terminology, Hash table size, Hash function collision resolution, Separate chaining, - Open Addressing, Re-hashing Priority Queues (Heaps) - Terminology, Simple implementations, Binary heaps, Heap sort Graphs - Terminology, Adjacency Matrix and List, Connectivity, Breadth vs Depth first search, - Topological sort, Shortest path algorithms, Unweighted graphs, Breadth first search, - Weighted Graphs, Minimum Spanning Tree, Prim's algorithm, Biconnectivity, - Articulation points Geometric algorithms - Convex hull

Learning and Teaching

Type	Hours
Tutorial	12
Revision	10
Follow-up work	18
Lecture	36
Preparation for scheduled sessions	18
Completion of assessment task	8
Wider reading or practice	48
Total study time	150

Resources & Reading list

Collins W (2004). Data Structures and the Java Collections Framework.

Weiss MA (2006). Data Structures and Algorithm Analysis in Java.

Main M (2005). Data Structures and Other Objects Using Java.

Assessment

Summative

Method	Percentage contribution
Assessed Tutorials	15%
Exam (1.5 hours)	50%
In-class Test	35%

Referral

Method	Percentage contribution
Exam	100%

Repeat Information

Repeat type: Internal & External

Linked modules

Pre-requisite: COMP1202 Programming I