Quantitative Reasoning Exam #1

studied byStudied by 36 people
0.0(0)
get a hint
hint

graph

1 / 137

encourage image

There's no tags or description

Looks like no one added any tags here yet for you.

138 Terms

1

graph

a set of edges connected by vertices

New cards
2

vertex/vertices

the points that connect each edge together

New cards
3

edges

the "links" between vertices

New cards
4

On a city map, ____ are vertices and ____ are edges

islands; bridges

New cards
5

valence/degee

the number of edges attached to a vertex

New cards
6

path

a sequence of vertices such that there is an edge between each vertex and the next one.

New cards
7

circuit

a path that starts and ends at the same vertex

New cards
8

eulerian circuit

a circuit that crosses each edge exactly once

New cards
9

A graph has a Eulerian circuit if and only if .....

the degree of all its vertices is even.

New cards
10

eulerian path

a path that crosses each edge exactly once.

New cards
11

A graph has a Eulerian path if and only if...

• either the degree of all its vertices is even (then it is even better: it has a Eulerian circuit); • or the degree of all its vertices except 2 of them is even (then it has a Eulerian path, but no Eulerian circuit)

New cards
12

hamiltonian circuit

a circuit that visits each vertex of the graph exactly once

New cards
13

hamiltonian path

a path that visits each vertex of the graph exactly once.

New cards
14

complete graph

a graph where there is exactly one edge between different pairs of vertices

New cards
15

weighted graph

a graph where there is a number attached to each edge

New cards
16

The weight of a path is the ....

sum of the weights on all edges encountered on this path (counted once for every passage)

New cards
17

traveling salesman problem

consists in finding a path / circuit that visits all vertices of a weighted graph (a Hamiltonian path / circuit); and that has the smallest weight.

New cards
18

brute force solution (for TSP)

  1. Look at all possible Hamiltonian paths.

  2. Check the weight of each of these paths.

  3. Choose the one with the smallest weight.

New cards
19

n factorial

In a complete graph with n vertices, there are n! Hamiltonian paths Even if n is small, n! is humongous

New cards
20

nearest-neighbor algorithm

  1. Start from any vertex.

  2. Jump to the closest vertex (that is, the edge to this vertex has the smallest weight).

  3. Then go to the closest vertex which has not been visited yet.

  4. Continue until you have seen all the vertices.

  5. If you want a circuit, eventually return to the starting vertex.

New cards
21

The nearest-neighbor algorithm provides a path with the following properties:

• It is usually “short”. • Its length can depend on the vertex that we start from. • Its length can depend of the choices that we make (if there are edges with the same length). • It usually does NOT provide a solution to the TSP (meaning, it is not always the shortest path).

New cards
22

sorted-edge algorithm

  1. List the weight of all edges in increasing order.

  2. Choose the first edge (the one with the smallest weight).

  3. As long as not all vertices are included, add the next edge in the list (except if it makes three chosen edges meet at a vertex or it closes a circuit that does not include all the vertices)

  4. When a Hamiltonian circuit has been created, we are done

New cards
23

The sorted-edge algorithm provides an approximate solution to the TSP. However...

-it is usually not the shortest path; -its length can depend of the choices that we make (if there are edges with the same length);

  • it only works to find a circuit

New cards
24

tree

a graph which contains no circuits

New cards
25

spanning tree

a tree that has only the edges of the original graph (but not always all the edges) and has all the vertices of the original graph

New cards
26

applications for a tree problem are:

Electrical grid: connect every home to the electrical grid at the minimum cost. Broadcasting: transmit one message to all recipients in the fastest way. Circuit board design: connect all parts at minimum cost.

New cards
27

How to obtain a spanning tree

• Start from the graph. • Remove edges one by one until no circuit remains.

New cards
28

The weight of a spanning tree is....

the sum of the weights of all its edges

New cards
29

minimum spanning tree

a spanning tree whose weight is minimum amongst all the possible spanning trees for a graph

New cards
30

kruskal's algorithm (MST)

  1. List all the edges in increasing order of their weights.

  2. At each step, add the next edge of the list if it does not create a circuit.

  3. Stop when we get a spanning tree.

New cards
31

Prim's algorithm (MST)

  1. Choose any vertex.

  2. Look at all edges attached to this vertex, and choose the one with the minimum weight.

  3. At each step, look at all the vertices that we saw, and all edges connected to these vertices, and choose the one with minimum weight, except if it creates a circuit.

  4. Stop when we get a spanning tree

New cards
32

