{\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\mo5\dy8\hr16\min3}{\printim\yr2003\mo5\dy8\hr16\min3}{\comment StarWriter}{\vern6410}}\deftab1250
{\*\pgdsctbl
{\pgdsc0\pgdscuse195\pgwsxn12240\pghsxn15840\marglsxn1083\margrsxn1083\margtsxn1083\margbsxn1083\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 - Final Study Suggestions\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 4}}}
\par }
\pgdscnxt0 Default;}}
\paperh15840\paperw12240\margl1083\margr1083\margt1083\margb1083\sectd\sbknone\pgwsxn12240\pghsxn15840\marglsxn1083\margrsxn1083\margtsxn1595\margbsxn1083\headery1083{\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 - Final Study Suggestions\tab \tab p. {\field{\*\fldinst \\page}{\fldrslt 4}}}
\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 Final - 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 final exam date and time:}}
\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{\*\tlswg8236}\tx1680{\ltrch\loch\f2{\b\f2 \tab {{\caps TUEsday}, MAY 13th at 12:40 pm in SCIB 128}}}
\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: 5-7-03}}
\par 
\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{\ltrch\loch\f2{\ulnone *\tab Final is {\b comprehensive }--- thus, this set of suggestions assumes that you will already have the Midterm #1 Review Suggestions, Midterm #2 Review Suggestions, Midterm #1, and Midterm #2 as part of your final review materials. (note that both of those earl
ier midterm suggestions' sets are still available from the course web page...) This just mentions suggestions for material since Midterm #2.}}
\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 
\par {\ltrch\loch\f2 *\tab everything discussed/involved in assigned reading, lectures, labs, and homework assignments and examples is fair game. The final is comprehensive, and covers the entire semester.}
\par 
\par {\ltrch\loch\f2 *\tab But, these are some especially-significant topics to help you in your studying for the final.}
\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 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 Java class contains a rich set of classes for stream input and output (and should thus be {\b import}ed into a class wishing to make use of these)? (see OutputPlay.java, which does contain simple examples of interactive and file input, also)}
\par 
\par {\ltrch\loch\f2 *\tab understand the basics of stream I/O in Java --- how a File instance can be created from a String containing a physical file's name, how the File class contains numerous methods for querying a File's state (and even deleting it), but not otherwise modifyi
ng its contents, but how an input stream or output stream instance can be connected to that File instance to obtain input from or to send output to its corresponding physical file, respectively.}
\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 "binary" stream input and stream output tends to be handled by subclasses of the classes InputStream and OutputStream; "text" stream input and stream output tends to be handled by subclasses of the classes Reader and Writer.}
\par 
\par {\ltrch\loch\f2 *\tab streams *should* be explicitly close()'d when one is done with them...}
\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 
\par {\ltrch\loch\f2 *\tab What is the name of the standard output stream that Java sets up for one automatically? What is the name of the standard input stream that Java sets up for one automatically?}
\par 
\par {\ltrch\loch\f2 *\tab You should understand the simple input/output examples in OutputPlay.java. }
\par 
\par {\ltrch\loch\f2 *\tab if a method A calls a method B that throws an exception C, but method A does not want to catch that exception --- what is an alternative for method A? (Hint: see method terminalInput() in class OutputPlay.java...)}
\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{\ulnone\fs24 *\tab {\b trees }(especially {\b binary trees}), new stuff:}}
\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 {\b balanced}{\b0  tree? Why is this an important/desirable tree property?}}
\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\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 priority queues} and {\b heaps}}
\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 priority queue? how does a priority queue differ from a "regular" queue?}
\par 
\par {\ltrch\loch\f2 *\tab what are some typical operations defined on priority queues? how can a priority queue be used?}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a priority queue appropriate?}
\par {\ltrch\loch\f2 *\tab what are some typical applications of priority queues?}
\par 
\par {\ltrch\loch\f2 *\tab need to be able to {\b use }a given priority queue ADT or UML or interface to solve problems;}
\par 
\par {\ltrch\loch\f2 *\tab what is a {\b heap}? What properties must a heap satisfy?}
\par 
\par {\ltrch\loch\f2 *\tab why does a {\b heap} work nicely for implementing a priority queue?}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a heap appropriate?}
\par {\ltrch\loch\f2 *\tab what are some typical applications of heaps?}
\par 
\par {\ltrch\loch\f2 *\tab how can a heap be implemented? Need to comfortable with both linked and array-based implementations of a heap, too.}
\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 {\ltrch\loch\f2 *\tab Consider a {\b complete heap}{\b0 . How can you }{\b rebalance}{\b0  a heap? How can you insert into a complete heap, and ensure that it is still complete (and still a heap) after the insertion? How can you delete from a complete heap, and ensure that it is still complete (a
nd still a heap) after the deletion?}}
\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 
\par {\ltrch\loch\f2 *\tab need to be able to {\b use }a given heap ADT or UML or interface to solve problems; you also need to be able to implement (and reason about the big O complexity of) heap operations in the different heap implementations. }
\par 
\par {\ltrch\loch\f2 *\tab should be comfortable with {\b heapsort}{\b0 ; what is its average and worst-case performance complexity?}}
\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 binary search 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 binary search tree? Is every binary tree a binary search tree? Is every binary search tree a binary tree?}
\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{\b0\ulnone\fs24\f2 *\tab you should be comfortable with {\b searching} a binary search tree. What are the average- and worst-case complexities for such searches?}}
\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 how does the {\b shape}{\b0  of the tree affect the performance complexity of binary search tree search?}}
\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 
\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 you should be comfortable with {\b inserting into} a binary search tree. What are the average- and worst-case complexity for such insertions?}
\par {\ltrch\loch\f2 *\tab you should be comfortable with {\b deleting} from a binary search tree.}
\par 
\par {\ltrch\loch\f2 *\tab you should be comfortable with {\b balancing} a binary search tree.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab How can you store a binary search tree as an ordered array?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1290\ri0\fi-435\ltrch\loch\f2{\ltrch\loch\f2{\b0 *\tab How can you then create a more-balanced form of that tree when re-creating it from that array?}}
\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 
\par {\ltrch\loch\f2 *\tab what are some of the typical operations defined on binary search trees? how can a binary search tree be used?}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a binary search tree appropriate?}
\par {\ltrch\loch\f2 *\tab what are some typical applications of binary search trees?}
\par 
\par {\ltrch\loch\f2 *\tab need to be able to {\b use }a given binary search tree ADT or UML or interface to solve problems; you also need to be able to implement (and reason about the big O complexity of) binary search tree operations in the different implementations.}
\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 \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 
\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 if you traverse a binary search tree inorder, printing the nodes' search key values as they are visited, what will be the case?}
\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 
\par {\ltrch\loch\f2 *\tab should be comfortable with {\b treesort}{\b0 ; what is its average and worst-case performance complexity?}}
\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\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 hashes, hash tables, and hashing}}
\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 hash function? What is a hash table? What is hashing?}
\par 
\par {\ltrch\loch\f2 *\tab what does a hash function do? How is it used?}
\par {\ltrch\loch\f2 *\tab what are some of the desired properties for a hash function? you should be able to implement a simple hash function, and be able to assess its quality;}
\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 are some examples of hash functions/some examples of typical hash function techniques?}
\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 
\par {\ltrch\loch\f2 *\tab what are some typical operations defined on hash tables? how can a hash table be used?}
\par {\ltrch\loch\f2 *\tab how are items inserted into a hash table? how are items retrieved from a hash table? What is the average case time complexity for such insertion and deletion? what is the worst-case time complexity for these operations (and when does it occur)?}
\par {\ltrch\loch\f2 *\tab what particular typical "collection of things" operation is particularly inefficient when hashing is used to implement that collection?}
\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 Be comfortable with open-addressing (plain array-based hash table) collision-resolution techniques such as linear probing, quadratic probing,double hashing, rehashing.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1320\ri0\fi-435\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what is meant by clustering? (primary and secondary clustering)}
\par {\ltrch\loch\f2 *\tab why is clustering a problem?}
\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 
\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-405\ltrch\loch\f2 {\ltrch\loch\f2 *\tab What is the significance of hash table size in hashing's performance, in general?}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1245\ri0\fi-405\ltrch\loch\f2 {\ltrch\loch\f2 *\tab what kind of characteristics are considered desirable for a hash  table's size?}
\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-405\ltrch\loch\f2 {\ltrch\loch\f2 *\tab if you decide to dynamically increase the size of the hash table in such a scheme, what must be done? (How would you do so?)}
\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 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a hash table appropriate?}
\par {\ltrch\loch\f2 *\tab what are some typical applications of hash tables?}
\par 
\par {\ltrch\loch\f2 *\tab need to be comfortable with both array-based and separate chaining/buckets-and-chaining hash table implementations.}
\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 {\ltrch\loch\f2 *\tab Given a hash function and a hash table implemented as an array of pointers to linked lists (that is, implemented using {\b separate chaining/buckets-and-chaining}), could you show what hashing would do for a collection of actions (insertions and deletions of 
specified values)? Could you do so for a hash table implemented as an array (open addressing) using a given collision strategy?}
\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 
\par {\ltrch\loch\f2 *\tab need to be able to {\b use }a given hash table ADT or UML or interface to solve problems; you also need to be able to implement (and reason about the big O complexity of) hash table operations in the different hash table implementations.}
\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
\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 graphs}}
\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 graph? What is its mathematical definition? What is the relationship between graphs and trees? }
\par 
\par {\ltrch\loch\f2 *\tab You should be comfortable with the basic graph terminology: vertex, node, edge, graph, subgraph, adjacent, path, simple path, cycle, simple cycle, connected, disconnected, complete, undirected graph, directed graph, undirected edge, directed edge, weight
ed edge, successor, predecessor.}
\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 for the above terms for which it is appropriate, be comfortable with their (sometimes different) meanings for directed graphs and indirected graphs.}
\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 
\par {\ltrch\loch\f2 *\tab what are some typical operations defined on graphs? how can graphs be used?}
\par 
\par {\ltrch\loch\f2 *\tab in what kinds of situations is a graph appropriate?}
\par {\ltrch\loch\f2 *\tab what are some typical applications of graphs?}
\par 
\par {\ltrch\loch\f2 *\tab traversals: depth-first-search (DFS)-based, breadth-first-search (BFS)-based}
\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 given a graph and a starting vertex, you should be able to show an order in which a graph's vertices could be visited using each of these;}
\par 
\par {\ltrch\loch\f2 *\tab for which is a recursive approach easier? For that traversal, if you do not use recursion, what abstract data type is particularly appropriate for use in that traversal?}
\par 
\par {\ltrch\loch\f2 *\tab in implementing a DFS-based traversal, which abstract data type is particularly useful/appropriate, if recursion is not used? Can recursion be used easily for this?}
\par 
\par {\ltrch\loch\f2 *\tab in implementing a BFS-based traversal, which abstract data type is particularly useful/appropriate, if recursion is not used? Can recursion be used easily for this?}
\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 
\par {\ltrch\loch\f2 *\tab need to be comfortable with both adjacency-list and adjacency-matrix implementations of graphs}
\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 {\ltrch\loch\f2 *\tab you should be able to sketch a conceptual depiction of a graph within an adjacency matrix implementation or within an adjacency list implementation, whether it is directed or undirected, whether it has weighted edges or not. You should be able to perform
 graph manipulations to a graph expressed in such form.}
