CoCalc -- Collaborative Calculation in the Cloud
Sharedsage_worksheets / MATH.5100-J1.ipynbOpen in CoCalc

Worksheets related to Applied Discrete Structures

# A Jupyter Notebook¶

This is a Jupyter Notebook that is running a SageMath Kernel

### Miscellaneous Computations ¶

taylor?

y=taylor(cos(x),x,0,6);y

-1/720*x^6 + 1/24*x^4 - 1/2*x^2 + 1
p=plot(y,(x,-2*pi,2*pi))
p+=plot(cos(x),(x,-2*pi,2*pi),color='red')
p.show()

A=Matrix(GF(7),[[2,-1,0,0],[-1,3,-1,0],[0,-1,4,-1],[0,0,-1,5]]);A

[2 6 0 0] [6 3 6 0] [0 6 4 6] [0 0 6 5]
A.eigenvalues()

[6, 6, 1, 1]
n=434233

n.factor()

47 * 9239

### Functions ¶

var('t')
f1(t)=-16*t^2+100*t

f1(3)

156
def f2(t):
return -16*t^2 + 100 * t

f2(3)

156

Symbolic inputs are allowed, as long as the variable is declared.

var('w')
[f1(w^2),f2(w^2)]

[-16*w^4 + 100*w^2, -16*w^4 + 100*w^2]

### Some Counting ¶

Lets do some counting. How many subsets of the set of integers from 0 to n-1 have no consecutive values? For example we would not count {0,3,4,8} but would count {0,3,5,8}

def valid(B):
v=true
for k in B:
if k+1 in B:
v=false
break
return v
[valid(Set([1,3,5,9])),valid(Set([1,2,4,9]))]

[True, False]
U=Set(range(10))
power_set=U.subsets()
len(power_set)

1024
count=0
for B in power_set:
if valid(B):
count+=1
count

144
def number_of_valid(n):
power_set=Set(range(n)).subsets()
count=0
for B in power_set:
if valid(B):
count+=1
return count

number_of_valid(6)

21
map(lambda n:[n,number_of_valid(n)],range(10))

[[0, 1], [1, 2], [2, 3], [3, 5], [4, 8], [5, 13], [6, 21], [7, 34], [8, 55], [9, 89]]

### Graphs and Dictionaries¶

NE={'ME':['NH'],'NH':['VT','MA'],'VT':['MA'],'MA':['RI','CT'],'RI':['CT']}

NE.keys()

['ME', 'NH', 'VT', 'MA', 'RI']
NE['MA']

['RI', 'CT']
g=Graph(NE)

g.adjacency_matrix()

[0 1 0 0 1 0] [1 0 0 1 1 1] [0 0 0 1 0 0] [0 1 1 0 0 1] [1 1 0 0 0 0] [0 1 0 1 0 0]
g.vertices()

['CT', 'MA', 'ME', 'NH', 'RI', 'VT']
g.graphplot().show()

g.neighbors('RI')

['MA', 'CT']
g.chromatic_number()

3
for state in g.vertices():
print [state,len(g.neighbors(state))]

['CT', 2] ['MA', 4] ['ME', 1] ['NH', 3] ['RI', 2] ['VT', 2]
g.distance_all_pairs()

{'CT': {'CT': 0, 'MA': 1, 'ME': 3, 'NH': 2, 'RI': 1, 'VT': 2}, 'MA': {'CT': 1, 'MA': 0, 'ME': 2, 'NH': 1, 'RI': 1, 'VT': 1}, 'ME': {'CT': 3, 'MA': 2, 'ME': 0, 'NH': 1, 'RI': 3, 'VT': 2}, 'NH': {'CT': 2, 'MA': 1, 'ME': 1, 'NH': 0, 'RI': 2, 'VT': 1}, 'RI': {'CT': 1, 'MA': 1, 'ME': 3, 'NH': 2, 'RI': 0, 'VT': 2}, 'VT': {'CT': 2, 'MA': 1, 'ME': 2, 'NH': 1, 'RI': 2, 'VT': 0}}