CS 61b: Final ReviewDISCLAIMERReview TopicsInheritance/Method CallsInheritanceSlide 6Slide 7Asymptotic AnalysisSlide 9Slide 10Slide 11Slide 12Asymptotic Analysis ProblemAsymptotic Analysis SolutionTrees: Binary TreeTrees: BST ProblemSlide 17Trees: BST SolutionTrees: B-Tree of Order 4 / 2-3-4 TreeTrees: 2-3-4 Tree SolutionSlide 21Slide 22Slide 23Slide 24Slide 25Slide 26Priority Queues – ProblemPriority Queues – InsertionPriority Queues – SolutionSlide 30Slide 31Slide 32Slide 33Slide 34Slide 35Priority Queues – RemovalSlide 37Slide 38Slide 39Hash Table ProblemHash TablesHash Table SolutionSearches (BFS and DFS)Searches (BFS and DFS) ProblemSearches (BFS and DFS) SolutionExample graphTopological SortSlide 48Dijkstra’s Algorithm ProblemDijkstra’s AlgorithmDijkstra’s Algorithm SolutionSlide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Kruskal’s Algorithm ProblemKruskal’s AlgorithmKruskal’s Algorithm SolutionSlide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Disjoint Sets – ProblemDisjoint Sets – SolutionDisjoint Sets – Solution, cont.SortingSlide 73Slide 74Slide 75Slide 76Slide 77Slide 78Skip List ProblemSkip ListsSkip List ExampleSkip List SearchingSkip List SolutionSlide 84Slide 85Slide 86Slide 87Slide 88ThreadingCreditsPowerPoint PresentationCS 61b: Final ReviewData StructuresData StructuresSteve Sinha and Winston LiawSteve Sinha and Winston LiawFinal Review2DISCLAIMERWe have NOTNOT seen the exam.We do NOTNOT know the format of the examWhat we are presenting is what we“think is important” for the examSteve Sinha and Winston LiawFinal Review3Review TopicsInheritance, Method CallsAsymptotic AnalysisData StructuresBinary Search TreesB-TreesHeapsHash TablesGraphsDFS, BFSTopological SortDijkstraKruskalSortingSkip ListsThreading, SynchronizationSteve Sinha and Winston LiawFinal Review4Inheritance/Method CallsGiven the class definitions on the next slide, which lines in class foobarbaz are illegal?Steve Sinha and Winston LiawFinal Review5Inheritancepackage foo;public class foo { static void f1() {…} protected boolean f2(int x) {…} private String f3(String s) {…}}package bar;import foo.foo;public class bar extends foo { protected boolean f3(int x) {…}}package foo;public class baz extends foo { private String f3(String s) {…}}package foo;import bar.bar;public class foobarbaz { static void main(String[] args) { foo f = new foo(); bar r = new bar(); baz z; r.f3(3); f.f2(3); z = (baz) f; f = new baz(); f.f2(3); z = (baz) f; z.f1(); r.f1(); ((foo) r).f1(); }}Steve Sinha and Winston LiawFinal Review6Inheritance/Method CallsAccess table: Static methods called according to static typeChild type can be assigned to parent variable without a cast, but the reverse requires one, and the dynamic types must matchworld package child definerpublicX X X XprivateXprotectedX X X<default>X XSteve Sinha and Winston LiawFinal Review7Inheritancepackage foo;public class foo { static void f1() {…} protected boolean f2(int x) {…} private String f3(String s) {…}}package bar;import foo.foo;public class bar extends foo { protected boolean f3(int x) {…}}package foo;public class baz extends foo { private String f3(String s) {…}}package foo;import bar.bar;public class foobarbaz { static void main(String[] args) { foo f = new foo(); bar r = new bar(); baz z; r.f3(3); // ILLEGAL f.f2(3); z = (baz) f; // ILLEGAL f = new baz(); f.f2(3); z = (baz) f; z.f1(); r.f1(); // ILLEGAL ((foo) r).f1(); }}Steve Sinha and Winston LiawFinal Review8Asymptotic AnalysisO – Upper bound/Worst caseΩ – Lower boundθ – botho – strictly Upper boundMore detail…Steve Sinha and Winston LiawFinal Review9Asymptotic AnalysisT(n) is O( f(n) ) if and only if there exists positive constants C and N such thatT(n) <= C f(n) for all n >= NnT(n)5 f(n)f(n)T(n) = 4nf(n) = n4n is O( n )Steve Sinha and Winston LiawFinal Review10Asymptotic AnalysisT(n) is O( f(n) ) if and only if there exists positive constants C and N such thatT(n) <= C f(n) for all n >= NNnT(n)C f(n)Steve Sinha and Winston LiawFinal Review11Asymptotic AnalysisT(n) is O( f(n) ) if and only if there exists positive constants C and N such thatT(n) <= C f(n) for all n >= NT(n) is Ω( f(n) ) if and only if there exists positive constants C and N such thatT(n) >= C f(n) for all n >= NSteve Sinha and Winston LiawFinal Review12Asymptotic AnalysisT(n) is θ( f(n) ) if and only ifT(n) is O( f(n) ) andT(n) is Ω( f(n) )Examples5n2+1 is θ(n2)3n is O(n2), but 3n is NOT θ(n2)because 3n is not Ω(n2)Steve Sinha and Winston LiawFinal Review13Asymptotic Analysis ProblemFind the running time of the following code:int foo(int x) { int ans = 1; for (int i = 0; i < x; i++) { for (int j = 0; j < i; j++) { ans *= (i + j); } } return ans;}Steve Sinha and Winston LiawFinal Review14Asymptotic Analysis SolutionThe nested loops give away the answer: the outer loop executes x times, the inner loop an average of x/2 times, for a running time of O(x2).int foo(int x) { int ans = 1; for (int i = 0; i < x; i++) { for (int j = 0; j < i; j++) { ans *= (i + j); } } return ans;}Steve Sinha and Winston LiawFinal Review15Trees: Binary TreeTree:ABCDEFGPreorder : ABCEGFDInorder : CEBAGDFPostorder: ECBDFGAWhat are the Pre-, In-, and Post- order traversals of this tree?Steve Sinha and Winston LiawFinal Review16Trees: BST ProblemRemove 8 from:87531113169Steve Sinha and Winston LiawFinal Review17Trees: BST ProblemRemove 8 from:875311131Replace with successor (left-most node in Replace with successor (left-most node in right subtree)right subtree)69Steve Sinha and Winston LiawFinal Review18Trees: BST SolutionFinal tree:9753111316Steve Sinha and Winston LiawFinal Review19Trees: B-Tree of Order 4 / 2-3-4 TreeSuggest a sequence of operations that would create the 2-3-4 tree.You can use removal as well as insertion. 5, 72, 4 6 8Steve Sinha and Winston LiawFinal Review20Trees: 2-3-4 Tree SolutionInsert: 4, 5, 6, 7, 8, 9, 2 Remove: 9 4, 5, 6Steve Sinha and Winston LiawFinal Review21Trees: 2-3-4 Tree SolutionInsert: 4, 5, 6, 7, 8, 9, 2 Remove: 9 4, 5, 6Touch node size = 3Touch node size =
View Full Document
Unlocking...