> KMJ (bjbjoo B
8TVzYYoooooor|oooosoowooo2wM-&0Vooos:
ICS 23
Review Questions for the Final
These questions are meant to help you review class material in preparation for the final exam. As with the midterm review question set, I've tried to be reasonably thorough, but there may be material that is "fair game" for the exam that is not covered here. Likewise, it's likely that not all particulars covered here will be on the test.
1. Consider this directed graph:
Construct its adjacency list representation.
Construct is adjacency matrix representation.
Is the graph weakly connected? Why or why not? Strongly connected? Why or why not? Are any components of the graph weakly connected? If so, which ones? Are any components of the graph strongly connected? If so, which ones?
What is the indegree of node Y? outdegree of node T?
Image a graph identical to the one above except that it is undirected.
Construct its adjacency list representation.
Construct is adjacency matrix representation.
Is the graph connected? Why or why not? Are any components of the graph connected? If so, which ones?
What is the indegree of node Y? outdegree of node T?
2. Consider this activity-on-vertex graph. The node weights are inside the circles (representing the nodes); the node numbers are underneath them.
What are the predecessors of 9? The successors of 11?
List the nodes (when reading left to right) in a topological order. Now list them again in another topological order.
3. In a depth-first traversal of a directed graph, using the algorithm presented in class, how does it know when a cycle has been found?
4. Briefly describe each of the following graph problems. If a hard graph problem is one that takes, as far as we know, exponential time (in the number of nodes) to solve deterministically (in the general case), which of these problems are hard?
- finding the minimal spanning tree of undirected, weighted (edge) graph
- determining the maximum flow through a flow network
- the 4-color problem
- finding k-cliques
- finding a Hamiltonian circuit in a directed graph
- the Traveling Sales Representative problem
- finding the shortest path between two points in a weighted, directed graph
5. Consider these sorts:
Quicksort
Mergesort
Insertion sort
Selection sort
Heapsort
Proxmap sort
Radix sort
Shell sort
Tree sort
Bubble sort
Chainsort
Sorting using an ordered skip list
What are their average case running times (in theta notation?) best case?
worst case? (We did not cover all of these for all sorts listedjust know the ones we did cover.)
For each, roughly how much extra space is required? (Assume an array of the items is presented to the sort, and the sorted items are to be placed back into the same array.)
For each, what arrangement of the input data (if it matters) will cause the worst-case performance? the best-case performance? (Again, for the ones we have studied.)
For each sort, does it work as well (e.g., have the same O-notation) if it is used on a list of items stored in a linked list instead of an array?
In what situations, if any, would be it faster to use an O(n2) sort than an O(n log n) sort? An O(n log n) sort over an O(n) sort?
Among merge sort, heap sort and quicksort, which has the lowest constant? Under what conditions would it make sense to use the sort with the lowest constant? with the highest constant?
For quicksort: what is the median-of-three method for choosing a pivot? What other methods are common? When do they work well? not work well?
6. Consider these search strategies:
sequential
binary
interpolation
binary search trees:
no special balancing done
AVL
splay
perfectly balanced
B-tree
hashing
with separate chaining
with linear probing
with quadratic probing
with double hashing
Skip List
ProxmapSearch
ChainSsearch
What are their average case running times (in theta notation?)
worst case running times? (We did not talk about both times for all algorithmsso just know the ones we did discuss.)
For each, roughly how much extra space is required? Assume the list to be searched is originally stored in an array and the items are in no particular order.
Which hashing technique(s) has/have the fastest search time when the hash table is relatively empty? when about 1/2 full? when close to full?
Given an array [0..12] and a hash function h(key) = key div 5. (div is integer division: keep the quotient and toss the remainder.) Add these keys to the hash table using one hash scheme given above, the do it again (from the beginning) with another, and so on until youve done them all. Use d(key) = key mod 5 + 1 for the second hash function (the one thats used in collision resolution) for double hashing.
53, 37, 19, 22, 3, 55, 59, 0, 17, 50
What are other good ways (besides the simple division hashing method given above) to choose a hash function? In particular, what are some good multiplicative techniques? What are some poor techniques?
What are some ways to choose m (the table size) and d(key) so that every element of the table is probed before the probe returns to the first element checked (that is, to ensure the table is covered)?
When, if ever, does it make sense to sort an (unsorted) list (stored in an array) so that you can use a search on it that requires the data to be in order?
For each search, does it work as well (e.g., have the same O-notation) if the original list is stored in a linked list instead of an array?
Consider a B-tree of order 3. What is the tree after insertion of these keys? (Assume the tree starts empty.)
M, C, F, S, W, Q, Z, A, B
Suppose you have an order m B-tree. How many levels are required at minimum to hold 3000 keys? How many levels at maximum are required?
What factors of the computer itself (e.g., disk and memory characteristics) should be taken into account when determining the optimum m order of a B-tree, given n keys are to be stored in it?
Under what conditions would it result in a faster search time to store a large number n of keys into a B-tree instead of a hash table? a hash table instead of a B-tree?
How do B+-trees differ from B-trees, in terms of their structure? in terms of their searching, addition and deletion algorithms? Which is faster, on average? Which tasks take more memory? Why would one use B+-trees instead of B-trees?
What are the advantages, if any, of best fit over first fit? of first fit over best fit? of Standishs algorithm as compared to first and best fit?
How fast is Standishs memory algorithm in the best case (in O-notation)? the average case? the worst case? When does the best case occur? the worst case? What are the disadvantages of Standishs algorithm?
Whats external fragmentation? How can it be reduced when using first fit? best fit? Whats internal fragmentation? How can it be reduced? Whats coalescing? compaction?
Whats garbage collection? What's the difference between a marking algorithm and a reference count approach? Under what conditions can they fail? When is it inappropriate to use garbage collection?
7. Describe the union-find algorithm. Give examples of a problem that's amenable to solution using union-find. (Hint: one of them is the bullet below!) What's path compression? What effect does it have on the algorithm? What's union by rank? What effect does it have? How fast is union-find, in terms of O-notation of its amortized time, when it's fully optimized? If the find operation is O(1), what does this say about the O-notation of the union operation? If the union operation is O(1), what does this say about the O-notation of the find operation?
8. Given these symbol frequencies:
a 70B 10b 15d 10e 50k 05l 10N 15n 35o 20R 05s 30t 40u 20
Construct a minimum Huffman tree for these symbols.
What is the Huffman encoding, using the tree you constructed, for the string NoBlanksButReadable ?
What methods might one use to get the Huffman tree to the receiving party? What "encodings" of the tree would allow it to be sent digitally without ambiguity as to its structure?
PAGE 2
'{
DF>?LMQRHIN&e&f&z&{&&&&#'7'''''''(hWmHnHuhWCJOJQJ
hW_H hW6hWCJEHj#hWUhW=hWCJjhWUhWhW=
h{KCJ*&'{ | }
efh^h`gdW$
ha$gdW
hgdW
h0]0gdW$a$12ijklmnopq
@
A
DEF>?h^h`gdW
hgdW?K #/=Inw h^h`wx
OP.Ebir 8h^8`h h^h`%&'(ivw45 h^h`5. !!!!""2#3####(&)&*&M&N&V&[&`&e&
h$IflI
h h^h`e&f&k&p&u&z&
h$IflIkkd$$IfP\ p!pppp4
Paz&{&&&&&
h$IflIkkdf$$IfP\ p!pppp4
Pa&&&&&&
h$IflIkkd$$IfP\ p!pppp4
Pa&&&&9':''''''((~||h^h`gdW
hkkd:$$IfP\ p!pppp4
Pa& 00P/ =!"#$%|HH(FG(HH(d'`#Dd
@$ <
CABt ¶zVWqX#oD Tgt ¶zVWqX#PuAL5xm+a?O$!MI\8(m.ۛ!PRLin-73%
gByI.y߭=<>0q(KJlϥ͒k,Iذ9(w1dMEs<ڔ-⺸azG!R e*%LQ%V1NvNa@; -#53zUwMJV&Uɹ>ɒEӒՠ \evG>Oܐ< ɘtdHM\6Yh!Wt}zAwjf:,s߱^n/7{y5/%bWDd
<
<
CABI
mJ5xuZP%g T
mJ5xuZP;Cԗ>xu?hQZ5^0FTS.ik.i5D:Kuu]K!]t$Z\G\:88 /{ӻ~{V0TSYӳ($l!y`&|R5\ 75Ʉd C\嵉]!/֗]^Fr^C- J"E{"R尝y04j[4`^\#U"L6666666666666666666666666666666666666666666666666hH6666666666666666666666666666666666666666666666666666666666666666666666666662 0@P`p2( 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p 0@P`p8XV~OJQJ_HmH nH sH tH D`DNormalCJOJQJ_HmH sH tH DA DDefault Paragraph FontZi@ZTable Normal :V4
l4a_H(k (No List4 @4Footer
!PK!K[Content_Types].xmlj0Eжr(]yl#!MB;BQޏaLSWyҟ^@
Lz]__CdR{`L=r85v&mQ뉑8ICX=H"Z=&JCjwA`.Â?U~YkG/̷x3%o3t\&@w!H'"v0PK!֧6_rels/.relsj0}Q%v/C/}(h"O
= C?hv=Ʌ%[xp{۵_Pѣ<1H0ORBdJE4b$q_6LR7`0̞O,En7Lib/SeеPK!kytheme/theme/themeManager.xmlM
@}w7c(EbˮCAǠҟ7՛K
Y,
e.|,H,lxɴIsQ}#Ր ֵ+!,^$j=GW)E+&
8PK!\theme/theme/theme1.xmlYOoE#F{o'NDuر i-q;N3'
G$$DAč*iEP~wq4;{o?g^;N:$BR64Mvsi-@R4mUb V*XX!cyg$w.Q"@oWL8*Bycjđ0蠦r,[LC9VbX*x_yuoBL͐u_.DKfN1엓:+ۥ~`jn[Zp֖zg,tV@bW/Oټl6Ws[R?S֒7 _כ[֪7 _w]ŌShN'^Bxk_[dC]zOլ\K=.:@MgdCf/o\ycB95B24SCEL|gO'sקo>W=n#p̰ZN|ӪV:8z1fk;ڇcp7#z8]Y/\{t\}}spķ=ʠoRVL3N(B<|ݥuK>P.EMLhɦM .co;əmr"*0#̡=6Kր0i1;$P0!YݩjbiXJB5IgAФa6{P g֢)҉-Ìq8RmcWyXg/u]6Q_Ê5H
Z2PU]Ǽ"GGFbCSOD%,p
6ޚwq̲R_gJSbj9)ed(w:/ak;6jAq11_xzG~F<:ɮ>O&kNa4dht\?J&l O٠NRpwhpse)tp)af]
27n}mk]\S,+a2g^Az
)˙>E
G鿰L7)'PK!
ѐ'theme/theme/_rels/themeManager.xml.relsM
0wooӺ&݈Э5
6?$Q
,.aic21h:qm@RN;d`o7gK(M&$R(.1r'JЊT8V"AȻHu}|$b{P8g/]QAsم(#L[PK-!K[Content_Types].xmlPK-!֧61_rels/.relsPK-!kytheme/theme/themeManager.xmlPK-!\theme/theme/theme1.xmlPK-!
ѐ'
theme/theme/_rels/themeManager.xml.relsPK]
B(B(?w5e&z&&&( !@HT] ? H V
_
$#6 T]
*?CAH #MTp t
)
58z}IKpr4
8
R
U
-06HJlqu~*.jo')-0WZ=?
03rt[]wy@C%/59NO[\`afgklpq{|#8<@ ::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::WMNV[`efkpuz{ @ P@UnknownGTimes New Roman5Symbol3Arial5Geneva9MNew YorkS PalatinoBook Antiqua":;9Fw;9FqV
8!;dW ;?m0Review Q's for midtermNorman JacobsonNorm
Oh+'0
<HT
`lt|'Review Q's for midtermNorman JacobsonNormal.dotmNorm23Microsoft Macintosh Word@1@j?s@SIk@:wV
՜.+,0$hp
'(Dept. of Info. & Comp. Sci., UC Irvine8
W Review Q's for midtermTitle
!#$%&'()+,-./0123456789;<=>?@ACDEFGHILRoot Entry F[2wNData
"1Table*WordDocumentBSummaryInformation(:DocumentSummaryInformation8BCompObj` F Microsoft Word 97-2004 DocumentNB6WWord.Document.8