Computer Science

Question 1

What are the types of knowledge?

Answer 1

(1) Declarative, (2) Imperative

Question 2

Algorithm

Answer 2

Finite list of instructions that describe a computation that when executed on a provided set of inputs will proceed through a set of well-defined states and eventually produce an output

Question 3

Fixed program computer

Answer 3

Solves a specific problem

Question 4

Store program computer

Answer 4

Stores/manipulates a sequence of instructions

Question 5

Church-turing thesis

Answer 5

If a function is computable, then a Turing Machine can be programmed to compute it.

Question 6

Turing completeness

Answer 6

A programming language is said to be Turing complete if it can be used to simulate a universal Turing machine (All modern programming languages)

Question 7

What are the components of each programming language?

Answer 7

(1) Primitive constructs—“words”, literals, infix operators
(2) Syntax—defines which strings of characters are well-formed ( )
(4) Static Semantics–defines which syntactically valid strings have meaning (3.2/’abc’)
(6) Semantics–what does it mean?

Question 8

Constant-time programs

Answer 8

A program for which the maximum running time is said to run in constant time. There exists a constant k such that the program is guaranteed to take no more than k steps to run. Running time does not grow with the size of the input. Limited.

Question 9

Decrementing function

Answer 9

A function (typically for describing a loop) that:

(1) maps a set of program variables into an integer (ans**2-|x|)
(2) When the loop is entered, its value is nonnegative
(3) Loop terminates when value is <= 0
(4) Value decreased every time through the loop

Question 10

What is the decrementing function for the following loop?

x = 8
ans = 0
while(ans**3<abs(x)):
    print ans
    ans = ans + 1

Answer 10

ans3 < abs(x)
0 < abs(x)-ans3

The decrementing function is abs(x) - ans**3

Question 11

Exhaustive enumeration

Answer 11

“Guess and check”. Enumerate all possibilities until we get to the right answer/exhaust all possibilities.

Question 12

Bisection search

Answer 12

Searches for answer based on approximations. Takes advantage of the fact that numbers are ordered.

Question 13

Newton’s method for roots

Answer 13

For a polynomial p(x) = x**2 + x + c, the root r is when p(r) = 0.

If a guess is an approximation of this root, then:

guess - p(guess)/p’(guess) is a better approximation of the root.

Question 14

What number is represented in the binary number 101?

Answer 14

1(22) + 0(21) + 1(2**0) = 4 + 1 = 5