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:
- Programming: The general programming concepts and Java constructs from CSE 143 (or equivalent) that we will use a lot.
- Theory: The CSE 311 topics that we are sure will arise.
- Tools: CSE 332 will use some different programming tools than you may have seen before. We will provide
all the information you need in section, handouts, etc. as needed, but many of these tools are also used in CSE 390A,
CSE 331, and other courses, and you can start learning about them on your own if you like.
We aren'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)
. If you haven't programmed in a while, we recommend doing one or two of the last few assignments in
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
Implement an ArrayStringList class which has add, remove, get-at-index, and find methods.
Your list should keep the elements sorted using compareTo.
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.
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
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.
Implement a BinarySearchStringTree class which has add, remove, find, in-order-traversal, pre-order-traversal, and
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.
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
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
Add an iterator method (and an inner class LinkedStringListIterator) to your implementation of LinkedStringList
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 Object
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:
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
users and explains how to use them. See also the CSE 390A materials.
We will be using gitlab
extensively in this course.
is basically identical to Github, except that it's a CSE-only version.
We provide instructions to set-up your CSE 332 environment
We will also be using gitlab-ci
(the ci stands for "continuous integration")
for providing unit tests to you.