A Boolean formula is a Boolean circuit wherein every gate has only one output wire. The same input variable may appear in multiple places of a Boolean formula. Prove that a language has a polynomial size family of formulas if it is in NC1. Ignore uniformity considerations. See attached file for full problem description.
Show the error in the following fallacious "proof" that P  NP. Proof by contradiction. Assume that P = NP. Then SAT  P. So, of some k, SAT  TIME(nk). Because every language in NP is polynomial time reducible to SAT, NP  TIME(nk). Therefore P  TIME(nk). But, by the time hierarchy the
Show that any PSPACE- hard language is also NP- hard.
Decimal Octal Hex Binary Value ------- ----- --- ------ ----- 000 000 000 00000000 NUL (Null char.) 001 001 001 00000001 SOH (Start of Header) 002 002 002 00000010 STX (Start of Text) 003 003 003
What character coding method is used in IBM 360 compatible mainframe computers?
What coding format encodes a real number as a mantissa multiplied by a power (exponent) of two?
A useless state in a pushdown automaton is never entered on any input string. Consider the problem of testing whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.
Show that the collection of decidable languages is closed under the operations of a. union. b. concatenation. c. star. d. complementation. e. intersection
Consider the language B = L (G), where G is the grammar given in Exercise 2.13 (page 121). The pumping lemma for context-free languages, Theorem 2.19 (page 115), states the existence of a pumping length p for B. What is the minimum value of p that works in the pumping lemma? Justify your answer.
Say that string x is a prefix of string y if a string z exists where xz = y and that x is a proper prefix of y if in addition x  y. In each of the following parts we define an operation on a language A. Show that the class of regular languages is closed under that operation. a. NOPREFIX (A) = {w  A| no prope
Normalize to the 3NF the following collections of data attributes, Write the normalized entities in the correct format and underline the attributes which form the primary key(s). Make whatever assumptions that you need to, but document your assumptions. 1) Video Tapes (Title, Director, Actors, Date, Music Tracks, Duration, Th
I am trying to write code that would sum 5 cells and then round to either .00, .25, .50, or .75 depending upon what range the sum of the cells falls into. Example if the sum of the cells equals 1.17 then I would need to round to 1.25. If the sum of the cell equals 15.38 I would need it to round to 15.50. So if the range of the d
Read this article from the Sun website: http://paul.rutgers.edu/java_tutorial/java/javaOO/subclass.html Concerning classes and inheritance. Why is the super keyword so important? Present examples of how inheritance can be found in real-life situations
Give the state transitions for a pda with only 2 states, for the language "a^n b^2n", where n >=1 .
You are now going to create the final table list for Fernando's Skate Shop. Use the following preliminary field list and list of subjects to get started. Realize that the lists are incomplete and you may need to add more information as necessary by inferring data from what you know about the case. Be sure to provide a rationale
(a) Encode the following bit sequence using run-length encoding with 4-bit codes eighteen zeroes, 11, fifty-six zeroes, 1, fifteen zeroes, 11. (b) Encode the same sequence using run-length encoding with 5-bit codes (c) Compare the two codes. Comment on two choices.
[a] Discuss and suggest a good set of test data for a program that gives an employee a $50.00 bonus cheque if the employee has produced more than 1,000 items in a week. [b] Assume that a library keeps a file with data about its collection, one record for each item the library loans out. Name at least eight(8) fields that mig
What is RSS? Describe a real-world application that uses RSS.
Mr. Oldie wants to share his wisdom too, but on a different topic: "These OO-guys looked at hardware assembly and car assembly mechanisms and dreamed that they can do it in software. They aimed for the moon using OO paradigm, but they ended up in clouds! OOD/OOP does not really make such "stand-alone" components that fit togethe
In computer programming would you say that a function could also be called an inheritance product due to the reuse of it in the program? A while loop that calls the function once the statement is true can be used over and over. What do you think?
Inheritance is a technique in object-oriented programming in which you derive new classes from existing classes in your code. Why might this be useful? Does this technique correspond to any other concepts we have discussed?
Why would a programmer intentionally code the following line into a program? #define true 1 while(true) { // Stuff inside loop. }
Why would a programmer intentionally code the following line into a program? (Code needed to make this a complete program intentionally left out.) #define true 1 while(true) { // Stuff inside loop. }
Examine this code snippet and explain why it will work or why not it will not. (Code needed to make this a complete program intentionally left out.) char a; for(a = 'a';a < 'm';a++) printf("%cn");
As you are writing a program, you will begin to conduct testing on your code as it becomes completed and operational. This is generally called unit testing. Describe how you feel unit testing should be conducted for a program with lots of conditional expressions.
You have functions that you wish to call for various individual year values, as well as ranges of years, and you are deciding on whether to use an if statement or a switch statement. The ranges and functions are: o 1900 to 1969 - functionA() o 1969 to 2000 - functionB() o 2001 - functionC() o
Find the write-write, read-write, and write-read dependencies in the following assembly language program: I1: LOAD R1, A // R1 -MEMORY (A) I2: ADD R2, R1 //R2 -R2 + R1 I3: ADD R3, R4 //R3 -R3 + R4 I4: MULTI R4, R5 //R4- R4 * R5
? Build use case diagrams and write use case descriptions ? Build class diagrams for static system modeling ? Build collaboration and sequence diagrams for dynamic system modeling Aims This assignment aims to establish a basic familiarity with the object-oriented system design and the use of UML for system modelling Ob
In the following lines of code, the result that is printed is the letter "B". Why does this occur? int a = 65; a = a + 1; printf("The value is: %c",a);
Please see attached file for detail (1) Describe the language generated by the following grammars: 1. <expression> ïƒ <expression> <woperator> <term> | <term> 2. <term>ïƒ <id> <soperator> <term> | <id> 3. <id> ïƒ a | b| c 4. <woperation> ïƒ * 5. <soperator> ïƒ + | - (2) 1. <S> ïƒ a<A> b | b <B>