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
  • CSCI 136, Spring 2022

Website for CSCI 136, Spring 2022 (instructors: Sam McCauley and Dan Barowy)

Powered by Bootstrap 4 Github Pages