CS 2110 - Fall 2009

Information on Test 2

The test will be held on Wednesday, Oct. 28, in class at the regular class-meeting time. You may come to either test session.
Be sure to come on time! You can start bubbling early!

• 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!

Topics:

Java Collections Framework:

• Readings: Chap. 9 and Slides

1. Introduction, concepts for this framework
   • What in general is a framework?
   • It contains interfaces, concrete classes, and some abstract classes
   • How it uses inheritance (both subclasses and interfaces)
2. How to use Java generics features to define a Collection that can only hold one kind of item.
3. Iterators and ListIterator vs. foreach loop
   • How to get one, how to use them to traverse a Collection
   • What functions can iterators do that foreach loops cannot?
4. 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
5. Ordering elements in Collections
   • 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
   
   
6. Sets and Maps - their ADT's and basic Java implementations
7. The three functions from Object: toString, equals, hashCode

Algorithm Complexity:

• Readings: Chapter 5

1. Definition of data structure, abstract data type (ADT)
   • Examples of ADTs
   • How these are related to data abstraction and procedural abstraction
   • Remember: an ADT is implemented by choosing a particular data structure
     • Choice of data structure may affect efficiency
2. Measuring an algorithm's efficiency
   • Based on input size
   • Count operations or some critical section to get a formula f(n)
   • Why we don't just time things
   • Worst-case, average-case
3. 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) )? BigOmega?
   • Listing or ranking common order-classes by their relative efficiency
4. 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 use this?
   • Sorting:  good sorts are O(n lg n),

Recursion and Recursive Algorithms:

• Chapter 5.5 and the slides.

• Definitions, concepts, use in mathematics
• Implementing basic recursive methods in programming languages
  • Base cases; recursive calls that make progress towards the base case
  • Activation records and the run-time stack
  • Simple examples: factorial, list processing, fibonacci
• When recursion is not a good idea?
  • Repeated subproblems e.g. fibonacci
  • Bottom-up approach that remembers small solutions better
• Know the algorithms/steps/complexities for:
• binary search
• fibonacci
• factorial
• mergesort 

• How is event driven programming different that what we've done before here?
• Examples of event driven programming
• How does Swing represent event driven programming?

• Binary trees - how they work, how to traverse them
• Binary tree node data structure
• Tree traversal types

• Know the basics of Scrum (sprint, backlog, etc) from Inova
• Know how these affect the development cycle and how they can meet the needs of their customers

• Know the basics of the testing styles
• You won't have to write test cases or JUnit code