## Get All Weeks Computer Science: Algorithms, Theory, and Machines Quiz Answers

## Table of Contents

### Computer Science: Algorithms, Theory, and Machines Week 01 Quiz Answers

#### Sorting and Searching

Q1. Which of the following results from using a blacklist filter (check all that apply)?

**Denies service to known untrustworthy clients**- Denies service to unknown clients
- Allows service to trusted clients
- Allows service to unknown clients

Answer:

Denies service to known untrustworthy clients

Q2. Suppose that an array of strings contains [“blueberry”, “chocolate”, “coconut”, “coffee”, “mint”, “strawberry”, “vanilla”]. How many comparisons are used for an unsuccessful search for “pistachio” with a binary search?

- 2
**3**- 4
- 5
- 6

Answer: **3**

Q3. Which of the following running times for a program sorting N 10-character strings is consistent with the hypothesis that the program is using *insertion sort*? Mark all that apply.

**1 second for N = 10,000, 4 seconds for N = 20,000, 256 seconds for N = 160,000**- 1 second for N = 1,000,000, 4 seconds for N = 2,000,000, 8 seconds for N = 4,000,000
**1 second for N = 10,000, 4 seconds for N = 20,000, 64 seconds for N = 80,000**- 1 second for N = 1,000,000, 4 seconds for N = 2,000,000, 16 seconds for N = 4,000,000
- 1 second for N = 10,000, 2 seconds for N = 20,000, 16 seconds for N = 160,000

**1 second for N = 10,000, 4 seconds for N = 20,000, 256 seconds for N = 160,000****1 second for N = 10,000, 4 seconds for N = 20,000, 64 seconds for N = 80,000**

Q4. Which of the following best describes the order of growth of the worst-case running time of sequential search?

- logarithmic
**linear**- linearithmic
- quadratic

Answer: **linear**

### Computer Science: Algorithms, Theory, and Machines Week 02 Quiz Answers

**Stacks and Queues**

Q1. Suppose that you start with an empty stack and interpret a letter to mean *push* and – to mean *pop*. Mark the sequences below that leave e at the *bottom* of the stack.

- a – b c – – d – e f g – h
- a – b c – d – e – f g – h
**a – b – c – d – e f g – h**- a b c d – – – – e f g – h
- a – b c – – d – e f g h –

Answer: **a – b – c – d – e f g – h**

Q2. Which of the following is the primary reason to use generics when implementing stacks and queues?

- More space-efficient than using primitive types
- Makes it possible to have stacks and queues holding objects of mixed types
**Eliminates need to have multiple implementations for different types**- More time-efficient than using primitive types
- Makes it possible to meet the performance specifications

Answer: **Eliminates need to have multiple implementations for different types**

Q3. When does a data type not implement the Stack API? Mark all that apply.

**When the operation of removing an arbitrary item is supported****When the space required cannot be bounded by a constant times the number of items in the stack at all time**- When the only operations that modify the stack are to insert an item and to remove the most recently inserted item
- When the order of growth of the time required to insert an item is logarithmic
**When the maximum size of the stack needs to be specified ahead of time****When the only operations that modify the stack are to insert an item and to remove the least recently inserted item**

**When the operation of removing an arbitrary item is supported****When the space required cannot be bounded by a constant times the number of items in the stack at all time****When the maximum size of the stack needs to be specified ahead of time****When the only operations that modify the stack are to insert an item and to remove the least recently inserted item**

Q4. For which of the following expressions is the maximum stack size the largest when evaluated with the Postfix client given in the lecture?

- 1 1 1 1 + * 1 1 + 1 *
- 1 1 + 1 1 + * 1 1 * +
**1 1 1 1 1 1 + + * + ***- 1 1 + 1 1 + * 1 + 1 +
- 1 1 1 + 1 + * 1 + 1 *

Answer: **1 1 1 1 1 1 + + * + ***

### Computer Science: Algorithms, Theory, and Machines Week 03 Quiz Answers

**Symbol Tables**

Q1. Which of the following are reasons to have ordered keys in a symbol-table API?

**They make it simpler to support iteration****They arise naturally in many applications****Implementations can take advantage of ordering to gain efficiency****They allow for useful extensions to the API**- They make it possible to support multiple types of data

**They make it simpler to support iteration****They arise naturally in many applications****Implementations can take advantage of ordering to gain efficiency****They allow for useful extensions to the API**

Q2. Of the following, which is the most important reason not to use a linked list for a symbol-table implementation?

- Doesn’t support ordered keys
**Not scalable because the search is too slow**- Uses too much space
- None of the above
- Not scalable because insertion is too slow

Answer: **Not scalable because the search is too slow**

Q3. In the BST built from the keys “is this an easy question” which key is in the root of the left subtree of the root?

- question
**an**- is
- this
- easy

Answer: **an**

