CSCI 136 :: Fall 2020
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: 09/11 | Course Overview/Aministration |
(pre)[Form : Getting to Know You]
(pre)[Video : Welcome to CS 136] (pre)[Video : HelloJava] (post)[Handout : Syllabus] (post)[Slides : Welcome to CS 136] |
Bailey Ch. 0 (book overview) |
| Mo: 09/14 | Java Basics |
(pre)[Video : Java 1]
(pre)[Handout : Java Essentials] (post)[Code : BasicNim (a 1st attempt)] (post)[Code :Nim (improved w/ methods)] (post)[Video : String & Scanner Classes] |
Bailey Appendix B (Java Reference)` |
| We: 09/16 | OOP, Designing and Organizing Code |
(pre)[Video : Overview,]
(pre)[Video : Why Java,] (pre)[Video : OOP] (pre)[Video : Interfaces] (pre)[Video : static]
[Slides : OOP.pdf] [Conference Code: - MethodNim.java - ClassNim.java - InterfaceNim.java - TwoPlayerGame.java - InterfacePlay.java ] |
Bailey 1-1.10 (focus on 1.6, particularly '5 informal steps') |
| Fr: 09/18 | Associations, Composition ('Has A' relationship) |
(pre)Video : Associations, Dictionaries, and Generic Types
[Slides : Associations+Dictionaries.pdf] GenericTypes.pdf] [Code : - RockPaperScissors.java (new) - InterfacePlay.java (new) - GameRoom.java(new) - InterfaceNim.java (old) - TwoPlayerGame.java (old) ] |
Bailey 1.4 Bailey 4.2.1 |
| Mo: 09/21 | Vectors (extensible arrays) |
(pre)Video: Overview
(pre)Video: Vectors [slides] [Vector Example] [Code : Bag/BagOfHolding] |
Bailey 3 Bailey 4-4.2.2 |
| We: 09/23 | Time and Space Complexity |
(pre)Video: Conditions and Assertions
(pre)Video: Measuring Complexity [Slides: Conditions and Assertions] [Slides: Measuring Complexity] [Slides: Music Catalog] [Code : - GenWordFreq.java (new) - TrackParser.java (new) - Track.java (new) - TrackList.java (new) - Catalog.java (new) - TrackTitles.java (old) ] |
Bailey 5.1 |
| Fr: 09/25 | Interfaces and Abstraction: What is a List? |
(pre)Video: Singly-Linked Lists
[Slides: Singly-Linked Lists] (post)Video: Variations on Singly-Linked List |
Bailey 7-7.1 Bailey 9-9.4 |
| Mo: 09/28 | Lists II |
(pre)Video: Doubly-Linked Lists
[Slides: Doubly-Linked Lists] (post)Video: Abstraction (post)Slides: Slides |
Bailey 9.5-end |
| We: 09/30 | Recursion and Induction I |
(pre)Video: Recursion
[Slides: Recursion] [Code : - Chain.java - RecursiveMethods.java ] |
Bailey 5.2-end |
| Fr: 10/02 | Recursion and Induction II |
(pre)Video: Mathematical Induction
[Slides: Mathematical Induction] |
Bailey 5.2-end |
| Mo: 10/05 | Sorting I |
(pre)Video: Simple Sorting Methods
(pre)Video: Making Sorting Generic [Slides: Simple Sorting Methods] [Slides: Making Sorting Generic] [Code : - BinSearch.java - BinSearchComparable.java ] (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: 10/07 | Sorting II |
(pre)Video: MergeSort and QuickSort
[Slides: MergeSort and QuickSort] [Code : - MergeSort.java ] (post)[Conference: RecPractice.java] (post)[Conference: Knapsack.java] |
Bailey 6.4 (Merge Sort) Bailey 6.5 (Quicksort) Bailey 6.6 (Radix Sort) Bailey 6.9 (Sorting Vectors) |
| Fr: 10/09 | Mountain Day | No Class | No Class |
| Mo: 10/12 | Reading Period | No Class | No Class |
| We: 10/14 | Exam Review in conferences |
(pre)Video: Sample solution Video
[Exam Format] |
Exam Review |
| Th: 10/15 | Midterm Exam |
[Study tips (read this first)
[Sample midterm] [Sample solutions] [Sample solution Video] [Exam Format] |
Midterm Exam |
| Fr: 10/16 | Linear Structures |
(pre)Video: Linear Structures (Stacks)
(pre)Video: Stack Examples (expressions) [slides] (post)[Conference: StackSort.java] (post)[Conference: JDB walkthrough] |
Bailey 10-10.1 (Stacks) |
| Mo: 10/19 | Linear Structures II |
(pre)Video: Queues
[slides] (post)[Code : (post)- MazeRunner.java (post)] |
Bailey 10.2 (Queues) Bailey 10.3-end |
| We: 10/21 | Iterators |
(pre)Video: Iterators
[Slides: Iterators] [Code : - FibonacciNumbers.java - ReverseIterator.java - SkipIterator.java - StackIterators.java ] (post)- TestIterator.java |
Bailey 8 |
| Fr: 10/23 | Ordered Structures |
(pre)Video: Ordered Structures
[Slides: Ordered Structures] |
Bailey 11 |
| Mo: 10/26 | Trees I |
(pre)Video: Introduction to Trees
[Slides: treesIntro.java] [Code : - BinaryExpressionTree.java ] (post)[Code : (post)- BinExpTreeFromPS.java (post)- InfiniteQuestions.java (post)] |
Bailey 12-12.3 |
| We: 10/28 | Trees II |
(pre)Video: Recursion and Induction on Trees
(pre)Video: Tree Traversals [Slides: Induction and Recursion on Trees] [Slides: Tree Traversals] ] (post)[Code : (post)- TreeVisitor.java (post)- TreeFile.java (post)- GoT.txt (post)] |
Bailey 12.4 |
| Fr: 10/30 | Trees III |
(pre)Video: Traversing trees with iterators
(pre)Video: Array-based tree representation [Slides: Traversing Trees with Iterators] [Slides: Array-based binary tree representation] (post)[Code : (post)- ArrayTrees.java (post)] |
Bailey 12.6 |
| Mo: 11/02 | Binary Search Trees I |
(pre)Video: Binary Search Trees
[Slides: Introducing Binary Search Trees] [Slides: BST Implementation] |
Bailey 14-14.2 |
| We: 11/04 | Binary Search Trees II |
(pre)Video: Balanced BSTs
[Slides: Balanced BSTs] (post)[Slides: BitOpsSlides.pdf] (post)[Code: BIterator.java] |
Bailey 14.3-end |
| Fr: 11/06 | Maps and Dictionaries |
(pre)Video: The Map Interface
[Map Interface slides] (post)[Code: HashTable.java] (post)[Code: Lumberjack.txt] |
Bailey 15-15.4 |
| Mo: 11/09 | Hashtables |
Video: Hashtables and Collisions
[slides] [NaiveProbing.java] |
Bailey 15.5-end |
| We: 11/11 | Hashtables |
Video: Hashtables: Loose ends
[slides] (post)[Code: HashValue.java] (post)[Code: HashBag.java] (post)[Code: HashBagIterator.java] (post)[Code: LexiconHashBag.java] (post)[Code: Lexicon.java] |
Bailey 15.5-end |
| Fr: 11/13 | Trees IV |
(pre)Video: Huffman Encoding
(pre)[slides] [ (post)[Code: BasicHuffman.java] (post)[Code: FrequencyList.java] |
Bailey 12.7-end |
| Mo: 11/16 | 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: 11/18 | Heaps and Heapsort |
(pre)Video: Creating Heaps
(pre)[Heapify slides] (pre)Video: Heapsort (pre)[HeapSort slides] (post)[Code: IsHeap.java] (post)[Code: CheckForHeapProperty.java] (post)[Code: CheckHeap.java] (post)[Video: Skew Heaps] (post)[SkewHeap slides] |
Bailey 13.5-end |
| Fr: 11/20 | Graphs I |
(pre)Video: Introduction to Graphs
(pre)[Introduction to Graphs] Optional Material: [PageRank] |
Bailey 16-16.1 |
| Mo: 11/23 | Graphs II |
(pre)Video: Trees, the Graph Interface, and Depth-First Search
(pre)[Slides from the videos] [Code: BFSComponentSize.java] [Code: DFSComponentSize.java] [Code: ComponentSize.java] [Code: RecDFSComponentSize.java] |
Bailey 16.2 (Interface) Bailey 16.4 |
| We: 11/25 | ThanksGiving Break | No Class | No Class |
| Fr: 11/27 | ThanksGiving Break | No Class | No Class |
| Mo: 11/30 | Graphs III |
(pre)[Graph Activity]
(pre)Video: Directed Graphs (pre)[Directed Graph Slides] (pre)Video: Describing Graphs (pre)[Describing Graphs Slides] (post)[Code: Triangles.java] |
Bailey 16.3 |
| We: 12/02 | Graphs IV |
(pre)Video: Adjacency Matrix Graph Implementation
[slides] (post)[Graph Code Snippets'] |
Bailey 16.3 |
| Fr: 12/04 | Graphs V |
(pre)Video: Adjacency List Graph Implementation
[slides] (post)[FindComponents.java'] (post)[Input file for FindComponents.java'] |
Bailey 16.4 |
| Mo: 12/07 | 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 |
| We: 12/09 | Graphs VII |
(pre)Video: Minimum Cost Spanning Trees
[slides] |
Bailey 16.5 |
| We: 12/09 | Exam Study Materials |
[Topic list/advice (read this first)
[Sample final] [Sample final with solutions] [Three Sample Final Problems] [Final Format] |
Exam Study Materials |
| We: 12/16 | Final Exam | Final Exam |