DCS128 Algorithms and Data Structures Notes

Notes written by Matthew Huntbach

These are the notes used when this course was run between 2002 and 2005.
They were superseded by a completely new set of notes in 2006.

Note, the code used in these notes will be made available here.
Some notes I wrote for a previous course that introduces programming in Java can be found here.

Structured programming: Revision notes part 1
Static methods: Revision notes part 2
Full array traversal: Revision notes part 3
Interrupted array traversal: Revision notes part 4

Iteration and recursion: the Powers example
Iteration and sorting-in-place: the Selection Sort example
Recursion and constructive sort: the Merge Sort example
Algorithm efficiency and the big-O notation: Comparing sorting algorithms
More recursion: the Array Search examples
Environments and tail recursion: more searching and sorting examples

Introduction to abstract data types: Sets using arrays, part 1
Implementation and application of abstract data types: Sets using arrays, part 2
Constructive and destructive abstract data types: Sets using Arrays, part 3
Intersection and union: Sets using Arrays, part 4

Linked lists: Sets using linked lists
Trees: Sets using trees
Recursion with linked structures: more destructive set implementations
Constructive recursion with linked structures: more constructive set implementations

Abstract data types: Lists
Another sorting algorithm: Quick Sort with Lists
Using the List and Tree abstract data types: Sets implemented using List and Tree ADT
Stacks and the type Object: set maintenance with a multiple undo
Using stacks and queues: stacks, queues, and recursion elimination
Doubly-linked lists: the Editor example
Array implementations: stacks, queues and lists implemented using arrays

Abstract classes and interfaces: Tables
Using tables and files: the student database examples, part 1
Hash tables: the student database examples, part 2
Enumerations: the students database examples, part 3

Representing graphs: Graphs, part 1
Path finding: Graphs, part 2
Shortest path finding: Graphs, part 3
Best first search of costed graphs: Graphs, part 4
Improving path search efficiency: Graphs, part 5

Heaps: Priority queues



Michael Main's PowerPoint Presentations

Associated with the book Data Structures and Other Objects Using Java

Preconditions and Postconditions
Object Oriented Programming
Collection Classes
Linked Lists in Action
Using a Stack
Recursive Thinking
Complete Binary Trees
Binary Search Trees
Heaps
Hash Tables
Quadratic Sorting

Frank M. Carrano and Janet J. Prichard's PowerPoint Presentations

Associated with the book Data Abstraction and Problem Solving with Java

Chapter 1: Principles of programming and software engineering
Chapter 2: Recursion: the mirrors
Chapter 3: Data abstraction: the walls
Chapter 4: Linked lists
Chapter 5: Recursion as a problem-solving technique
Chapter 6: Stacks
Chapter 7: Queues
Chapter 8: Class relationships
Chapter 9: Algorithm efficiency and sorting
Chapter 10: Trees
Chapter 11: Tables and priority queues
Chapter 12: Advanced implementations of tables
Chapter 13: Graphs
Chapter 14: External methods