Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Announcements

• Computer Science end-of-semester party, Friday 2:35 PM, up in the CS Lounge.
• Lab 11 this afternoon. You should be able to do most or all of it in lab. We'll meet in TCL 217a.

Agenda

• Hashing
  • Open addressing
  • External Chaining
  • Implementations in Java and structure
  • Sumamry of Hashing
• Course Overview
• Course Evaluations

Course Overview

So, what have we learned?

• How to implement and use a variety of data structures in Java.
• How to decide which structures are most appropriate for a given task.
• How to analyze the time and space complexity of structures and algorithms.
• How to think critically about the inherent tradeoffs in time, space, and (software development) complexity.
• How to decompose a problem into objects and methods.
• Lots of Java programming and object-oriented design.
  • Developing modular and reusable software.
  • Defining appropriate interfaces that expose needed functionality but hide implementation details.
  • Style and documentation.
  • Debugging techniques.

We have done much of this in the context of the text's "structure" package. However, you have the knowledge to develop your own data structures, use other available implementations (including Java's standard Collections framework), or apply this knowledge to other programming languages (e.g., C, C++ with the Standard Template Library).

And here is a list of topics.

• Java syntax. Classes, abstract classes, interfaces.
• Java memory management. What is allocated and how when regular variables, arrays, and instances of classes are created?
• Information hiding and why it's good.
• Extending classes: Inheritance.
• Pre- and post-conditions. Assertions.
• Vectors. Implementation and usage. and its methods.
• Complexity: Big "O" definition, determining for a mathematical function, determining for a given algorithm, worst, average, and best case analysis, both time and space complexity.
• Searching. Linear and binary.
• Recursion and induction. Proving correctness and complexity of a given structure or algorithm.
• Sorting. Bubble sort, selection sort, insertion sort, merge sort, quicksort, radix sort. Using Comparators and/or Comparables for sorting.
• Iterators. How to use them, how to implement them.
• Linked lists. Implementations, usage, relative merits.
  • singly-linked
  • circular
  • doubly-linked
• Linear structures and why these (and other) restricted structures can be beneficial
  • Stacks. Implementations with arrays, vectors, lists. Usage.
  • Queues. Implementations with arrays, vectors, lists. Usage.
• Ordered structures.
• Trees. Implementations and usage.
  • binary trees
  • general trees
  • tree traversals
• Heaps. Implementations and applications.
• Priority queues.
• Heapsort. Comparisons of advanced sorts.
• Binary search trees.
  • Implementation
  • Balanced trees: AVL Trees, Red-black Trees.
• Graphs: representations and algorithms
• Dictionaries and Hashing