COS 126 Mini-Practice Test 2 11. Combinational LogicConsider a 3-bit binary number X represented in 2’s complement format.(a) Write out the truth table for the following Boolean function of X: the absolute value ofX is greater than 2(b) Write out the sum-of-products form of this Boolean function.(c) Does the logic array circuit below correspond to your sum-of-products Boolean expres-sion? If not, give two examples of inputs to this circuit that do not give the desiredoutput.2 PRINCETON UNIVERSITY2. Regular Expressions, Deterministic Finite State AutomataWe have the three letter alphabet { a, b, c } and the language of all strings that start andend with a.Here are some examples of strings, and whether they are in the language:Yes No_______ _______________a empty stringabca abcabacaa bacaa) Which one of these Regular Expressions generates all strings that start and end with a?Circle the roman numeral that goes with your answer.i) a* ( a | b | c )* aii) a ( a | b | c )* aiii) a ( ( b | c )* a )*iv) a* ( ( b | c )* a )*v) a ( b | c )* aCOS 126 Mini-Practice Test 2 32. RE, DFA continuedb) Which one of the following DFA accepts all strings that start and end with a? Circlethe roman numeral that goes with your answer.i)ii)iii)4 PRINCETON UNIVERSITY3. Linked Lists Assume you have access to the private Node class:private class Node {double value;Node next;}Consider the following method which operates on linked lists:public boolean linky_dink (Node head) {Node a,b;a = head;if (a == null) return true;b = a.next;while ( b != null && b != a ) {b = b.next;if (b == null) return true;b = b.next;a = a.next;}return (b == null);}(a) What does linky dink return on the following lists? Circle your answer.i)returns true returns false does not returnii)returns true returns false does not returnCOS 126 Mini-Practice Test 2 53. Linked Lists continuediii)returns true returns false does not returniv)returns true returns false does not return(b) What does linky dink do?(c) If your linked list has N nodes, what is the order of growth of the running time oflinky dink? Circle your answer.N N log N N22N6 PRINCETON UNIVERSITY4. Turing Machinea) The Turing Machine above starts in the leftmost state. If this Turing Machine is run onthe tape below, with the tape head starting at the position marked by the arrow, whatwill be the contents of the tape when it halts, AND where will the head be?Write your answer in the empty tape below.b) What computation does this Turing Machine perform?5. Data Structures (3 points) Circle your answer.Circle the data structure that is most appropriate choice for the described problem.(a) Store and retrieve student records, which have unique usernames.Array Linked List Queue Symbol Table(b) Store all student grades and retrieve all grades higher than 90.Linked List Binary Search Tree Symbol Table Stack(c) Implement the Back button in a browserQueue Binary Search Tree Stack Circular Linked List6. True or False (6 points) Circle your answer.T F (a) P is the set of search problems solvable in Polynomial time by a deterministic TuringMachine.T F (b) NP is the set of search problems not solvable in Polynomial time by a deterministicTuring Machine.T F (c) For proper encapsulation, instance variables should always be declared public.T F (d) Because the Halting Problem is unsolvable, it is impossible to tell if your TSP programfor Assignment 6 has an infinite loop.T F (e) A Universal Turing Machine can compute anything that any other Turing Machine couldpossibly compute.T F (g) If P equals NP, then the Traveling Salesperson Problem can be solved in polynomialtime by a deterministic Turing Machine.T F (h) If P does not equal NP, then there is no case of the Traveling Salesperson Problem forwhich you can find the optimal tour in polynomial time.T F (j) Factoring is known to be in NP but has not been proven to be NP-complete, so thediscovery of a polynomial-time algorithm for factoring would mean that P equals NP.T F (k) Factoring is known to be in NP but has not been proven to be NP-complete, so nopolynomial-time algorithm for factoring is
View Full Document