CSCI 136 :: Spring 2021

Data Structures & Advanced Programming

Home | Schedule | Labs | Handouts | Links | CS@Williams

Course Schedule

The table below lists the topics we will discuss and supplemental readings associated with each topic. This schedule represents our goals for this semester and is based on our previous experiences exploring this material at Williams—it is tentative: we may get ahead or behind as the semester progresses. The calendar will be updated to reflect any shift in topics or readings. We will also be making regular GLOW posts associated with new material/updates.

Lecture slides and additional digital resources (when used) will be posted along with lecture videos. Click on the topic to access the slides. Some of these resources will only be accessible from within the campus network. If you are off campus, please use the library's proxy server. Such slides and course materials are to help you with the course. Please do not post them publicly.

Book references:

Date Topic Lecture Materials Supplemental Reading(s)
Fr: 02/19 Course Overview/Administration  (pre)  [Form : Getting to Know You]
 (pre)  [Video : Welcome to CS 136]
 (pre)  [Video : HelloJava]

(post) [Handout : Syllabus]
(post) [Handout : Honor Code for CS136]
(post) [Slides : Welcome to CS 136]
Bailey Ch. 0 (book overview)
Mo: 02/22 Java Basics  (pre)  [Video : Java Basics]
 (pre)  [Slides : Java Basics]
 (pre)  [Handout : Java Essentials]

