CMSC 335 Advanced Data Structures
Lecture Notes
Lecture 2 -- Inheritance and Polymorphism
Read -- Weiss, Chapters 1 - 3
Animal.java, Dog.java, Cat.java, AnimalHouse.java
Read -- Weiss, Chapter 4
Lecture 4 -- Linked Lists and Iterators
Read Weiss, Chapter 17
Lecture 5 -- An Introduction to Binary Trees
Read -- Weiss, Chapters 18, 19.1 – 19.3
Lecture 6 -- Height Balanced Trees
Read -- Weiss, Chapter 19.4-19.5
Read -- Weiss, Chapter 21.1-21.5
Lecture 9 -- Amortized Analysis Lecture -- November 4
The article may be accessed using the Marist Digital Library.
Marist home page à Library à Catalog tab à Other Libraries
ACM Digital Library à (acct., password if at home) à
Search (Skip Lists) à #11 Article by Pugh (1991)
Read Weiss Chapter 22
Read Weiss Chapter 14
Software
eclipse -- eclipse download
java 2 -- java 2 Standard Edition download (need JRE 6 or better)
Generic Tree Classes (jar file)
You may choose to use the NetBeans IDE instead of Eclipse (It has
bundled features that will be useful in your later Software Development
course)
To download NetBeans, you must first download J2SE from the sun site if not already done.
Java SE download (be sure to download jdk1.6.x or later)
Once you have downloaded the jdk, you should download NetBeans IDE.
Click on the rounded rectangle containing "Download NetBeans IDE 6.7.1 in the middle of the page.
When you link to the next page select "All" the full 669 MB pack. The download will take
about 40 minutes. NetBeans comes bundled with Tomcat, a UML graphical tool, and a JDBC driver.
On the NetBeans home page there is a link to Tutorials
(in red, just below the box to download the IDE).
There are a number of tutorials there to get you started.
Basic Java Programming acquaints you with the basic features of the IDE
(not much different from Eclipse) and has a section on creating and running Unit Tests.
Homework
Homework # 1 -- Big O Notation (due Sept. 9)
Homework # 2 -- Foundations of Java 1.6 or better (due Sept. 23)
Homework # 3 -- Introduction to Binary Trees (due Oct. 7)
Homework # 4 -- AVL/Red-Black Tree Homework (due Oct. 28)
Homework # 5 -- Heaps (due November 11)
Homework # 6 -- Amortized Analysis (due November 18)
Homework # 7 -- Splay Trees and Graphs (due Dec. 9)
Programming Assignments
Programming Assignment # 1 (due September 30)
Programming Assignment # 2 -- Binary Search Tree (due October 14)
Programming Assignment # 3 -- Height Balanced Trees (due Nov. 4)
See Software Links above for Generic Tree Classes
Announcements
If you are using a browser other than Internet Explorer (not with Vista), some
of the symbol fonts will not be properly displayed. With Firefox select View on the
top Menu Bar à Character Encoding, and on the pop-up window that appears select
Western(Windows)
The first Exam will occur on October 21 after discussing the material relating to
binary trees.
The second Exam will be held on Wed. December 2. Topic covered include height-balanced trees (AVL and Red-Black trees), the binary heap, Amortized Analysis and Hashing.
The final exam will be comprehensive and will be given on Wed., Dec 16 at 6:30 in LT001.
Review Material
Review Questions for First Exam
C++ Based text -- A work in progress