CSCI 136 - Fall 2019
Data Structures & Advanced Programming
Home | Bill's Lectures | Sam's Lectures | Labs | Handouts & Problem Sets | Links | CS@Williams
Bill's (9 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 Updated on 9/9 at 10:27 am (minor formatting) |
||
| 11 Sept | More on OOP in Java |
Object Nim toString Nim Student.java TestStudent.java Student2.java TestStudent2.java TrackTitles |
Lecture 3 Updated 9/11 at 10:00 am: minor typos |
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 Updated 10/14 at 10:10 am: error in description of static) |
Bailey: §§1.5-1.10 | |
| 16 Sept | Code Documentation; Vectors |
Vector-based: DictionaryVector.java Histogram: WordFreq.java |
Lecture 5 Updated 9/17 at 5:45 pm: Minor edits |
Bailey: Chapter 3 | |
| 18 Sept | Measuring Complexity |
GenWordFreq.java |
Lecture 6 Updated 9/19 at 11:53 am: Minor edits |
Bailey: Chapters 2, 4; § 5.1 | |
| 20 Sept | Recursion & Induction I |
RecursiveMethods.java Towers.java |
Lecture 7 |
Bailey: §§ 5.2-5.4 Handouts: Induction Essentials Problem Set 1 |
|
| 23 Sept | Recursion & Induction II |
ReursiveMethods.java Towers.java LIS.java |
Lecture 8 | Same as above |
|
| 25 Sept | Sorting I |
BasicCard.java Rank.java Suit.java Card.java CardRankSuit.java Card52.java Card52v2.java BinSearch.java BinSearchComparable.java |
Lecture 9 Updated 9/25 at 10:08 am: Minor edits |
Bailey: §§ 6.1-6.4; §§7.1-7.3 Java Interfaces |
|
| 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 |
Card.java CardAbstract.java CardRankSuit.java CardRankSuitPoints.java CardDeck.java Rank.java Suit.java MergeSort.java |
Lecture 11 Updated 10/2 at 8:15 am: Minor edits | Bailey: §§9.1-9.4 Handouts: Java Inheritance |
|
| 2 Oct | Lists II |
Node.java SLL.java TestSLL.java |
Lecture 12 Updated 10/2 at 8:15 am: Minor edits | Bailey: §§9.5-9.7 | |
| 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 |
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 |
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 Updated 10/18 at 10:34 am: Minor edits |
Bailey: Chapter 8 & Chapter 11 | |
| 21 Oct | Ordered Structures | Lecture 17 Updated 10/21 at 10:10 am: Minor edits |
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 |
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 Problem Set 3 | |
| 4 Nov | Heaps & Heapsort |
Lecture 23 |
Bailey: §§13.4.1-13.4.3 | ||
| 6 Nov | Binary Search Trees I |
Binary Search Tree Code Fragment |
Lecture 24 |
Bailey: §§14.1-14.4 | |
| 8 Nov | Binary Search Trees II Problem Set 3 Due Today! |
Lecture 25 Updated 11/8 at 8:45 am: Minor edits |
Bailey: §§14.4-14.8 | ||
| 11 Nov | Graphs I | Lecture 26 Updated 11/11 at 10:30 am: Minor edits |
Bailey: §16.1, 16.4.1 | ||
| 13 Nov | Graphs II |
Lecture 27 |
Bailey: §16.2 | ||
| 15 Nov | Graphs III |
BFSComponentSize.java DFSComponentSize.java RecDFSComponentSize.java |
Lecture 28 |
Bailey: §16.3 | |
| 18 Nov | Graphs IV |
MapDemo.java |
Lecture 29 |
Bailey: §16.3 | |
| 20 Nov | Graphs V | Lecture 30 |
Bailey: §16.3 | ||
| 22 Nov | Graphs VI |
FindComponents.java ShortestPathsByEdgeCount.java |
Lecture 31 |
Bailey: §§16.4.2-16.4.4 | |
| 25 Nov | Graphs VII |
Dijkstra's algorithm for finding a set of shortest paths from a given vertex Prims's algorithm for finding a minimum-cost spanning tree |
Lecture 32 |
Bailey: §16.4.5 | |
| 27-29 Nov | Thanksgiving Break | ||||
| 2 Dec | Maps & Hashing I | NaiveProbing.java GetHash.java |
Lecture 33 Updated 12/3 at 11:05 am: minor typos |
Bailey: §§15.1-15.4 | |
| 4 Dec | Maps & Hashing II |
Lecture 34 Updated 12/4 at 11:05 am: minor typos |
Bailey: §§15.4-15.7 | ||
| 6 Dec | Wrapping Up |
Lecture 35 Updated 12/6 at 8:45 am: minor typos |
|||
| Date TBD | Final Exam: Time: Monday, Dec. 16, 9:30—noon. Location: TCL 123 (Wege) |
||||