Lecture 1: January 8, 2007
Find the max number in a list
This class is not about Java. It's about how to design programs. We
will use Java as the programming language to develop programs.
All you need to know prior to this class you have already
learned in kindergarden (i.e. in Fundamentals of Computing 1).
- In this lecture we focus on recalling how to design
programs with accumulators in the Beginner HtDP Language - and
in the process recall the
design recipe for data definitions and for functions.
Lecture 2: January 10, 2007
Data Definition in Scheme and Java
One can only understand computing if one understands the
connection between the information provided by the user and the
way the information is represented as data that the program manipulates.
We will look at what we already know about data definitions
and learn that the same information can be represented as
data in a different language.
- However, the most important lesson is that the data no
matter how represented corresponds to the same information, and
that the structure of the data representation is identical in
two different programming languages.
Lecture 3: January 11, 2007
Data Definition for unions of data
Unions of data combine several related classes of data under
the same name.
While in HtDP this common name did not have any meaning
within the language, class-based programming languages not
only provide for a language-based definition of commonality
among several classes of data, but lster leverages this
commonality in program design.
- The most important lesson here is that a piece of data
can be an instance of some class of data, and at the same time
be known to represent data of a given type (super-type). So, for
instance of a
Book is also an object of the type
Lecture 4: January 17, 2007
Data Definition for self-referential
unions of data
Unions of data combined with a self-referential containment
represent quite complex structures of data, such as ancestor
trees and river systems.
We look at how the data definitions we have seen in HtDP
translate in a systematic way to class-based data definitions.
- The most important lesson here is that following the
DESIGN RECIPE for data definitions we learned in HtDP
helps us in identifying the classes of data we need to define
and the relationships between the classes and interfaces.
Lecture 5: January 18, 2007
Designing methods for simple classes
and classes with containment
Designing methods for a class-based language is very similar to
designing function in functional languages.
The main difference is that in a class-based language a method
is invoked by an object of the class in which the
method is defined. This object than becomes
an implicit argument to the method.
- The most important thing to remember is that the program
designer need to think very carefully which class should be
responsible for defining a method that may involve instances of
more than one class.
Lecture 6: January 22, 2007
Designing methods for
Designing methods for a unions in a class-based language
leverages the fact that the
represents the union has a meaning in the language.
In a class-based language when an instance of a class invokes
a method, the
method definition lookup is dispatched first to the
class to which the instance belongs.
- The most important thing to remember is that the method
dispatch eliminates the need for the conditional we used in HtDP
to distinguish between the variants of a union. However, we are
now responsible for defining the method with the same
signature in all classes that implement the common
Lecture 7: January 24, 2007
Designing methods for self-referential
Designing methods for self-referential unions typically leads
to a self-referential method invocation by a field in the class
that is itself an instance of the class.
Including the method declaration (method signature) in the
common interface defines a contract between the interface and
all of the implementing classes; requiring that each of them
implements the specified method.
The most important thing to remember is that as in HtDP,
learning to read the purpose statement in the
context of this self-referential field, typically provides a
deeper understanding of the program behavior and helps greatly
in the method design.
Lecture 8: January 25, 2007
More methods for self-referential
The rule of one task, one function
we learned in HtDP is just as relevant in the context of
class-based program design.
In complex class hierarchies, following the arrows in the
class diagram often serves as a guide where the method that
solves the next task should be defined.
- The most important thing to remember is the
rule delegate each task to the class that should be
responsible for providing the answer.
Lecture 9: January 29, 2007
Typical data for a large project contains a number of mutually
referential dependencies. The need for delegating tasks to the
classes that are responsible for providing the answer becomes
even more obvious.
Before we start designing methods, we have to make sure that
we thoroughly understand the nature of the problem, the
relevant information, and how the information is represented
- The most important thing to remember is to make sure it is
clear what information each piece of data represents
(interpreting data as
information) and how is
the given information encoded as data (representing information
Lecture 10: January 31, 2007
We continue designing methods for more
complex class hierarches.
Following the DESIGN RECIPE faithfully, designing
helper method when needed, guides us seamlesly through this
- The most important thing to remember is to let the dynamic
dispatch of the method invocations be the mechanism for
Lecture 11: February 1, 2007
Designing methods with accumulators
The methods that process lists of data that we have designed
(that follow the structure of the data) defer the computation
until the series of recursive calls reduces the problem to the
trivial case. The result is then accumulated as the nested
recursive method invocations return the computed value.
It is possible to rewrite these methods is such a way that the
known values and partial results are accumulated during the
initial method invocation and the recursive method uses the
accumulated value to produce the final result - eliminating
the need for retracing the recursion steps.
- The most important thing to remember is that the mechanism
for performing the transformation of structural recursion to
recursion with accumulators follows a pattern that can be
described precisely, regardless of the specific details of the
Lecture 12: February 5, 2007
Comparing Union Objects for Equality;
Abstracting over common fields and methods
In the previous course we used the DESIGN RECIPE FOR
ABSTRACTIONS to eliminate repetition in the code. This is
not just an aesthetic issue - it also help in following the
single point of control principle.
We start by identifying the situations where the current data
definitions (with interfaces representing unions of data) do
not give us enough power to design the programs we need to
design. We then introduce several solutions to our problem.
- The most important thing to remember is that while an
abstract class provides a common base for several classes that
extend it (its subclasses or derived classes) we
cannot construct an instance of an abstract class.
Lecture 13: February 7, 2007
Lifting methods to the abstract class
or a super class
We can now eliminate repetition from the method definitions as
well --- continuing with the theme of the
single point of control principle.
We look for methods that have a common implementation in
several classes. At times, we can lift the entire
implementation into the abstract class --- defining concrete
methods in an abstract class. In other cases the
implementations in different classes may be completely
distinct, and there is no abstraction possible. The third
situation occurs when several classes share the implementation
of a method, but one class may differ. In that case we may
implement a concrete method in the abstract class and let the
one class that needs a different implementation
override this method.
- The most important thing to remember is that abstract
class is a perfectly good place for defining methods. However,
every class that extends this super class must provide tests for
each such concrete method.
Lecture 14: February 8, 2007
Deriving subclasses; overriding
We now look down. At times, the class we are working with
seems to represent several different situations. In that case,
it may be helpful to derive a subclass that represents one
the behavior, while the original class retains the other.
An additional reason for deriving subclasses is when we want
to add new behavior to an existing library class. We cannot
modify the library class, but our class that extends it can
contain new methods relevant for our application.
- The most important thing to remember is that each class
should be designed to represent a common collection of objects,
and if the behavior can be clearly divided into two cases, we
should consider deriving subclasses.
Lecture 15: February 12, 2007
Designing constructors; overloading
constructors and methods.
So far every time we invoked the constructor to create a new
instance of a class we provided the full collection of values
needed to initialize the fields. However, the class designer may
choose to provide several constructors for one class. A
class can define more than one constructor as long as no two
constructors have the same sequence of argument types. This is
Methods can also be overloaded, but they all must have the
same return type.
We see several reasons for overloading constructors. The first
is a convenience for the user when one of more of the fields
is typically initialized to a known value, and the user
provides it only if the value differs from the
default value. The second reason is to provide an
alternative way of supplying the initial values (for example
temperature in degrees Celsius instead of degrees Fahrenheit).
- The most important thing to remember is that a method or a
constructor that oveloads existing methods or constructors must
have a different sequence of argument types than any existing
method or constructor with the same name.
Lectures 16-17: February 14-15, 2007
Circularly referential data; Methods
for circularly referential data.
We get a preview of how constructors can be used to assure
integrity of data - but defer more discussion of this topic to
We explore the possibility of data definitions forming a
circularity that cannot be avoided. We run into problems
trying to define examples of data. This is the first time we
see a need for changing the values that an object represents
after the object has been constructed. This is called
- The most important thing to remember is that when we
introduce mutation, the values that an object represents change
as the program runs. This requires that tests verify the state
of the program both before and after the changes
have been made.
Lecture 18: February 21, 2007
Assuring integrity of data;
We learn how constructors can be used to assure
integrity of data. We also learn about the need for
through the use of
private visibility modifier.
We learn three new concepts in this context. First we see how
Java reports runtime errors by raising an
exception. We learn about class methods in
contrast to the instance methods we have seen so
static modifier indicated that a method
belongs to the class and is invoked by specifying the name of
the class where it is defined. Finally, we learn about
private visibility modifier that prevents the
client from seeing and using some of the class code directly.
- The most important thing to remember is that the class
code can provide many services to the client while protecting the
integrity of the data represented by an instance.
Lecture 19: February 22, 2007
Touching the Void
The need for mutation.
We explore further the need for mutation
i.e. making changes in the data values represented by an
instance of a class after it has been constructed.
We first look at the need for modifying fields in a simple
class. We then attempt to modify the structure of a complex
piece of data ... leaving the solution till the next time.
- The most important thing to remember is that mutation
introduces time dependency into a program and requires
that the tests check the state of the program before and
after the occurrence of the mutation.
Lecture 20: February 26, 2007
Mutating the contents of a list.
We explore further the need for mutation.
We now want to change the contents of a list - either remove
items from a list or add new elements to the list. The problem is
that some other objects (for example fields in
a database) may refer to our list. If our method were to
produce a new list, all fields that refer to this list would
have to be notified. And, of course, we really do not know
what all these fields are.
We therefore need to find a way to
change the contents of the object that represents a list of
items. To be able to do so we introduce a wrapper
class that refers to the current list. That way the wrapper
class is the only reference to the list and all other fields
that need to know about the list refer to the instance of the
- The most important thing to remember is that when we need
to change the contents of a structure such as a list or a tree,
we have to think carefully not to produce a new object, so that
other places in the program that refer to it will not be
Lecture 21: February 28, 2007
Abstracting over the datatype
Abstracting over the datatype.
We now look how we can avoid defining new and new classes to
represent a list of objects. The Design Recipe for
Abstractions should help us in replacing the repetitive code
with parameters that represent the common behavior.
We define an interface
ISame to represent the
fact that the class implements
same method to compare two instances of this
class. That makes it possible to not only define a list of
objects of the type
ISame, but also to design
comparison of two lists that can then be used to design tests.
- The most important thing to remember is that each time we
get more power, we also end up having more responsibilities. When
we define a list of
ISame objects, we can mix
Songs, something we did not
have to worry about earlier. We will see soon that this can be
avoided using Java generics.
Lecture 22: March 1, 2007
Abstracting over the behavior
Abstracting over the behavior.
Lecture 23: March 12, 2007
Abstracting over Traversals - Part 1
Abstracting over traversals - Part 1.
We first review the use of function objects from the previous
lecture. We see, that as we design new and new algorithms that
consume list data, we keep changing the classes that represent
lists. If we wanted to build a library of data, we would no
longer want to change these classes. Instead, we want to observe
the contents of the list in some orderly fashion, and process the
data using methods defined outside of the list classes.
We introduce a new interface that allows us to traverse over
the elements of a list. We then show how this allows us to
design algorithms outside the classes that represent
lists. Later, we will see that other classes the represent a
dataset of items can be traversed (and processed) the same
way, as long as they implement the same Traversal
- The most important thing to remember is that when we
design libraries, we should encapsulate the internal structure of
the dataset and provide the outside users with appropriate interfaces
that allow them to observe (and possibly, later, mutate) the
contents of our dataset.
Lecture 24: March 14, 2007
Abstracting over datatype: Generics
Abstracting over datatype: Generics.
We get back to looking at lists of data and the algorithms we
designed. We see that we now can build a mixed list of songs and
books and persons, and have to work very hard to make sure we do
not make a mistake. The Design Recipe for Abstraction
tells us to use a parameter to ditinguish between the different
variants of the same code. Here we want to use a paramter to
specify the type of data that can be used to construct a list, or
the type of data a selector function object consumes.
Java generics (type parameters) allows us to do this. When we
specify that a list contains only objects of the type
Book, Java will throw an exception if someone tries
to include a book in the list. When designing the function
object that consumes an element of some type given by the type
parameter, the concrete implementing class specifies the
desired type in the declaration and know that the argument
will have the properties of an object of that type - its
fields and methods.
- The most important thing to remember is that using
generice we produce better and safer programs, as well as more
Lecture 25: March 15, 2007
Abstracting over traversals: Part 2
Abstracting over traversals: Part 2.
We are now ready to look at how some of the Java libraries are
built. We understand how to design classes, how to design
abstract classes, use functon objects, implement the behavior
specified by an interface, hide the implementation with
visibility modifiers, etc. We also understand well the different
ways how two pieces of data can be considred the same,
which is extremely important for understanding the effects of
We explore further the use of the Traversal interface
and see that it can work not only for lists, but also for binary
search trees and for ArrayList data type defined in the
Java Collections Framework library. Some of the deails
are left for the next time...
- The most important thing to remember is that corerctly
designed interfaces allow us to implement the behavior in several
ways, depending on what seems to be the most appropriate for the
Lecture 26: March 19, 2007
ArrayList: Direct access data structure
ArrayList: Direct access data
Code for this lecture.
Lecture 27: March 21, 2007
From Accumulators to Java Loops
From Accumulators to Java Loops.
We have seen loops where accumulators were used to keep track
knowledge we have gained as we traversed over the early parts
of the list of data. Java language contains
several statements that represent similar loops. Each of them
specifies how to travers over the
data in a dataset, and allows the programmer to define action to
take as each new item in the dataset is seen.
We see that the Java loops consist of the same components as
the loops with accumulators we have used for our
Cons lists. By following the template, we can
design loops as we did before, and modify our original
solution to use Java loops.
- The most important thing to remember is that Java is not
well suited for working with recursively defined data. Therefore,
the use of
ArrayList with Java
loops produces a more efficient solution.
Make sure you
always design a method that wraps the loop, so you
can reason about it, design it, and test it.
Code for this lecture.
Lecture 28: March 22, 2007
Java Loops; Mutation: Selection Sort
Java Loops; Mutation: Selection Sort.
Code for this lecture.
Lecture 29: March 28, 2007
Exploring Java Collections Framework; Iterator
Exploring Java Collections Framework; Iterator.
Java Collections Framework is a library of classes that
represent different ways of organizing data, traversing over the
data, as well as a standard set of the most common algorithms
needed for processing data.
We explore the structure of this class hierarchy, the design
choices, and especially the design of the
Iterator interface. This also leads us to the new
for loop, commonly referred to as
The most important thing to remember is that a programmer
should become familiar with the libraries that are available
and use them whenever appropriate. This makes code easier for
others to understand and maintain.
Lecture 30: March 29, 2007
Exploring Data Structures: Stacks and Queues
Exploring Data Structures: Stacks and Queues.
We recall that both the recursively built lists and the
ArrayLists handled addition of new items and the
removal of an item from the dataset. The Cons lists
always placed the new item at the
front, and it was the only item we could remove. The
ArrayList added the items at the end (if we did not
ask for a specific place), but could remove from
anywhere. However, the cheapest removal was from the end
--- removing the item that was added last.
This data organization Last In First Out or
LIFO is called a stack.
We somtimes need to organize data differently. If the data
represents requests that have to be processed in the order in
which they were received, we need to represent the data as a
queue. We compare the definitions and
implementations of stacks versus queues.
- The most important thing to remember is that there is a
distinction between the interface that represents how the data
can be accessed and manipulated and the implementation that is
typically hidden from the user. However, the implementation
should explain which operations are costly and give the
estimate of their expected running times.
Code for this lecture.
Lecture 31: March 30, 2007
Data Organization and Algorithm Complexity
Data Organization and Algorithm Complexity.
Over the past several weeks we have seen that the way we
organize the representation of information as data affects the
design of the methods that access and manipulate this data. One
of the concerns a program designer must address is the efficiency
of the algorithms used to solve the problem.
We compare the different data structures we have seen and
explore the cost of simple operations, such as finding an item
to the dataset represented by the data structure. We define
the algorithm (time) complexity as an approximate
function of the size of the dataset.
- The most important thing to remember is that we need to
consider not only the average time it takes to perform
the task, but also the worst case scenario.
Lecture 32: April 2, 2007
Key-Based Data Organization: Hash Map
Key-Based Data Organization: Hash Map.
We have seen that finding an item at the given index in a
direct-access data structure is very simple and fast. That means
ArrayList can represent a look-up table of
data, as long as we look up the values based on a numeric index,
and as long as all locations in the table are filled.
We explore how we can leverage the direct table lookup by
mapping the value of the unique key for each item into
numerical value that can then be used as an index to a
hash table of data items. We then learn how we can
design our own
- The most important thing to remember is that the
hashCode method and the
method go hand-in-hand and if we override one of them we
must override the other one in a way that
maintains their relationship.
Lecture 32: April 4, 2007
BigOh and Sorting Algorithms
BigOh and Sorting Algorithms.
We explore further the time complexity of different
algorithms. We use sorting algorithms to illustrate the
difference between the running times that are logarithmic,
linear, n log n and quadratic.
We see that at times one algorithm may be a better choice,
because the data organization corresponds to the best time,
not the average time; at other times, we may rejact a faster
algorithm if the data organization causes us to expect the
worst running time, not the average time.
- The most important thing to remember is that the selection
of a suitable algorithm and data organization involves
tradeoff and judgement. The designer needs to
consider the whole problem when selecting the data
organization and the algorithm.