Information on Exam 3, CS 2110 - Spring 2011
Weds. May 4. Added info on Stack
When and Where:
- 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
- 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
- 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
- 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.
Event Driven Programming (~20% of the new material on the test)
- Slides: cs2110-swing-s11.ppt
- How is event driven programming different that what we've done
- 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
- 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
- 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
- What is a recursive data structure, and how defined in Java
- 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
- 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
- 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.
(~15% of the new material on the test)
- 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
- Important ideas and terms:
- task, process, thread, context switch, parallel programming,
- thread blocks (or waits); deadlock; cooperative threads, or
- 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
- Creating a Runnable, creating a Thread with a Runnable, starting
- 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
- 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;