1 of 29

Lecture 30:

Review & Wrap-Up

CS 136: Spring 2024

Katie Keith

2 of 29

Final project presentation schedule here (“Schedule” tab)

Please attend to support your classmates and learn new data structures!
Any remaining lecture time will be project work time / open help session
Present what you have completed so far (not expected to be fully finished)

Final projects due to Gradescope May 19 at 10pm (hard deadline set by the College)

📣 Announcements

3 of 29

Today’s agenda

Review & Reflection (~15 minutes)
Student Course Survey (SCS) (~15 minutes)
Final exam information (~15 minutes)

4 of 29

CS 136: Learning Goals

Analysis

Tradeoffs of Time and Space

Advanced Programming

OOP, Java, JUnit, Git

ADTs &

Data Structures

Use & Implement

5 of 29

ADTs to Data Structures

Abstract Data Types (ADTs)

Data Structures

Abstract. Defines a particular set of operations that can be performed on data, (without necessarily describing how they are implemented).

Concrete. The ADT implementation in a programming language.

6 of 29

ADTs to Data Structures

ADTs

List

Finite number of elements

(same element may occur more than once)

Stack

Last in first out (LIFO) operations

Symbol Table

Associates a key with a value

Graphs

A set of vertices, pairs of which are connected by edges

Priority Queue

Poll operation removes and returns elements with min (max) priority

Queue

First in first out (FIFO) operations

7 of 29

ADTs to Data Structures

Adjacency matrices

ADTs

Data Structures

Adjacency lists

List

Finite number of elements

(same element may occur more than once)

Stack

Last in first out (LIFO) operations

Queue

First in first out (FIFO) operations

Symbol Table

Associates a key with a value

Graphs

A set of vertices, pairs of which are connected by edges

Priority Queue

Poll operation removes and returns elements with min (max) priority

8 of 29

ADTs to Data Structures

Singly Linked Lists

ADTs

Data Structures

Arrays

int[] arr = {1, 2, 3, 4, 5};

List

Finite number of elements

(same element may occur more than once)

Stack

Last in first out (LIFO) operations

Queue

First in first out (FIFO) operations

Symbol Table

Associates a key with a value

Graphs

A set of vertices, pairs of which are connected by edges

Doubly Linked Lists

Priority Queue

Poll operation removes and returns elements with min (max) priority

9 of 29

ADTs to Data Structures

List

Finite number of elements

(same element may occur more than once)

Stack

Last in first out (LIFO) operations

Queue

First in first out (FIFO) operations

Symbol Table

Associates a key with a value

Graphs

A set of vertices, pairs of which are connected by edges

Priority Queue

Poll operation removes and returns elements with min (max) priority

Hash Table

w/ separate chaining

ADTs

Data Structures

Binary Search Tree

Hash Table

w/ linear probing

10 of 29

CS 136: Learning Goals

Analysis

Tradeoffs of Time and Space

Advanced Programming

OOP, Java, JUnit, Git

ADTs &

Data Structures

Use & Implement

11 of 29

Running time of algorithms of different orders of growth

Very long = exceeds 10^25 years

n is the number of elements

(in the data structure)

12 of 29

Analysis of Symbol Table’s Data Structures

Data Structure	put	get
(Unordered) Linked List	O(n)	O(n)
Two arrays (keys sorted, binary search)	O(n)	O(log n)
Binary Search Tree	Ave = O(log n) Worst = O(n)	Ave = O(log n) Worst = O(n)
Hash Table (with separate chaining)	Ave = O(1)* Worst= O(n)	Ave = O(1)* Worst= O(n)
Hash table (with linear probing)	Ave = O(1)* Worst= O(n)	Ave = O(1)* Worst= O(n)

*Depends on uniform hashing

Classic time-space tradeoff

13 of 29

Analysis: Sorting Algorithms

