Detailed schedule
Class 24
Exam review. Whiteboard notes: whiteboard-12-9-2021.png
Class 23
Please fill out the official feedback form if you have not done so already.
Today’s topic: depth-first and breadth-first graph traversals.
PowerPoint: intuitive-graph-traversals.pptx
Handout: graph-traversals-handout.pdf
Handout solution: graph-traversals-handout-solution.pdf
Class 22
Please fill out the official feedback form for the course (we will do this in class time).
Today’s topic: graphs, including adjacency matrices and adjacency lists.
PowerPoint: class22-graphs.pptx
Class 21
Today’s topic: Java Stream API. We pick up where we left off last time
with the filter() method. A slightly updated version of
streamdemo.zip is available.
Class 20
Main topics for today: functional programming and lambda expressions. We may also begin on the Java Stream API.
Code: functionAsParam.py, FunctionParameterDemo.java, streamdemo.zip
To run Python code without installing anything, repl.it is a good option.
Purely for interest: If you are curious about where the “lambda” in lambda-expressions comes from… The use of the Greek letter lambda to represent an anonymous function was first introduced by Alonzo Church in his 1936 paper “An Unsolvable Problem of Elementary Number Theory”, American Journal of Mathematics, Vol. 58, No. 2. (Apr., 1936), pp. 345-363. This paper is one of two that are most closely linked with the birth of computer science as an academic discipline. The other is Alan Turing’s paper on computable numbers, also from 1936. To find out more, take COMP314.
Class 19
Hash tables, session II. We continue with the PowerPoint, Java files, and handout from last time.
As part of our discussion of a few computer scientists, it’s well worth checking out Joy Buolamwini’s poetofcode.com site, especially her video art “AI, Ain’t I A Woman.”
Class 18
Hash tables, session I.
PowerPoint: class18-hash-tables.pptx UPDATED on 11/18/2021 – fixed an error on slide 29
Java: HashCodes.java and ComputerScientist.java
Handout: hash-table-handout.pdf (and the handout solution UPDATED on 11/18/2021 – fixed errors)
Class 17b
Exam review session. Please bring any questions.
Also, we will go over stable sorting again, using an updated explanation.
As previously announced, homework assignment 6 will be graded on completeness only. Solutions are being made available today. Unlike most other homework assignments, you may consult the solutions when working on this assignment. To benefit as much as possible from the assignment, you should make a serious attempt at each question before consulting the solution.
Class 17
Note the announcement of midterm exam 2. Also note that homework six will be graded on completeness only, and can optionally be turned in before the exam or after the exam.
Topics:
- Heap sort
- Stability of sorting algorithms
- Example of real-world sorting algorithm
PowerPoint: class17-heap-sort.pptx UPDATED on 11/6/2021
Class 16
Sorting algorithms: Today we study insertion sort and merge sort. Next time we study heap sort. Note that the textbook also discusses selection sort and mentions bubble sort and quick sort. It is good to read about and be aware of selection sort and bubble sort but we do not study them in detail.
We’ve seen this before:
Powerpoint: class16-insertion-and-merge-sort.pptx
Class 15
Mid-semester feedback results:
Topics for today (all optional, not on the exam or homework):
- Generic expressions like
CS232PriorityQueue<K extends Comparable<K>, V>- These are called bounded type parameters. See https://docs.oracle.com/javase/tutorial/java/generics/bounded.html
- AVL trees, or balanced trees generally.
- description
- demo
- other balanced trees that are used in practice:
- Javadoc demo
- check out the Project | Generate Javadoc… command in Eclipse.
- Proof that height of complete tree is O(log n).
- follows from the fact that 1 + 2 + 4 + 8 + 16 + … + 2^d = 2^(d+1) -1
Help and discussion of homework 5 (bring your own questions)
Class 14
-
Main topic: heaps
Class 13
-
Please complete the mid-semester survey
-
Main topic for today: binary search trees (BSTs)
- Important note: In the textbook, equal keys are stored in the left child. In the CS232 sample code, equal keys are stored in the right child. For the homework, you must store equal keys in the right child, not the left child.
- three BST operations:
- find
- add (also called insert)
- remove: 3 cases
- zero children (easy)
- one child (easy)
- two children (swap in value from smallest node in right subtree, then delete that node)
- PowerPoint slides describing the three BST operations
- handout to practice adding and removing BST nodes
Class 12
Binary trees session 2. Today’s topics:
- Definitions of full and complete binary trees
- Statement of two theorems about binary trees
- Review traversals
- Examine the code for level order traversal, which uses a queue rather than employing recursion.
- Review binary tree ADT, and compare with the Map ADT
- Overview of the Visitor design pattern (see sample code
tree.PrintVisitor.javafor an example). Additional examples of the Visitor pattern (very useful for the binary tree homework assignment): - Homework help for the binary tree homework assignment
A useful example of how to add methods that assist in debugging your code: BTNode.java
Resources:
- whiteboard notes – including updated list of nodes traversed for the warm-up example at the start
Class 11
Binary trees session 1. Today’s topics:
- Basic definitions (root, leaves, internal loads, descendants, ancestors, depth, height, path length).
- recursive nature of binary trees
- Four types of traversals: Level order, pre-order, in order, post-order.
- Our ADT for Binary trees
Resources:
For next time:
- Make a start on the binary tree homework assignment (HW4). Try to look through all the questions and highlight areas where you need a hint to get started. In the next class meeting, we will spend some time giving hints where necessary.
Exam review session
Class 10
Today’s topics:
- Iterators
- This is a repeat of class meeting 41 from COMP132. See topic 12e of the COMP132 study guide.
- code: Friends.java, FriendsIterator.java, FriendsIteratorUnfinished.java, FriendsNested.java.
- slide explaining traversal
- Example of amortized analysis: cost of adding to an ArrayList
- This is an optional topic that will not appear on exams or homework.
- tollbooth-allegory.pptx
Class 9
Today’s topics:
- Abstract data type (ADT)
- List ADT
- Array-based list implementation
- linked list implementation
- running times for list operations (array versus linked)
- stack ADT
- queue ADT
Except for stacks and queues, all of the above is review of COMP132. See Topic 12 of the COMP132 study guide.
Fill-in slide for running times of list operations (array versus linked).
Class 8
Review of how to use generics. Then the new idea for this course: how to create your own generic classes and methods.
Class 7
Review of algorithm analysis topic.
- SayHi.java
- handout for practising asymptotic analysis from first principles
- whiteboard notes
Class 6
Formal definition of big-O, big-omega, big-theta. Solving recurrence relations via expansion.
Class 5
Overview of asymptotic running times, especially big-O.
Class 4
Backtracking and its connection to recursion, via recursion trees.
- PermutationsIncomplete.java
- subsets recursion tree – fill this in for the recursion homework assignment
- whiteboard notes
Class 3
Some more sophisticated examples of recursion, including isReverse()
from the textbook and the following two examples based on COMP232
sample code:
Class 2
Elementary examples of recursion, using the coding examples in the textbook.
Class 1
Overview of the course.
Review: install Eclipse, create and run a Java program.
Homework 0: pulling an assignment from GitHub and pushing your solution for grading.
Please fill out the GitHub username form.
Last modified: Mon Dec 06 16:28:58 UTC 2021 by jmac.