Warning! You are probably being recorded (and transcribed).
Approximate overview
Did you miss anything about the grading policy?
Unfortunately, yes. In order to pass the class, you must receive a satisfactory on at least one assessment and at least one project. I hope that won’t be an issue.
If I already have satisfactory on seven assessments, do I have to do the 8th assessment?
Yes, you must make a valiant attempt at everything!
Our code seems to work.
What are some experiments you’d like to carry out?
Um We Are Talking About
U:Um [2]
l A:About [1]
l r T:Talking [0]
r W:We [0]
The entire alphabet in order: A B C D E F G H I J
A:A [9]
r B:B [8]
r r C:C [7]
r r r D:D [6]
r r r r E:E [5]
r r r r r F:F [4]
r r r r r r G:G [3]
r r r r r r r H:H [2]
r r r r r r r r I:I [1]
r r r r r r r r r J:J [0]
Nothing
One thing
O:One [0]
Replacing one thing: Foo Fu
-------------------------
INSERTING F:Foo
F:Foo [0]
-------------------------
INSERTING F:Fu
F:Fu [0]
-------------------------
A tongue twister: She Sells Seashells By The Sea Shore
S:Shore [1]
l B:By [0]
r T:The [0]
How would you update this code to make it an AVL tree?
int BST.height(BSTNode<K,V> node) method available to you. /**
* Insert a key/value into a BST.
*/
BSTNode<K,V> insert(BSTNode<K,V> root, K key, V value) {
// If the root is empty, build a new node
if (null == root) {
return new BSTNode<K,V>(key, value);
}
else {
// If the key is already in the current place, replace it
if (key.equals(root.key)) {
root.setValue(value);
}
// If the key is less than the key of the current place, work on the left
else if (key.compareTo(root.key) < 0) {
root.setLeft(insert(root.left(), key, value));
}
// If the key is greater than the key of the current place, work on the left
else {
root.setRight(insert(root.right(), key, value));
} // inner if/else
} // if/else
return rebalance(root);
} // insert
BSTNode<K,V> rebalance(BSTNode node) {
// If the left subtree is too tall
if (BSTNode.height(node.left()) - BSTNode.height(node.right()) > 1) {
BSTNode<K,V> left = node.left();
// The easy case
if (BSTNode.height(left.left()) > BSTNode.height(left.right()) {
return rotateRight(node);
}
// The hard case
else {
node.setLeft(rotateLeft(node.left()));
return rotateRight(node);
}
}
// If the right subtree is too tall
else if (BSTNode.height(node.right()) - BSTNode.height(node.left()) > 1) {
BSTNode<K,V> right = node.right();
// The easy case
if (BSTNode.height(right.right()) > BSTNode.height(right.left()) {
return rotateLeft(node);
}
// The hard case
else {
node.setRight(rotateRight(node.right()));
return rotateLeft(node);
}
}
// No rebalance needed
else {
return node;
}
} // rebalance
BSTNode<K,V> rotateRight(BSTNode<K,V> node) {
BSTNode<K,V> sub = node.left();
node.setLeft(sub.right());
sub.setRight(node);
return sub;
} // rotateRight
Skipped
/**
* Remove a key/value pair from the tree.
*/
public void remove(K key) {
this.root = remove(this.root, key);
} // remove(K)
/**
* Remove the element with a particular key from a tree.
*/
BSTNode<K,V> remove(BSTNode<K,V> node, K key) {
return node; // STUB
} // remove(BSTNode<K,V>)
/**
* Remove the largest (rightmost) element from a BST.
*
* @return a pair that contains (a) the BST without the node
* that held the largest key and (b) that node.
*/
Pair<BSTNode<K,V>,BSTNode<K,V>> removeLargest(BSTNode<K,V> node) {
// ...
} // removeLargest(BSTNode<K,V>)
Skipped
We will use “ethics” fairly broadly in this class. While ethics is a philosophical discipline, we also use it to mean “consideration of the impact of the work we do, particularly with regards to bias”.
Background reflection
What is an algorithm?
A set of unambiguous instructions that take an input and convert that input into a desired output in finite time.
Can algorithms be biased?
Yes. An algorithm might consider irrelevant knowledge.
boolean admit(Student s) {
int score = evaluate(s);
if (s.name.contains("y")) {
score += 5;
}
return (score > 100);
}
Not all biases are bad. Ones that consider “irrelevant” knowledge in making their decisions probably are.
Can the kinds of algorithms we write in this class be biased? E.g., Can a sorting algorithm be biased? Can a string matching algorithm that uses dynamic programming be biased?
What kinds of “algorithms” are discussed in the readings? E.g., the results of a machine learning algorithm, a large language model. Why would Sam say “these aren’t algorithms”?
boolean heads() {return Math.random() > 0.5;}Is there a difference between these “algorithms”
What did you see as the “big picture” ideas from the readings?