\par \pard\plain \s1\cf1{\*\hyphen2\hyphlead2\hyphtrail2\hyphmax0}\aspalpha\rtlch\af4\afs24\lang255\ltrch\dbch\af3\afs24\langfe255\loch\f0\fs24\lang1033\li1695\ri0\fi-420\ltrch\loch\f2 {\ltrch\loch\f2 *\tab (you should be able to read/manipulate/express a graph as a drawing or in G = (V, E) form as well)}
\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 
\par {\ltrch\loch\f2 *\tab need to be able to {\b use }a given Graph ADT or UML or interface to solve problems; you also need to be able to implement (and reason about the big O complexity of) graph operations in the different graph implementations.}
\par 
\par {\ltrch\loch\f2 *\tab if you are given a connected, undirected graph --- what is an easy way to tell if it has any cycles?}
\par 
\par {\ltrch\loch\f2 *\tab What is a {\b topological order}? what is {\b topological sorting}? What are two algorithms for topological sorting (for obtaining a topological order)?}
\par 
\par {\ltrch\loch\f2 *\tab what is a spanning tree? what is a minimum spanning tree? what is meant by a shortest path in a weighted directed graph?}
\par 
\par {\ltrch\loch\f2 *\tab some graph-related facts 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 if a connected, undirected graph has n vertices, at least how many edges should it have?}
\par {\ltrch\loch\f2 *\tab if it has exactly that many edges, what do you know that it cannot obtain?}
\par {\ltrch\loch\f2 *\tab if it has more than that many edges, what do you know it must contain?}
\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 if you have a connected undirected graph with cycles and you remove edges until there are no cycles, what do you get?}
\par 
\par {\ltrch\loch\f2 *\tab What is a circuit? What is an Euler circuit (a circuit that passes through every {\b edge}{\b0  exactly once)}? What is a Hamilton(ian) circuit (a circuit that passes through every {\b vertex}{\b0  exactly once, except it begins and ends at the same vertex v)}?}
\par }