CS61B Midterm ReviewAgendaStatic vs. DynamicStatic vs. Dynamic cont.Slide 5Slide 6Box and Pointer diagramsSlide 8Slide 9Box and Pointer diagrams cont.Coding QuestionCoding Question SolutionBit RepresentationSlide 14Modular ArithmeticAnother Coding QuestionAnother Coding Question SolutionAnother Coding Question Solution cont.Algorithmic AnalysisSlide 20Slide 21Access rightsQuickiesCS61B Midterm ReviewWinston Liaw and Amir KamilMidterm Review 2Agenda1. Static vs. Dynamic2. Box and pointer diagrams3. Code Questions and examples4. Bit representation5. Algorithmic Analysis6. Access rights7. Quickie questionsMidterm Review 3Static vs. DynamicWhat happens? Assume we have defined:Homer h = new Homer();Bart b = new Bart();Homer h1 = b;h1.talk2();Answer: Homer, Bart: dudeMidterm Review 4Static vs. Dynamic cont.What happens? Assume the same definitionsBart b1 = b;b1.talk2();Cartoon c1 = h;((Homer)c1).talk4();Answer: Homer, Bart: dudeAnswer: Homer, Homer: doh!Midterm Review 5Static vs. Dynamic cont.What happens?Cartoon c2 = b;((Bart)c2).whoa();Lumpy l2 = b;((Homer)l2).talk4();Answer: dudeAnswer: Bart: dudeMidterm Review 6Static vs. Dynamic cont.For calls with an object of interest (i.e. h.f()), static methods are called based on static type, non-static methods are based on dynamic typeFor calls involving “this”, things get a little trickier. Static calls “stay” in the same class, dynamic calls are based on the dynamic set.Midterm Review 7Box and Pointer diagramsDraw the diagrams that result from this code:int [] x = new int[3];int [] y = new int[0];int [][] z = new int[3][2];Midterm Review 8Box and Pointer diagramsDraw the diagrams that result from this code:int [] x = new int[3];int [] y = new int[0];int [][] z = new int[3][2];0 0 00 00 00 0xyzMidterm Review 9Box and Pointer diagrams cont.Modify the box and pointer diagram according to this code:z[1] = z[2];Midterm Review 10Box and Pointer diagrams cont.Modify the box and pointer diagram according to this code:z[1] = z[2];0 00 00 0zMidterm Review 11Coding QuestionFinish this method:/* Given an IntList, it will reverse it destructively and return the new list */public IntList reverse(IntList l) {…}Midterm Review 12Coding Question Solutionpublic IntList reverse(IntList l) { IntList prev = null; IntList next = l.tail; while (l != null) { next = l.tail; l.tail = prev; prev = l; l = next;} return prev; //once we are done reversing all the pointers //we need to set l's head to the new head }Midterm Review 13Bit RepresentationWhat is the bit representation for:byte b = 15;What is this value as a char?10110111What about as a byte?Answer: 00001111Answer: 183Answer: -73Midterm Review 14Bit RepresentationTwo’s complementIf the Most Significant Bit (MSB) is 0, then treat the remaining bits as normal (as a positive number).If the MSB is 1, flip the remaining bits, add 1, and that is your negative value.Remember, two’s complement only applies to signed values. For an unsigned integer, for instance, treat it as “normal.”Midterm Review 15Modular ArithmeticFor modular arithmetic:Find out how many times your divisor can divide into your dividend. Remember, the remainder must be positiveIf the remainder is greater than the range of your values (byte can have values btw –128 and 127 for instance) then loop value aroundMidterm Review 16Another Coding QuestionFinish these methods: IntList pqueue; /* removes the node with smallest value */ public int remove() {… }/* inserts the value into pqueue */public void insert(int k) {…}Midterm Review 17Another Coding Question Solution public int remove() {int x = pqueue.head;pqueue = pqueue.tail;return x;}Midterm Review 18Another Coding Question Solution cont.public void insert(int k) {IntList temp = pqueue;IntList prev = null;while (temp != null) {if (k < temp.head) { if (prev != null) { prev.tail = new IntList(k, temp); } else { pqueue = new IntList(k, pqueue); } return; } else { prev = temp; temp = temp.tail;}}Midterm Review 19Algorithmic AnalysisDefinition of Big-OhO(g(n)) = {f(n) : there exist positive constants c and n0 such that 0 <= f(n) <= cg(n) for all n >= n0Definition of Big-Omega(g(n)) = {f(n) : there exist positive constants c and n0 such that 0 <= cg(n) <= f(n) for all n >= n0Midterm Review 20Algorithmic AnalysisOne method takes O(n2), while another takes O(n lg(n)). The O(n lg(n)) method is always preferred.True or false?Midterm Review 21Algorithmic AnalysisWhat are the running times (Big-Oh, Big-Omega, Big-Theta) for this code?for (int i = k; i < z; i++) { for (int j = 0; j < z; j++) {//some lg (n) code here}} Answer: all are (z-k)(z)lg(n)Midterm Review 22Access rightsIf you override a method in a child class, Java allows you to change the access rights to be less restrictive Ex. – Parent’s method is protectedChild’s method is publicRefer to page 113 in Programming into Java for more detailsMidterm Review 23QuickiesWhat class has no superclass?Why would you want to pick an array over a
View Full Document
Unlocking...