CSCI 136 - Fall 2019
Data Structures & Advanced Programming
Home | Bill's Lectures | Sam's Lectures | Labs | Handouts & Problem Sets | Links | CS@Williams
Sam's (10 am) Lecture Notes and Examples
Links to lecture slides and files will be available after class on the date shown. You must be on-campus or using the Williams
proxy server (or VPN) to access these materials.
Note: The lecture schedule (cleverly) assumes that Mountain Day will occur on the first Friday of October. If it doesn't, subsequent lecture topics will be covered until Mountain Day finally occurs, after which the schedule of topics will proceed as indicated.
| Date | Lecture | Examples | Slides | Reading | |
| 6 Sept | Welcome & Java Recap |
Hello.java Hello2.java Hello3.java Hello4.java Sum1.java Sum2.java Sum3.java Sum4.java Sum5.java |
Lecture 1 | Bailey: Chapter 0 Handouts: Syllabus, Java Essentials |
|
| 9 Sept | Object-Oriented Programming in Java | No-Object Nim | Lecture 2 | ||
| 11 Sept | More on OOP in Java |
Object Nim toString Nim Student.java TestStudent.java Student2.java TestStudent2.java TrackTitles |
Lecture 3 | Bailey: §§1.1-1.4 Handouts: Java Class Types I BasicCard.java |
|
| 13 Sept | End of Java Review |
Dictionary.java TrackTitles.java trackList.xml Track.java TrackList.java Catalog.java TrackParser.java |
Lecture 4 | Bailey: §§1.5-1.10 | |
| 16 Sept | Code Documentation; Vectors |
Vector-based: DictionaryVector.java Histogram: WordFreq.java |
Lecture 5 Updated on 9/16 at 9:50 am (added leftover slides from Lecture 4) | Bailey: Chapter 3 | |
| 18 Sept | Measuring Complexity |
GenWordFreq.java |
Lecture 6 Updated on 9/18 at 9:50 am (added leftover slides from Lecture 5) | Bailey: Chapters 2, 4; § 5.1 | |
| 20 Sept | Recursion & Induction I | Lecture 7 Updated on 9/20 at 7:00 pm (small typos) | Bailey: §§ 5.2-5.4 Handouts: Induction Essentials Problem Set 1 |
||
| 23 Sept | Recursion & Induction II |
ReursiveMethods.java Towers.java LIS.java |
Lecture 8 Updated on 9/23 at 12:10 pm (small typos and formatting) |
Same as above |
|
| 25 Sept | Sorting I |
BasicCard.java Rank.java Suit.java Card.java CardRankSuit.java Card52.java BinSearch.java BinSearchComparable.java |
Lecture 9 | Bailey: §§ 6.1-6.4; §§7.1-7.3 Handouts: |
|
| 27 Sept | Sorting II: Problem Set 1 Due Today! |
JavaArraysBinSearch.java MergeSort.java |
Lecture 10 |
Bailey: §§ 6.4-6.9 Strong Induction Problem Set 2 |
|
| 30 Sept | Lists I |
Comparator examples FindShortestString.java MinElem.java Card classes Card.java CardAbstract.java CardRankSuit.java CardRankSuitPoints.java CardDeck.java Rank.java Suit.java |
Lecture 11 | Bailey: §§9.1-9.4 | |
| 2 Oct | Lists II | CardsWithAbsBase CardsWithPoints | Lecture 12 | Bailey: §§9.5-9.7
Handouts:
Java Inheritance | |
| 4 Oct | Problem Set 2 Due Today! If Mountain Day, turn in by 6:00pm |
???Mountain Day??? | |||
| 7 Oct | Linear Structures: Stacks & Queues I |
Lecture 13 Updated on 10/4 at 8:21 am (Added Announcements slide) |
Bailey: §§10.1-10.2 | ||
| 9 Oct | Linear Structures: Stacks & Queues II |
Position.java Maze.java Solver.java RecSolver.java |
Lecture 14 |
Bailey: §10.2 | |
| 11 Oct | Linear Structures: Stacks & Queues III and Iterators |
Count.java FibonacciNumbers.java Overflow.java ReverseIterator.java SkipIterator.java StackEx.java TestIterator.java |
Lecture 15 |
Bailey: §10.3 & Chapter 8 | |
| 14-15 Oct | Fall Reading Period | ||||
| 16 Oct | Mid-term exam during lab: No class meeting | ||||
| 18 Oct | Iterators; Ordered Structures |
Count.java FibonacciNumbers.java EvenFib.java SLLIterator.java ReverseIterator.java SkipIterator.java TestIterator.java |
Lecture 16 |
Bailey: Chapter 8 & Chapter 11 | |
| 21 Oct | Ordered Structures | Lecture 17 |
Bailey: Chapter 11 | ||
| 23 Oct | Trees I |
BinaryTreeCode.java BinaryExpressionTree.java BinExpTreeFromRPN.java |
Lecture 18 |
Bailey: §§12.1-12.4 | |
| 25 Oct | Trees II |
Lecture 19 |
Bailey: §§12.4-12.6 | ||
| 28 Oct | Trees III |
LeftShift.java TreeVisitor.java |
Lecture 20 |
Bailey: §§12.6-12.7 | |
| 30 Oct | Trees IV |
Lecture 21 |
Bailey: §§12.8-12.10 | ||
| 1 Nov | Priority Queues | VectorHeap.java | Lecture 22 | Bailey: §§13.1-13.4.1
|
|
| 4 Nov | Heaps & Heapsort |
Lecture 23 |
Bailey: §§13.4.1-13.4.3 | ||
| 6 Nov | Binary Search Trees I |
Heapsort Example |
Lecture 24 |
Bailey: §§14.1-14.4 | |
| 8 Nov | Binary Search Trees II Problem Set 3 Due Today! |
BinarySearchTree.java Binary Search Tree examples: AVL Tree Red-black tree Splay tree |
Lecture 25 |
Bailey: §§14.4-14.8 | |
| 11 Nov | Graphs I | Lecture 26 |
Bailey: §16.1, 16.4.1 | ||
| 13 Nov | Graphs II |
Lecture 27 |
Bailey: §16.2 | ||
| 15 Nov | Graphs III |
Lecture 28 |
Bailey: §16.3 | ||
| 18 Nov | Graphs IV |
Lecture 29 |
Bailey: §16.3 | ||
| 20 Nov | Graphs V | Lecture 30 |
Bailey: §16.3 | ||
| 22 Nov | Graphs VI |
Example from board |
Lecture 31 |
Bailey: §§16.4.2-16.4.4 | |
| 25 Nov | Graphs VII |
Prim's example Example from board Dijkstra's implementation Prim's implementation Large graph for testing Small graph for testing |
Lecture 32 |
Bailey: §16.4.5 | |
| 27-29 Nov | Thanksgiving Break | ||||
| 2 Dec | Maps & Hashing I |
Dijkstra's example GetHash.java Board photo |
Lecture 33 |
Bailey: §§15.1-15.4 | |
| 4 Dec | Maps & Hashing II |
Lecture 34 |
Bailey: §§15.4-15.7 | ||
| 6 Dec | Wrapping Up |
Lecture 35 |
|||
| Date TBD | Final Exam: Time: Monday, Dec. 16, 9:30—noon. Location: TCL 123 (Wege) |
||||
