DOC PREVIEW
Princeton COS 126 - mini Exam 2

This preview shows page 1-2 out of 7 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 7 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Princeton COS 126 - mini Exam 2

Download mini Exam 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view mini Exam 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view mini Exam 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?