UC Berkeley – Computer Science
CS61B: Data Structures
Midterm #2, Spring 2016
This test has 10 questions worth a total of 60 points. The exam is closed book, except that you are allowed to use two pages (both front and back, for 4 total sides) as a written cheat sheet. No calculators or other electronic devices are permitted. Give your answers and show your work in the space provided. Write the statement out below, and sign once you’re done with the exam. Write the statement out below in the blank provided and sign. You may do this before the exam begins.
“I have neither given nor received any assistance in the taking of this exam.”
________________________________________________________________________________________________ ________________________________________________________________________________________________
Points Points
0 0.55 6 1 96 3.5 2476 3488 4099 10 10
Total 60
Signature: Z.T.H
Name: Ziro
SID: 80
Three-letter Login ID: zth
Login of Person to Left: qgj
Login of Person to Right: sid
Exam Room: Coruscant, Underwater Primary TA (if any): Ugnaught
Tips:
There may be partial credit for incomplete answers. Write as much of the solution as you
can, but bear in mind that we may deduct points if your answers are much more
complicated than necessary.
There are a lot of problems on this exam. Work through the ones with which you are
comfortable first. Do not get overly captivated by interesting design issues or complex
corner cases you’re not sure about.
Not all information provided in a problem may be useful.
Unless otherwise stated, all given code on this exam should compile. All code has been
compiled and executed before printing, but in the unlikely event that we do happen to catch any bugs during the exam, we’ll announce a fix. Unless we specifically give you the option, the correct answer is not ‘does not compile.’
The last problem is the “hard” one.
Optional. Mark along the line to show your feelings Before exam: [____________________]. on the spectrum betweenand. After exam: [____________________].
UC BERKELEY Login: _______
0. So It Begins II (0.5 points). Write your name and ID on the front page. Circle the exam room. Write the IDs of your neighbors. Write the given statement. Sign when you’re done with the exam. Write your login in the corner of every page.
1. BST and Hash Table Essentials (9 Points).
a) Suppose we’re building a map that represents the rental cost in dollars per square foot of various locations. Starting from an initially empty BSTMap, if we call put(“SAN JOSE”, 2.9), we’d get the tree shown in the box containing one node, with height equal to zero.
Draw the BSTMap after all of the following put operations have completed, in the order given. Assume that the tree is ordered based on alphabetical order. Draw your answer in the box to the right. This tree is not self-balancing. For reference, the alphabet is _ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.
put(“LA”, 2.0)
put(“NYC”, 2.1)
put(“SD”, 6.3)
put(“BOSTON”, 2.3)
put(“UNIT 3”, 18.0)
put(“SF”, 2.7)
put(“SD”, 1.9)
b) Suppose we repeat the exercise from part a, but with a hash map. Assume the hashCode of our strings is equal to the number of the first letter of the string. For example, the hashCode(“SF”) = 19. For reference, B2, L12, N14, S19, U21. Assume we have 5 buckets, and assume no resizing happens. Use the method we used in class (chaining).
2
CS61B MIDTERM, SPRING 2016
Login: _______
c) Suppose we use a BST to represent a TreeSet. Suppose we call remove(29) on the TreeSet below. Draw a valid BST that results. You must use the deletion procedure from class (also known as Hibbard deletion). At most two references should change. Draw your tree in the space to the right.
or
d) Suppose we try to use a HashMap on a data type where the key’s hashCode always returns 2000000000, and the value’s hashCode always returns -5. Will the HashMap’s containsKey and get methods always return the expected result (don’t worry about runtime)? Assume that equals is properly implemented. State yes or no, and briefly explain your answer in the space below.
Yes. Though our key’s poor hashCode method will cause all keys to be thrown into one bucket, the HashMap will still be able to function correctly by iterating over the keys in that bucket and checking if each is .equals to the query key. This is guaranteed to work because equals is properly implemented.
e) Suppose we try to create HashSet
No. Glelk’s hashCode method calls the Object class’ hashCode method, which simply returns the object’s memory address. This means that two keys considered equal by Glelk’s equals method may hash to different buckets, causing keys to “disappear” from the HashSet.
public class Glelk {
private int x;
private int y;
/** Normally an equals method should check that o is actually a Glelk, as in HW3. However we have omitted this check for brevity. This will not affect the answer to part e.*/
public boolean equals(Object o) {
Glelk other = (Glelk) o;
return (this.x == other.x) && (this.y == other.y);
}
public int hashCode() {
return super.hashCode() / 2;
}
}
3
2. WeightedQuickUnionUF (4 Points).
a) Draw a valid WeightedQuickUnionUF tree with worst case height, given sizes of N=1, N=2, N=4, N= 6, and N=8 in the boxes below, where N is the number of items in the WeightedQuickUnionUF. The first two are done for you. Recall that the height of a tree is the length of the longest path from the root to any leaf, so the height of the tree for N=2 is 1.
There are many valid examples for worst case heights. One approach is to do a union of two sets of size N that have worst case height.
2
b) Give the best case height and worst case height of a WeightedQuickUnionUF tree in Θ notation in terms of N, the number of items in the WeightedQuickUnionUF.
Best: Θ(1)
If all unions are made such that the second set is size 1, the height will be 1.
2
increase the height of the tree by 1 every time you double 𝑁, which translates to log2(𝑁).
UC BERKELEY Login: _______
Worst: Θ(log 𝑁)
In the worst case, we can combine 2 trees of size 𝑁 that already have worst case height. Doing so will
4
CS61B MIDTERM, SPRING 2016
Login: _______
3. Exceptions (4 Points).
Consider the code below, with print statements in bold. Recall that x / 2 rounds down to the nearest
integer.
public static void checkIfZero(int x) throws Exception {
if (x == 0) {
throw new Exception(“x was zero!”);
}
System.out.println(x);
}
public static int mystery(int x) {
int counter = 0;
try {
while (true) {
x = x / 2;
checkIfZero(x);
counter += 1;
System.out.println(“counter is ” + counter);
}
} catch (Exception e) {
return counter;
}
}
public static void main(String[] args) {
System.out.println(“mystery of 1 is ” + mystery(1));
System.out.println(“mystery of 6 is ” + mystery(6));
}
What will be the output when main is run? You may not need all lines.
mystery of 1 is 0
3
counter is 1
1
counter is 2
mystery of 6 is 2
Note that “x was zero!” never gets printed. Java only prints exceptions automatically when they cause the program’s execution to stop (i.e., if they’re not caught), in which case Java would print something like:
Exception in thread “main” java.lang.Exception: x was zero!
at Exceptions.checkIfZero(Exceptions.java:4)
at Exceptions.mystery(Exceptions.java:14)
at Exceptions.main(Exceptions.java:26)
5
UC BERKELEY Login: _______
4. (0 points). This religion, founded by J.R. “Bob” Dobbs, first made its public appearance in the 1979 pamphlet “The World Ends Tomorrow and You May Die”. The Church of the Subgenius
5. Runtime in Context (6 Points).
a) Suppose we read a text file containing a list of city names and their cost of living, using the following code. Here BSTMap is the same as the implementation you created for lab8 with no special balancing features. Assume isEmpty, readString, and readDouble run in constant time. Assume that all Strings are of constant length. Assume throughout the problem that the input files are properly formatted and that no errors occur during execution. Assume all city names are unique.
public static Map
Map
while (!in.isEmpty()) {
m.put(in.readString(), in.readDouble());
}
return m; }
If there are N such cities in the file, what will be the runtime needed to complete execution of the readData function? Give your answer in Θ notation, for the best and worst case.
Best case: Θ(𝑁 log 𝑁)
Worst case: Θ(𝑁2)
In the best case, the data luckily results in a balanced tree. In the worst case, the tree looks like a LinkedList.
b) Suppose that instead of a BSTMap, we use a HashMap like the one you implemented in lab9 or java.util.HashMap. Give the best and worst case runtimes to complete execution of the readData method. The String class’s hashCode method takes takes Θ(1) time (since our Strings are of constant length).
Best case: Θ(𝑁)
Worst case: Θ(𝑁2)
In the worst case, all items accidentally hash to the same bucket, and again we have a LinkedList structure. In the best case, there is a nice bin distribution, and we achieve our amortized constant time insertion for each single insertion, so we’ll have linear time overall.
c) Finally, suppose that instead of a BSTMap, we instead use a 2-3-TreeMap. Give the best and worst case runtimes to complete execution of the readData method.
Best case: Θ(𝑁 log 𝑁)
Worst case: Θ(𝑁 log 𝑁)
A 2-3 tree is self-balancing, so asymptotically, the worst case is the best case, Θ(𝑁 log 𝑁).
6
CS61B MIDTERM, SPRING 2016
Login: _______
6. Empirical Analysis (3.5 Points).
a) Suppose we write a program that takes one argument as input N. Suppose we use the Stopwatch class to measure the total running time R(N) of our program for various values of N, collecting the following data. Approximate the empirical run time in tilde notation as a function of N. Reminder from Asymptotics III: assume the formula is of the form ~ aNb , and use only the largest data points. It is OK to round your exponent. It is OK to leave any constant factors in terms of a fraction. Do not leave your answer in terms of logarithms.
N R(N)
————–
62 125 250 500
17000
39000
75000
500000
1000 4000000
R(N) ~ 0.004𝑁3
We want to express the runtime as 𝑎𝑁𝑏, for some 𝑎 and 𝑏.
By using the last two data points (just throw away earlier data points), we can first solve for 𝑏 as follows:
𝑅(1000) = 𝑎1000𝑏 𝑅(500) 𝑎500𝑏 4000000 1000 𝑏
500000 =(500) 8 = 2𝑏
𝑏 = log2 8 = 3
Then we use the last data point to find 𝑎:
4000000 = 𝑎(1000)3 = 𝑎1000000000
𝑎 = 4000000 = 4 = 0.004 1000000000 1000
Putting this together, we get a runtime of 0.004𝑁3.
𝑅(𝑁) ~ 𝑎𝑁𝑏
7
Designated Chillout Zone. Have a good time!!
….,.:,::iirr77i. ….,.,,::i:ir777:.
. …,:,::i:ii777i. . ….,,::::ii77vi:
……,,::::iirrvr: . ….,,::::iir7v7i.
….,,::::iiir77;. ….,.:::::iir77r,
….,.:,:::ii;77r:. ……,,::::ii777i.
……,,::::iir77i: . ….,,::::iir7vr:
…..,,::::iirrvri. . ….,,::::iirrv7i.
….,,::::ii;rv7r, ……::::i:ir777:.
. ….,,::::ii777i. ….,:::ii77vi:
. ..,,::::;rvr: ..,::iirri.
. ,.:::ir;.
. ,::::ri.
. ,:::i;,
. ,::iii
. ,,::ii:
. .,:::iirrr;rr777ii::::,,…. .
. ..,,::::ii;i;ii::::,,.,….
…..,,:::::::,:,,.,…. . ….,.,.,.,…….. . ……….. .
,rjujLYJuu1U555S8v .iLJuJYYju2U15FFk2XMN ,7YuYJYuJUu1u1U1uS2kq@O .iLuJjLjJuj22F15Fk1q0PEMMO :7uJJLJJuu11F1SFS5XSNZq0OG@F .iYjjLYYjJ2U11SFkSPSkFXPPX0POBi
.:777ii::::,,……
.JJu .J7LY Y77LL
.,L7jr YvUi vu1: 7. .kF. .S LZ. vU. E,
: .. Uu …. . . Pr …
. ,2. .. i: . .i:7i .
;vYv. :YY:,jv7. :. :u:,ii, ;:.::,ruvi .kr :i,. vJj2Lvj2L5Yv:,,,,..::,7;: i7LYL7;Lk21uUuuukqGO8FL.:7U5017uL
.7:YkEFJriiiiiirr;rYuLUFiv5j7rrL1r.7, rLM07;iiiiii:i: :r, u..r.:::,:Fvi . :PSrririiii:ii: .7 : :. .:,.1M. .
.Lu,
,.
.
1@Xi NNOMPi PkUFPPY, X55U121uLu
, ,7SE@@7 .,ru8BM8Z8Z.
vBGj25F55kSL ….:Oi .5UJuqui vX77uUr r: LY … r5 ,F15i u: ,.vuU ,.:57 :O, .05:i; .2U, 75r i8: .. :u. r ru. 5: . r2jN. .. . :
1Sv2u5i j: u:
7uYv
.jvLu;
rYvvj2i .:7Yv1@L7rr:…,iiri;rv::v: i r, :i:::: ,5L77JUjri:.7@Mrrr,.. .i;rrrr7 :v :ii;::. .7
.iZqrr;;iii;ii:iir. iL…; ,i,:7u
71vJYJJuLi.LBk:i,:uS5Sjr ,r777:,:.7i: rU,:. v5uYvjLYuFuGi:i:v2uqEMB@Bu .iLi..r. :uuLMj:L i111jjvJ8@2::i:ij@7FB@UvkFM: .. :E@@v@Mqivr . .7Sq2uuEBJ:i:i,:7vj0U:i:2@BE7.:vLEM@vk M@Ur7r u, .r1EOB@Liri:i:,.,:rLj5055u2L7jOBMSkri77Pvv2.
:7PB2ivi r:::::iirr7ir7:::ir7rii: 1MJv. .:GFi7L. rii:::iiiirrvii::,:,:..:0i.
:J0:rri, ,ii:iirr1v7rr:ii::,,,.i kY772SSLi.. .77:i :;:iiiivUvi..,,7:::. 7:. .SY7rvu221UY77LLi. :7iiii:,:ijE12v:.::, v7, 7i
5urir7LY1SSS0MBu, .iii::,:ir77ju7: .,,uv, :Jv u5Lr77u1k11SZB@@j.::irkMBM@OZENE@v.iFY:.;2uL. 7Pk ::r7JuX0@B@ki,::YF11q002Ji:LqL::uk2Jv
:GL .ki
ri . .u. .
,r7ii:i:i:::::7JFG@BZuuLLJYvLiLB@M@B@OBB8X5uJJL:ru0OEqOBX7:.75E5: .ri::::::::::,:,::i70B@q5JY7YvYirBBOOMOEO8MZquuSG0N5Uuk1j.:iiri,r@N i:..:;7L7r:. ..,.::::70BMPuL7Lvv:7G8ZE:iY1jFU2Y2jujuj2k07..ii:., 7Bq i,YqMEFJXOBqj, .,:i;iLEBB0NF2P0G10N1uUFFJvLJLjuUuLL2u1SS7:.:ii:, @i :ZB8GX7rvSqqOBSk08GMM@B@80EG0M8EJ2jGEZPFUUJJLL7LJuLY7r,,:r21::rr.L5 LBqNPi:JEZNZE8BMO0EOB1SqOOMB@BM2j:rk011JJYYLvvJv7:irviii::iML,r:XBr v@OE::5M088MGEOOMB@@Gv7Y8@MZ1SEkjrvj2uLL7YJuJL;. :77ri:i87:iiE,
.kL. 2Yur jjvJ1Li
…………. . . . ..,,::iii:i::::,:,:,,.,…….. :r10GSr
..,:::..,,::::iiiiiiiii::::,.. .vMB@BMGMB@X ..,,:. .,:::78@@BMOOM8G@B@r:
..,:::. .,:rJ208@BBMMM@8MOOB@@@Bui:ii , ..,,::::rFMMZ0OOMB@B@B@OGEOSPGM0OB@B@M050BM2 ,: ,vkFFuNB@O8kFU1UFPSUZO80OM@B@B@Bu:::UM@r …r.
,rr:… ,OqZX55kPP08EMEPZOOqr:r0qru12jqPY;i,:ir,
,72BB@OGB7J@uYE@GOOF. .::i0B@MBU 7OZ@r M@BLu@BkuFu2G@0: :q@B@M8BZB@MMGj. ,. :8@XBS j@@2i@BG:: .
2UJLL77: ,N@@B@BOEXY:.:,. .r….,M@BB.@B@7ui
71LLvj2SuviuM@@@G17rriii, rY:..: EB@0S2, 8O@@@@Ev: JLrrrvLLLLr71@@@B8uL7ri:.UL7::iuEr LEM@@@B@@@u2qUrrrr72LYv;rNB@B@qJ7r:iGF7777 r77r77YuZ@@B@BBXj7r7LL22v:uB@M@BGJiLMPYvv;: ,v0B@B1
XB7 iB@B5:
P@v :OO0EOOSO1BB@BGBXEi;1BGJ7LUuYu2jJLYLujur, J5 .MO0OEOSUi5B@MMPq0FuXFGUY7v7vLJLYLjuu7: ,,.SBPE0EMXPrv1BOX2uPFEPFLJJuuuYJLJuuvi. i:;@Z0PNq8ENEEE8kuYuJuJuJJuUjjYJLJLr.
.rirvF7r7L: r7;i:i::,
.iLFr… :7uuUXr.,….
:J:FBZNqPE0ZOM08PFUkFS15u2uuYjYuYv: ;jvUZBGZ0NkSG0kXSXSS22ujYJJuJL:. ,i7FMMBOEFXXP15u2jJLYLujYi.
.,:vu1E8SFuuYJLJLJjJr: .UPUjLLvJJj7:
. ………rUjjjuLi. ….,,:::::::;uLr.
.;YjuYjSF,….. :LJuLLLu5u……
.rLjLYLjJuFS …. ivuYJLJLuu21XE,
:vJuLLvJYuu15SFXXkSPPXPNSqNO8BB@ .iv5jYLjJUu11kFXPNk0XqSqEMGGM@MB@@S :rvri7UYYJ2U51F2SN8GO8G0EGOMBMMMBM@B,
,i77rii.:11uu1kSPSkq8OMO80OM@MMMMOMOMM@ :777;i::, :N5k2SX0N0E8GO0EZBMBOMMMOMO88MB
.;77r;i:::. .PNkkXkENZGOEOGG8BMMMMOMMO8OPZG@: .irvrrii::,. :GZqNZPqZ8EGNGOMMBOMMMMMOMOOZZNMBu ,;v7rii::::. L@0q0EPqPZqEqEZOMBOBOMMMOMMMGGZPE@B
.:777ii::::,,. SBBEPqEqGZMZ8EGGOOMOMOMMMGMMM8Z08kNM@F :r77ri::::,,.. :kS8MGXZOMG8E8GZEMZMMMOMMBOOMMO0NZqN088@v
.i77riii::,:…. rEF1LF8OGM8GZGG8ZOOOMMOO8MMMNMOONZEE08ZO8@; :rvrrii::::,,…. Zu551Jj5GM@OOG8ZMMOEOOMZ8OMMOZGOOPNOOGZOMBG
.i777ii::::,,…. MBXvJU51uJ2qBB@MMO8NO8MMBZMOMOMZMZ00MZGPMONXS
:r77;i::::,:…… .i7vr;i:::::.,….
BB8ZGuJu51SuJL20BB@OGOMM@BOOMOO0OOZP8O00OB8 :B7 M@8PZEMZXLLuF5kuYJSqOO@B@u2BM8O8NNO00E8NPM@Bu vB. q@GGZNEZMBMXuLu1XSFujj5X@U i@@M8MOMMMMMM@B@Zv87 BB
:r77rii::::,,…. . ,iv77ii::::,,…. .
.:777;i::::,,…. . ,r77rii:::,,.,….
.ir7rrii::::.,…. :rv7rii::::,,….
OBGqOEE08MOOMMOF2Ju2F1F5M0 OqPPZB@B@B@B@B@kuU10: @P @@OqOENqE8O0ZZMOMMONSujuqB. FBq5SP@i ,Zu2OFO@i U@OXEGZqZZ8NOE8MO0OB@BMZZBr iMF1XZ@L i8B@BBB@
B@NZqG0ZZGEMGGGOOMMMMOOMB@F7B@ZNSBv . ….. . JM55jj@OJ@ iMBZ8EOO00qMMOOOOMOMOOEM8OO@B@@@MOE ,.. … . 5Lvv78BrBi Ou0BMOMOGPGOMZ8GOZMM8ZMMMMBOGSFu1SMP .. … . uFYLL7v@kLi
vO5v5O@BBOMMMO8OBOMB@MBMOEk1uYu5XSXN@1 FM551SFSq@r v015juukXGOM8MOMEZEEUU77277ZS512uUUXq@r.,,,::::.i@@@MB8MNNBE 0252F25uuJujuJujuU5XirXkBv:S1u15GBSL1EBME2Xk8OO821MPNqXk0S8Bi 7BSJUU5FkFF2uUFFk5XFOv:Ykuvvq8MB@BBvuuYJurvk77v7777GNqEXkEqSBO
M@MGF2LvvYLYLuJujJLjUSFNNOB@B@OO8@XLvLvL7rXMu77vv27NGEqP5qGN0@L i@8OEOMBZEkXFPPqPEEOOOM@MMMMMOEEE@BuL2Uuv7rUu7v5kqkuuMG0PqFGZ0G@ MMZEGGMO@@@M8MBMMOBOMMMZZE8GO8GNMBGrLFXF1Lr7jivvLvJF70M0qqPSZEEMX
iB80MOMqZMMG8ZZGONZ8MOM8GEOOMZOZGM@57FY7vLJ72q7vuvvvLL2MOEGqkXP1XB7 M@0OOMO0OMGOZ8ZOOGN88OEZ088M0ZO8ZMMu7L7vvJJ72Xvrr77vruvPOGZqkXSqqMB.
:
.:7P@BEi:,:ivjj7i,ikP7:vMNFuu
;XM1vi:,:. FBP7i5@OGqU iXM@@BZ5LLM@BGi L@NBi O@B,:;i:,@B@5:
,i:::::::. XEOOMGMkXPESB@MFr :2@@OS: .:,::.J@XqU0ZSN@MGU:
.;0B@BMuruMM@u.,:::.rBSSqOBBBY. :YZBBE1770@BZv rMB@:.,,,.7@O@@Mj,
r: ,7v7. ..
UC BERKELEY Login: _______
:FU111P75r.L
8
CS61B MIDTERM, SPRING 2016
Login: _______
7. Leeway (6 Points). Consider the binary search tree below. Each symbol represents an object stored in the BST, e.g. might represent the string “josh”, and might represent the string “snowman”.
a) Based on the ordering given by the tree above, fill in the tree below with valid symbols. Symbols must be unique. You may only use the 7 printed symbols (do not include any symbols from part b).
b) For each of the insertion operations below, use the information given to “insert” the element into the
TOP TREE WITH PRINTED SYMBOLS, NOT THE TREE WITH YOUR HANDWRITTEN SYMBOLS by drawing the object (and any needed links) onto the tree. You can assume the objects are inserted in the order shown below. You should not change anything about the original tree; you should only add links and nodes for the new objects. If there is not enough information to determine where the object should be inserted into the tree, circle “not enough information”. If there is enough information, circle “drawn in the tree above” and draw in the tree AT THE TOP OF THE PAGE.
9
8. Balanced Trees (8 Points)
a) Suppose we have the max heap below, with array representation as shown. Show the heap after the maximum is deleted, using the procedure described in class. Give your answer as an array.
—8 6 5 2 3 5 1 1 0
Your answer:
—6 3 5 2 0 5 1 1
We delete the node containing 0, then replace 8 with 0. We then swap, sinking the 0 node down: First we swap 0 and 6, then 0 and 3. We then write our answer as an array by doing a level-order traversal (top-to-bottom, left-to-right).
b) Consider the 2-3 tree below. What order should we insert these numbers so that we get the tree shown? There may be multiple correct answers.
Answer:
One way to start is to recognize that the final numbers inserted could be 8 and 9. In this case, we must now figure out how to build a max-height 2-3 tree containing the numbers 1 through 7. This tree is relatively easy to obtain by guessing and checking. (Nearly half of all permutations of the numbers 1 through 7 would work.)
UC BERKELEY Login: _______
There are multiple answers, including the sequence [1, 2, 3, 4, 5, 6, 7, 8, 9].
10
CS61B MIDTERM, SPRING 2016
Login: _______
c) Tumelo Barttrain suggests creating a special version of a heap where each item has 4 children to improve performance. Would such a heap have better, worse, or the same asymptotic performance in Θ notation as compared to a normal binary heap? Briefly explain your reasoning.
Tumelo’s heap would have the same asymptotic performance as a normal binary heap. The height of a heap where each item has 4 children is log4(N) instead of log2(N). Using the change of base formula for logs, log4(N) = log2(N) / log2(4) = 0.5 * log2(N), so the height of the heap is still Θ(𝑙𝑜𝑔𝑁).
9. That Asymptotics Problem You Knew Was Coming (9 Points).
For each of the pieces of code below, give the runtime in Θ(·) notation as a function of N. Your answer
should be simple, with no unnecessary leading constants or unnecessary summations.
Θ(𝑁2)
public static void p1(int N) {
for (int i = 0; i < N; i += 1) {
for (int j = 1; j < N; j = j + 2) { System.out.println(“hi!”);
} }
}
The outer for loop makes N iterations. In each of these, the inner for loop makes N/2 iterations, so we have running time N*(N/2) = Θ(N2)
public static void p2(int N) {
for (int i = 0; i < N; i += 1) {
for (int j = 1; j < N; j = j * 2) { System.out.println(“hi!”);
} }
}
The outer for loop makes N iterations. In each of these, the inner for loop makes log2 N iterations, so we have running time N*( log2 N) = Θ(N log N)
public static void p3(int N) { if (N <= 1) return;
p3(N / 2);
p3(N / 2); }
Think of the recursive calls as nodes in a binary tree. This makes a perfectly balanced tree with height log2 N. The work done in each node is independent of N (constant), so the total runtime is proportional to the number of nodes in the tree. This gives us the sum 1+2+4+8+...+2logN =Θ(N).
Θ(𝑁 log 𝑁)
Θ(𝑁)
11
Θ(1) public static void p4(int N) {
int m = (int) ((15 + Math.round(3.2 / 2)) *
(Math.floor(10 / 5.5) / 2.5) * Math.pow(2, 5));
for (int i = 0; i < m; i++) {
System.out.println("hi");
}
}
None of the computation depends on N so p4 runs in constant time!
Θ(𝑁2) public static void p5(int N) {
for (int i = 1; i <= N * N; i *= 2) {
for (int j = 0; j < i; j++) {
System.out.println("moo");
} }
}
This time the inner for loop is different for differing values of i, so we cannot simply multiply the iterations of the two for loops. The inner for loop runs i iterations at each i, so to get the overall runtime we sum over the sequence of values of i. Since the outer for loop does i *= 2 each iteration, we sum over powers of 2, up until the value N2. This lookslike1+2+4+8+...+N2 =Θ(N2).
Note: This is a similar sum to p3. A sum of the powers of 2 is in big theta of the largest term, which was N in p3 but N2 in p5.
UC BERKELEY Login: _______
12
CS61B MIDTERM, SPRING 2016
Login: _______
10. Yum Yum Agar (10 Points). The Agar class is defined as follows: public class Agar {
public int size; /* assume this is always even and positive */ public Agar(int s) { size = s; }
public boolean equals(Object o) {
Agar other = (Agar) o;
return this.size == other.size;
}
public int hashCode() { /* Not shown, but assume it’s consistent with equals, always positive, and does not change unless size changes. */
} }
Usually, Agars are simple, inert creatures, and coexist peacefully with one another... but not always. You are going to store these Agars in a HashSet. Agars are inserted using a special insertAgar method: If you try to insert an Agar into a hash bucket, and there is already an Agar with exactly half its size in the same bucket, then the new Agar will eat the smaller Agar, absorb its size (new size will be the original size plus the eaten Agar’s size), and then attempt insertion (now bigger) into the HashSet again. It is possible for an Agar to eat multiple other Agars before finally being inserted into the HashSet. Agars do not eat Agars in other buckets. Next page has an example and clarifications.
Your ultimate goal for this problem is to write the code for insertAgar to successfully emulate these rules. Don’t worry about null input cases. Here is a description for each of your input arguments:
- x, the Agar that you are inserting. You have access to its public fields and methods.
- set, the HashSet that will contain all Agars so far (if they haven't been gobbled up). It should be noted all instance variables of HashSet are private.
- M, the number of buckets in the HashSet. You may assume M does not change during the method call.
a) Write a helper method that returns true if a given Agar x is going to eat a smaller Agar. Assume HashSet uses the same process for converting hashCodes to bucket numbers that we used in class. Note that the hashCode is always positive, so there’s no need for abs or & 0x7FFFFFFF1. For full credit, your solution should be as asymptotically fast as possible (we won’t say exactly how fast). static boolean shouldEatSomething(Agar x, HashSet
/* Make a dummy agar */
Agar mini = new Agar(x.size / 2);
/* Now determine corresponding bins */
int xBin = x.hashCode() % M; // floorMod works too
int miniBin = mini.hashCode() % M;
return (set.contains(mini) && miniBin == xBin);
}
An inserting Agar will eat if two conditions are satisfied. 1: There is an agar of half size, and 2: the inserting Agar inserts into the same bin as the half-sized Agar. We can create a duplicate mini Agar for hashCode() and contains() purposes. We can calculate the bin by applying the same HW3 trick.
1 Though we didn’t discuss in HW3: the reason we did & 0x7FFFFFFF was to handle negative hash codes.
13
UC BERKELEY Login: _______
b) Now finally write insertAgar. You may use shouldEatSomething even if you did not implement it successfully. The simplest solution will use shouldEatSomething, but it is possible to implement insertAgar without using it.
static void insertAgar(Agar x, HashSet
Agar mini = new Agar(x.size / 2);
set.remove(mini);
x.size += mini.size;
insertAgar(x, set, M);
} else {
set.add(x);
}
}
If an Agar is not supposed to eat, it should just add into the set. If an Agar is supposed to eat, then we can create a duplicate mini, remove it from the set (this works because of the consistent equals() definition of Agars), let our inserting agar grow, and finally attempt to reinsert again.
Many students attempted to iterate through all the Agars in the set in search of the half-size Agar. This did not receive full credit because it’s a slower solution. In addition, you cannot modify a set (by removing an element) during an iteration, so correct linear-time solutions involved removing and then immediately breaking/returning, or remembering the Agar to remove and removing it after the iteration. For a video walkthrough, see: https://youtu.be/_ZP2IdkebCs
Example:
Suppose we have a HashSet called set with 1000 buckets, and there is an Agar of size 20 in
bucket 0, an Agar of size 30 in bucket 1, and an Agar of size 180 in bucket 5.
Suppose we create Agar chris = new Agar(40), then call insertAgar(chris, set,
1000). If (and only if) chris tries to go into bucket 0, chris will eat the Agar of size 20 (destroying it), increase in size to 60, and then attempt insertion again, potentially with a different hash code. If (and only if) chris (now of size 60) happens to try to go into bucket 1 this time, chris will eat the Agar there of size 30, increase in size to 90, and then attempt insertion yet again. If chris tried to go into bucket 5, he’d get inserted into that bucket, joining the existing Agar of size 180. chris is not eaten, since the size 180 Agar was not just inserted.
Some clarifications and notes:
Assume that the size never exceeds the maximum integer value in Java: 2147483647.
Assume that the size of an existing Agar is never changed by any code other than yours.
Any call to insertAgar should increase the number of Agars by at most one, but could
actually decrease the number of Agars, if some Agars are eaten.
If we call insert(x, set, M) and x exists in the HashSet, we abort the operation, even if
shouldEatSomething(x, set, M) is true.
public HashSet methods include add, addAll, clear, contains, containsAll, equals,
getClass, hashCode, isEmpty, iterator, remove, removeAll, size, toArray, toString.
14