Lecture 30:
Review & Wrap-Up
CS 136: Spring 2024
Katie Keith
📣 Announcements
Today’s agenda
CS 136: Learning Goals
Analysis
Tradeoffs of Time and Space
Advanced Programming
OOP, Java, JUnit, Git
ADTs &
Data Structures
Use & Implement
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.
ADTs to Data Structures
ADTs
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
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
ADTs to Data Structures
Hash Table
w/ separate chaining
ADTs
Data Structures
Binary Search Tree
Hash Table
w/ linear probing
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
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
CS 136: Learning Goals
Analysis
Tradeoffs of Time and Space
Advanced Programming
OOP, Java, JUnit, Git
ADTs &
Data Structures
Use & Implement
Running time of algorithms of different orders of growth
Very long = exceeds 10^25 years
Our running example: n is the number of elements in an array
Analysis: Sorting Algorithms
Algorithm | Time | Auxiliary Space |
Selection Sort | Best = Worst = O(n2) | O(1) |
Insertion Sort | Best = O(n) Worst = O(n2) | O(1) |
Merge Sort | Best = Worst = O(n log n) | O(n) |
Quick Sort | Average = Best = O(n log n) Worst = O(n2) | O(1) |
Sorting algorithms are an example of the time-space tradeoff.
CS 136: Learning Goals
Analysis
Tradeoffs of Time and Space
Advanced Programming
OOP, Java, JUnit, Git
ADTs &
Data Structures
Use & Implement
Principles of software development
Iterative Development
Compile often, execute often, test often.
Test-Driven Development
First write tests, then write code to pass those tests.
Lab progression
Lab 0: “Onboarding”
Final project: Open-ended! Aim to have you be a independent, proficient programmer
Lab progression
Lab 1
Lab 6:
Binary Search Trees
Lab 8: Graphs &
Dijkstra’s algorithm
Lab 7:
Tries
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?
Student Course Survey (SCS)
Instructions:
To access:
SCS
(15-20 minutes)
Q6. For CS “feedback from instructor” also includes:
Final exam
Breakdown of points
Total points = total number of minutes the exam should take you
Breakdown of points can help you weight the importance of studying different topics
Tips for Final Exam Studying
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.
In order traversal!
Binary Search Trees (Lab 6)
public class BinarySearchTree<Key, Value> implements SymbolTable<Key, Value>{
public Node first; // Root of BST
public int countPrint; // Number already printed for order traversal
public int size; // Number of key-value pairs
public class Node {
public Key key; // sorted by key
public Value val; // associated data
public Node left, right; // left and right subtrees
public Node(Key key, Value val) {
this.key = key;
this.val = val;
}
BST put
public void put(Key key, Value val, Comparator comparator){
first = putHelper(first, key, val, comparator);
}
private Node putHelper(Node x, Key key, Value val, Comparator comparator) {
if (x == null){
this.size += 1;
return new Node(key, val);
}
int cmp = comparator.compare(key, x.key);
if (cmp < 0) x.left = putHelper(x.left, key, val, comparator);
else if (cmp > 0) x.right = putHelper(x.right, key, val, comparator);
else x.val = val;
return x;
}
BST get
public Value get(Key key, Comparator comparator){
return getHelper(this.first, key, comparator);
}
public Value getHelper(Node x, Key key, Comparator comparator){
if(x == null){return null;}
int cmp = comparator.compare(key, x.key);
if (cmp < 0) return getHelper(x.left, key, comparator);
else if (cmp > 0) return getHelper(x.right, key, comparator);
else return x.val;
}
In-order traversal
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);
}
Number to print
Today’s agenda