DCS128: Algorithms and Data Structures - Course Notes
This course will be based around notes I have written myself. You
can find the notes listed below. The code given in these notes can be found
in the code directory.
- Drinks Machines, part 1
Introduction to using objects
- Drinks Machines, part 2
Aliasing, environments, types and scope
- Arrays in Java, part 1
Using arrays in Java
- Arrays in Java, part 2
Constructive and destructive methods on arrays
- Arrays in Java, part 3
Adding and removing items from arrays
- ArrayLists in Java
A flexible, generic, collection type from Java's library
- Strings and related types in Java
String methods (including recursive methods), string tokenizing, text input,
wrapper classes
- Lisp Lists
A simple recursive, immutable collection type
- Sorting Lisp Lists
An introduction to sorting algorithms using Lisp lists
- Recursion
How recursion works, using Lisp lists
- Return to Drinks Machines
How to represent objects in Java
- Implementing ArrayLists
An introduction to the idea of Abstract Data Types
- Sorting arrays, part 1
Insertion sort and Selection sort
- Sorting arrays, part 2
Quick sort and Merge sort
- Efficiency the "big-O notation"
- Extended drinks machines
Introduction to inheritance
- Interface and bounded generic types
Writing generalised code in Java, and the interface
Comparable
- Implementing Lisp lists
Linked lists as an alternative data structure to arrays
- Implementing ArrayLists using linked lists
More operations on linked list data structures
- Variations on ArrayLists using linked lists
Linked lists with back pointer and doubly-linked lists.
- Java's Collections Framework
An introduction to the algorithms and data structures provided in Java's
code library.
- Further aspects of Java's Collections Framework
Map types, and views.
Matthew Huntbach
Last modified: 27 January 2006