Topic

CS 241: Data Structures—Midterm Exam Review Notes

Important note!

click on the triangles to the left to expand or contract sections!

use the text size feature in your browser to make this text larger and more readable!

About the exam

the midterm exam will take place on Tuesday, March 20th, at the usual lecture time and place

the exam will be designed so that you should be able to complete it in one to one and a half hours

you will not have access to books, notes, computers, networks or neighbors during the exam
(you may use scratch paper and it will be supplied if needed; you are encouraged to ask your instructor for clarifications during the exam if necessary)

In preparing for the exam, you should consult:

your textbook (see especially chapters and sections mentioned below)

your notes from lecture and lab—these are likely to be especially helpful

the home page for the course and various links, examples, etc., provided there

… and also especially the lab assignments linked from the home page, as well as your programs

graded quizzes you completed during lecture (3 of them, hopefully)

Format: the exam will consist of several kinds of questions; typically:

10-15 True-or-False questions at 1-2 points each

8-10 short answer questions at 4-6 points each

2-4 longer answer questions at 8-15 points each

These review notes are not exhaustive, but are meant as a guide to coverage—see other sources for details!

Not on the exam: no material on trees (Chapter 4) or the NetBeans IDE will be on the exam

General background to Data Structures and modularity

Chapter 1, section 1.1; also Chapter 3, section 3.1

large software projects are often written and maintained by groups of people

programming language features can allow us to manage complexity by circumscribing various tasks

different classes which implement the same interface can be "plugged" and "unplugged" (replaced) at will

ideally, we unplug a slower implementation and plug in a faster one, each implementing the same interface

a common language of specification, implementation and analysis (O notation) supports communication

the use of standard techniques is valued so that people can understand and modify each other's code

standard solutions to standard problems often involve "tricks" (innovations) that would be hard to come up with on the spot

Math review and recursion

Chapter 1, sections 1.2-1.3

Functions and algorithms

a (mathematical) function is a set of input-output pairs, without regard to how they are computed

the inputs and outputs may be numbers, but also data structures, etc.

an algorithm is a technique for computing a function, step by step method, but still somewhat abstract

a program is a very specific realization of an algorithm in a particular language, with choices of variable names, etc.

these three ideas form a kind of hierarchy, with functions the most abstract and programs the most concrete

the relationships are many-to-one between algorithms and functions, and between programs and algorithms

algorithms have (abstract, O-notation style) running times; functions do not (and programs have real-world running times)

Exponents and logarithms

the logarithm is a very slowly growing function of its argument

technically, the log is the power to which you must bring the base to equal the argument number

roughly, a log in "base b" is the number of digits required to write the argument in base b

so, in base 10, the log of one thousand is 3, and of one million is 6

at the whole power of the base, there is actually one more digit, as the "odometer" turns over

logarithms obey certain mathematical laws similar to those for exponents

example: log (a·b) = log(a) + log(b)

example: log (ak) = k·log(a)

log functions sit below linear functions, and (n log n) sits between linear and squaring in the hierarchy of O-notation (see below)

O notation eliminates the need for specifying the bas of the logarithm, since it ignores constant factors

(but many logs in computing are really base 2)

Basics of recursion

an algorithm is recursive if it refers to itself (calls itself) in its own definition

recursion is often an alternative to iteration (loops)

for non-linear structures (e.g., trees), we may need an auxiliary stack to hold pending nodes while we iterate

recursion is implemented using a stack, one item for each method call

(actually, all method calls are implemented this way, partly out of anticipation of recursion)

recursion can be efficient, but watch out for:

multiple recursive calls (as in the Fibonacci example)

a missing base case or lack of progress, each of which can make the recursion go forever

Java review and new features

Chapter 1, sections 1.4-1.5

Review—see external notes!

the Java ontology page linked from the home page

Interfaces (and abstract classes)

signatures include the name of a method, the type of the result and the number and type of the arguments

