Readings for CS 3500
Required readings
This list will be updated weekly to provide references for the topics covered each week. A preliminary outline of weekly reading assignments from the Liskov text is shown below.
For the first regular assignment you should read the guide that shows you one way to translate an algebraic specification into Java.
Red-Black Trees ina Functiona Setting
Sestoft: Essential concepts in Java
The Sestoft’s book gives you a very concies but accurate explanation of Java programming language. It covers many topics you may not have seen, and elucidates those you have already used. Get into a habit of re-reading sections as we cover the related topics, and use it as an initial refresher of what you know about Java as we start the semester.
Sestoft chapter 1: compilation, loading, and execution
Sestoft chapter 3: Java naming conventions
Sestoft chapter 4: comments and program layout
Sestoft chapter 6: variables, parameters, fields, and scope
Sestoft chapter 9: classes
Sestoft chapter 10: classes and objects in the computer
Sestoft chapter 11: expressions (may omit sections 11.1 through 11.4 and 11.6)
Sestoft chapter 5: types
Sestoft chapter 21: generic types and methods
Reading in the Liskov text
Liskov’s book gives you motivation and explanation of why and how one designs the abstractions we will be covering in this course. The book takes a more informal approach, but comes with a very nice explanation and examples. Reading it will help you understand the course material and see iit from a different perspective.
We will update weekly which chapters are relevant to each week’s topics.
For the first week, review what you have learned about Java, and make notes if you see something that is new to you. Ask questions about this in the next class.
To see a discussion of why specification is important and see another way of defining specification read Chapter 5 of Liskov, especially section 5.5.
Week 1: 9/4, 9
Read these chapters to review Java programming language
Review of Java; Introduction (Ch. 1 Liskov)
Understanding Objects in Java (Ch. 2 Liskov)
Lecture 1: Review of Java
Lecture 2: Review of Java; Abstraction Barrier
Week 2: 9/11, 16
These chapters give you another view of Procedual Abstraction
Procedural Abstraction (Ch. 3 Liskov)
Exceptions (Ch. 4 Liskov)
Lecture 3: Review of Liskov - Chapters 1-3
Lecture 4: Understanding algebraic specification: Design Recipe
Lecture4.zip
Week 3: 9/18, 23
Data Abstractions (Specification and Implementation) (Ch. 5 Liskov)
Data Abstractions (Abstraction Function, Representation Invariant, Side Effects) (Ch. 5 Liskov)
Lecture 5: Designing tests and test harness; Exceptions
Lecture 6: Data Abstractions - Specification and Implementation
Lecture 6: Slides
Week 4: 9/25, 30
Data Abstractions (Reasoning, Design Issues, Locality and Modifiability) (Ch. 5 Liskov)
Testing: unit tests, black box testing
Lecture 7: Data Abstractions - Abstraction Function, Representation Invariant
Week 5: 10/2, 7
Iteration Abstraction (Ch. 6 Liskov)
Functional Iterators; Java for-each loop; Java 8 proposal
Lecture 8: Iterator Abstraction
ListTraversal.java Functional iterator
for recursively built list and for the ArrayList
Ariter.java Iterator for ArrayList
Week 6: 10/9, 16
Complexity. Algorithms: Red-Black Trees
Functional Red-Black Trees
Midterm Exam
Week 7: 10/21, 23
Visitors
Type Hierarchy: overview, abstract classes, interfaces (Ch. 7 Liskov)
Type Hierarchy: multiple implementations, subtyes, equality, substitution principle (Ch. 7 Liskov)
Week 8: 10/28, 30
Polymorphic Abstractions (Ch. 8 Liskov)
Parametric Polymorphism - Java generics
Parametric procedures: covariance, contravariance
Week 9: 11/4, 6
Specifications (Ch. 9 Liskov)
Testing and Debugging (Black-Box, Glass-Box) (Ch. 10 Liskov)
Week 10: 11/13, 18
Testing and Debugging - Tools for Testing; Debugging (Ch. 10 Liskov)
Design Patterns (Ch. 15 Liskov)
Week 11: 11/20, 25
Design Patterns - additional
Algorithms 1
Week 12: 12/2, 4
User Algorithms 2
Summary