{\rtf1\ansi\deff0\adeflang1025
{\fonttbl{\f0\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f1\froman\fprq2\fcharset0 Times New Roman{\*\falt Thorndale};}{\f2\froman\fprq2\fcharset0 Times New Roman;}{\f3\fnil\fprq2\fcharset0 HG Mincho Light J;}{\f4\fnil\fprq2\fcharset0 Arial Unicode MS;}}
{\colortbl;\red0\green0\blue0;\red128\green128\blue128;}
{\stylesheet{\s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\snext1 Default;}
{\s2\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\sbasedon1\snext2 Header;}
}
{\info{\author Sharon Tuttle}{\creatim\yr2003\mo2\dy18\hr10\min55}{\operator Sharon Tuttle}{\revtim\yr2003\mo4\dy10\hr11\min37}{\printim\yr1601\mo1\dy1\hr0\min0}{\comment StarWriter}{\vern6410}}\deftab1250
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1800\margrsxn1800\margtsxn1440\margbsxn1440\headery0{\*\headeryb283\headerxl0\headerxr0\headeryh0}{\header \pard\plain \s2\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\ltrch\loch\f2\fs20 {\ltrch\loch\f2 CS 132 - Midterm #2 Study Suggestions\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 5}}}
\par }
\pgdscnxt0 Default;}}
\paperh15840\paperw12240\margl1800\margr1800\margt1440\margb1440\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1800\margrsxn1800\margtsxn1952\margbsxn1440\headery1440{\header \pard\plain \s2\cf1{\*\tlswg8236}\tqc\tx4320{\*\tlswg8236}\tqr\tx8640{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\ltrch\loch\f2\fs20 {\ltrch\loch\f2 CS 132 - Midterm #2 Study Suggestions\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 5}}}
\par }
\ftnbj\ftnstart1\ftnrstcont\ftnnar\aenddoc\aftnrstcont\aftnstart1\aftnnrlc
\pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\qc\ltrch\loch\f2\b {\ltrch\loch\f2 CS 132 Midterm #2 - Study Suggestions}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b REMEMBER THE DATE CHANGE! Midterm #2 will be IN LAB on THURSDAY, APRIL 17th (location to BE ANNOUNCED)}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2\b 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab {\b last modified: 4-10-03}}
\par 
\par {\ltrch\loch\f2 *\tab everything discussed/involved in assigned reading, lectures, labs, and homework assignments and examples is fair game. The test covers through HW #8, and material through the 4-1 lecture (that is, binary trees are fair game, but priority queues onward ar
e not).}
\par 
\par {\ltrch\loch\f2 *\tab But, these are some especially-significant topics to help you in your studying for the midterm.}
\par 
\par {\ltrch\loch\f2 *\tab You are responsible for being familiar with, and following, the class {\b style} guidelines.}
\par 
\par {\ltrch\loch\f2 *\tab EXPECT to have to read and write Java code, pseudocode, UML notation; you might also be expected to complete or debug or etc. fragments of code.}
\par 
\par {\ltrch\loch\f2 *\tab {\b lists }were not on Midterm #1 --- they definitely will be on Midterm #2!}
\par 
\par {\ltrch\loch\f2 *\tab Java basics and details}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is a Java interface? how does another Java class make use of an interface? what is the purpose of an interface (why are they useful)? If a Java class implements an interface, what  effect (if any) does that have on what type an object of that class 
might be considered? What can be defined in an interface? What is assumed?}
\par 
\par {\ltrch\loch\f2 *\tab what is the safer way of comparing two objects than ==?}
\par 
\par {\ltrch\loch\f2 *\tab Java wrapper classes for primitive types (Integer, Double, Character, etc.)}
\par 
\par {\ltrch\loch\f2 *\tab What is a Java exception? a Java try-catch block? How can an exception be caught? How can an exception be thrown?  What are their advantages? (disadvantages? 8-) )}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab more data-structure/ADT-oriented:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is {\b abstraction}{\b0 ? what is }{\b information hiding}{\b0 ?}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 
\par {\ltrch\loch\f2 *\tab what is an {\b abstract data type (ADT)}? what is a {\b data structure}? How do they relate? (Is an ADT a data structure?)}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab Given an ADT specification (in the form of prose or UML or in the form of a Java interface or Java abstract class), could you write code {\b using}{\b0  that ADT?}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-435\ltrch\loch\f2 
\par {\ltrch\loch\f2 *\tab Given an ADT specification (in the form of prose or UML or in the form of a Java interface or Java abstract class), could you write code {\b implementing} that ADT?}
\par 
\par {\ltrch\loch\f2 *\tab What issues should you consider in designing an ADT?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab recursion-related:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is recursion? What is a recursive definition? What is a recursive solution to a problem? What is a recursive method/function? (How can you tell that a method/function or definition is recursive?)}
\par 
\par {\ltrch\loch\f2 *\tab what is binary search? how does it work? what are some differences between sequential search and binary search?}
\par 
\par {\ltrch\loch\f2 *\tab how can integers stored within a linked list be summed recursively?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2{\ltrch\loch\f2{\b0 *\tab you may have to somehow read/show your understanding of a recursive function; you may have to write, debug, or complete a recursive function}.}
\par 
\par {\ltrch\loch\f2 *\tab what two cases must you have (at least) in a recursive solution to a problem?}
\par 
\par {\ltrch\loch\f2 *\tab what are the two requirements for a "good" recursive function?}
\par 
\par {\ltrch\loch\f2 *\tab is a recursive solution always an efficient one? ever an efficient one?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab lists:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420 {\ltrch\loch\f0 *\tab Be comfortable with the basic concepts of the list ADT discussed in class, lab and used in homeworks}
\par 
\par {\ltrch\loch\f0 *\tab how can you use an array to implement a list? how can you use nodes with fields that reference other nodes (a linked list) to implement a list?}
\par 
\par {\ltrch\loch\f0 *\tab linked lists}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420 {\ltrch\loch\f0 *\tab {\b0\ulnone\fs24\f2 be comfortable with how to set up, use a typical singly-linked list node object}}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 
\par {\ltrch\loch\f2 *\tab what kind of components make up a linked-list node, typically?}
\par 
\par {\ltrch\loch\f2 *\tab how do you access the fields within a node? set them?}
\par 
\par {\ltrch\loch\f2 *\tab what are the typical data fields for a singly-linked list class? What is the head of a singly-linked list?}
\par 
\par {\ltrch\loch\f2 *\tab what is the difference between a singly-linked list and a doubly-linked list? What are the trade-offs between them? Why might you choose one over the other?}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with how to perform the various typical actions discussed on linked lists (singly- and doubly-linked) (How do you "walk through" a linked list? How do you properly delete a specified node? How do you add a node? etc.)}
\par 
\par {\ltrch\loch\f2 *\tab you should be able to do things to a linked list recursively;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you should be able to compare/contrast the different implementations of the list ADT --- its array-based implementation, its linked-list-based implementation. (Now that we have covered big-O notation, I could ask such questions about the different list o
perations in these two implementations.)}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab stacks:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is LIFO?}
\par 
\par {\ltrch\loch\f2 *\tab you need to be comfortable with the stack ADT;}
\par 
\par {\ltrch\loch\f2 *\tab what is a stack? what are the typical operations defined on stacks? how can a stack be used?}
\par 
\par {\ltrch\loch\f2 *\tab how can stacks be implemented? (you should know of at least 3 different ways)}
\par 
\par {\ltrch\loch\f2 *\tab you need to be able to {\b use }the stack ADT in problem solutions; you also need to be able to implement stack operations in the different stack implementations.}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a stack appropriate?}
\par 
\par {\ltrch\loch\f2 *\tab how can you implement stacks using arrays? using pointers? using the list ADT?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you should be able to compare/contrast these implementations; discuss their tradeoffs, big(O) complexity for different operations using the different implementations, etc.}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what are some typical applications of stacks?}
\par 
\par {\ltrch\loch\f2 *\tab how can stacks be used to help in various expression-based activities? in searching?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab queues:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is FIFO?}
\par 
\par {\ltrch\loch\f2 *\tab you need to be comfortable with the queue ADT;}
\par 
\par {\ltrch\loch\f2 *\tab what is a queue? what are the typical operations defined on queues? how can a queue be used?}
\par 
\par {\ltrch\loch\f2 *\tab how can queues be implemented?}
\par 
\par {\ltrch\loch\f2 *\tab you  need to be able to {\b use} the queue ADT in problem solutions; you also need to be able to implement queue operations in the different queue implementations.}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a queue appropriate?}
\par 
\par {\ltrch\loch\f2 *\tab how can you implement queues using arrays? using pointers? using the list ADT?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab you should be able to compare/contrast these implementations;}
\par 
\par {\ltrch\loch\f2 *\tab in an array-based implementation, what is rightward drift? How can it be avoided?}
\par 
\par {\ltrch\loch\f2 *\tab in the different array-based implementations, how can you distinguish between a full queue and an empty one?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li825\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what are some typical applications of queues?}
\par {\ltrch\loch\f2 *\tab how can queues be used to read in a string of characters? to recognize palindromes?}
\par 
\par {\ltrch\loch\f2 *\tab what is {\b simulation}? How might queues be helpful in simulations?}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab algorithm efficiency, algorithm complexity, big-O notation:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is analysis of algorithms? what do we mean by algorithm efficiency? what are some of the possible ways to assess an algorithm's efficiency?}
\par 
\par {\ltrch\loch\f2 *\tab what do we mean by order-of-magnitude analysis? What is the order of an algorithm? How is it expressed?}
\par 
\par {\ltrch\loch\f2 *\tab you need to be comfortable with Big-O notation;}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab need to be able to read it, write it, understand what it means;}
\par 
\par {\ltrch\loch\f2 *\tab given a function representing the number of operations that an algorithm takes relative to the size of the data {\b n}, you should be able to give the corresponding Big-O notation;}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with the intuitive interpretations of growth-rate functions, and their properties.}
\par 
\par {\ltrch\loch\f2 *\tab you need to understand its limitations;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li855\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what do we mean by worst-case analysis? average-case analysis? best-case analysis?}
\par 
\par {\ltrch\loch\f2 *\tab you should be able to reason about, compare/contrast the efficiency of two algorithms as the size of input n increases; for example, sequential search vs. binary search;}
\par 
\par {\ltrch\loch\f2 *\tab you should be able (for some algorithms) be able to come up with its order of magnitude;}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab searching and sorting (mostly sorting):}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what are searching algorithms? what are sorting algorithms?}
\par 
\par {\ltrch\loch\f2 *\tab need to be comfortable and familiar with all of the sorts discussed;  you should know their algorithms, how they work, their orders of magnitude, their strengths and weaknesses;}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what kinds of situations are appropriate for each? what are the characteristics of each of these algorithms?}
\par 
\par {\ltrch\loch\f2 *\tab given performance data, you should be able to reason about which sort was in use;}
\par 
\par {\ltrch\loch\f2 *\tab given pseudocode or code, you should be able to recognize which search is being implemented by that code;}
\par 
\par {\ltrch\loch\f2 *\tab bubblesort, selection sort, insertion sort, mergesort, quicksort, radix sort}
\par 
\par {\ltrch\loch\f2 *\tab should be able to compare these in various ways;}
\par 
\par {\ltrch\loch\f2 *\tab (for radix sort, should be able to do it "on paper" like we did it on the board in-lecture;)}
\par 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li420\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab trees}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li840\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is a (general) tree? what is a binary tree?}
\par 
\par {\ltrch\loch\f2 *\tab be comfortable with the basic tree-related terminology: node, vertex, edges, parent, child, sibling, root, leaf, interior node, ancestor, descendant, subtree, left child, right child, left subtree, right subtree, height of a tree, level of a node, full b
inary tree, complete binary tree}
\par 
\par {\ltrch\loch\f2 *\tab you should be able to implement and demonstrate {\b preorder}, {\b inorder}, and {\b postorder} traversal of binary trees. What is the complexity of such traversals?}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with typical binary tree ADT operations.}
\par 
\par {\ltrch\loch\f2 *\tab what is an arithmetic expression tree? How is it built? What do you get if you traverse such a tree in preorder? in inorder? in postorder? How can its expression then be evaluated?}
\par 
\par {\ltrch\loch\f2 *\tab how can a prefix expression be converted/stored into a corresponding expression tree?}
\par 
\par {\ltrch\loch\f2 *\tab how might a binary tree be implemented using arrays? using linked nodes?}
\par 
\par {\ltrch\loch\f2 *\tab some facts about binary trees that you should know:}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1275\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab A {\b full} binary tree of height {\b h>=0} must have how many nodes?}
\par 
\par {\ltrch\loch\f2 *\tab The maximum number of nodes in a binary tree of height h is what?}
\par 
\par {\ltrch\loch\f2 *\tab The minimum height of a binary tree with n nodes is what?}
\par 
\par {\ltrch\loch\f2 *\tab what kinds of binary trees have this minimum height?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li360\ri0\fi-360\ltrch\loch\f2 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li360\ri0\fi-360\ltrch\loch\f2 
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li720\ri0\fi-360\ltrch\loch\f2 
\par }