MIT 600

Question 1

Algorithm

Answer 1

Sequence of steps

Flow of control process that specifies when each step is executed

A means of determining when to stop

Question 2

Turning Complete

Answer 2

Anything computable in one language is computable in any other programming language.

Question 3

Syntax

Answer 3

Determines if code is legal.

Question 4

Static Semantics

Answer 4

Determines whether code has meaning.

Question 5

Semantics

Answer 5

Assigns meaning to a legal sentence.

Question 6

Python Types

Answer 6

Int-integer
Float-real numbers
Bool-boolean, True + False
NoneType - special, value of None.

Question 7

Casting

Answer 7

Type conversion, i.e.
Changing from Int type to Float.

Float(5)–5.0

Question 8

Branch Programs

Answer 8

Simplest is a condition. A test, a block of code to execute if true, and optional block to execute if false.

Is a linear program, runs in constant time.

Question 9

String

Answer 9

Letters, special characters, spaces, digits encompass in single or double quotes.

Question 10

Concatenation

Answer 10

Adding string together, i.e.

AB+CD=ABCD

Question 11

While Loops

Answer 11

If condition if true, run code, check condition, repeat until false

Question 12

Bisection Search -Sqrt Example

Answer 12

Know square root of x is between 1 and x. Rather than starting at 1, start at a number in the middle.
If not close enough, if g**2>x, g is too big.

Throws away half if possible guesses each iteration

Question 13

Bisection Search Big Oh

Answer 13

Logarithmic time, log2N steps

Question 14

Implications of Binary

Answer 14

If there’s is not an integer p such that x*(2**p) is whole, then the internal representation is an approximation.

Question 15

Newton-Raphson

Answer 15

Approximation to root, g is the approximation;

g-p(g)/p1(g) is a better approximation where p1 is the derivative.

Question 16

Abstraction

Answer 16

Suppress details of method to compute something from the use of that computation

Question 17

Decomposition

Answer 17

Break problem into different, self-contained pieces

Question 18

Function

Answer 18

Reusable piece or chunk of code, not run in a program until called or invoked.

Question 19

Recursion

Answer 19

Divide and conquer or decrease and conquer. Technique where a function calls itself.

Flow passes back to previous scope once the function call returns the value.

Question 20

Module

Answer 20

A .py file containing of collection of python definitions and statements. Call using the import keyword.

Question 21

Tuples

Answer 21

Ordered sequence of elements
Immutable, cannot change element values
Represented with parentheses
Iteratable and can be sliced

Question 22

List

Answer 22

Order sequence of elements
Denotes by square brackets
Mutable
Iterable, can be indexed

Question 23

List Operations

Answer 23

L.append()
L.extend()
del(L[index])
L.pop() remove and return the element
L.remove(element) removes first occurrence

Question 24

Memoization

Answer 24

optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

Question 25

Defensive Programming

Answer 25

Write specifications for functions Modularity Programs Check conditions on inputs/outputs

Question 26

Unit Testing

Answer 26

Validate each piece of program. Testing each function separately.

Question 27

Regression Testing

Answer 27

Add test for bugs as you find them. Can reintroduce errors that were previously fixed

Question 28

Integration Testing

Answer 28

Does the overall problem work?

Question 29

Black Box Testing

Answer 29

Explore paths through specification; through docstring

Question 30

Glass Box Testing

Answer 30

Explore paths through code. Path complete if every potential path through code is tested.

Question 31

Overt Bugs

Answer 31

Bug with obvious manifestation

Question 32

Covert Bugs

Answer 32

Not obvious; codes returns a value, but it is incorrect.

Question 33

Raising Exceptions

Answer 33

Try: Code Except Code such as raise Exception("desc")

Question 34

Object

Answer 34

Every object has; A type An internal representation of data Set of procedures for interaction

Question 35

Defining a Python Type

Answer 35

class ClassName(object):

Question 36

Attributes

Answer 36

Data and procedures belonging to the class.

Question 37

Big Oh Notation

Answer 37

Measures an upper bound in the asymptotic growth often called order of growth.

Question 38

Complexity Classes Order

Answer 38

O(1), O(log n), O(n), O(nlog n), O(n^c), O(c^n)

Question 39

Searching

Answer 39

Search method for finding an item or group of items with specific properties within a collection of items

Question 40

Linear Search

Answer 40

Brute force, list does not need to be sorted

Question 41

Bisection Search

Answer 41

List must be sorted. Looks for item at the center, if it doesn't find it, checks if the center is too low or too high and searches the corresponding half.

Question 42

Monkey Sort or Bogo Sort

Answer 42

Stupid sort, essentially sorting a deck of cards by throwing it in the air, picking it up and hoping it's sorted. Repeat if not.

Question 43

Bubble Sort

