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

Some exercises may require submitting to multiple gradescope assignments (e.g. if there is a programming component as well as a written component). The assignment instructions will make it clear when this is the case.

1.1 Exercise 0

The objectives of this exercise are to:

Set up your Java environment
Refresh our Java programming skills
Gain experience implementing data structures from an ADT
Use Java generics
Use benchmarking to study the running time of algorithms

This assignment has two main parts. The first involves implementing some data structures. The second involves analyzing the running times of your implementations using benchmarking. Each part will have a separate Gradescope submission, which will combine together to count as your exercise 0 grade.

For this exercise, you will need:

Starter Code - which contains various classes that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.
Benchmarking Worksheet - which you will copy and complete for the benchmarking portion of the assignment.

1.2 Exercise 1

The objectives of this exercise are to:

Gain experience identifying running times of given code
Use the formal definitions of big-Oh, big-Omega, and big-Theta
See examples of what changes to function do/don’t change their asymptotic behavior

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

1.3 Exercise 2

The objectives of this exercise are to:

Gain experience with solving recurrence relations using the tree method
See examples of how different changes to recurrence relations do/don’t change their asymptotic behavior

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

1.4 Exercise 3

The objectives of this exercise are to:

Understand the binary heap data structure by implementing it
See how to modify the binary heap data structure to add new operations efficiently
Apply the binary heap data structure to create a new data structure

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.

1.5 Exercise 4

The objectives of this exercise are to:

Identify the relationships between binary search trees and AVL trees by implementing AVL trees as a subclass of binary search trees (and thereby inheriting methods whenever possible).
Develop familiarity with the AVLTree data structure by implementing it. In particular: understanding what information needs to be maintained in order to preserve the structure property (height of subtrees differs by 0 or 1), using that information to correctly identify to perform rotation operations.
Highlight the advantages of using an ordered dictionary data structure (like a binary search tree) by using one to implement a new data structure

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.

1.6 Exercise 5

The objectives of this exercise are:

Understand the mechanics of an efficient chaining hash table by implementing one of your own
See how to write a good hash function for a new data structure
Apply the advantages of a hash table by using it as part of an algorithm that involves a large number of inserts and finds of a large dictionary.

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.

1.7 Exercise 6

The objectives of this exercise are:

Recognize the need for various sorting algorithm properties in applications in order to select the best-fit algorithm
Demonstrate how to determine whether or not an algorithm possess the property of being a stable sort
Apply the insights utilized from studying sorting algorithms to develop a new algorithm

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

1.8 Exercise 7

The objectives of this exercise are:

Interpret a non-graph problem into a graph problem
Implement a graph using an adjacency list representation
Adapt a standard graph algorithm (depth-first search) to solve a new problem

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes and testing files that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.

1.9 Exercise 8

The objectives of this exercise are:

Identify graphs for which Dijkstra’s algorithm gives a different answer from a BFS
Show why Disjkstra’s algorithm requires the assumption that no edge weights are negative
Show that a reasonable idea for how to deal with negative edge weights does not correctly address the problem.

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

1.10 Exercise 9

The objectives of thie exercise are:

Implement a minimum-spanning-tree algorithm
Use minimum spanning trees combined with breadth-first-search to solve a clustering problem

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes and testing files that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment.

1.11 Exercise 10

The objectives of thie exercise are:

Use the Java ForkJoin framework to write a parallel implementation of dot product.
Use the Java ForkJoin framework to write a parallel implementation of matrix multiplication.
Use the Java ForkJoin framework to write a parallel implementation of a filter operation (which will filter out empty strings from a given array of strings).

This is a programming exercise which you will submit to gradescope. There is no written component to this exercise, your code is your only submission. For this exercise, you will need:

Starter Code - which contains various classes and testing files that will be needed for this assignment.
Specification - which contains all instructions for what to do for this assignment

1.12 Exercise 11

The objectives of this exercise are:

Identify potential concurrency inssues in code
Specify the circumstances where those occur
Correct those errors

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

1.13 Exercise 12

The objectives of this exercise are:

Articulate carefullly the definitions of P and NP
Explore the relationships between complexity classes
Express how reductions help to result the P=NP question.

