All the released exercises will be placed here. Please refer to the calendar for anticipated due dates in the future. Future due dates are tentative.

• 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.
• You may find these Math Identities useful for some exercises.

Exercise Descriptions

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.

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

Exercise 2

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.

Exercise 3

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

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.

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.

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 possesses the property of being a stable sort
• Apply the insights utilized from studying sorting algorithms to develop a new algorithm

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

Exercise 7

The objectives of this exercise are:

• Interpret a non-graph problem into a graph problem (or maybe better said, solve a problem whose input isn't a graph, but can be interpreted as a graph)
• 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.

Exercise 8

The objectives of this exercise are:

• Identify graphs for which Dijkstra’s algorithm gives a different answer from a BFS
• Show why Dijkstra’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).

Exercise 9

The objectives of this exercise are:

• Practice using a reduction as a method of code reuse; that is use a library function to solve a variant problem.
• Examine the accuracy of a reduction (by finding a counter-example to an incorrect one).
• Design a hardness reduction .
• Make connections between sorting and one of our data structures.

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

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.

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

Exercise 11

The objectives of thie exercise are:

• Use the Java ForkJoin framework to write a parallel implementation of parallel suffix.
• 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

Exercise 12

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

Exercise 13

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.

Exercise 14

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 resolve the P vs. NP question.

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