P204 - Data Structures and Algorithms
Lecturer: Ross Paterson
(room A505, phone 020-7477 8342)
Tutor: Mike Iossif
(room A516, phone 020-4777 3700)
Department of Computing,
School of Informatics,
City University
NEW:
electronic handin procedure
for coursework.
This module will be delivered over a period of 10 weeks.
The provisional plan for the coverage of topics is as shown below
(the numbers in brackets are the relevant portions of the textbook):
- Introduction to algorithms: binary search.
Correctness using assertions.
Time and space complexity.
Asymptotic analysis (big O notation).
[2]
[slides,
exercises and solutions]
- Elementary sorting techniques: selection and insertion.
[9.1.1-2]
Lower bounds.
[9.2]
[slides,
exercises and solutions]
- Recursion.
[5]
Quicksort.
[9.3.3]
[slides,
exercises and solutions]
- Introduction to Abstract Data Types.
Priority queues and heaps.
[6.9,9.3.2]
[source files,
slides,
exercises and solutions]
- Stacks, queues, vectors and singly linked lists. [3.1,4.1,4.2]
[slides,
exercises and solutions]
- Circular lists. [3.3]
Doubly linked lists. [3.2]
[slides,
exercises and solutions]
- Hash tables.
[10.1-3]
[slides,
exercises and solutions]
- Tree structures.
Tree traversals.
[6.1-4]
[slides,
exercises and solutions]
- Search trees.
[6.5-6]
Overview of rebalancing schemes.
[6.7-8,7.1]
[slides,
exercises and solutions]
- Graph algorithms: traversals, shortest paths.
[8.1-3]
[slides,
exercises and solutions]
The coursework for this module will take the form of two programming
assignments in Java:
- (40%) distributed in week 4, due in week 6.
[file Parameters.java
needed for the coursework]
- (60%) distributed in week 6, due in week 8.
[files
needed for the coursework]
Data Structures and Algorithms in Java
by Adam Drozdek,
published by Brooks/Cole.
You can also download the
source code for the programs in the book.