(post) [Code : Nim (a 1st attempt)]
(post) [Video : String & Scanner Classes]
(post) [Slides : Java String and Scanner Classes]
Bailey Appendix B (Java Reference)`
We: 02/24 OOP, Designing and Organizing Code  (pre)  [Video : OOP]
 (pre)  [Slides : OOP-slides]
 (pre)  [Video : Interfaces]

(post) [Code : OOPNim]
(post) [Code : TwoPlayerGame.java interface]
Bailey 1-1.10 (focus on 1.6, particularly '5 informal steps')
Fr: 02/26 Associations, Composition ('Has A' relationship)  (pre)  [Video : Associations and Dictionaries]
 (pre)  [Slides : Associations+Dictionaries.pdf]
 (pre)  [Video : static]
 (pre)  [Slides : static.pdf]
 (pre)  [Video : Generic Types]
 (pre)  [Slides : GenericTypes.pdf]

(post) [Code :
(post) - RockPaperScissors.java (new)
(post) - TwoPlayerGame.java (old)
(post) - InterfaceNim.java
(post) - InterfacePlay.java (new)
(post) - StaticInterfacePlay.java (new)
(post) ]
Bailey 1.4
Bailey 4.2.1
Mo: 03/01 Vectors (extensible arrays)  (pre)  [Video : Vectors]
 (pre)  [Slides : Vectors.pdf]
 (pre)  [Video : structure5 and Vector src]
 (pre)  [Video : Bag Of Holding]
 (pre)  [Slides : BagOfHolding.pdf]
[Code : BagOfHolding.java/Bag.java]
(post) [Code : GenWordFreq.java]
Bailey 3
Bailey 4-4.2.2
We: 03/03 Conditions and Assertions; Time and Space Complexity  (pre)  [Video : Conditions and Assertions]
 (pre)  [Slides : Conditions+Assertions.pdf]
 (pre)  [Video : Measuring Complexity]
 (pre)  [Slides : Measuring Complexity.pdf]

(post) [Code :
(post) - GWF2.java (a variant on GenWordFreq.java)
(post) - Music Catalog slides
(post) - TrackParser.java
(post) - Track.java
(post) - TrackList.java
(post) - Catalog.java
(post) - TrackTitles.java (old)]
Bailey 5.1
Fr: 03/05 Interfaces and Abstraction: What is a List?  (pre)  [Video: Singly-Linked Lists]
 (pre)  [Slides: Singly-Linked Lists]
 (pre)  [Video: Variations on Singly-Linked Lists]
 (pre)  [Slides: Variations on Singly-Linked Lists]
Bailey 7-7.1
Bailey 9-9.4
Mo: 03/08 Lists II  (pre)  [Video: Memory, Types, and Scope]
 (pre)  [Slides: Memory, Types, and Scope]
 (pre)  [Video: Doubly Linked Lists]
 (pre)  [Slides: Doubly Linked Lists]
 (pre)  [Video: Abstract Classes]
 (pre)  [Slides: Abstract Classes]
Bailey 9.5-end
We: 03/10 Recursion and Induction I  (pre)  [Video: Recursion]
 (pre)  [Slides: Recursion]

(post) [Code :
(post) - Collatz.java
(post) - Tower.java]
Bailey 5.2-end
Fr: 03/12 Recursion and Induction II  (pre)  [Video: Induction]
 (pre)  [Slides: Induction]

(post) [Code :
(post) - Induction.java]
Bailey 5.2-end
Mo: 03/15 Sorting I  (pre)  Video: Simple Sorting Methods
 (pre)  Video: Making Sorting Generic
 (pre)  [Slides: Simple Sorting Methods]
 (pre)  [Slides: Making Sorting Generic]

(post) [Slides:
Vector ensureCapacity analysis]
Bailey 6.1 (Bubble Sort)
Bailey 6.2 (Selection Sort)
Bailey 6.3 (Insertion Sort)
Bailey 6.7-6.8 (Comparing Objects)
We: 03/17 Sorting II  (pre)  [Video: MergeSort and QuickSort]
 (pre)  [Slides: MergeSort and QuickSort]
 (pre)  [Code : MergeSort.java]

(post) [Code : Knapsack.java]
Bailey 6.4 (Merge Sort)
Bailey 6.5 (Quicksort)
Bailey 6.6 (Radix Sort)
Bailey 6.9 (Sorting Vectors)
Fr: 03/19 Linear Structures  (pre)  Video: Stacks
 (pre)  Slides: Stacks
 (pre)  Video: Stack Examples

(post) [Code : StackSort.java]
Bailey 10-10.1 (Stacks)
Mo: 03/22 Reading Period No Class
We: 03/24 Exam Review in conferences
(post) final format
(post) final study sheet
(post) sample problems
(post) old exam problems
(post) Sample final with solutions
Exam Review
Th: 03/25 Midterm Exam [Study Guide]
[Midterm Format]
[Sample Midterm]
[Sample Solutions]
[Solutions Video]
Midterm Exam
Fr: 03/26 Linear Structures II  (pre)  Video: Queues
 (pre)  Slides: Queues

(post) [Code :
(post) - MazeRunner.java
(post) ]
Bailey 10.2 (Queues)
Bailey 10.3-end
Mo: 03/29 Iterators  (pre)  Video: Iterators
 (pre)  [Slides: Iterators]

(post) [Code :
(post) - FibonacciNumbers.java
(post) - ReverseIterator.java
(post) - SkipIterator.java
(post) - StackIterators.java
(post) - Collatz.java
(post) - Primes.java
(post) ]
Bailey 8
We: 03/31 Ordered Structures  (pre)  Video: Ordered Structures
 (pre)  [Slides: Ordered Structures]

(post) - Giterator.java
(post) - TestIterator.java
Bailey 11
Fr: 04/02 Trees I  (pre)  Video: Introduction to Trees
 (pre)  [Slides: treesIntro.java]

(post) [Code :
(post) - BinaryExpressionTree.java
(post) - BinExpTreeFromPS.java
(post) ]
Bailey 12-12.3
Mo: 04/05 Trees II  (pre)  Video: Recursion and Induction on Trees
 (pre)  Video: Tree Traversals
 (pre)  [Slides: Induction and Recursion on Trees]
 (pre)  [Slides: Tree Traversals]

(post) [Code :
(post) - InfiniteQuestions.java
(post) - TreeFile.java
(post) - GoT.txt
(post) ]
Bailey 12.4
We: 04/07 Trees III  (pre)  Video: Tree Iterators
 (pre)  Video: Tree Arrays
 (pre)  Slides: Tree Iterators and Arrays

(post) [Code :
(post) - TreeVisitor.java
(post) - ArrayTrees.java
(post) - animals.txt
(post) ]
Bailey 12.6
Fr: 04/09 Binary Search Trees I  (pre)  Video: Binary Search Trees
 (pre)  [Slides:
Introducing Binary Search Trees]
 (pre)  [Slides: BST Implementation]
Bailey 14-14.2
Mo: 04/12 Binary Search Trees II  (pre)  Video: Balanced BSTs
 (pre)  [Slides:
Balanced BSTs]

(post) [Slides: BitOpsSlides.pdf]
(post) [Code: BIterator.java]
Bailey 14.3-end
We: 04/14 Maps and Dictionaries  (pre)  Video: Maps
 (pre)  Slides: Maps
Bailey 15-15.4
Fr: 04/16 Hashtables: Collisions  (pre)  Video: Hashtables: Collisions
 (pre)  Slides: Collisions
 (pre)  [Code: NaiveProbing.java]

(post) [Code: Conference23.java]
Bailey 15.5-end
Mo: 04/19 Hashtables  (pre)  Video: Hashing: Loose Ends
 (pre)  Slides: Hashing: Loose Ends
Bailey 15.5-end
We: 04/21 Health Day Breathe Relax
Fr: 04/23 Trees IV  (pre)  Video: Huffman Encoding
 (pre)  [slides]

(post) [Code: BasicHuffman.java]
(post) [Code: FrequencyList.java]
Bailey 12.7-end
Mo: 04/26 Priority Queues and Heaps  (pre)  Video: Priority Queues and Heaps
 (pre)  [slides]

(post) [Code: GenericFrequencyList.java]
(post) [Code: CompBinTree.java]
(post) [Code: HeapHuffman.java]
(post) [Code: FileCompressor.java]
Bailey 13-13.4
We: 04/28 Heaps and Heapsort  (pre)  Video: Heapify
 (pre)  Video: Heapsort
 (pre)  [slides]

(post) Video: Skew Heaps
(post) [Slides: Skew Heap Slides]
(post) [Code: isHeap.java]
(post) [Code: CheckForHeapProperty.java]
(post) [Code: CheckHeap.java]
Bailey 13.5-end
Fr: 04/30 Graphs I  (pre)  Video: Introduction to Graphs
 (pre)  [Introduction to Graphs]
Bailey 16-16.1
Mo: 05/03 Graphs II  (pre)  Video: Trees, the Graph Interface, and Depth-First Search
 (pre)  [Slides from the videos]

(post) [Code: BFSComponentSize.java]
(post) [Code: DFSComponentSize.java]
(post) [Code: ComponentSize.java]
(post) [Code: RecDFSComponentSize.java]
(post) [Code: FindComponents.java]
(post) [Code: TrianglesFile.java]
(post) [Code: graphOfEdges.txt]
(post) [Code: bipartite.txt]
Bailey 16.2 (Interface)
Bailey 16.4
We: 05/05 Graphs III  (pre)  Video: Directed Graphs
 (pre)  [Directed Graph Slides]
 (pre)  Video: Describing Graphs
 (pre)  [Describing Graphs Slides]

(post) [Code: MemoFib.java]
(post) [Code: MemoCollatz.java]
Bailey 16.3
Fr: 05/07 Health Day Breathe Relax
Mo: 05/10 Graphs IV  (pre)  Video: Adjacency Matrix Graph Implementation
 (pre)  [slides]
Bailey 16.3
We: 05/12 Graphs V  (pre)  Video: List Graph Implementation
 (pre)  [slides]
Bailey 16.4
Fr: 05/14 Graphs VI  (pre)  Video: Shortest Paths by Edge Count
 (pre)  [Shortest Paths by Edge Count Slides]
 (pre)  [Code: ShortestPathsByEdgeCount.java']
 (pre)  [Input file for ShortestPathsByEdgeCount.java']
 (pre)  Video: Dijkstra's Algorithm
 (pre)  [Dijkstra Slides]
 (pre)  [Code: Dijkstra.java']
 (pre)  [Input file for Dijkstra.java']
Bailey 16.5
Mo: 05/17 Graphs VII  (pre)  Video: Minimum Cost Spanning Trees
 (pre)  [MCST Slides]
 (pre)  [Code: MCST.java]
 (pre)  [Sample Input for Code]
Bailey 16.5
We: 05/19 Exam Review in conferences
(post) final format
(post) final study sheet
(post) sample problems
(post) old exam problems
(post) Sample final with solutions
Exam Review
Thurs: 05/20
Tues: 05/25 Final Exam : 9:30-noon (E.T.) Final Exam