

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:




1015 TrueorFalse questions at 12 points each




810 short answer questions at 46 points each




24 longer answer questions at 815 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.21.3




Functions and algorithms




a (mathematical) function is a set of inputoutput 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 manytoone between algorithms and functions, and between programs and algorithms




algorithms have (abstract, Onotation style) running times; functions do not (and programs have realworld 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 Onotation (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 nonlinear 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.41.5




Review—see external notes!




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 errorchecking




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.




Algorithm analysis and asymptotics (O notation)




Chapter 2, sections 2.12.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 highorder term, will dominate all low order terms




the hierarchy of Onotation functions typically seen is:




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




how do we measure times for Onotation?




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.23.5




Arrays




see your introductory Java text for review and examples




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)




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




doublylinked lists: links run in both directions (takes more space, more complex operations)




circularlylinked lists: single or double links, no first node




be careful of the order when relinking list nodes on insertion and deletion!




Stacks and Queues




Chapter 3, sections 3.63.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 depthfirst order (e.g., preorder, inorder or postorder)




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 resetting 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 breadthfirst 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 (variablefree) 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




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 preexisting 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 treelike fashion, such that each component contains many others, etc.