Q4. Of the following, which is most likely to be closest to the height of a red-black tree with 1 million nodes?

- 10
**100**- 1000
- 10000
- 100000

Answer: **100**

### Computer Science: Algorithms, Theory, and Machines Week 04 Quiz Answers

**Theory of Computing**

Q1. Which of the following strings matches the RE a*bb(ab|ba)* ?

**aaaaaabbababababbaab****abbababbabaabbaabbaabbabba**- bbbb
- bbabbabaabaaab
- aaabbaaa

**aaaaaabbababababbaab****abbababbabaabbaabbaabbabba**

Q2. Consider a two-state DFA with a binary alphabet having the following transitions: Stay in state 0 if the input is 0 and stay in state 1 if the input is 1, otherwise switch to the other state. If state 0 is the accept state, which of the following does this DFA accept?

- Bitstrings with at least one 0
- Bitstrings with an equal number of occurrences of 01 and 10
**Bitstrings that end in 0**- Bitstrings with more 0s than 1s
- Bitstrings with an equal number of occurrences of 0 and 1

Answer: **Bitstrings that end in 0**

Q3. Which of the following strings matches the generalized RE [$_A-Za-z][$_A-Za-z0-9]* ? Mark all that apply.

- 23abcxyz
- 123456
**$****$ABABab$****abcxyz23**

**$****$ABABab$****abcxyz23**

Q4. Which of the following statements are true? Mark all that apply.

**Every DFA can be simulated by some NFA****Every NFA can be simulated by some DFA**- All formal languages are regular
**Every formal language can be recognized by some NFA****NFAs and REs are equivalent**

**Every DFA can be simulated by some NFA****Every NFA can be simulated by some DFA****Every formal language can be recognized by some NFA****NFAs and REs are equivalent**

### Computer Science: Algorithms, Theory, and Machines Week 05 Quiz Answers

**Turing Machines**

Q1. Which of the following properties are common to both Turing machines are and DFAs? Mark all that apply.

- No limit on number of steps
**Simple model of computation****Finite number of states**- Can read from or write onto the tape
**State transitions are determined by the current state and input symbol****Input on tape is a finite string with symbols from a finite alphabet**

**Simple model of computation****Finite number of states****State transitions are determined by the current state and input symbol****Input on tape is a finite string with symbols from a finite alphabet**

Q2.Which of the following models of computation are universal? Mark all that apply.

**Java**- Conway’s Game of Life
- NFAs
**your mobile phone****Turing machines**- regular expressions

**Java****your mobile phone****Turing machines**

Q3. Which of the following best characterizes the following statement: “*There exists a mathematical function that can be computed in Java, but cannot be computed on a Turing machine.*“

**known to be false**- known to be true
- truth or falsity not known
- if true would prove the Church–Turing thesis
**if true would falsify the Church–Turing thesis**

**known to be false****if true would falsify the Church–Turing thesis**

Q4. Which of the following problems is undecidable?

**Do two given programs always print the same value?**- Is every variable in a given program initialized before it is used?
- Is every statement in a given program executed at least once?
**Does a given program contain a computer virus?****All of the above**

**Do two given programs always print the same value?****Does a given program contain a computer virus?****All of the above**

### Computer Science: Algorithms, Theory, and Machines Week 06 Quiz Answers

**Intractability**

Q1. Assume that checking a box below corresponds to setting the variable to 1 and leaving it unchecked corresponds to setting it to 0. Give settings that solve the integer programming problem for the equations v+w+x ≥ 1, w+x+y ≥ 2, x+y+z ≥ 3, v+x+z ≥ 2, and v+w+x+y+z ≤ 3.

**v****w****x****y****z**

Answer: **v,w,x,y,z**

Q2. Assume that P = NP. Mark all correct options for FACTOR.

**is computable****is in NP**- is NP-complete
- is intractable
**is in P**

**is computable****is in NP****is in P**

Q3. Let A and B be two decision problems. Suppose we know that A polynomial-time reduces to B. Which of the following can we infer? Mark all that apply.

- A and B cannot both be NP-complete
**If A is NP-complete then so is B****If B is NP-complete and A is in NP then A is NP-complete****If B is in P, then A is in P**- If A is in P, then B is in P
- If A is NP-complete and B is in NP then B is NP-complete
- If B is NP-complete then so is A

**If A is NP-complete then so is B****If B is NP-complete and A is in NP then A is NP-complete****If B is in P, then A is in P**

Q4. Which of the following can we infer from the fact that a problem is NP-complete, if we assume that P ≠ NP? Mark all that apply.

- No algorithm exists that solves arbitrary instances of the problem
**No algorithm exists that efficiently solves arbitrary instances of the problem**- There exists an algorithm that efficiently solves arbitrary instances of the problem, but no one has been able to find it
**The problem is not in P**- All algorithms that are guaranteed to solve the problem run in polynomial time for some family of inputs
- All algorithms that are guaranteed to solve the problem run in exponential time for all families of inputs

