1 Exercises

All exercises will be submitted and graded on Gradescope.

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

Exercise 0 will be released Tuesday, June 23 and due Tuesday, June 30.

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 three main parts. The first involves setting up your java programming environment. The second involves implementing some data structures. The third involves analyzing the running times of your implementations using benchmarking. There is no deliverable for part 1. Parts 2 and 3 each have a separate Gradescope submission, which will combine together to count as your exercise 0 grade.

For this exercise, you will need:

  • CSE332 VSCode Profile - Our recommended configuration profile for VSCode. This disables gen-AI tools for you.
  • EX00 Starter Code - which contains various classes that will be needed for this assignment.
  • EX00 Specification - which contains all instructions for what to do for this 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 functions do/don’t change their asymptotic behavior

Instructions for this exercise appear 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 appear 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:

  • Implement the binary heap data structure
  • See how to modify the binary heap data structure to add new operations efficiently
  • Apply the binary heap data structure towards the creation of 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:

  • EX03 Starter Code - which contains various classes that will be needed for this assignment.
  • EX03 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: identify what information needs to be maintained in order to preserve the structure property (height of subtrees differs by 0 or 1), use 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:

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

1.6 Exercise 5

The objectives of this exercise are:

  • Implement the mechanics of an efficient chaining hash table
  • Write a good hash function for a new object and observe its properties
  • 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:

  • EX05 Starter Code - which contains various classes that will be needed for this assignment.
  • EX05 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
  • Identify when it is best to use comparison vs radix vs bucket sort.
  • Get a little more familiar with proof writing and decision trees.

Instructions for this exercise appear 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:

  • EX07 Starter Code - which contains various classes and testing files that will be needed for this assignment.
  • EX07 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 apear 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 (Optional)

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:

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

1.11 Exercise 10

The objectives of thie exercise are:

  • Gaining a deeper understanding of MST (Minimum Spanning Tree) algorithms.
  • Based on the understanding of MST problems, design a new algorithm to solve a related problem.

Instructions for this exercise apear 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.12 Exercise 11

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 points from a given array of points).

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:

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

2 Concept Checks

All concept checks will be submitted and graded on Gradescope.

Concept checks are submitted on Gradescope. Each is auto-graded, with feedback provided instantaneously. You also have unlimited submissions. This means you can, and should, continuously reattempt each concept check until you receive full credit.

It will be a viable strategy to simply guess and check solutions until you receive full credit, but we recommend making earnest attempts at all concept checks to maximize their usefulness helping you to self-assess your understanding. If you are ever unsure why any answer is marked correct/incorrect, we encourage you to reach out on Ed, in office hours, or in section!

We do not intend for these to be time-consuming, but instead hope that they will result in a net savings of time since they will offer some confidence in your understanding of course materials before you’re called upon to apply them in an exercise or exam.

2.1 CC0 Getting to know you

Concept check 0 will be available in Gradescope starting Monday June 22. There is not specific course material referenced by this concept check. Instead, this concept check is intended to do the following:

  1. Introduce you to how concept checks will work in this course
  2. Give you an opportunity to introduce yourself to us by providing some info
  3. Introduce you to the course by asking you to look through the syllabus to answer some questions
  4. Introduce ourselves to each other one-on-one through a Get to know the staff! activity.

The concept check must be submitted by Friday 6/26. You have until Friday 7/17 to complete the Get to know the staff! activity.