Prim’s algorithm is conceptually more _______ than Kruskal’s, but Kruskal’s needs to compare the weight of all the edges at the _______.

complicated; same time

New cards
33

coloring problem

consists in giving a color to each vertex, in such a way that two vertices that are connected by an edge have different colors.

New cards
34

chromatic number

the minimum number of colors needed to solve the vertexcoloring problem

New cards
35

how do you find the chromatic number?

  1. Start from a vertex and give it a color.

  2. Give a different color to a neighboring vertex.

  3. Continue by going from neighboring vertex to neighboring vertex.

  4. Try to use as few colors as possible: reuse colors as much as possible

New cards
36

planar graph

a graph that can be drawn without any edges intersecting

New cards
37

According to the four-color theorem, the chromatic number of a planar graph is at most ___

4

New cards
38

statistics

the art and science of • collecting data; • summarizing and analyzing data; • presenting data; • interpreting data

New cards
39

population

all the individuals for a problem

New cards
40

sample

all the individuals that we will actually gather data from

New cards
41

variables

the information that we gather from the experiment (ex: intended vote, grades, size, opinion, …)

New cards
42

discrete variable

an integer/whole number (1, 2, 3) ex: number of pets, number of classes taken

New cards
43

continuous variable

can be any number, not only whole; like 2.5, 3.9, etc ex: weight, height, price, size

New cards
44

how to find the frequency distribution of a variable:

  1. Choose some non-overlapping intervals of values (for instance 0, 1 –2, 3 – 5, 6 – 10, more than 10).

  2. Count how many times the variables takes such values.

New cards
45

how to find the relative frequency distribution of a variable:

  1. Choose some non-overlapping intervals of values (for instance 0, 1 –2, 3 – 5, 6 – 10, more than 10).

  2. Count the percentage of times the variables take such values.

New cards
46

histogram

a graphical representation of the distribution of a variable using bars of different heights.

New cards
47

outlier

an individual or data that does not fit the overall pattern

New cards
48

symmetric distribution

A distribution is symmetric if we can draw a vertical line on the histogram, and both sides are approximate mirror images of each other

New cards
49

skewed right distribution

A distribution is skewed right if the longer tail of the histogram is on the right side

New cards
50

skewed-left distribution

A distribution is skewed left if the longer tail of the histogram is on the left side

New cards
51

mean

the average of all the values

New cards
52

median

a list of values is a number such that half the values are higher than this number and half the values are lower than this number.

New cards
53

mode

the most frequently occurring value in a set of data

New cards
54

standard deviation

the average amount a value deviates from the mean; the square root of the variance

New cards
55

variance

The square of the standard deviation

New cards
56

how to find the variance and standard deviation

  1. Compute the mean

  2. Compute the deviations (x1-mean), (x2-mean),...

  3. Compute the squared deviations (x1-mean)^2, (x2-mean)^2,....

  4. Sum all these quantities.

  5. Divide the result by n− 1 to get the variance.

  6. Take the square root of the result to get the standard deviation

New cards
57

normal distribution

When the shape of a distribution is more or less "regular". • It looks like a bell curve. • The curve is an idealized version of the distribution

New cards
58

A normal distribution is characterized by two parameters:

  1. The mean is where the curve reaches its maximum.

  2. The standard deviation is the width of the curve, between the two points where it changes curvature (inflection points).

New cards
59

The 68-95-99.7 rule

For a normal distribution with a mean µ and a standard deviation σ: 68% of the values are between µ-σand µ+σ 95% of the values are between µ– 2σ and µ+ 2σ 99.7% of the values are between µ– 3σ and µ+ 3σ

New cards
60

For a normal distribution, less than ___% of the values are more than 2σ from the mean and less than ____% of the values are more than 3σ from the mean.

5%; 0.3%

New cards
61

distributions

we study one variable, and wish to analyze it: average value, spread of the values, etc.

New cards
62

relationships

we study two variables and wish to know whether they are related

New cards
63

response variable

measures the outcome of a study; is typically directly observed.

New cards
64

explanatory variable

a variable that explains the changes of a response variable; is typically hidden / not obvious.

New cards
65

correlation coefficient

a numerical value that measures the strength and direction of the relationship between two variables (usually denoted by r)

New cards
66

correlation

a relationship between two or more things

New cards
67

If r> 0, then it is a ________ association, if r< 0, then it is a ___________ association

positive; negative

New cards
68

The closer r is to 1 or -1, the more _______ associated/ correlated the variables are.

strongly

New cards
69

