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 |