(argument names don't matter for matching a signature)

(signatures with different result types, but the same name and argument types, conflict)

interfaces are collections of method names and signatures: no method bodies!

an interface allows us to specify a set of capabilities without (yet) specifying how they will be implemented

interfaces support a notion of contractual agreement about how a class can be accesses and used, how it will behave

but Java does not allow behavioral specification beyond signatures

one interface may be declared as extending another, so as to provide some (hierarchical) structure

a class can be declared as implementing an interface: class A implements I { ... }

but note that only the signature, not the behavior, is specified in Java or checked by the compiler!

abstract classes are "halfway between" a class and an interface

they may have some signatures and some full definitions

this allows a form of "default implementation" when a full method is defined

classes may extend abstract classes, forming a hierarchy

you may not instantiate (with new) an abstract class!

Exceptions

rationale for exceptions: allow for unexpected circumstances without littering your code

the try { ... } catch (...) { ... } statement wraps around code, minimizing the cognitive interference of error-checking

methods must be "branded" with the "throws Exception" decoration if they might throw an uncaught exception

some exceptions are exempt from annotation requirements—standard runtime exceptions such as array bounds and null references

exceptions themselves are declared like other classes, but they extend Exception

exceptions are created and thrown as in: throw new Exception(...)

Wrapper classes

for each primitive type (int, boolean, char) there is a wrapper class (Integer, Boolean, etc.)

the wrapper class provides a kind of a "box" which holds values of the associated type

the value can be changed, but the box object remains the same

the wrapper class also supplies a "home" for static methods related to primitive types (e.g., Integer.parseInt(…))

Generics

in order to avoid the problem of Object casting, we can specify an element type for a structure

the <T> type variable is affixed to the end of the class name in declarations of the class and of variable types

once in scope, the T type variable can be used as the type of variables, etc.

see Generics page at Oracle for a tutorial or section 1.5 in the textbook

Algorithm analysis and asymptotics (O notation)

Chapter 2, sections 2.1-2.4.5

Context and goals

we want a way to describe and compare the running times of algorithms, but:

it should be insensitive to particular hardware/machines

it should emphasize the behavior as problems (or data sets) grow large

we abstract away the detail of a function (e.g., a polynomial) representing the running time

we eliminate low order terms: just keep the highest one

we eliminate constant factors (this has a downside, though)

technically, we say that f is O(g) when there is a constant factor c and an initial point n0

f(n) is less than or equal to c·g(n) for all n > n0

idea: we can pick a constant that, when multiplied by the high-order term, will dominate all low order terms

the hierarchy of O-notation functions typically seen is:

log(n) < n < n log(n) < n2 < n3 < ... < cn

how do we measure times for O-notation?

count individual operations as steps

ignore constant amounts of steps: look for loops, traversals that depend on n somehow

‘Big O’ and related notations

Watch out for this!

when f is O(g), it may be that f is less than g

List of typical complexities

Arrays, ArrayLists and linked lists

Chapter 3, sections 3.2-3.5

Arrays

see your introductory Java text for review and examples

or see the Oracle Java arrays tutorial page

ArrayLists

ArrayLists provide

Linked Lists

basic tasks: insertion, deletion, search, indexing, containment, size, emptiness

header nodes vs. special cases

empty lists can be handled as a special case, or we can use a technique of an extra node at the front of a list (header node)

a wrapper class can also be used: not strictly a header node, since not a node

... but allows methods to be called on it (whereas they cannot be called on a null reference)

singly-linked lists: links run only in one direction (can't easily go backwards)

doubly-linked lists: links run in both directions (takes more space, more complex operations)

circularly-linked lists: single or double links, no first node

be careful of the order when re-linking list nodes on insertion and deletion!

Stacks and Queues

Chapter 3, sections 3.6-3.7

Stacks

a stack supports insertion (push) and deletion (pop), but with a specific "discipline"

push and pop behave in a LIFO way: last in, first out

(think of a stack of dinner plates on a spring at Goudy)

applications of stacks:

keeping track of pending method calls

matching parentheses (and brackets and braces) in program syntax

traversing the nodes of a tree in depth-first order (e.g., pre-order, in-order or post-order)

implementing a stack with an array

keep an index of the top item (or the next top: this is different!)

increment on add, decrement on remove

remember to check for empty (or full!)

implementing a stack with a list

keep a reference to (the node for) the top item

add a new node at the front to push a new item (set the next reference before changing the top reference)

remove a node from the front top pop an item (hold onto the item while re-setting the top reference)

Queues

a queue supports insertion (add) and deletion (remove), but with a specific "discipline"

add and remove behave in a FIFO way: first in, first out

(think of a line of people waiting at the bank or grocery store)

applications of queues:

round robin allocation of resources (fair scheduling)

holding a buffer of items that cannot be treated (and released) as quickly as they arrive

traversing the nodes of a tree in breadth-first order (i.e., by levels)

implementing a queue with an array

keep indices for the front and the back: increment the appropriate index upon add or remove

(but do the indices "point" to current or next items?)

wrap around to the front when you reach the end (use modulus operator % after addition)

note that the full part of the queue can "wrap around" from the end to the beginning of the array

keep a separate size variable to make it easier to distinguish empty from full

implementing a queue with a list

keep pointer to first and last nodes

add at the last end; remove from the first (the other way won't work as well)

the empty queue is a special case

Infix and Postfix expressions

Chapter 3, sections 3.6.3

Infix form

algebraic expressions are usually written with binary operators (like +, - and *), constants (numerals) and variables

when we write expressions, we can use parentheses to show structure

we leave excess parentheses out according to the usual "order of operations"

multiplication and division have higher precedence than addition and subtraction

when it matters, we associate to the left: a+b+c really means (a+b)+c, even though the value is unaffected by the order

… but sometimes we need to use parentheses, when the order does not match our intent

we can always put extra parentheses in for emphasis

this usual way of writing expressions is called infix form

Postfix form

an alternative style is to put the operators after their arguments: 2 3 +

in this case, called postfix form, we never need parentheses

postfix form is based on the ideas of Polish logicians and is sometimes called Polish notation

Evaluating postfix

we can use a stack to evaluate (variable-free) postfix forms:

proceed through the expression from left to right

for a constant, push it on the stack

for an operator, pop off two arguments and apply the operator, then push the result back on

be careful of the argument order: first one popped is the right argument!

when done, we should always have exactly one number on the stack (and have never failed to pop 2)

Converting infix to postfix

we can use a stack to convert infix to postfix:

proceed through the expression from left to right

for a constant, simply pass it through to the (accumulating) result

for an operator, push it on a stack

… but, before pushing, pop any operators of equal or lower precedence

Introduction to Applets and GUIs

See online examples and resources

online examples at course homepage, near the top

for resources, see e.g., the Java Applet tutorial at the Oracle website

General notes on GUIs

writing GUIs in Java involves inversion of control: you don't write the main, but a main somewhere calls parts of your code

this is most often done by extending an Applet class (either Applet or JApplet), although there are other ways

if you are working directly with graphics, you will implement a paint method that will be given a Graphics parameter

a Graphics object can be "asked" (through method calls) to draw shapes, display images, etc.

you implement a paint method, but only ever call the repaint() method: the latter clears the drawing area (among other things)

Handling events

in order to use the mouse and keyboard, you must implement an event handler interface (MouseListener, etc.)

these interfaces require you to define methods that say what you will do when various things happen (e.g., the mouse is clicked)

the handler methods are called with an event object that gives details (e.g., location)

GUI libraries

many pre-existing libraries of code are available which implement common GUI objects such as text fields, buttons, checkboxes, sliders, scroll bars, etc.

these are typically arranged in a hierarchical or tree-like fashion, such that each component contains many others, etc.