Answer 43

Compare consecutive pair of elements, swap elements so that smaller is first, when reaches the end of list, start again. Stop when no more swaps have been made.

Question 44

Selection Sort

Answer 44

Extract minimum element, swap with element at index 0. Extract minimum element from remaining sub list and swap with element at index 1. Keep left portion sorted.

Question 45

Merge Sort

Answer 45

Divide and conquer approach. If list is of length 0 or 1, already sorted. Split list in two two lists and sort/keep splitting each list. Merge sorted lists; Look at first element of each, move smaller to end of result list. When one list is empty just copy the rest of the other list to the end of result. BEST MOST EFFICIENT SORT

Question 46

Optimization Models

Answer 46

An objective that is to be maximized or minimized using a set of constraints (possibly empty) that must be honored.

Question 47

Knapsack Problem Formalized

Answer 47

Find a V that maximizes; The sum from i to n-1 of V[i] *I[i].value Subject to constraints that; The sum from i to n-1 of V[i] *I[i].weight < w

Question 48

Greedy Algorithm

Answer 48

Practical alternative. While knapsack not full, put "best" available item in knapsack. Finds local optimizations.

Question 49

Search Tree

Answer 49

Built top down starting with root.

Question 50

Dynamic Programming

Answer 50

Trade time for space, so algorithms run quicker.

Question 51

When does dynamic programming work?

Answer 51

Optimal substructure and/or overlapping sub problems.

Question 52

Optimal Substructure

Answer 52

A globally optimal solution can be found by combining optimal solutions to local subproblems. Fib(x) and merge sort.

Question 53

Overlapping Subproblems

Answer 53

Finding an optimal solution involves solving the same problem multiple times. Fib(x)

Question 54

Graph

Answer 54

Set of nodes (verifies) that might have associated proprieties and set of edges (arcs) each consisting of a nice pair.

Question 55

Undirected Graph

Answer 55

Two way street, like being friends on Facebook.

Question 56

Directed graph

Answer 56

Source (parent) and destination (child) node.

Question 57

Depth-first Search

Answer 57

Must keep track of what nodes have been visited. Search down an entire node path first to try and find the destination solution. Lots of back tracking.

Question 58

Breadth-first Search

Answer 58

Explore all paths with n hops before exploring any path with more than n paths. Cannot be easily modified for weighted shortest path the way DFS can.

Question 59

Stochastic Process

Answer 59

An ongoing process where the next state might depend on both the previous state and some random element.

Question 60

Copenhagen Doctrine of Causal Nondeterminism

Answer 60

At its most fundamental level, the behavior of the physical world cannot be predicted. Let by Bohr and Heisenberg

Question 61

Random Walk

Answer 61

A mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space. Can explain the observed behaviors of many processes in these fields, and thus serve as a fundamental model for the recorded stochastic activity.

Question 62

Law of Large Numbers (Bernoulli's Law)

Answer 62

In repeated independent tests with the same actual probability p of a particular outcome in each test, the chance that the fraction of times that outcome occurs differs from p converges to zero as the number of trials approach infinity.

Question 63

Probability Density Function

Answer 63

Probability of a random variable lying between two values. Defines a curve where the values on the x-axis lie between a max and min of the value. Area under the curve of two points is the probability of example falling within that range.

Question 64

Central Limit Theorem

Answer 64

Given a sufficiently large sample; The mean of the samples in a set of samples (the sample means) will be approximately normally distributed. This normal distribution will have a mean close to the population mean. The variance of the sample means will be close to the variance of the population divided by the sample size.

Question 65

Monte Carlo Simulation

Answer 65

Method of estimating the value of an unknown quantity using randomness and the principles of inferential statistics.

Question 66

Buffon-Laplace Estimate of Pi

Answer 66

Circle in a 2x2 square, drop needles at random, because circle's area is equal to pi, pi equals the area of the square times the ratio of needles in the circle to the needles in the square.

Question 67

Simple Random Sampling

Answer 67

Each members of the population has an equal change of being chosen. (Not always appropriate).

Question 68

Stratified Sampling

Answer 68

Partition population into homogeneous subgroups and take a random sample from each subgroup.

Question 69

R Squared

Answer 69

Compared estimation errors to variance of the original values. Intended to capture the proportion of variability in the data that is explained by the model. R^2 = 1, model explains all.

Question 70

Cross-Validation

Answer 70

Generate model using one dataset, then test on another.

Question 71

Leave One Out Testing for Cross-Validation

Answer 71

Leave out one example, train model on others and then test on left out example. Repeat until every example has been the left out one.

Question 72

K Fold Testing for Cross-Validation

Answer 72

Data partitioned into K equal size sets. Model trained on K-1 sets and tested in the remaining. Repeat until each of the K sets has been left out. Average the results.