Algorithm	Time	Auxiliary Space
Selection Sort	Best = Worst = O(n²)	O(1)
Insertion Sort	Best = O(n) Worst = O(n²)	O(1)
Merge Sort	Best = Worst = O(n log n)	O(n)
Quick Sort	Average = Best = O(n log n) Worst = O(n²)	O(1)

Sorting algorithms are an example of the time-space tradeoff.

14 of 29

CS 136: Learning Goals

Analysis

Tradeoffs of Time and Space

Advanced Programming

OOP, Java, JUnit, Git

ADTs &

Data Structures

Use & Implement

15 of 29

Lab progression

Lab 0: “Onboarding”

Final project: Open-ended! Aim to have you be a independent, proficient programmer

16 of 29

Lab progression

Lab 1

Lab 6:

Binary Search Trees

Lab 8: Graphs &

Dijkstra’s algorithm

Lab 7:

Tries

17 of 29

1. How has your understanding of data structures and programming changed since February?

2. What are you excited to keep learning about after this class end?

18 of 29

Student Course Survey (SCS)

Instructions:

These end-of-semester course evaluations help improve this course for other students.
They are also used by Williams to determine whether I am awarded tenure & remain at Williams.
You may skip questions you don’t wish to answer and there is no penalty for choosing not to participate
All your answers are confidential and I will only receive a report after I have submitted final grades for this class

To access:

Log into Glow
On Glow, you’ll see a course called “Course Evaluations”
Fill out the evaluation for CS 136

19 of 29

SCS

(~15 minutes)

Q6. For CS “feedback from instructor” also includes:

Lab autograder
Lab 1-on-1’s

20 of 29

Final exam logistics

Saturday May 24 from 1:30-4pm in Biology 112
2 hours + 30 minute reading period (I’m writing the exam to take 2 hrs)
Covers all material: Labs 0-8 (excluding the extensions), Lecture 0 through (and including) Lecture 27 (Dijkstra’s algorithm)

The test is cumulative so there may be repeats of midterm questions

Emphasis on problem-solving

Pen & paper exam. You’ll read some code, write some code, answer some conceptual questions

Closed book, closed notes except for:

Allowed one 8.5x11in hand-written reference sheet (front & back)

21 of 29

Final exam logistics

Accommodations → email and/or talk to Katie
Due to the size of the class, the department does not allow me to schedule alternative exam days. Only exceptions:

Official exam hardship. “Three or more exams in consecutive exam periods is considered a hardship.”
Note from a doctor / medical professional

22 of 29

Breakdown of points

Total points = expected number of minutes the exam should take

Breakdown of points can help you weight the importance of studying different topics

23 of 29

Tip: Review the learning objectives of the labs

24 of 29

Review: Binary Search Tree to implement a Symbol Table

To implement a Symbol Table with a Binary Search Tree:

The keys of nodes still obey the left subtree/right subtree ordering
And nodes also have an associated value.

'E'

root node

the key of this node is ‘E’

105

'S'

30

'X'

106

'A'

35

'C'

12

'H'

24

'R'

45

the value of this node is 105

25 of 29

Printing first n keys in alphabetical order

this.countPrint;

…

public void inOrderTraversalPrint(Node node, int n) {

if (node == null || this.countPrint >= n) {

return;

}

// Traverse left

inOrderTraversalPrint(node.left, n);

// Print center/parent node

if(this.countPrint < n){

System.out.println(node.key);

this.countPrint++;

}

// Traverse right

inOrderTraversalPrint(node.right, n);

}

Instance variable (earlier in the class)

26 of 29

Tip: Review the think-pair-shares

27 of 29

Tip: Reading the book now can also solidify concepts!

https://algs4.cs.princeton.edu/home/

28 of 29

Tips for Final Exam Studying

Create study groups
Post questions to Piazza
Review your labs
Readings from the textbook
Exercises from the textbook
Review your midterm/midterm corrections
Practice exam from Jim:

Disclaimer: He may have covered a different subset of material than we did

29 of 29

Today’s agenda

Review & Reflection (~15 minutes)
Student Course Survey (SCS) (~15 minutes)
Final exam information (~15 minutes)