Ch. 20 Lecture Notes - Set, Map, HashSet, TreeSet, HashMap, TreeMap, PriorityQueue, binary tree, binary search tree, & heap

Demo Programs

BinarySearchTreeWithStaticMethods - a client program with static methods such as insertNode, findNode, nodeCount, etc.
BinarySearchTree - as a standalone class that includes helper methods

Handouts

Set & Map chart
Big Oh Examples - same as Ch. 18 handout

Worksheets

Maps
map worksheet #1 - exercises with Map's
map worksheet #2 - implement add & reverse methods

Binary Trees
binary tree worksheet #1 - binary tree definitions & exercises
binary tree worksheet #2 - preorder, inorder, & postorder traversals (only available from instructor)
binary tree worksheet #3 - preorder, inorder, & postorder traversals (only available from instructor)

Binary Search Trees
binary search tree worksheet #1 - writing recursive BST methods including nodeCount, findMin, & treeSum
binary search tree worksheet #2 - writing recursive BST methods including countLeafs, treeDepth, & internalPathLength
binary search tree worksheet #3 - writing a BST method
binary search tree worksheet #4 - writing recursive BST methods including areSimilar & distance (between 2 related nodes)
binary search tree worksheet #5 - writing a recursive BST method that finds the right most leaf (only available from instructor)

Animations (some links may not work)

• "wiki for data structures" - http://web-cat.cs.vt.edu/AlgovizWiki/Catalog
• hashing animations from the Univ. of Michigan
• hashing animation from New Mexico
• neat hashing animation of potted trees
• hashing animation of prisoner's
• hashing animation of linear and double hashing
• hashing animation of guests at a hotel
• hashing animation & another from Oregon State
• http://www.cs.jhu.edu/~goodrich/dsa/trees/btree.html - inserting nodes into a binary tree
• http://www.ibr.cs.tu-bs.de/lehre/ss98/audii/applets/BST/BST-Example.html - binary search tree
• http://www2.hawaii.edu/~copley/665/HSApplet.html - heapsort
• http://www-cse.uta.edu/~holder/courses/cse2320/lectures/applets/sort1/heapsort.html - heapsort
• http://nova.umuc.edu/~jarc/idsv/lesson1.html - preorder, inorder, postorder & levelorder tree traversals
• http://www.cs.usask.ca/resources/tutorials/csconcepts/2001_3/tutorials/traversal.html - various tree traversals

 

Programming Assignments

Ch. 20 Project #1 - Write a program that uses HashSets to find the union of 2 sets, the intersection of 2 sets, the difference between 2 sets, and determine whether one set is a subset of another set

Ch. 20 Project #2 - determine if a value is found anywhere in a Map.

Ch. 20 Project #3 - write a MinHeap class that implements College Board's PriorityQueue interface.

Ch. 20 Project #4 - write an AccountLookup class that uses a HashSet and a HashMap

Ch. 20 Project #5 - write a translation dictionary that uses a HashMap

Ch. 20 Project #6 - create a histogram of word frequencies with a HashMap

Ch. 20 Project #7 PriorityQueueImplementationProject - implement a Priority Queue as an unordered ArrayList and as an ordered LinkedList.

Ch. 20 Project #8 PriorityQueue Implementation as a Heap Project - implement a Priority Queue as a heap which in turn is based on an ArrayList.