Detailed schedule

Class 24

Exam review. Please bring questions and suggestions for review.

Class 23

There is an additional feedback form that will provide computer science faculty with significant additional assistance in shaping the COMP232 data structures course:

• Please help us by filling out the COMP232 topic assessment form at the start of class today.
• In addition, please fill out the usual 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 [UPDATED 12/7/2022] (fixed error on slide 5)

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. Java code: streamdemo.zip.

Class 20

Main topics for today: functional programming and lambda expressions. We may also begin on the Java Stream API.

This class and the next one will closely follow the corresponding textbook chapter, which is available for download as a Word document or PDF file.

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

Java: HashCodes.java and ComputerScientist.java

Handout: hash-table-handout.pdf (and the handout solution)

Class 17b

Exam review session. Please bring any questions.

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

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:

• fun link comparing sorting algorithm running times

Powerpoint: class16-insertion-and-merge-sort.pptx [UPDATED 10/31/2022]

Important basic fact: sum-of-1-to-n.pdf

Class 15

Topics for today (all optional, not on the exam or homework):

1. Climate symposium discussion (and NYTimes article on the Merge at Ethereum)
2. 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
3. AVL trees, or balanced trees generally.
   • description
   • demo
   • other balanced trees that are used in practice:
     • red-black trees
     • B-trees
4. Javadoc demo
   • check out the Project | Generate Javadoc… command in Eclipse.

Help and discussion of homework 5 (bring your own questions)

Class 14

• Results of midsemester feedback
• Main topic: heaps
  • PowerPoint slides for heaps

Next time: Help and discussion of homework 5 (bring your own questions)

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 (also called get)
    • add (also called insert)
    • remove: 3 cases to remove node N
      • zero children (easy: remove N)
      • one child (easy: promote N’s child to N’s position)
      • two children (harder: swap in value from smallest node S in right subtree of N, then call remove on S)
  • PowerPoint slides describing the three BST operations
  • handout to practice adding and removing BST nodes
  • handout solution

Class 12

Binary trees session 2. Today’s topics:

1. Definitions of full and complete binary trees; and also perfect binary trees
2. Statement of two theorems about binary trees (low importance – see textbook)
3. Very important theorem about perfect binary trees:
   • a perfect binary tree of height h has 2^(h+1)-1 nodes (required knowledge, not in textbook, see powerpoint from previous class meeting).
   • therefore, any complete binary tree with n nodes has height in O(log n) – also required knowledge. [UPDATED 10/20/2022]
   • details are available in the Binary tree PowerPoint notes from the previous class meeting.
4. Overview of the Visitor design pattern (see sample code tree.PrintVisitor.java for an example). Additional examples of the Visitor pattern (very useful for the binary tree homework assignment):
   • SumVisitor.java
   • AverageWithoutLowestVisitor.java
5. Homework help for the binary tree homework assignment
   • Hints for HW4, question 6

A useful example of how to add methods that assist in debugging your code: BTNode.java

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:

• Binary tree PowerPoint notes    UPDATED AGAIN on 10/20/2022

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

Please bring any questions for material you would like to review before the exam.

• Review of stacks and queues: stacks-and-queues-review.pptx

• If interested, read about a Canvas bug that is consuming CPU in browsers (this affects our textbook).

• Don’t forget, HW3 will be graded only on completeness, not correctness. The solutions are available on Moodle.

• Useful tip for adding Javadoc to a class, method, or constructor in Eclipse: use Generate Element Comment from the Source menu. After writing your comments, use Format Element in the same menu to fix formatting.

Class 10

Today’s topics:

1. Iterators
   • This is a repeat of material from COMP132. See topic 12e of the COMP132 study guide.
   • code: Friends.java, FriendsIterator.java, FriendsIteratorUnfinished.java, FriendsNested.java.
   • slide explaining traversal
2. 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:

1. Abstract data type (ADT)
2. List ADT
3. Array-based list implementation
4. linked list implementation
5. running times for list operations (array versus linked)
6. stack ADT
7. 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.

• warmup exercise
• MyThreeFavoriteThings.java
• MyThreeFavoriteThingsGeneric.java

Class 7

Topics:

• Asymptotic analysis of recursive programs. Example code:
  • PrintXs.java
  • SayHi.java
  • DoManyIncrements.java
• Solving recurrence relations by expansion.
  • Examples: recurrence-expansion-examples.pdf
• Useful formula: sum of geomtric progression   NEW on 9/22/2022

We may also have time to review formal definitions of asymptotic notation, in which case the following handout will be used:

• asymp-formal-defn-practise.pdf

Class 6

• Formal definition of big-O, big-omega, big-theta.
  • Handout on formal definitions of asymptotic notation.
• Best case, worst-case, and average case analysis. Example code:
  • OpCountExamples.java
  • AverageCase.java
• Solving recurrence relations via expansion.

Class 5

Overview of asymptotic running times, especially big-O.

• As an optional alternative to today’s reading from the textbook, an excerpt from the book What Can Be Computed? (WCBC) is available on Moodle (section 1, section 2)
• fun link comparing sorting algorithm running times
• Slides for asymptotic analysis: asymptotic-notation.pptx
• Handout on formal definitions of asymptotic notation
• Code for understanding best, worst, and average case:
  • OpCountExamples.java
  • AverageCase.java

Class 4

Backtracking and its connection to recursion, via recursion trees.

• SubsetsIncomplete.java, Subsets.java
• PermutationsIncomplete.java, Permutations.java
• subsets recursion tree – fill this in for the recursion homework assignment

Class 3

• Warmup: isReverse() – textbook example 1.5.2, also available as IsReverse.java, IsReverseCompleted.java

• Main idea of recursion: solve a given problem using a simpler version of the same problem

• Key technique often needed: recursive problem transformation (add extra parameters so the recursion will work properly).
  • Two examples:
    • SplitArrayIncomplete.java, SplitArray.java
    • SubsetsIncomplete.java, Subsets.java
  • slides: recursive-prob-transformation.pptx
• Note for hw1: you will need to add JUnit to the project. Search for “JUnit” on the howto page for details.

Class 2

Elementary examples of recursion, using the coding examples in the textbook, including: 1.2.1, 1.3.2, 1.3.7, 1.3.9, 1.4.3. We will return to 1.4.2 next time.

Source code:

• RecursionExamples.java
• RecursionExamplesCompleted.java

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: Wed Dec 07 05:08:19 UTC 2022 by jmac.