**No algorithm exists that efficiently solves arbitrary instances of the problem****The problem is not in P**

### Computer Science: Algorithms, Theory, and Machines Week 07 Quiz Answers

**A Computing Machine**

Q1. Which of the following is the 4-digit hexadecimal two’s complement representation of the decimal number –16?

- 0010
- 0011
**FFF0**- FFF1
- FF16

Answer: **FFF0**

Q2. Which of the following are components of a machine’s state (value at the beginning of each instruction cycle determines what happens next)? Mark all that apply.

**IR**- ALU
**PC****Memory****Registers**

**IR****PC****Memory****Registers**

Q3. Suppose that R[2] contains a small integer x. Which of the following describes the value in R[2] after the instruction 5222 is executed?

- 0
- x
*x* **2×2***x*- 2^x2
*x* - x2^x
*x*2*x*

Answer: **2×2 x**

Q4. Suppose that the following sequence of instructions is loaded into memory locations 10-16: 10: 7C0A 11: 7101 12: 7201 13: 1222 14: 2CC1 15: DC13 16: 0000 and you set the PC to 10 and press RUN. Give the decimal number represented by the contents of R[2] when the machine halts.

Answer**: final value in memory location C1 is 0, and the PC points to instruction 22.**

### Computer Science: Algorithms, Theory, and Machines Week 08 Quiz Answers

**von Neumann Machines**

Q1. Suppose that the following sequence of instructions is loaded into memory locations 10-14: 10: 8113 11: 2111 12: 9113 13: 8113 14: 0000 and you set the PC to 10 and press RUN. What is the contents of R[1] when the machine halts?

- FFFF
**8113**- 0000
- 9113
- 2111

Answer: **8113**

Q2. Which of the following are programs that process programs? Mark all that apply.

- ALU
**Java Virtual Machine****Assembler****Compiler****Interpreter**

**Java Virtual Machine****Assembler****Compiler****Interpreter**

Q3. Which of the following are (approximately) true of your cellphone, as compared to von Neumann’s EDVAC? Mark all that apply.

**thousands of times faster****thousands of times more memory**- millions of times smaller
**millions of times faster****thousands of times smaller****millions of times more memory**

**thousands of times faster****thousands of times more memory****millions of times faster****thousands of times smaller****millions of times more memory**

Q4. Which of the following is true about virtual machines? Mark all that apply.

**They allow software to be prepared for a new computer before it is built.**- They are faster and have more memory than real machines.
**They allow for backward capability.**- They are generally too expensive to be useful in modern computing.
- They cannot be implemented on von Neumann machines.

**They allow software to be prepared for a new computer before it is built.****They allow for backward capability.**

### Computer Science: Algorithms, Theory, and Machines Week 09 Quiz Answers

**Combinational Circuits**

Q1. How many different Boolean functions of 4 variables are there?

- 4
- 16
- 64
- 1024
**65536**

Answer: **65536**

Q2. Suppose that one input of a NAND gate is set to x and the other is set to 1. Which function of x does it compute?

- 0
- 1
- x
**x’**- x+1

Answer: **x’**

Q3. By checking a box for 1 and leaving it unchecked for 0, give the truth table column that defines the EVEN PARITY Boolean function of 3 variables.

- 0 0 0
- 0 0 1
- 0 1 0
- 0 1 1
- 1 0 0
- 1 0 1
- 1 1 0
- 1 1 1

Answer: **1 0 0 1 0 1 1 0**

Q4. Which of the following circuits have 4 outputs? Mark all that apply.

- 2-bit majority
**4-bit decoder****2-bit decoder****4-bit adder****4-bit ALU**

**4-bit decoder****2-bit decoder****4-bit adder****4-bit ALU**

### Computer Science: Algorithms, Theory, and Machines Week 10 Quiz Answers

**CPU**

Q1. Which of the following modules are found in a memory? Mark all that apply.

**odd parity****majority****flip–flop****multiplexer****decoder**

**odd parity****majority****flip–flop****multiplexer****decoder**

Q2. Which of the following are *not* combinational circuits? Mark all that apply.

**CLOCK**- ALU
**CONTROL****MEMORY**- INCREMENTER

**CLOCK****CONTROL****MEMORY**

Q3. Which of the following decodes instructions?

- ALU
- CLOCK
**CONTROL**- MEMORY
- PC

Answer: **CONTROL**

Q4. How many flip–flops are in the TOY-8 CPU?

Answer: **128**

##### Get All Course Quiz Answers of Software Development Lifecycle Specialization

Software Development Processes and Methodologies Quiz Answers

Agile Software Development Coursera Quiz Answers

Lean Software Development Coursera Quiz Answers

Engineering Practices for Building Quality Software Quiz Answers