1 Exercises

All exercises will be submitted and graded on this Gradescope for exercises and exams.

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 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 (right click to download) - 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.
  • 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 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:

  • 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:

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

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

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.

2 Concept Checks

All concept checks will be submitted and graded on this Gradescope for concept checks.

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 is available in Gradescope! 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 meet the staff activity.

The concept check must be submitted by Thursday 1/15. You have until Friday 1/30 to complete the meet the staff activity.

2.2 CC1 Running Time

Concept Check 1 is available in Gradescope! This concept check applies to the running times and asymptotic complexity. This concept check references content covered in class on 1/7 and 1/9. You can additionally view the summaries on running time and asymptotic complexity.

Remember, you have unlimited attempts at concept checks! You’ll know the answer is correct when a explanation box pops up explaining the answer to you. Pleaes reach out via Ed, office hours, or in section if you have any questions, concerns, or confusions!

2.3 CC2 Heaps

This concept check applies to priority queues and heaps. This concept check references content covered in class on 1/12 and 1/14. You can additionally view the summaries on heaps.

2.4 CC3 Recurrences

This concept check applies to priority queues and heaps. This concept check references content covered in class on 1/16 and 1/21. You can additionally view the summaries on recurrence relations.

2.5 CC4 AVL Trees

This concept check applies to dictionaries and AVL Trees. This concept check references content covered in class on 1/23 and 1/26. A content summary will be posted shortly.

2.6 CC5 Hash Tables

This concept check applies to dictionaries and hash tables. This concept check references content covered in class on 1/28, 1/30 and 2/02. A content summary will be posted shortly.

3 Exams

The course staff will scan, upload and grade exams on this Gradescope for exercises and exams.

3.1 Exam 1

The Midterm Exam will be held on Wednesday February 11 during our normal lecture session.

A review session will be held at 5:30pm on Monday February 9, the room is TBD.

3.1.1 Policies

  1. Closed book, closed notes except for a 1-page 2-sided reference sheet of your own creation.
  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 (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

Below I have several quarters’ midterm exams. Be advised that the question style, length, difficulty, and content may differ among quarters. Most notably, prior to autumn 2024 the course included two additional data structures on the midterm exam – Tries and B-Trees.

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 these that you find confusing or do not recall, seek clarification. This can be done by reviewing lecture recordings, talking with classmates, or attending office hours.
  • 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 your answer is equally valid, or else where you may have a misconception (you’re welcome to come to office hours for help!).
  • 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 a 50 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 answer key and give you feedback.
  • Use this feedback to decide where to review.

Past Exams:

3.2 Exam 2

The Final Exam will be held at 12:30pm-2:20pm on March 19. The location is TBD