Information on Exam 2, CS 2110 - Spring 2011
Updated! Fri., March 25, 12pm
The test will be held on Wednesday, March 30, in class at the
regular class-meeting time.
Be sure to come on time!
- If you know in advance that you have a problem with that date,
contact the instructor by the end of the class before the exam.
- If you need extra time because your are an LNEC-approved student,
email the instructor to remind him of this by
that same date.
- If an emergency causes you to unexpectedly miss the exam, contact
the instructor by phone or email as soon as possible!
the MSD textbook:
- Chapter 1 on testing: pp. 23-26, but not that book's definition
of black-box testing is not one I agree with. See the slides.
- Chapter 2 on finding classes (section 2.3.1) and UML class
diagrams (section 188.8.131.52)
- Chapter 8: Section 8.1 and 8.2 are listed on the Schedule page.
- But, these introduce sets and maps (you DO need to know this)
but then show how to implement them (you do NOT need to know this).
- Pages 529-531 describe hash functions in more detail than given
in class. Reading this may help you if you didn't follow what was
taught in class.
- Chapter 9
- Page 611 through Section 9.3.4 (which ends on p. 640)
- but skip text on ListIterator (pp. 631-635)
- Pages 650-660
- Pages 665-671.
- Chapter 5
- Except Section 5.5 on recursion (next exam)
All slides from this part of the
slides on the class notes
page on the website
- From the set labeled "Collections" through the set labeled
"Events, Anonymous Classes in Swing".
There might be coding questions on
- Using the Collection interface and its common operations
(including constructors and "bulk" or "all" type of operations.
- Using Set and Map objects
- Using Iterator objects: how to get one; methods in
Iterator. No coding on ListIterator.
- Using the for-each statement instead of an iterator
- No coding to write Comparable or Comparator objects
- Know the principles of writing hashCode() but no long coding
questions on this
SW Engineering and Design:
- Design (see the textbook
for some of this)
- CRC cards
- subclasses, abstract classes, interfaces,
- finding classes from written requirements (see "Lab
Solutions" link on Schedule page for 2/28 lecture).
ideas, Dijkstra's quote (and its point)
- All definitions from
- Some basic JUnit ideas. (You won't have to write JUnit
- The "forms of
inheritance" listed on pp. 53-55 and in slides.
- Specifically specialization vs. specification
- From slides: inheritance of interface vs. inheritance of
Java Collections Framework:
- Readings: Chap. 9 and Slides
- Introduction, concepts for this framework
- What in general is a framework?
- It contains interfaces, concrete classes, and some abstract
- How it uses inheritance (both subclasses and interfaces)
- How to use Java generics features to define a Collection that can
only hold one kind of item.
- Iterators vs. foreach loop
- How to get one, how to use them to traverse a Collection
- What functions can iterators do that foreach loops cannot?
- ListIterator will not be on the exam!
- Procedural and Data abstraction
- Definition, general ideas
- Iterators as examples of procedural abstraction
- Comparator classes as an example of procedural; List class
example of data
- Ordering elements in
Collections We did
this on Exam 1.
- Comparable interface and the compareTo() function
- How these are used in Collections and Arrays static methods like
sort(), max(), etc.
- Know what a static method is in Java
- Sets and Maps - their ADT's and basic Java implementations
- hashCode(). An additional member of the set of three
functions we override from Object (the other two are toString, equals)
- Abstraction as an important principle in CS and computational
- Definition, difference between data and procedural
- Examples of abstraction in programming in general and in OO
- Why is this important?
- See also procedural abstraction in next set of topics
- Readings: Chapter 5 (except Section 5.5)
- Definition of data structure, abstract data type (ADT)
- Examples of ADTs
- How these are related to data abstraction and procedural
- Remember: an ADT is implemented by choosing a
particular data structure
- Choice of data structure may affect efficiency
- Measuring an algorithm's efficiency
- Based on input size
- Count operations or some critical section to get a
- Why we don't just time things
- Worst-case, average-case
- Asymptotic complexity
- How cost f(n) grows as input size n gets larger
- Group cost-functions into order-classes of
similarly-growing functions, e.g. O(n), O(n lg n), etc.
- If an algorithm has cost f(n), what's it mean to says
this is O( f(n) )? How is this different than BigTheta( f(n)
- Listing or ranking common order-classes by their
- Searching and sorting
- Sequential search: how does it work? what's
it's worst-case? Average case? Why?
- Binary search: general ideas of how it works!
what's it's complexity? how does this compare to
sequential search? What must be true of the list before we
- Sorting: good sorts are O(n lg n),