Course Outline

1. Introduction
2. Programming Strategies
   • 2.1 Objects and ADTs
     • 2.1.1 An Example: Collections
   • 2.2 Constructors and destructors
   • 2.3 Data Structure
   • 2.4 Methods
   • 2.5 Pre- and post-conditions
   • 2.6 C conventions
   • 2.7 Error Handling
   • 2.8 Some Programming Language Notes
3. Data Structures
   • 3.1 Arrays
   • 3.2 Lists
   • 3.3 Stacks
     • 3.3.1 Stack Frames
   • 3.4 Recursion
     • 3.4.1 Recursive Functions
     • 3.4.2 Example: Factorial
4. Searching
   • 4.1 Sequential Searches
   • 4.2 Binary Search
   • 4.3 Trees
5. Complexity
   • 5. Complexity (PS)
6. Queues
   • 6.1 Priority Queues
   • 6.2 Heaps
7. Sorting
   • 7.1 Bubble
   • 7.2 Heap
   • 7.3 Quick
   • 7.4 Bin
   • 7.5 Radix
8. Searching Revisited
   • 8.1 Red-Black trees
   • 8.1.1 AVL trees
   • 8.2 General n-ary trees
   • 8.3 Hash Tables
9. Dynamic Algorithms
   • 9.1 Fibonacci Numbers
   • 9.2 Binomial Coefficients
   • 9.3 Optimal Binary Search Trees
   • 9.4 Matrix Chain Multiplication
   • 9.5 Longest Common Subsequence
   • 9.6 Optimal Triangulation
10. Graphs
    • 10.1 Minimum Spanning Tree
    • 10.2 Dijkstra's Algorithm
11. Huffman Encoding
12. FFT
13. Hard or Intractable Problems
    • 13.1 Eulerian or Hamiltonian Paths
    • 13.2 Travelling Salesman's Problem
14. Games

    Appendices

    1. ANSI C
    2. Source code listings

    Slides

    Slides from 1998 lectures (PowerPoint).

    Course Management

    • Key Points from Lectures
    • Workshops
    • Past Exams
    • Tutorials

    Texts

    Texts available in UWA library
    Other on-line courses and texts
    Algorithm Animations
    

    © John Morris, 1998