Instructions for this exercise are in Gradescope. To submit you will provide your answers there (either as a fill-in-the-blank or by uploading your work as an image or pdf).

2 Resubmissions

2.1 Resubmission 1

For this resubmission you may resubmit any assignment which covered content through the midterm exam. This includes EX0, EX1, EX2, EX3, and EX4. To indicate which assignment you would like to resubmit, please fill out this form. Please do so by Thursday, 7/25.

If you choose to resubmit a programming exercise (EX0, EX3, EX4) then we will extend your deadline for that exercise until Monday 7/29. Written exercises (EX1, EX2) have different versions for the resubmission with slightly alterred questions. We will enable you to submit to these altered version if you choose to resubmit one of those exercises.

Resubmitting is completely optional. If you are satisfied with your current grades then you’re welcome to ignore the resubmissions. If you choose to resubmit an assignment, the new submission’s grade will replace the original, whether lower or higher.

2.2 Resubmission 2

For this resubmission you may resubmit any assignment which covered content after the midterm exam. This includes EX5, EX6, EX7, EX8,EX9, EX10, EX11, and EX12. To indicate which assignment you would like to resubmit, please fill out this form. Please do so by Friday, 8/16 at 12:00pm (so shortly after the conclusion of the final exam).

3 Exams

3.1 Exam 1

The Midterm Exam will be held on Friday July 19 during our normal lecture session.

Here are sample solutions for the midterm.

3.1.1 Policies

Closed book, closed notes except for a 1-page 2-sided reference sheet of your own creation.
No calculators, cell phones, or other electronic devices allowed.
No writing after time is called, make sure you put your name on your paper first.
You will be provided a reference sheet (tentative) during the exam.

3.1.2 Content

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

3.1.3 Past Exams

I have drafted a practice exam that is representative of this quarter’s midterm: 24su practice midterm and Solution

Below I have several quarters’ midterm exams. Be advised that the question style, length, difficulty, and content may differ among quarters. Most notably, prior quarters covered two data structures that have been omitted from the course this quarter - Tries and B-Trees. In lieue of those, the summer 2024 exam has a greater emphasis on running time content.

Overall, here is how I would recommend that you use these sample exams to prepare.

First, study on your own without using any of the provided sample exams. To do this, review the exercises, lecture slides, and section materials. If there are things included in there that you do not recall or find confusing, look those up to seek clarification.
Next, use the past exams below to evaluate your preparedness. Attempt some problems, then compare your answer against the solution provided. If they differ, try to diagnose whether you answer is equally valid, or else where you may have a misconception (you’re welcome to come to office hours for help!). In other quarters the final exam was cumulative, so you will be able to find additional practice within the previous final exams as well.
Once you are confident with your ability to answer questions in the past exams, take the practice exam above as a simulation of the actual exam (so create your reference sheet and then set aside as 60 minute block of time to take the exam from start to finish). Then trade exams with a friend so that they can compare your solutions to the key above and give you feedback.
Use this feedback to decide where to review.

Past Exams:

3.2 Exam 2

The Final Exam will be held on Friday August 16 in lecture.

3.2.1 Policies

Closed book, closed notes except for a 1-page 2-sided reference sheet of your own creation.
No calculators, cell phones, or other electronic devices allowed.
No writing after time is called, make sure you put your name on your paper first.
You will be provided a reference sheet (tentative) during the exam.

3.2.2 Content

The final exam 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
  - Bucket 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)
  - Critical section size
  - Deadlock

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.

The final exam is not designed to be cumulative in that there may be questions designed to specifically test on content from the midterm. However, knowledge of all content from the midterm will be assumed, and so some questions may incidentally involve midterm material. For example, a question relating to sorting may involve evaluating the running time of code. A question involving graphs may require knowledge of trees.

3.2.3 Past Exams

We have provided links to past exams below. Be advised that in other (non-summer) quarters the final exam has been cumulative and has included P/NP content, and so you will see content on these covered on the midterm. Your final exam for this summer will not include that content, and can be best approximated by simply omitted those portions of the exams below. I recommend that you mostly use these exams to evaluate your preparedness rather than as a study guide.