Lectures (Dan)
| Lecture | Date | Topic | Lecture Materials |
|---|---|---|---|
| 1 | Friday, February 4 | Course intro |
slides |
| 2 | Monday, February 7 | essential Java, static data types |
slides HelloWorld.java SumSome1.java SumSome2.java SumSome3.java SumSome4.java SumSome5.java SumSome6.java SumSome7.java |
| 3 | Wednesday, February 9 | more Java, Random, Scanner, design documents, Nim |
slides A design document for Nim Nim.java |
| 4 | Friday, February 11 | Exceptions, classes, and objects |
slides Nim.java (with exception handling) Program.java (Triangle driver) Triangle.java (a Triangle class) |
| 5 | Monday, February 14 | Abstraction |
slides WordSeq.java |
| 6 | Wednesday, February 16 | Generics |
slides WordFreq.java words.txt (sample input) |
| Friday, February 18 | no class, Winter Carnival | ||
| 7 | Monday, February 21 | Object equality |
slides |
| 8 | Wednesday, February 23 | Asymptotic analysis |
slides |
| 9 | Friday, February 25 | Pre-/Post-conditions, Recursion |
slides Examples where post-condition might not hold if we're not careful with pre-conditions: Example0.java (this one is probably ok) Example1.java (oh, that's weird) Example2.java (oh no!) Example3.java (Assert to the rescue) A recursive version of factorial: Factorial.java A recursive solution to the subset sum problem: SubsetSum.java |
| 10 | Monday, February 28 | Recursion/Mathematical Induction |
slides |
| 11 | Wednesday, March 2 | Interfaces/Lists |
slides A function that works with any kind of List: Example.java (generic) Example2.java (non-generic) |
| 12 | Friday, March 4 | Abstract Data Types |
slides An example using an interface and an abstract class.: Honkable.java (interface) AbstractHonkable.java (abstract class) Car.java (derived class) Goose.java (another derived class) Test.java (driver code) |
| 13 | Monday, March 7 | Sorting, part 1 |
slides Another example, this time using just an abstract class.: Cycle.java (abstract class) CycleShop.java (driver code) RoadBike.java (derived class) Tricycle.java (derived class) |
| 14 | Wednesday, March 9 | Sorting, part 2 |
slides Using bubble sort to sort an array of integers: Sorter1.java (driver class) BubbleSort1.java (sort routine and swap function) But what if we're sorting people instead of numbers? Person.java (not a number) Sorter2.java (driver class) BubbleSort2.java (generic sort and generic swap) |
| 15 | Friday, March 11 | Sorting, part 3 |
slides Sorter3.java (driver class) A comparator used to sort Person: PersonComparator.java (comparator) Some faster sort implementations: SelectionSort.java (selection sort) InsertionSort.java (insertion sort) |
| 16 | Monday, March 14 | Sorting, part 4 |
slides Be sure to see the handouts page for midterm exam prep materials. |
| 17 | Monday, April 4 | Linear structures, part 1 (stacks) |
slides |
| 18 | Wednesday, April 6 | Linear structures, part 2 (queues) |
slides Also, have a look at the structure5 source code to see how we implemented our stack and queue data structures. |
| 19 | Friday, April 8 | Iterators and binary search |
slides |
| 20 | Monday, April 11 | Ordered vectors and more binary search |
slides OrderedStructure.java OrderedVector.java Test.java |
| 21 | Wednesday, April 13 | Number representations and more iterators |
slides BIterator.java Test.java |
| 22 | Friday, April 15 | Even more iterators / tree ADT |
slides ReverseIterator.java Test.java |
| 23 | Monday, April 18 | Trees, part 1 |
slides |
| 24 | Wednesday, April 20 | Trees, part 2 |
slides BinaryTreeNode.java TreeTest.java |
| 25 | Friday, April 22 | Trees, part 3 |
slides BinarySearchTreeNode.java TreeTest.java Observe that we have not yet added a way to `get` elements from our tree! |
| 26 | Monday, April 25 | Trees, part 4 |
slides BinarySearchTreeNode.java TreeTest.java The above has been extended to have separate `key` and `value` types (`K` and `V`), as well as `find` and `contains` methods. It is still missing the `remove` method. See the course textbook for details! |
| 27 | Wednesday, April 27 | Maps |
slides MapTree.java MapTest.java Note that this version of `MapTree` includes implementations for methods we did not have time to fill in during class. |
| 28 | Friday, April 29 | Hash tables |
slides LetterFreq.java google-10000-english-usa.txt (originally from here) It looks like the first or last letter of a word is a terrible hash function; the sum of all the character is pretty good, though! |
| 29 | Monday, May 2 | Hash table collisions |
slides |
| 30 | Wednesday, May 4 | Graphs |
slides graph terminology |
| 31 | Friday, May 6 | Graph representations |
slides |
| 32 | Monday, May 9 | Priority queues and heaps |
slides |
| 33 | Monday, May 9 | Heap implementation and Dijkstra's algorithm |
slides |