Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

1870: Theoretical Compounds > Week 1 - 10 > Flashcards

Week 1 - 10 Flashcards

You may prefer our related Brainscape-certified flashcards:
Organic Chemistry 101 flashcards
1
Q

Bipartite graph

A

vertices can be divided into 2 sections

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Complete graph

A

vertices are all connected to every other vertices

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

matching

A

a set of edges so that every vertex is incident with at most one vertex in the matching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

perfect matching

A

a set of edges where each vertex is incident with exactly one vertex in the matching - solves the assignment problem

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

path

A

sequence of vertices joined together in edges

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

alternating path

A

edges in the path alternate from being in the matching and not in the matching

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

set

A

collection of objects

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

power sets

A

contains other sets

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

data structure

A

method of storing information so that a computer can access it

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

cartesian product

A

the set of all ordered pairs with the first element A and the second element from B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

function

A

each input is mapped to exactly one input

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

symmetric difference

A

set of elements in exactly one of A or B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

injective function

A
  1. one-to-one
  2. different arrows go to different locations
  3. if (a1, b) and (a2, b) both belong to f then a1 = a2
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

surjective function

A
  1. every element of the codomain there is an element of the domain relating to it
  2. image of f = B
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

bijective function

A

both injective and surjective

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

relation

A

a relation from A to B is a subset of the cartesian product A x B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

reflexive graph

A
  1. every element has a self directed arrow loop
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

symmetric graph

A
  1. every arrow is two-way
  2. whenever (a, b) is contained in R, then (b, a) is in R
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

anti-symmetric graph

A
  1. no two-way arrows (exception for loops)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

transitive graph

A
  1. if we can get from a to c in two steps, we can get there in one step
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

equivalence relation

A
  1. symmetric
  2. reflexive
  3. transitive
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

partial order

A
  1. anti-symmetric
  2. reflexive
  3. transitive
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

predicate

A

act likes a function which can take an element of the domain as input and produce a truth value as a output

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

existential quantifier

A

there exists x, an element of the domain such that … is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
Q

universal quantifier

A

for every value of x such that … is true

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

¬ (universal quantifier(x)…)

A

existential quantifier(x)¬(…)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
27
Q

¬(existential quantifier(x)…)

A

universal quantifier(x)¬(…)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
28
Q

A ⇒ B is the same as …

A

(¬A) v B

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

arguments

A
  • sequence of statements (premises) and a conclusion
  • valid = accept the premises as being true then we must accept the conclusion as true
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

rules of interference

A
  • list of premises of the argument
  • use rules to produce logical statements
  • eventually, produce the conclusion of the argument
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
31
Q

conjunction elimination

A

j: A ^ B
= A (or B)
- ^ Elim j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

conjunction introduction

A

j:A
k: B
= A ^ B
- ^Intro j, k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
33
Q

implication introduction

A

j:A
k:B
= A ⇒ B
- ⇒Intro j-k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
34
Q

implication elimination

A

j:A ⇒ B
= A becomes B
- ⇒Elim j,k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
35
Q

disjunction introduction

A

j:A
= A v B (or B v A)
- v Intro j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
36
Q

disjunction elimination

A

j: A v B
k: ¬A
= B
- v Elim j, k

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
37
Q

negation introduction

A

