Lectures (Dan)
| Lecture | Date | Topic | Lecture Materials |
|---|---|---|---|
| 1 | Fri, 9/8 | Course intro |
Slides |
| 2 | Mon, 9/12 | Java basics |
Slides Programs discussed in class: HelloWorld.java SumSome1.java SumSome2.java |
| 3 | Wed, 9/14 | Program design |
Slides Audio recording of Kelly's lecture Programs discussed in class: SumSome3.java (pass inputs as command-line arguments; but this program does not compile. Why?) SumSome4.java (convert string arguments into numbers) SumSome5.java (takes an arbitrary number of arguments) 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) TwoPlayerGame-minimal.java (same interface but with comments removed for readability) Nim.java (what we did together in class; you are welcome to use this code!) |
| 4 | Fri, 9/16 | Classes and objects |
Slides Audio recording The Nim code we worked on in class. Nim.java (still incomplete, but more complete) TwoPlayerGame.java (the interface) Some complete examples showing two different error recovery approaches for Scanner: Example1.java (using Exceptions) Example2.java (using hasNext) Either approach is fine for this class. Choose the one you prefer. |
| 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 How to use Scanner to read two inputs on the same line: TwoInputs.java |
| 9 | Wed, 9/28 | Pre/post-conditions and recursion |
Slides Video recording 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 | Mathematical induction |
Slides Video recording |
| 11 | Mon, 10/3 | Lists |
Slides |
| 12 | Wed, 10/5 | 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 | Fri, 10/7 | Sorting, part 1 |
Slides |
| 14 | Wed, 10/12 | Sorting, part 2 |
Slides An example sorting algorithm modified to be generic and to take a comparator.: Sorter.java (driver code) BubbleSort.java (sort method) Person.java (non-primitive data) PersonComparator.java (sort order defined by comparator) |
| 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 Because I was asked about my "coding music" playlist, here it is. I make no guarantee that you will like it. It does help me concentrate. Also, yes, I use Apple Music. I'm sorry. It's not what the cool kids do. |
| 17 | Fri, 10/21 | Queue ADT / Motivation for iterators |
Slides |
| 18 | Mon, 10/24 | Midterm review |
No slides. |
| 19 | Wed, 10/26 | Iterators |
Slides |
| 20 | Mon, 10/31 | Binary search / Ordered structures |
Slides Binary search: BinarySearch.java |
| 21 | Wed, 11/2 | Ordered vector / Number representations |
Slides Ordered structure and vector: OrderedStructure.java OrderedVector.java Program.java (driver program) |
| 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 | Trees, part 2 |
Slides |
| 24 | Wed, 11/9 | Trees, part 3 |
Slides A binary search tree node: BinarySearchTreeNode.java TreeTest.java |
| 25 | Fri, 11/11 | Trees, part 4 |
Slides |
| 26 | Mon, 11/14 | Maps |
Slides A tree-backed map: MapTree.java MapTest.java |
| 27 | Wed, 11/16 | Hash tables |
Slides A program that tests uniformity for three simple hash functions: LetterFreq.java google-10000-english-usa.txt |
| 28 | Fri, 11/18 | Hash table collisions |
Slides and video |
| 29 | Mon, 11/21 | Graphs, part 1 |
Slides and video |
| 30 | Mon, 11/28 | Graphs, part 2 |
Slides |
| 31 | Wed, 11/30 | Connectness, Heaps |
Slides and video. |
| 32 | Fri, 12/2 | Heap implementation |
Slides and video. A simple binary heap implementation on top of a vector: 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. |
| 35 | Fri, 12/9 | Final exam review |
No slides. Good luck on the final exam, and enjoy your break! |