ODL127: Algorithms - Course Notes

This course will be based around notes I have written myself, which are also being used for the course DCS128 Algorithms and Data Structures. 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.

A completely different set of notes which was used to teach DCS128 earlier can be found here.

Exercises

Regular exercises will be set, with links from here.

  • Exercise 1 with solutions here
  • Exercise 2 with solutions here
  • Exercise 3 with solutions here and here
  • Exercise 4 with solutions here (for all questions, both an iterative and a recursive solution is given)
  • Exercise 5 with a solution here.
  • Exercise 6 with solutions here.
  • Exercise 7 with solutions here.
  • Exercise 8 with solutions here.
  • Exercise 9 with solutions here.
    There was an Exercise 10 in DCS128, but it was the same problem as you have had set for Coursework 2. Solutions to it can be found here. DCS128 had two term-time test rather than two assessed coureworks, they can be found here (mid-term) and here (end-of-term).

    Further Information

    The course text book Data Structures with Java by Ford and Topp provides an alternative coverage of the concepts, but please note this textbook covers enough material for at least two course units on algorithms and data structures. ODL127 will only cover the material in the first half of this textbook.

    As the ODL course is being run in parallel with the equivalent DCS course, you may find it useful to see a summary of the lectures that have been given to the DCS students. You can find this summary here.

    The official guide to the programming language we are using, Java 5, can be found here, see the API documentation link for full documentation on the classes provided by Java's library.

    You may find a page of links I have made to general information on Java programming to be useful, you can find that page here.

    Matthew Huntbach

    Last modified: 17 August 2006