j: A ⇒ (B ^ (¬B)
- ¬ Intro j

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
38
Q

types of proof

A
  1. direct - X ⇒Y
  2. contrapositive - ¬X ⇒ ¬Y
  3. by contradiction - ¬X ⇒ (p ^ (¬p)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
39
Q

inductive proof

A
  1. check the base case - prove the property holds for 1 or 0
  2. hypthesis - states that it works up to an arbituary point int the integers - k
  3. prove that statement is past the arbituary point in the integers - k + 1
  4. if we accomplish these steps, we have proved the statement is true for all positive integers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
40
Q

well-ordering principle

A

inductive proofs work because if P(x) is false for some choice of x, then it is false for some smallest choice of x

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
41
Q

uses of the well-ordering principle

A
  • analysing running time for algorithms
  • proving the correctness of algorithms
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
42
Q

cardinality

A

the number of elements in a set - |A|

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
43
Q

countable infinities

A
  • countably infinite if it has the same cardinality as Z+
  • if the set is countable infinite, then there is a path which steps through all the elements of the set, one by one
44
Q

uncountable infinities

A

set of real numbers

45
Q

addition principle

A

|A v B| = |A| x |B|
- does not work if A ^ B has one or more elements

46
Q

mulitplication principle

A

|A x B| = |A| x |B|

47
Q

permutation

A

ordering of the elements of the set
- let A be a set with |A| = n
- the number of permutations of A is n!

48
Q

ordered selections

A
  • let A be a set with |A| = n
  • the number of ways we can make an ordered selection of k elements of A is n!/(n - k)!
49
Q

unordered selections

A

n!/(n-k)!k! = binomial coefficent

50
Q

binomial theorem

A

(a + b)^n = the sum of (nCi)a^(n-i)b^i

51
Q

pascals identity

A

(nk) = (n-1 k-1) + (n-1 k)

52
Q

inclusion-exclusion

A

|A v B v C| = |A| + |B| + |C| - |A ^ B| - |A ^ C|- |B ^ C| + |A ^ B ^ C|

53
Q

recursive definitions

A

F(n) = F(n-1) + F(n-2) because every sequence summing to n either ends with a 1 or with a number that is at least 3

54
Q

number theory

A

the study of integers and their properties

55
Q

divisibility

A

assume p and q are integers. when we say p divides q we mean there exists an integer k such that q = kp

56
Q

when does a sequence have a multiplicative inverse

A
  • gcd(a, m) = 1
  • a and m are coprime
57
Q

subset problem

A

input: a sequence of positive integers, and an integer c
question: is there a subset of {w1, w2 … wt} that sums to c?

58
Q

super-increasing

A

every number is larger than the sum of previous numbers.
- if a sequence is super-increasing we can easily solve the subset sum using the greedy approach

59
Q

why use graphs

A
  • helps to solve complex problems
  • used in data structures
  • visualisation
  • used in search engines
60
Q

d-regular graph

A

every vertex in G has d degrees

61
Q

what is a degree

A

number of edges incident to a vertice

62
Q

isomorphisim

A

a graph in which a single graph can have more than one form. that means two different graphs can have the same number of edges, vertices, and same edges connectivity

63
Q

what to do to prove an equivalence relation between graphs

A
  1. reflexive: G is isomorphic to itself
  2. symmetric: if G1 is isomorphic to G2, then G2 is isomorphic to G1
  3. transitive: if G1 is isomorphic to G2 and G2 is isomorphic to G3, then G1 is isomorphic to G3
64
Q

what is G’

A

a subgraph of G

65
Q

what is a spanning sub-graph

A

if V(G’) = V(G) then G is a spanning sub-graph

66
Q

what is a walk

A

a sequence of vertices and edges in a graph
- allow for repeated vertices and edges

67
Q

what is a trail

A

a sequence of vertices and edges in a graph where all edges are distinct
- repeated vertices but not allowed repeated edges

68
Q

what is a path

A

a sequence of vertices and edges in a graph where all vertices are distinct
- repeated edges but not allowed repeated vertices

69
Q

what is meant by a closed (walk/path/trail)

A

v0 = vk

70
Q

eurelian tour

A

a closed walk in a graph G that passes through every edge exactly once

71
Q

eurelian theorem

A

a connected (multi)graph with at least one edge has a Eurelian tour if every vertex has an even degree

72
Q

eurelian trail

A

a walk in graph G that passes through every edge exactly once (NOT CLOSED)

73
Q

hamiltonian cycle

A

a cycle that visits every vertex exactly once

74
Q

theorem 1.11

A

number of vertices with odd degree is even

75
Q

adjacency list

A

associates each vertex in the graph with a list of its neighbours in some order

76
Q

adjacency matrix

A

a rectangular array of numbers (called entries or elements) of the matrix

77
Q

matrix addition

A
  • same shape needed
  • add each one in each position together
78
Q

matrix multiplication

A

height of first matrix and length of second matrix

79
Q

A^K

A

A multiplying itself k times
- shows the number of length k walks between the nodes

80
Q

incidence matrix

A

vertices and edges

81
Q

biadjacency matrix

A
  • for a bipartite graph
  • V(one group) x V(other group)
82
Q

graph matching

A

a set of M of non-overlapping edges

83
Q

graph perfect matching

A

a graph is a matching where every vertex is incident to an edge in the matching

84
Q

maximum cardinality

A

maximum matching

85
Q

saturated

A

v is incident to an edge in M

86
Q

alternating path (graph)

A

if edges in P are alternating between M and not M

87
Q

acyclic

A

graph with no cycles

88
Q

tree

A

connected acyclic graph

89
Q

leaf

A

vertex of degree one in a forest

90
Q

any tree with at least two vertices has ….

A

at least two leaves

91
Q

characterisation of trees

A
  1. G is a tree
  2. G is connected and has exactly n -1 edges
  3. G is acyclic and has n-1 edges
92
Q

a spanning tree of a connected graph is a …

A

sub-graph of G, is a tree and contains all elements in V(G)

93
Q

matrix equality

A

the matrices A and B are equal if they have the same order and their corresponding entries are equal

94
Q

diagonal matrix

A

an n x n matrix A where A[i, j] = 0 for all i != j and at least one for A[i, i}

95
Q

square matrix

A

number of rows = number of columns

96
Q

identity matrix

A

a diagonal matrix where all diagonal elements are equal to 1

97
Q

transpose of a matrix

A

columns = rows
rows = columns

98
Q

symmetric matrix

A

A = A^T

99
Q

skew symmetric matrix

A

A^T = -A

100
Q

euclidean plane

A

a geometric space where each point is represented by a pair of ordered real numbers

101
Q

dot product

A

sum of each individual vertice pairs
- v1u1 + v2u2 + … + vnun

102
Q

cosine rule

A

v . u = |v||u|cosA

103
Q

cross product where

A

only in R^3

104
Q

cross product (sin)

A

v x u = |v||u|sinA x n
n = unit vector perpendicular to v and u

105
Q

cross product

A

1870: Theoretical Compounds (1 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions