CSE 373 Winter 2006

Midterm 1 topics

You are responsible for everything covered in lecture and on the homework up to stacks and queues and simple implementations of them. You are not responsible for any specific readings in the book, but you should be familiar with the material in the book relevant to these topics.

• Basic container types and their operations; understand how to use them
  • Lists (add, contains, indexOf, size, isEmpty, remove, clear, etc.)
  • Stacks (push, pop, top, isEmpty, etc.)
  • Queues (enqueue, dequeue, front, isEmpty, etc.)
  • Sets (add, contains, size, remove, etc.)
• Standard Java container (collection) classes - don't memorize JavaDoc, but be able to use these classes given reference information about them
• Implementation techniques for containers; both Java implementations, and being able to diagram data structures and algorithms (Don't waste time memorizing detailed Java code - instead focus on knowing the ideas and strategies behind the different algorithms so you can come up with diagrams and code when you need to)
  • Arrays
  • Linked lists (single, double, with and without extra header nodes, circular)
  • Binary trees and binary search trees; including terminology, traversals, etc.
  • Trading off extra data and bookkeeping to speed up operations (e.g., size of a list)
• Iterators
  • Creating and using iterators; why do we have them?
  • Implementing iterators for various containers (arrays, lists, trees)
• Basic complexity theory
  • Concept of asymptotic complexity
  • Definition of O(...); know how to prove that a function is O(...) and what that means
  • Basic complexity classes in order from least to most expensive (O(1), O(log n), O(n), ...)
  • Complexity classes of operations in the different container implementations
  • Amortized complexity - why can we say that insert in an arraylist is O(1) and how do we prove it?
• Java coding
  • Proper coding style and techniques, mostly from CSE143 (how to define interfaces and classes; public/private; use of Java language constructs including arrays, objects and new; types; inheritance basics; etc.)
  • Commenting, including writing and reading basic JavaDoc
  • Testing, particularly using JUnit for unit tests and test coverage strategies (empty, one, many; typical vs edge cases; etc.)