Notizen
cs 6.042
Inhalt der Notizen (4)
Seite 1
Seite 2
Lecture 10 :
Hamiltonian path :
path where every node is visited only once.
Tournament Graph:
an edge from one node to other basically mean that a given vertex has beaten other vertex
THM : every tournament graph actually contain a hamiltonian path.
Proof : Induction on the no of nodes in the graph
removing a node in tournament graph still keep it as tournament graph.
consider smallest i such that V beats Vi
since its smallest other has beaten V so V will be between Vi-1 and Vi
Seite 3
Lecture 11 :
Relations, partial orders, and scheduling
Relations :
A relation from set A to set B is a subset R of A X B
ex : for a set A : no of student and set B(classes )
then R (a,b) is the relation of student taking which subject
aRb is denoted by a~Rb
SET A together with R forms a directed graph.
edges : it is joining those nodes which satisfies given relation
vertex : it is the set of all the valid point in given set.
Properties of Relation :
Reflexive : if x is related to itself for all x in set A
Symmetric : if xRY => yRx for all x and y
anti Symmetric : if xRy and yRx => x=y
transitive : if xRy and yRz => xRz
Equivalence relations:
if a relation is Reflexive + symmetric + transitive
ex : equality (=),
equivalence classes : [x] is all the set of x which satisfy a given relation
Partition of A : It is a collection of all disjoint , non empty set whose union is A.
equivalence class form the partition of equivalence relation
Partial ordering
if a relation has Reflexive + anti symmetric and transitive -- (WEAK) PARTIAL ORDERING
Hasse diagram : A Poset based directed graph where we remove reflexive(self loop) and all the edges which are implied by trasitivity
POSET : a graph representation of partial ordering
A Poset has no directed cycle apart from self loop.
A POSET without self loop is a DAG
Total order : Aa partial order where all the element are comparable.
Topological sort :
it is a total order of a poset with new relation M such that Poset relation is a subset of M.
THM : every finite Poset has a topological sort
Seite 4
Lecture 12:
N year M dollar annuity : paying M dollar at start of each year for N year
1 dollar currently with P% rate will be (1+p) in a year
(1+p)^2 in two year
(q+p)^3 in three year
and so on.
similarly 1 dollar in one year = 1/(1+P) now
1 dollar in 2 year = 1/(1+p)^2 now
and so on
if |x| <1 then summation of [ 1/x^n ] to infinity is 1/(1-x)
Perturbation method of calculation.
S = x + 2x^2 + 3x^3 + 4x^4 .....nx^n
x*S = x^2 + 2x^3 + 3x^4 ..... .... n*x^n+1
subtract
S(1-x) = x +x^2 +x^3 + x^4 .....x^n+1
Informationen
- Beschreibung
- Computer Science Notiz am cs 6.042, erstellt von Kumar Shubham am 26/09/2019.
- Erstellt von
- Kumar Shubham · Sep 2019
- Aktualisiert
- 29 Sep 2019
- Aufrufe
- 11
- Bewertung