You are being recorded and transcribed.
Approximate overview
Cultural
Peer
Wellness
Misc
Greedy algorithms are optimization algorithms that follow the principle that the locally best choice leads to the globally best choice. That is not always the case.
Given a set of stamp prices and a total price to make, find the minimum number of stamps needed to make that price.
For example, if stamps are 17 cents, 10 cents, and 1 cent, the best way to make 35 cents is 2x17 + 1x1, which is three stamps.
Find a case (using stamp values of 17, 10, 1) in which the obvious greedy algorithm fails.
For the LA, you should find an example of a greedy algorithm.
Dijkstra’s Shortest-Path Algorithm
The algorithm:
Integer.MAX_VALUE).Why does this algorithm terminate?
Why is the algorithm correct?
Is this a greedy algorithm?
Some things that went wrong, and a few that went right.
//-style comments to document methods. Use /** ... */ comments
for methods (and constructors and fields).// My cool class NO
public class Cool {
// Fix object orientation NO
public void foo() {
// Don't forget the flobinator YES
..
} // foo() YES
} // class Cool YES
/**
* My cool class. YES
*/
public class Cool {
/** Fix object-orientation YES */
public void foo() {
// Don't forget the flobinator YES
..
} // foo() YES
} // class Cool YES
Please phrase ADTs as interfaces. In most cases, you should also implement the interface. (Distinguish interfaces from implementations.)
A set is an unordered collection of values. No value in the set appears more than once.
I don’t care about the (stupid) decisions that Sun/Oracle made. Lists
should not be indexed. Arrays are the primary indexed data structure.
Do not have operations like get(int index) in your List ADT.
Hash tables are not associative arrays. They have a similar set of methods, but that’s because both implement the Dictionary (or MAP) ADT.
Yes, in the Dictionary LA you can give an associative array or a hash table or a BST (or an association list) (or a sorted array of K/V pairs) as an implementation. Make sure to specify a Dictionary interface first.
INCORRECT A binary search tree is a binary tree in which the key of each node’s left subchild is less than the key of the node and the key of the node’s right subchild is greater than the key of the node. INCORRECT
7
/ \
5 8
/ \ / \
2 9 1 9
Taken from “Design Data Structures”
/**
* Records in our tournament.
*/
class Record {
/** An array of wins, losses, and ties. */
int[] wlt;
/** Create a new, empty, record. */
public Record() {
wlt = new int[3];
wlt[0] = 0;
wlt[1] = 0;
wlt[2] = 0;
} // Record()
} // Record
/**
* The tournament
*/
class Tournament {
// ...
public record(String team) {
Record r = this.lookup(team);
return r.wlt;
} // record(String)
} // class Tournament
This is a bad design because the client now has the array that we’re
storing in the Record class, which means that the client can now
change that record.
One of you decided to have fields for the “current winner” and their score, updating after each victory or tie. That made “winner” much faster.
I like this as an example of amortizing the cost.
“Here’s are some classes I wrote to give an example of how a shelter works. The Shelter class uses two lists, one of Cats and one of Dogs. Both of those classes have a name, age and breed variable, but they have different sounds that they make, and methods to go along with those sounds. The Cat and Dog classes are contributing to the Shelter class, which implements the other classes.”
public class Dog {
private String name;
private int age;
private String breed;
public Dog(String name, int age, String breed) {
this.name = name;
this.age = age;
this.breed = breed;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
public String getBreed() {
return breed;
}
public String setName(int name) {
this.name= name;
}
public int setAge(int age) {
this.age = age;
}
public String setBreed(int breed) {
this.breed= breed;
}
public void bark() {
System.out.println(name + " barks!");
}
}
public class Cat {
private String name;
private int age;
private String breed;
public Cat(String name, int age, String breed) {
this.name = name;
this.age = age;
this.breed = breed;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
public String getBreed() {
return breed;
}
public String setName(int name) {
this.name= name;
}
public int setAge(int age) {
this.age = age;
}
public String setBreed(int breed) {
this.breed= breed;
}
public void meow() {
System.out.println(name + " says meow!");
}
}
import java.util.ArrayList;
import java.util.List;
public class Shelter {
private List<Cat> cats;
private List<Dog> dogs;
public Shelter() {
cats = new ArrayList<>();
dogs = new ArrayList<>();
}
public void addCat(Cat cat) {
cats.add(cat);
}
public void addDog(Dog dog) {
dogs.add(dog);
}
public void showAvailablePets() {
System.out.print("Cats: ");
for (Cat c: cats) {
System.out.println(c.getName() + " - " + c.getBreed() + " - " + c.getAge());
System.out.println(c.meow(););
}
System.out.println("Dogs: ");
for (Dog d: dogs) {
System.out.println(d.getName() + " - " + d.getBreed() + " - " + d.getAge());
System.out.println(c.bark());
}
}
}
Issues:
bark is not a useful method.Cat and Dog should have a superclass that encapsulates the common
code.System.out.println(void) is not a good strategy.Ethical reuse involves many things:
Ideally, your answers should speak to all three.
Today’s labs should provide you with enough material to do the LAs on (a) traversal, (b) shortest path, (c) greed (b/c Dijkstra’s is a greedy algorithm), and (d) graphs.
Can you move the LA due date to Saturday night?
Sure.
Can you talk about the mental model LA?
Yes, on Friday.
What do you want me to do about README files in my ethical use LA?
“Here’s the line from my README where I provided appropriate citations.”
Sam left. Do we have to stay?
Yes, please.