CSE 332 – Tasks
Looking for someone to talk to about CSE332? Try the Study Center in CSE room 006! There's a table there just for working on and discussing CSE332!

All tasks will be submitted and graded on Gradescope.

1 Exercises

2 Exercise 5

Exercise 5 is a programming assignment that asks you to write Java code which checks whether a given tree is a valid AVL tree. We have created a gitlab repository for you containing the description and starter code for this exercise. You will submit on Gradescope

3 Projects

Links to projects will be posted here as they become available.

To complete the projects you will need to set up your CSE332 programming environment, which is outlined in this handout.

If you want something to reference regarding java generics, check this out: java generics reference.

If you have a pesky bug in your code that you’re struggling to track down, try following our debugging guide.

At the end of each checkpoint we will have a survey. This is intended just for us to keep up with the overall sentiment of class as a whole, and to reach out and help students who request additional support. It’s not required fill out the survey, but doing so will give us more information on how we can better serve you!

3.1 Project 1

You can see the description (specification) of project 1 here.

You can find the code for project 1 in this gitlab repository. This code is also in a gitlab repositorty we created for you at gitlab.cs.washington.edu/cse332-24wi-students/p1-yournetid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

3.2 Project 2

You can see the description (specification) of project 2 here.

You can find the code for project 2 in this gitlab repository. This code is also in a gitlab repositorty we created for you at gitlab.cs.washington.edu/cse332-24wi-students/p2-yournetid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

3.3 Project 3

You can see the description (specification) of project 3 here.

You can find the code for project 3 in this gitlab repository. This code is also in a gitlab repositorty we created for you at gitlab.cs.washington.edu/cse332-24wi-students/p3-yournetid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

4 Exams

4.1 Exam 1

The Midterm Exam will be held on Monday Feb 5 during your normal lecture sessions.

An optional review session will be held at a 4:30pm on Friday February 2 in Gates (CSE2) room G20.

Here is a preview of the actual cover page of the exam. This includes the instructions and per-topic points breakdown. The section called Algorithms will ask you to write algorithms involving data structures we’ve covered, then analyze their running times. To prepare for this section make sure you know how each data structure is organized, and how to evaluate the running time of an algorithm (material already covered in the content section below). Since this section involves multiple data structures, it was broked out into its own section rather than being included in one of the others.

4.1.1 Policies

  1. Closed book, closed notes
  2. No calculators, cell phones, or other electronic devices allowed.
  3. No writing after time is called, make sure you put your name on your paper first.
  4. You will be provided a reference sheet during the exam.

4.1.2 Content

The exam will cover all material from the beginning of the quarter up through B Trees. This includes:

  • Abstract Data Types and Data structures:
    • Their Definitions and Differences
    • Examples
  • Stacks and Queues:
    • Array and Linked List implementations and running times
    • ADT Operations
  • Asymptotic Complexity:
    • Definition of big-oh, big-omega, big-theta
    • Identifying whether f(n) belongs to O(g(n)) (or big-omega, big-theta)
    • Finding constants c and n0 to demonstrate this
    • Identifying running times (best case and worst case) of example code
  • Recurrence Relations:
    • Given a recurrence relation, solve it to closed form
  • Priority Queues:
    • ADT operations (insert, findMin, deleteMin, increaseKey, decreaseKey, remove)
    • The Heap data structure (including the heap property, complete tree, and buildHeap)
  • Tries:
    • Find, insert, and delete operations
  • Trees:
    • Definitions of height, branching factor
    • Preorder, Inorder, Postorder traversals of binary trees
  • Dictionaries:
    • ADT operations
    • Binary Search Trees: Definition, algorithms and running times of dictionary operations
    • AVL Trees: Definition, algorithms and running times of dictionary operations (including the definition of rotations and when to do them). The delete operation will NOT be covered.
    • B-Trees: Definition and motivation, algorithms and running times of dictionary operations.

4.1.3 Past Exams

We have provided links to past exams below. Since all past exams were given by a different instructor, be advised that the question style, length, and difficulty may be different this quarter. I recommend that you mostly use these exams to evaluate your preparedness rather than as a study guide.

4.1.4 Answer key

You can find an answer key for this midterm exam here.

4.2 Exam 2

The Final Exam will be held on Thursday March 14 at 12:30pm-2:20pm in Kane 120.

An optional review session will be held on Tuesday 3/12 at 4:30pm in CSE2 room G20.

Here is a preview of the actual cover page of the exam.

4.2.1 Policies

  1. Closed book, closed notes
  2. No calculators, cell phones, or other electronic devices allowed.
  3. No writing after time is called, make sure you put your name on your paper first.
  4. You will be provided a reference sheet during the exam.

4.2.2 Content

The final exam is cumulative, but will focus more on material covered since the midterm exam. In addition to the content list for the midterm exam provided above, the final will cover:

  • Hash Tables:
    • Principles of good hash function design
    • Insert/Delete/Find using these collision resolution strategies:
      • Separate Chaining
      • Linear Probing
      • Quadratic Probing
      • Double Hashing
    • Strengths and weaknesses of each collision resolution strategy
    • Load Factor, including how to calculate it and how it interacts with collision resolution
    • Rehashing
  • Sorting
    • Definitions, procedures, running times, and other properties of these algorithms:
      • Selection Sort
      • Insertion Sort
      • Heap Sort
      • Merge Sort
      • Quick Sort
      • Buckeet Sort
      • Radix Sort
  • Graphs
    • The definitions of the many terms presented in the graphs section, including:
      • node/vertex
      • edge, edge weight
      • directed/undirected graph
      • (in/out) degree
      • complete graph
      • simple graph
      • path, simple path, and cycle
      • connected graph
      • DAG
      • tree
      • Any other definitions presented in the slides
    • Graph data structures (adjacency list, adjacency matrix) and the advantages and disadvantages of each.
    • Graph Traversals (breadth-first search and depth-first search)
    • Dijkstra’s Algorithm
    • Prim’s algorithm and Kruskal’s Algorithm
    • Topological Sort
  • Parallelism:
    • ForkJoin Parallelism
    • Efficiency analysis (including work, span, perfect linear speedup, and Amdahl’s Law)
    • ForkJoin applications:
      • Reduce: Parallel sum, max, find, etc.
      • Map: vector addition, function application, etc.
    • Parallel Prefix Sum
    • Parallel Filter
  • Concurrency
    • Race Conditions:
      • Data Races
      • Bad Interleavings
    • Code Synchronization:
      • Locks, reentrant locks
      • Java’s Synchronized statement
      • Lock scheme granularity (coarse vs. fine)
      • Criticl section size
      • Deadlock
  • P, NP, NP-Completeness, EXP
    • Definitions and relationships between these classes. For example, questions like:
      • If a problem belongs to class NP, does it belong to P? How about EXP?
      • If I have a verification algorithm that runs in quadratic time, which classes does it belong to from P, NP, EXP?
    • Examples of problems in each

Note: You will likely be asked to write java code using ForkJoin and/or threads. We will not require your syntax to be perfectly correct, but it should be correct enough that we can verify the code’s would be correct if syntax issues were fixed. That is, we expect edge cases and other considerations of an algorithm to be correct, but don’t necessarily expect all keywords or semicolons to be perfect.

4.2.3 Past Exams

We have provided links to past exams below. Since all past exams were given by a different instructor, be advised that the question style, length, and difficulty may be different this quarter. I recommend that you mostly use these exams to evaluate your preparedness rather than as a study guide. In summary, question style will be similar to the midterm, quest content will be similar to the exams below.

4.2.4 Answer key

You can find an answer key for this midterm exam here.