Information on Exam 3, CS 2110 - Spring 2011

• The 10am section's exam is Saturday, May 7, 9am-noon, in our regular class room, OLS 005.
• The 1pm section's exam is Friday, May 6, 9am-noon, in our regular class room, MEC 205.
• On your Honor, you will pledge that you have not discussed the exam in any way with a student who is taking the exam at a different time than when you take it.
  
• If you need extra time because you are an LNEC-approved student, email the instructor to remind him of this by Tuesday, May 3, noon.
• If an emergency causes you to unexpectedly miss the exam, contact the instructor by phone or email as soon as possible!

Exam conflict or scheduling issue?   See the Announcement on the Collab site that was posted (and emailed) on April 28, 12:59pm.   Complete the form ASAP.  I'll contact each person by the end of reading day to confirm a permitted scheduled change.

Exam format:   It will be designed to be one-third longer than previous exams (which were 50 minutes). Having a three-hour limit on the exam should give you plenty of time.  So it will almost certainly be OK if you arrive at the exam room a little late.

This is worth 20% of your final grade. (Previous exams were worth 15%).  It will include:

• About three-quarters of it will be on recursion and the material covered since the last exam. (See topics below.)
  
• The other quarter will be:
• Some high-level review questions from previous exams on key topics.
• At least one Java design and coding problem on topics covered on earlier exams.  Such a question would require the fundamentals of things you've learned about programming techniques and skills practiced in labs and homeworks throughout the term.  (Nothing horribly complex! For example, no Swing.)
• We suggest you look at the previous tests and also the review sheets for the earlier tests.

More details on topics are below. Readings and slides are listed with each set of topics below.

On the new material, there might be longer coding questions on the following:

• Writing a recursive method for a relatively simple mathematical calculation (study factorial, Fibonacci numbers, etc.)
• Modifying or completing or adapting recursive binary search or recursive mergesort (but not the merge() part of mergesort).
• A node-level or tree-level operation for a binary tree.  (Study the classes for the tree and the node.)
• A node-level or tree-level operation for a binary search tree.
• No long coding questions on multi-threaded programs etc.
• No long coding examples of writing Swing. Maybe some short one or two line snippets to answer a question
• But know the fundamentals of Swing components, containers
• Know the principles of event-driven programming in Swing. Including what an Event is, what a Listener is, how they all this is connected with a component, etc.
• Also, there will be a 2nd longer coding question similar to those you had or might have had on the previous exams.
  

Topics:

• Slides:  cs2110-swing-s11.ppt
  
• 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?

Introduction to Recursion and Recursive Algorithms (~25% of the new material on the test)

• Slides: cs2110-14-recursion.ppt
  
• Readings: pages 267-269;
• 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
• Recursive binary search
  
• Divide and conquer algorithm design strategy
• Mergesort: how it's defined recursively
  

Recursion and Trees and Grammars  (~40% of the new material on the test)

• Slides: cs2110-15-trees.ppt
• Readings: MSD text, Chapter 7.1 through 7.4 but note the following:
• We won't cover the data structures for general trees on pp. 394-395
• We also won't cover Sections 7.3.3 or 7.3.5
• In 7.3.4, make sure you understand the relationship between the two classes, LinkedBinaryTree and BinaryTreeNode.  Study the find() methods and the traversal methods (including the callback object).
  
  
• What is a recursive data structure, and how defined in Java classes
• Trees:  definitions and common terms 
  • Note recursive definition using sub-trees
  • Binary trees vs. general trees
  • Generating of statements from a grammar, as done in HW4
    
• ADT Tree and data structures that implement it
  • What operations might we define for binary trees
  • Java classes for tree-nodes and for tree
  • Binary Tree implementation using references.  You don't need to memorize all of the operations presented in the book, but study it all and in particular the following things:
    • In the BinaryTreeNode class, the recursive traveral methods, the recursive find method
    • In the BinaryTreeNode class, the recursive height method and the recursive size method
    • In the BinaryTree class, see how calls of the same name as the above methods are coded.  (It's simple -- just call the method with the same name on the root.  May need to check if there is a root node.)
    • In the BinaryTree class, I won't ask about equals or toString or treeToString.
• Binary Search Trees (BSTs)
  • How different than "plain" or "just" binary trees.  (Answer:  nodes are stored in a particular order based on their key value.)
    • How this is done in Java using the Comparable interface for nodes.
  • The important methods for BSTs: insert(), contains()  (sometimes called find).
  • How insert knows where to place an object
  • You DO NOT need to know anything about:
    • How to remove nodes from a BST
    • The math formulas on p. 452, but see the next item...
  • Study the code for class BinarySearchTree for insert() and contains()
    • Note how they use a loop instead of recursion.  Compare contains() here to recursive find() in class BinaryTree
  • Advantages of BSTs
    • If the tree is balanced (or reasonably balanced), the cost of find() can be O(lg n).
    • The cost of maintaining the tree when adding new items is low.  Insert can be O(lg n).
    • Design choice: Keep items in a list, sort and use binary search?   Or, keep items in BST and use find?
      • When is one better than the other?   Think of cost of sort and how often you need to do it or repeat it.

• See slide 16 in slides cs2110-16-parallelprog.ppt
• Read pages 347-351 in MSD text
• Examples we talked about:  run-time stack (in book pp 350-351);  undo stack for Calc example
  

• Slides: cs2110-16-parallelprog.ppt
  
• Readings: Chapter 11 for info on the terms and ideas below and those mentioned in the slides. The coding examples in the book do not match what we did in the slides and examples.  So many of the book's coding examples are not that useful.
  
  
• Important ideas and terms: 
  
• task, process, thread, context switch, parallel programming, concurrency, non-deterministic
• thread blocks (or waits); deadlock; cooperative threads, or cooperative multitasking
  
• synchronization; concurrent data access; race condition; critical section; thread-safe object (or class); synchronized method
  
• lock; mutex; semaphore;
  
• Task idea and Java's Runnable interface
• Task-objects: why? storing state, using constructors to pass in data
  
• Creating a Runnable, creating a Thread with a Runnable, starting the Thread
• Task-objects used for an Undo operation in an application like the Calculator example.
• The ForkJoin framework: the ForkJoinPool object, the RecursiveTask task-object; how to structure the "recursion"
• SwingWorker class
  
• The idea of an Executor, what its responsibilities would be; submitted a task to an Executor
• Why synchronization and locking matters when threads can share a data object?
• Solution: two uses of synchronized keyword in Java. The book's code and examples are just like what we did class.
  
• Important: no long coding problems using threads or tasks!
• Important: the book uses many methods that we did not cover and will not have on the exam.  We replaced these with the Java techniques and classes in the slides.  These include:
• Extending Thread class; wait/notify; Thread.join and yield; Thread.isAlive;