COMP20012: Algorithms and Data Structures (2007-2008)
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.
On successful completion of this course unit you will:
Understand basic ideas about algorithms.
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 outcomesOutcomes 1 - 12 are assessed by examination Outcomes 1, 2, 4, 5, 7 - 12 are assessed by laboratory.
Contribution to Programme Learning OutcomesA1, B1, B2, C5
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. 
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 
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).
The Table ADT. Hash tables. Open and closed hashing. Hash functions.
Representations of Trees. Traversing Trees. Heaps and Priority Queues. Ordered Binary Trees. AVL trees. 2-3 Trees. B trees.
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 TextTitle: Data structures and problem solving using Java (4th edition)
Author: Weiss, Mark Allen
This will be the course textbook.