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!

1 Exercises

1.1 Exercise 1

Exercise 1 asks you to perform asymptotic running time analysis on given Java code. You can find Exercise 1 on Gradescope.

1.2 Exercise 2

Exercise 2 asks you to manually manipulate heaps. You can find Exercise 2 on Gradescope.

1.3 Exercise 3

Exercise 3 asks you to solve recurrence relations, you can find Exercise 3 on Gradescope.

1.4 Exercise 4

Exercise 4 asks you to perform insertions into AVL Trees and B Trees, you can find Exercise 4 on Gradescope.

1.5 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.

2 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!

2.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-23au-students/p1-your netid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

Post Checkpoint 1 Survey

2.2 Project 2

You can see the description (specification) of project 1 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-23au-students/p1-your netid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

Post Checkpoint 2 Survey

2.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-23au-students/p3-your netid. You will submit this repository to gradescope for your project submissions (checkpoints and final submission).

Post Checkpoint 3 Survey

3 Exams

3.1 Exam 1

The Midterm Exam will be held on Monday October 30 during our normal lecture session (12:30-1:20pm in CSE2 G20).

An optional review session will be held in CSE2 G20 from 4:30pm-6:00pm on Friday October 27.

Here’s a preview of the cover page of the exam. You can see the instructions and a per-topic points breakdown!

3.1.1 Answer Key

You’re welcome to view our answer key for the midterm exam.

3.1.2 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 (this is the actual exam reference page).

3.1.3 Content

The exam will cover all material from the beginning of the quarter up through hashing 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.

3.1.4 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.

3.2 Exam 2

The Final Exam will be held on Thursday December 14 at 8:30am-10:20am in CSE2 G20.

An optional review session will be held Tuesday December 12 at 4:30pm-6:20pm in CSE2 room G01.

Here’s a preview of the cover page of the exam. You can see the instructions and a per-topic points breakdown!

3.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 (this is the actual exam reference page).

3.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
    • Definitions and relationships between these classes
    • 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.

3.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.