# COMP20012: Algorithms and Data Structures (2007-2008)

## This is an archived syllabus from 2007-2008

Algorithms and Data Structures
Level: 2
Credit rating: 10
Pre-requisites: (COMP10021 or COMP10020 (or equivalent e.g MATH10111 and MATH10131 and MATH10211 and MATH10232) plus (COMP10081 and COMP10092) or (COMP17010 or INFO10001)
Co-requisites: No Co-requisites
Duration: 11 weeks in second semester
Lectures: 22 in total, 2 per week
Labs: 10 hours in total, 5 2-hour sessions, partly credited to COMP20910/COMP20920
Lecturers: Graham Gough, David Rydeheard
Course lecturers: Graham Gough

David Rydeheard

Timetable
SemesterEventLocationDayTimeGroup
Sem 2 w19-25,29-32 Lecture 1.1 Mon 11:00 - 12:00 -
Sem 2 w19-25,29-32 Lecture 1.1 Tue 16:00 - 17:00 -
Sem 2 w20,22,24,29,31 Lab Eng Tue 09:00 - 11:00 F
Sem 2 w20,22,24,29,31 Lab UNIX Tue 09:00 - 11:00 F
Sem 2 w20,22,24,29,31 Lab UNIX Wed 09:00 - 11:00 G
Assessment Breakdown
Exam: 80%
Coursework: 0%
Lab: 20%

## Aims

This course is an introduction to the design, analysis and wide variety of algorithms (a topic often called `Algorithmics'). We shall look at the specification of computational tasks, varieties of algorithms for tasks, demonstrating (through informal proof) that algorithms perform given tasks, the structure of algorithms and, finally, measures for comparing the performance of algorithms. We also consider the implementation of algorithms and relevant data and program structures, and principles of program design.

## Learning Outcomes

On successful completion of this course unit you will:
Be able to develop efficient algorithms for simple computational tasks.
Be able to reason about the correctness of algorithms.
Understand the concepts of time and space complexity, worst case, average case and best case complexities and the big-O notation.
Be able to compute complexity measures of algorithms, including recursive algorithms using recurrence relations.
Understand the range of behaviours of algorithms and the notion of tractable and intractable problems.
Know a range of algorithm structures and how to implement them.
Know and understand a wide range of searching and sorting algorithms.
Understand how the table ADT is used and constructed.
Understand several representations of trees, and their applications.
Understand several representations of graphs, and their applications, together with a selection of important algorithms on graphs.
Be able to construct and use the data structures mentioned above.

## Assessment of Learning outcomes

Outcomes 1 - 12 are assessed by examination Outcomes 1, 2, 4, 5, 7 - 12 are assessed by laboratory.

A1, B1, B2, C5

## Syllabus

### Introduction to Algorithms[4 ]

Idea of algorithms, algorithms and programs. Some history. Example: Simple task with a variety of not-so-simple algorithms. Algorithms and data structures (representations). Formalising algorithms in programming languages (we use both C and Standard ML in the course). Machine models. Specifications, role of correctness and mathematics. Informal proofs of correctness - format and examples.

### Performance of algorithms. [4]

Issues. Performance measures -- what we measure, machine independence, counting. Complexity. Orders of performance relative to size of input. Notation (f(n))\$. Worst case and average case complexity. Solution of recurrence relations. Examples of calculating complexity.

### Searching and Sorting Algorithms [4]

General survey of sorting algorithms and their behaviour including: mergesort, quicksort, transposition sorting (bubblesort), specialist sorting algorithms (bucketsort, radix sort), tree based algorithms (see below) (treesort, heapsort).

### Tables[3]

The Table ADT. Hash tables. Open and closed hashing. Hash functions.

### Trees[4]

Representations of Trees. Traversing Trees. Heaps and Priority Queues. Ordered Binary Trees. AVL trees. 2-3 Trees. B trees.

### Graphs[4]

Representations of Directed Graphs. Single source shortest paths problem. Dijkstra's algorithm. All pairs shortest paths. Floyd-Warshall algorithm. Directed Acyclic Graphs. Topological Sort. Undirected graphs. Kruskal's Algorithm

The course textbook is Data Structures & Problem Solving using JAVA, and the lectured material will mainly be based upon this book.

All students are urged to get hold of a copy

##### Core Text
Title: Data structures and problem solving using Java (4th edition)
Author: Weiss, Mark Allen
ISBN: 9780321546227
Publisher: Pearson
Edition: 4th
Year: 2008
This will be the course textbook.