Course Overview
- 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).
- 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
