The University of Southampton

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 & Objectives

Aims

Knowledge and Understanding

Having successfully completed the module, you will be able to demonstrate knowledge and understanding of:

A1.  Knowledge of common data structures and algorithms

A2.  Understanding of time complexity

A3.  Understanding of how to code data structures using object oriented methods

Intellectual Skills

Having successfully completed the module, you will be able to:

B1.  Choose the most appropriate data structure for a particular problem

B2.  Understand the operation of a number of important computer algorithms using those structures

B3.  Understand how to evaluate an algorithm for efficiency

B4.  Choose an appropriate algorithmic strategy to solve a problem

Subject Specific Skills

Having successfully completed the module, you will be able to:

C1.  Have a greater confidence to write programs in Java

C2.  Be able to code a simple data structure

C3.  Be able to use data structures to build complex algorithms

Employability/Transferable/Key Skills

Having successfully completed the module, you will be able to:

D1. Be able to solve problems algorithmically

Syllabus

  • Introduction
    • Data Objects, Data Structures, Complex Data Structures
  • Algorithm Analysis
    • The big O
    • Correctness
  • 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 & Teaching

Learning & teaching methods

ActivityDescriptionHours
Lecture36
Tutorial12

Assessment

Assessment methods

MethodHoursPercentage contribution
Assessed Tutorials-15%
Exam2 hours85%

Referral Method: By examination

Share this module FacebookTwitterWeibo