Correlation only makes sense for _______ values and ________ relationships

numerical; straight-line

New cards
70

If two variables are highly correlated, then....

• when one goes up, the other one goes up (r close to 1) • or when one goes up, the other one goes down (r close to -1)

New cards
71

correlation does not imply _______

causation

New cards
72

the equation of a line is

y=mx+b

New cards
73

m in a regression line equation is the _____

slope (rise over run; (y2-y1/x2-x1)

New cards
74

b is the ______ or a regression line equation

y-intercept

New cards
75

slope

rise over run (y2-y1/x2-x1)

New cards
76

(least-square)regression line

the line that fits the closest to all the points

New cards
77

how to find the least-square regression line

  1. Take a straight line.

  2. Compute the vertical distances from each point to the line.

  3. Square these distances.

  4. Sum all these quantities.

  5. The line that makes this sum as small as possible is the least-square regression line

New cards
78

The regression line allows to make predictions only if the correlation is ______ (r close to -1 or +1) and only works for ______ correlations

high; linear

New cards
79

proportion

the number of times something happens out of the total outcomes

New cards
80

occam's razor

the principle that entities should not be multiplied needlessly; the simplest of two competing theories is to be preferred

New cards
81

statistical inference

the method of drawing conclusion about an entire population based on data from a sample

New cards
82

parameter

a fixed quantity that describes some characteristic of the population (for instance average height, proportion of women, result of a vote, opinion about hippos, etc.)

New cards
83

statistic

a quantity that describes some characteristic of a sample

New cards
84

central limit theorem

the larger the population, the closer the results will be to a normal distribution

New cards
85

confidence interval

the amount of confidence we have that a certain range of values will fall within 95% of the possible outcomes for that data

New cards
86

how to find the 95% confidence interval

  1. find the approximate standard deviation (square root of p(1-0)/n)

  2. take the percentage/probability you have and subract and add that by 2 times the approximate standard deviation ex: if your percentage is 56% and your approximate standard deviation is 5%, then you would calculate for 56%-(25%) and 56%+(25%)

New cards
87

Each poll comes with a _______, which is given by the standard deviation

Each poll comes with a margin of error

New cards
88

Sample Space (S)

the set of all possible outcomes of a random phenomenon

New cards
89

probability of an outcome (an element of the sample space)

the proportion of times the outcome occurs in an infinitely long series of repetitions

New cards
90

Probabilities can be expressed as....

decimals, percentages, or fractions

New cards
91

The probability of an outcome is between __ and ___ (inclusive)

New cards
92

Probability of a coin flip

For a coin flip: the probability of H or T is 1/2 = 0.5 = 50%

New cards
93

Probability of picking a card

the probability of each card (1S, 1H, …) is 1/52

New cards
94

event (E)

any set of outcomes of a random phenomenon; an event is the occurrence of something.

New cards
95

probability of events

For an event (E) we denote by P(E) the probability of E, that is, the proportion of times that the event E occurs when we repeat the same experiment infinitely many times

New cards
96

The goal of probability is to compute the _________: the proportion of time this event will occur when we repeat the _______ experiment infinitely many times

probability of events; same

New cards
97

property

The probability of an event is the sum of the individual probabilities of each outcome that it contains

New cards
98

The sum of the probabilities of all outcomes must be ____

1

New cards
99

The complement of an event A

-the event that happens when A does not occur; denoted by A^c -It contains all the outcomes of the sample space that; does not contain

New cards
100

The probability of the complement of an event is 1 minus the probability of the ______

event

New cards

Explore top notes

note Note
studied byStudied by 58 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 59 people
Updated ... ago
5.0 Stars(3)
note Note
studied byStudied by 58 people
Updated ... ago
4.0 Stars(1)
note Note
studied byStudied by 4 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 3 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 68 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 16 people
Updated ... ago
5.0 Stars(1)
note Note
studied byStudied by 2 people
Updated ... ago
5.0 Stars(1)

Explore top flashcards

flashcards Flashcard30 terms
studied byStudied by 13 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard44 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)
flashcards Flashcard20 terms
studied byStudied by 7 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard27 terms
studied byStudied by 1 person
Updated ... ago
5.0 Stars(1)
flashcards Flashcard235 terms
studied byStudied by 103 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard316 terms
studied byStudied by 29 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard20 terms
studied byStudied by 9 people
Updated ... ago
5.0 Stars(1)
flashcards Flashcard25 terms
studied byStudied by 28 people
Updated ... ago
5.0 Stars(1)