Lectures (Kelly)
| Lecture | Date | Topic | Lecture Materials |
|---|---|---|---|
| 1 | Fri, 9/9 | Course intro |
Slides |
| 2 | Mon, 9/12 | Java basics |
Slides |
| 3 | Wed, 9/14 | Program design |
Slides Nim: Design document (a complete design doc for Nim; before you look at it, try to write one yourself, then compare) TwoPlayerGame.java (interface supplied in your starter code; don't change this) Audio recording of lecture |
| 4 | Fri, 9/16 | Exceptions and classes |
Slides |
| 5 | Mon, 9/19 | Abstraction and generics |
Slides Video recording The code we worked on in class. Reverser.java (a program that reverses an integer array; how can we make it work for an array of any type?) GenericReverser.java (we can't do it "safely" in Java; instead we use a Vector, which is designed for arbitrary element types) |
| 6 | Wed, 9/21 | Boxes and arrows |
Slides Video recording The code we worked on in class. Triangle.java (instance vs. static) |
| 7 | Fri, 9/21 | Static, accessibility modifiers, and Vector |
Slides Video recording Our class activity about the static keyword: activity.1.pdf (the handout) Program.java (the code that shows what happens) point-call-stack-activity-diagram.pdf (a diagram that shows the state at the end of the main method) Our class activity about accessibility modifiers: Program2.java (we made one change from Program.java; do you understand why it no longer compiles?) |
| 8 | Mon, 9/26 | Asymptotic analysis |
Slides Video recording |
| 9 | Wed, 9/28 | Pre/post-conditions and recursion |
Slides Video recording (to be posted later today) The programs we discussed: Example0.java (a seemingly benign program) Example1.java (x could actually be a string, though) Example2.java (integer overflow) Example3.java (a program that states more precisely what we want using Assert) |
| 10 | Fri, 9/30 | Recursion and mathematical induction |
Slides |
| 11 | Mon, 10/3 | Lists |
Slides |
| 12 | Wed, 10/5 | Lists, inheritance, interfaces |
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 | Fri, 10/7 | Inheritance and sorting |
Slides |
| 14 | Wed, 10/12 | Sorting cont. |
Slides The programs we discussed.: BubbleSort1.java Sorter1.java Person.java PersonComparator.java BubbleSort2.java Sorter2.java |
| 15 | Mon, 10/17 | Sorting, part 3 |
Slides |
| 16 | Wed, 10/19 | Radix sort / Stack ADT |
Slides A silly recursive algorithm that makes heavy use of a call stack.: Meowww.java |
| 17 | Fri, 10/21 | Stacks / Queue ADT |
Slides |
| 18 | Mon, 10/24 | Midterm review |
No slides. |
| 19 | Wed, 10/26 | Iterators / binary search |
Slides |
| 20 | Mon, 10/31 | Binary Seach / Ordered Structures |
Slides Binary search: BinarySearch.java Ordered Structures: OrderedStructure.java OrderedVector.java |
| 21 | Wed, 11/2 | Ordered Structures / Binary Iterators |
Slides Bit iterators: BIterator.java BIteratorTest.java |
| 22 | Fri, 11/2 | BIterator / Tree ADT |
Slides A bit iterator and a reverse iterator: BIterator.java ReverseIterator.java BIteratorTest.java (driver program) A binary tree data structure: BinaryTreeNode.java TreeTest.java (driver program) |
| 23 | Mon, 11/7 | Tree terminology |
Slides |
| 24 | Wed, 11/9 | Tree traversal / Binary Search Trees |
Slides A binary tree data structure: BinaryTreeNode.java TreeTest.java (driver program) A binary search tree data structure: BinarySearchTreeNode.java BSTreeTest.java (driver program) |
| 25 | Fr, 11/11 | Binary Search Trees |
Slides A binary search tree data structure: BinarySearchTreeNode.java TreeTest.java (driver program) |
| 26 | Mon, 11/14 | Balanced Trees / Maps |
Slides A map implemented using a binary search tree: MapTree.java MapTest.java (driver program) |
| 27 | Wed, 11/16 | Hashtables |
Slides Letter frequency example and input file tree: LetterFreq.java google-10000-english-usa.txt (input file) |
| 28 | Fri, 11/18 | Open addressing |
Slides |
| 29 | Mon, 11/21 | Graphs, part 1 |
Slides |
| 30 | Mon, 11/28 | Graphs, part 2 |
Slides |
| 31 | Wed, 11/30 | Graphs (part 3), Priority Queues, Heaps |
Slides |
| 32 | Fri, 12/2 | Heaps, Priority Queues |
Slides Priority Queue, Priority Vector, and Min Heap Code: PriorityQueue.java PriorityVector.java VectorHeap.java |
| 33 | Mon, 12/5 | Heap sort |
Slides. You have the skills now to write a heapsort algorithm yourself. If you're looking for a good study challenge, why not use my VectorHeap implementation above and see if you can modify it with a method public Vector<E> heapSort()? It's OK if calling heapSort is destructive (i.e., makes the internal Vector no longer a heap). |
| 34 | Wed, 12/7 | Dijkstra's algorithm |
Slides. Recording. |