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

Announcements

• Cortland continues to have trouble. You may wish to work on the FreeBSD systems for your labs.
• Computer Science colloquium today, 2:30 PM, TCL 206, by Greg Andrews, University of Arizona.
• Lab 4 is due Wednesday. Lab 5 out now because of reading period.
• TA hours changing for reading period. Ben will still be in on Sunday evening. Ed will be in on Tuesday instead.
• Our first exam is October 19 at 1:30 PM in Physics 205.
  • There will be an opportunity to ask exam-related questions each day up until our exam. If there is interest in a review session, we can arrange a time Monday or Tuesday evening before the exam.
  • A list of topics is available in the last section of today's online lecture notes.
  • Old exam available now.

Agenda

• Wrapup of sorting
  • Quicksort implementation and complexity
  • Sorting summary and comparisons
    • Implementations of selection sort, insertion sort, merge sort, quicksort available in SortingComparisons example
    • Selection sort: O(n²) compares, O(n) swaps in all cases
    • Insertion sort: O(n²) compares on average, O(n) best case, O(n²) swaps on average, O(n) best case
    • Merge sort: O(n logn) compares in all cases, bit O(n) space overhead
    • Quicksort: O(n²) compares in worst case (sorted or reverse sorted data), O(n logn) average case, can use some tricks to avoid worst case behavior
• Design Methods - interfaces and abstract classes
• Iterators
• Linked structures

Examples

• SortingComparisons
• Iterables
• SimpleLinkedList

Exam Topics

This is a list of some topics we have covered that you should think about for the first exam. The exam will be designed to take 90 minutes. You may use one page of handwritten notes. The use of other reference materials or electronic devices is a violation of the honor code. To be fair to everyone, papers will be collected promptly when time expires. Plan accordingly. This exam counts as 15% of the course grade.

Generally, you are responsible for anything we covered in class or in lab, and everything in the assigned reading from Java Structures, up to and including class on October 14 and Lab 5. Be sure you know how to do the assigned homework problems and programs.

• Java syntax, as we have used it in our programming assignments. 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.
• class Vector, its implementation in the structure package, 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 function or algorithm.
• Sorting. Bubble sort, selection sort, insertion sort, merge sort, quicksort, radix sort. Using Comparators and/or Comparables for sorting.
• Iterators.
• Linked lists.