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.

  1. Drinks Machines, part 1 Introduction to using objects
  2. Drinks Machines, part 2 Aliasing, environments, types and scope
  3. Arrays in Java, part 1 Using arrays in Java
  4. Arrays in Java, part 2 Constructive and destructive methods on arrays
  5. Arrays in Java, part 3 Adding and removing items from arrays
  6. ArrayLists in Java A flexible, generic, collection type from Java's library
  7. Strings and related types in Java String methods (including recursive methods), string tokenizing, text input, wrapper classes
  8. Lisp Lists A simple recursive, immutable collection type
  9. Sorting Lisp Lists An introduction to sorting algorithms using Lisp lists
  10. Recursion How recursion works, using Lisp lists
  11. Return to Drinks Machines How to represent objects in Java
  12. Implementing ArrayLists An introduction to the idea of Abstract Data Types
  13. Sorting arrays, part 1 Insertion sort and Selection sort
  14. Sorting arrays, part 2 Quick sort and Merge sort
  15. Efficiency the "big-O notation"
  16. Extended drinks machines Introduction to inheritance
  17. Interface and bounded generic types Writing generalised code in Java, and the interface Comparable
  18. Implementing Lisp lists Linked lists as an alternative data structure to arrays
  19. Implementing ArrayLists using linked lists More operations on linked list data structures
  20. Variations on ArrayLists using linked lists Linked lists with back pointer and doubly-linked lists.
  21. Java's Collections Framework An introduction to the algorithms and data structures provided in Java's code library.
  22. Further aspects of Java's Collections Framework Map types, and views.

Matthew Huntbach

Last modified: 27 January 2006