Study Guide for the Midterm Exam - ZOOMED EDITION Exam Wednesday 4/1. The exam will take place during the regularly scheduled zoom session for the class. When the exam begins an "assignment" will be made available on blackboard. During the test, you're asked to turn on your camera but TURN OFF your microphone unless you want to ask a question. You will also be able to chat with the host. You must submit your solutions before the end of the zoom session. The exam will consists of the following types of questions: 1. Writing small programs. For example, I may ask you to write a non-abstract subclass that extends an abstract class, or a class that implements some interface. I may also give you an incomplete fragment of code, or even a fragment of code that's full of errors and ask you to fix it. Even if you can't get the program to compile and run correctly, I will still grade your submission and assign partial credit. On the other hand, just because your program gives the expected output doesn't necessarily mean that it's fully correct. It still has to satisfy all specified requirements. Efficiency (is it n or log n) will always count. I've provided practice problems below. The key to preparing for this type of test is to practice programming. Also, you should avoid bad programming habits like misleading variable names, misaligned indentation, etc. 2. Analyzing code fragments, identifying errors. Because there's nothing to prevent you from compiling/running the code during the test, these questions will always ask you to provide an EXPLANATION. You will be graded based on your explanation, not on identifying the correct behavior of the program. Topics to be covered: 1. Technical aspects of the Java language, including when references (pointers) are used and not used. The technicalities of creating classes and instances of classes, arrays of objects, etc. The meaning and usage of "static," "this", "int" versus "Integer", "Object" superclass. 3. Data structures: Circular queue, Priority Heaps and Hash tables. You need to study both how they're implemented as well as their advantages and tradeoffs. For example, why is a binary heap better suited for implementing a priority queue compared to a sorted circular queue? (the answer is that, although dequeue in a sorted circular queue is constant time, inserting something in sorted order is linear - O(n), whereas with a heap both operations are log n). 4. Informal complexity analysis of the algorithms. E.g., what is the complexity of pushing something on top of a stack? What is the average and worst case complexity of inserting something into a hash map? 5*. Inheritance, abstract classes and interfaces. Know how to use inheritance, create subclass constructor, etc. Understand what interfaces and abstract classes are, know at least how to use and how to implement the Comparable interface, etc. Know how to use lambda expressions. Understand what is *DYNAMIC DISPATCH*, i.e., the difference between the static and runtime types of objects and how it affects programs. What to study: lecture notes, labs, sample programs, handouts, web links. Things that I have talked about repeatedly will have a greater chance of appearing on the exam. The following topics will NOT be covered on the exam: **Recursion.** We will go back to this topic after the exam. Graphics and any form of IO (except System.out.print) How to write a subclass constructor Java-specific restrictions regarding generic array creation. ---------------------- Sample Problems ----------------------- Programming Questions: 1. Given the following class: class student { public final String name; public final int ID; protected double gpa; protected String major; public student(String n, String m) { name =n; major=m; gpa = 0; // initial gpa of new students ID = 700000000 + (int)(Math.random()*1000000); // create random ID } // other boring stuff... }//student a. MODIFY the class so that class student implements Comparable You must add the necessary code to the class, as well as observe other requirements of the Comparable interface. b. Override the toString method to change the string representation of student objects. Parts a and b must be implemented in the same program. Submit program with a main that creates at least two students and calls all the *new* methods that you've added. 2. Given the CHMap abstract class for closed hash maps (find on class homepage), implement as a non-abstract subclass a hashmap from Doubles to Strings (key type is Double and value type is String). You *must* write an extension of CHMap that implements all of its abstract methods. You may not use java.util classes or any other class that I have written. You may not change CHMap. The following code should work when you're done: public static void main(String[] av) { DSmap M = new DSmap(); // create a new DSmap for math constants M.set(3.14,"pi"); M.set(2.718,"e"); M.set(0,"zero"); System.out.println( M.get(3.14) ); // prints pi System.out.println( M.get(1) ); // prints null } 3. A binary sequence of 0's and 1's has "odd parity" if it contains an odd number of 1's. The associated diagram at cs.hofstra.edu/~cscccl/csc17/oddpar.jpg defines a finite automaton that recognizes sequences with odd parity. Implement it as a sublcass of the abstract class FSM4 for generic finite state machines. To simplify the problem for you, part of the code is provided (but won't compile and run until you fill in the rest). public class oddparfsa extends FSM4 { String instring; // the input string of 0 and 1 characters int si=0; // instring index; public oddparfsa(String s) { instring = s; numstates = 2; maxinputs = 2; keeprunning = true; skipbadinput = false; // only recognize 0 and 1 setTable(); }//constructor protected Character nextInput() // gets next available input, null if none { if (si > instring.length()-1) return null; else return instring.charAt(si++); } protected int getindex(Character x) { return (char) ((int)x - 48); // 48 is ascii value of '0' } ////////////// // Put your additional code here: ////////////// public static void main(String[] av) { oddparfsa sample1 = new oddparfsa("000110110101"); // even parity oddparfsa sample2 = new oddparfsa("1011001010"); // odd parity System.out.println( sample1.run() ); // should print false System.out.println( sample2.run() ); // should print true }//main }//oddparfsa class ======================== Additional Practice Problems ============ (the numbers are not contiguous because some questions were removed) 1. In a closed hash map (using a "linear probing" rehash method), explain why removing a key-value pair requires the key to stay inside the table. That is, why the value becomes null but the key stays in the table at least until the table is resized. 2. What are the time-complexity classes (n, log n, etc) of each of the following operations. In cases where the average and worst-case differs, given the classifications for both. a. searching for a value in a heap b. inserting a new value into a heap c. heapsort: insert, then delete the highest number from a heap d. deleting something from the end (as opposed to front) of a circular queue e. deleting something from the end (as opposed to front) of a linked list (where each node has a pointer to the next node). f. searching for a value in a hash table g. insert/set a key-value pair in a hash table 3 What are the types Integer and Double? How are they different from int and double? 4. Determine the output of the following program and EXPLAIN WHY. This question will be graded based on the explanation. class A { public double f() { return 2.5; } public void h(B n) { System.out.println("B object"); } public void h(A n) { System.out.println("A object"); } } class B extends A { public double f() { return 4.5; } } public class aaa // main class { public static void main(String[] argv) { A a = new A(); A b = new B(); System.out.println(b.f()); a.h(b); }//main } 9. Determine the output of the following program, and EXPLAIN WHY class bigobject { public int x; public bigobject(int y) {x=y;} } public class quiz013 { public static void f(bigobject A) { A = new bigobject(8); } public static void main(String[] argv) { bigobject A = new bigobject(2); bigobject B = A; A.x = 4; System.out.println("B.x is "+B.x); // question 9a. f(A); System.out.println("A.x is "+A.x); // question 9b. }// main } 9c. show how to create an array of 1000 bigobjects (create 1000 actual instances of the class). 10. The following class sorts doubles class sorter { double[] A; // pointer to array to be sorted public sorter(double[] B) {A=B;}// contructor sets pointer to array. public boolean sorted() // checks if A is already sorted { boolean ax = true; for(int i=0;iA[i+1]) ax = false; return ax; } // bubblesort, quicksort, etc..., details not important for questions } Rewrite the class so that it can work for ANY array of sortable values, not just doubles. THEN, show how to use the class by creating at least two instances of it and call the sorted() function. 11. Explain what's wrong with the following code. (don't try to correct it, just point out what's wrong). public abstract class tooabstractforme { protected double[] A; protected abstract void f(); public tooabstractforme(double[] B) {A=B;}// constructor sets pointer public static int getlength() { return A.length; } public static void main(String[] av) { tooabstractforme n = new tooabstractforme(new double[100]); System.out.println(n.getlength()); }//main } 12. Consider the interface: interface predicate { boolean p(T x); } Write enough code to show how to create a class that implements this interface as well as an instance of that class. Show how to call the p method on this instance. USE LAMBDA EXPRESSIONS. 13. Somebody who doesn't understand object oriented programming wrote the following classes that define an array, a function f that returns an int, and another function that calls f on each element of the array and returns the sum of the values returned: class fstr { protected String[] A; // array of strings public fstr(String[] B) {A=B;} // constructor public int f(String x) { return x.length(); } public int sumf() { int sum = 0; for(String s:A) sum = sum + f(s); return sum; } }//fstr class fdoub { protected Double[] A; // array of Doubles public fdoub(Double[] B) {A=B;} // constructor public int f(Double x) { return (int)(x+0.5); } public int sumf() { int sum = 0; for(Double x:A) sum = sum + f(x); return sum; } }//fdoub You should notice that the two classes have much in common. Your task is to rewrite the SAME program using an abstract class and then two non abstract classes that extend the abstract class. The abstract class must contain as much code as possible. i.e., there should not be any repetitive code that's not necessary.