What Is This Page?

The CSE 332 course staff wants you to succeed and to learn as much as you can. Students often ask what they can do at the beginning of the quarter (or even before the quarter starts), to make sure they have the background they need. This is a great question, particularly because CSE 332 relies substantially on the CSE 143 and CSE 311 pre-requisities.

This page attempts to answer the question, by listing specific topics that are worth reviewing and making sure you are familiar with them. For many topics, we list optional practice problems because doing something is often irreplaceable for making sure you understand something — and CSE332 contains lots of doing.

We list topics in three categories:

We don't aiming to list every pre-requisite topic that may come up, but comfortable with the topics listed should put you in great shape to dive into the course.

Programming (CSE 142 and CSE 143)

We expect you to come into this course already familiar with Java and having done well in (a course like) CSE 143. If you haven't programmed in a while, we recommend doing one or two of the last few assignments in CSE 143 and/or completing some of the relevant exercises below. CSE 332 will have some substantial Java programming assignments, including one near the beginning of the course.

Be able to implement the following data structures in Java

  • ArrayList
    Implement an ArrayStringList class which has add, remove, get-at-index, and find methods. Your list should keep the elements sorted using compareTo.
  • LinkedList
    Implement a LinkedStringList class which has add-at-index, remove-at-index, get-at-index, and find methods. Your methods should all throw appropriate exceptions when given invalid arguments. Make sure to use a static inner class for your StringListNode.
  • BinaryTree
    Review the difference between a BinaryTree and a BinarySearchTree. With this in mind, implement a "TernaryIntTree" which has three children (left, middle, right) instead of two (left and right). Your TernaryIntTree class should have the following methods:
    • remove-min (removes the minimum of the tree)
    • add-leftest (adds the value as far left as possible to the tree)
    • add-rightest (adds the value as far right as possible to the tree)
    • swap (takes an int, and a String of ("left", "middle", or "right") and swaps node that the value is in with the node on the same level of the tree represented by the string without editing the nodes themselves)
    • make-list (creates and returns a java.util.List containing the same values as the tree)
    Note that since this is not a search tree, all of these operations will usually look at all the nodes in the tree. Use a static inner class for your IntTreeNode.
  • BinarySearchTree
    Implement a BinarySearchStringTree class which has add, remove, find, in-order-traversal, pre-order-traversal, and post-order-traversal methods. Your tree should order the elements using compareTo. Make sure to use a static inner class for your StringTreeNode.

Become more comfortable with recursion, as needed

You should make sure you are comfortable with both recursion (and backtracking).
Implementing any of the above tree structures will involve recursion practice.
Doing the TSP Extra Credit Assignment from CSE 143 (Spring 2015) will help you practice backtracking.

Be comfortable with interfaces, abstract classes, inheritence, and polymorphism

You should be able to understand where interfaces, abstract classes, and inheritence are useful. We won't ask you to design a hierarchy of interfaces and abstract classes, but we will ask you to work with one. Make sure you understand the super keyword.

Be comfortable with iterators and inner classes

You should be able to write an iterator for simple classes.
Add an iterator method (and an inner class ArrayStringListIterator) to your implementation of ArrayStringList above.
Add an iterator method (and an inner class LinkedStringListIterator) to your implementation of LinkedStringList above.

Be comfortable as a client of sets and maps

We will expect you to understand sets and maps (and nested maps and sets). In fact, much of our second project will involve implementing data structures with multiple levels of Objects.
Reviewing (or doing) the Evil Hangman Assignment from CSE 143 will be a nice reminder.
Doing the TSP Extra Credit Assignment from CSE 143 (Spring 2015) will help you practice these data structures.

Be comfortable with searching and sorting

Depending on the quarter you took CSE 143 (or equivalent), you might have learned none/some/all of the searching and sorting algorithms usually taught. We recommend looking over this list to make sure the ideas look familiar. We will re-cover many of these, but we will go at a quick pace, building on the CSE 143 material. As indicated below, as you go down the list, we expecting you to be less familiar with the details of the algorithms.

  • Write Code: Linear Search, Binary Search
  • Self-Learn: Insertion Sort, Selection Sort
  • Describe: Merge Sort
  • Ignore: Quick Sort

Theory (CSE 311)

CSE 311 is an important pre-requisite for this course. Please make sure you understand the following topics from CSE 311.

Proofs (specifically, Induction)

We will be writing proofs in this course! They will mostly be related to the run-time and correctness of programs which means many of them will be induction proofs. You will write some proofs on the homework and maybe even an exam. We will also apply the types of logical reasoning you learned in CSE 311 (informal, not formal) to many situations in this course.

Recurrences & Summations

We will expand on what you learned previously about recurrences and summations (usually proving closed forms by induction) to be useful in the context of analyzing algorithms. This will be very important and we expect you to remember how recursive definitions work.

Something Something Undecidable Problems

Near the end of CSE 311 you learned about the Halting Problem and discussed showing that problems are undecidable. We will use arguments somewhat like these toward the end of this course, and you should at least vaguely remember how they work. Because this will be near the end of the course, it's less important to review this material at the beginning of the quarter.

Tools for CSE 332

If you feel comfortable with all of the things above and you still want something to do to get a head start, we will expect you to pick these tools/skills up in the first few weeks of the course. Many of you will have used some of them before, but it is fine if you have not.

Choose a Java Programming Environement

We don't require you to use a particular Java environment in CSE 332, but we (officially) support the eclipse IDE (and the vim text editor). Attempting to use JGrasp in this course is a bad idea — please do not do it for your own benefit in efficiently completing the projects. JGrasp is great for introductory programming, but our projects are too substantial (multiple Java files, complicated tests and input files) for JGrasp to be a good choice. If you haven't already, now is the time to learn a more “industrial-strength” IDE. We recommend eclipse, but allow you to use another one of your choice. Ultimately, the tool you choose to use is your decision, but the course staff will be unable to (officially) offer support for JGrasp, NetBeans, BlueJ, or IntelliJ. If you run into issues using these editors with the course infrastructure, we will, unfortunately, not be able to help.

Learn to use Java command-line arguments

Many of the projects in this course will use command-line arguments to specify inputs to your program which is different than your previous programming courses. This tutorial is very helpful to eclipse users and explains how to use them. See also the CSE 390A materials.

Learn to use Gitlab

We will be using gitlab extensively in this course. Gitlab is basically identical to Github, except that it's a CSE-only version. We provide instructions to set-up gitlab in eclipse. We will also be using gitlab-ci (the ci stands for "continuous integration") for providing unit tests to you.