Computer Science 211
Data Structures

Agenda

• Announcements
• Lecture Assignment Recap
• Sorting Wrapup
  • Merge sort proofs
  • Doing better than O(n logn): radix sort
  • SortingComparisons program
• Design Methods - interfaces and abstract classes
• Iterators

Examples

• SortingComparisons
• Iterables
• Iterators

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 75 minutes. You may use one page of handwritten notes, two sides, up to 8 (1)/(2) ×11 in size. 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 assignments, and everything in the assigned reading from Java Structures, up to and including class on October 5 and Lab 3. Be sure you know how to do the lecture assignment problems and programs.

• Java syntax, as we have used it in our programming assignments.
• 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. Using Comparators and/or Comparables for sorting.

Lecture Assignment

No new lecture assignment for Friday.