##### Algorithms implemented in Python from the book "Discrete Mathematics" by Dossey, Otto, Spence and Eynden



```python
import numpy as np
import random
from sympy import *
```

### Chapter 1

#### Algorithm for evaluating $x^n$


```python
def eval(x, n):
    P=x
    k=1
    while k<n:
        P*=x
        k+=1
    return P

eval(3, 4)
```




    81



#### Polynomial Evaluation Algorithm: computes $P(x)=a_nx^n + a_{n-1}x^{n-1} +...+ a_0$, given the non-negative integer $n$ and real numbers $x$, $a_0$, $a_1$, ..., $a_n$


```python
def P(x, a):
    # a is the list of the constants: a0, a1, ..., an
    S=a[0]
    k=1
    n=len(a)-1
    while k<=n:
        S+=a[k]*x**k
        k+=1
    return S
P(2, [4, 3, -2, 5])
```




    42



#### Horner's Polynomial Evaluation Algorithm


```python
def HP(x, a):
    n=len(a)-1
    S=a[n]
    k=1
    while k<=n:
        S=x*S+a[n-k]
        k+=1
    return S
HP(2, [4, 3, -2, 5])
```




    42



#### Next Subset Algorithm


```python
def NS(a):
    """a is a string of 0s and 1s corresponding to a subset of n elements"""
    n=len(a)
    a=list(a)
    k=n-1
    while k>=0 and a[k]=='1':
        k-=1
    if k>=0:
        a[k]='1'
        for j in range(k+1, n):
            a[j]='0'
        return ''.join(a)
    else: return 'The string contains all 1s'
NS('110')
```




    '111'



#### Bubble Sort Algorithm


```python
def BS(a):
    """A is a list of unsorted real numbers"""
    n=len(a)-1
    for j in range(n):
        for k in range(n-1, j-1, -1):
            if a[k+1]<a[k]:
                t=a[k+1]
                a[k+1]=a[k]
                a[k]=t
    return a

BS([1.2, 3.2, 9.0, 3.2, 0.5, 0.43, 8.44])
```




    [0.43, 0.5, 1.2, 3.2, 3.2, 8.44, 9.0]



#### Revised Polynomial Evaluation Algorithm


```python
def RP(x, a):
    S=a[0]
    y=1
    k=1
    n=len(a)-1
    while k<=n:
        y=x*y
        S+=y*a[k]
        k+=1
    return S
RP(2, [4, 3, -2, 5])
```




    42



 ### Chapter 3

#### The Euclidean Algorithm


```python
def gcd(m, n):
    """m and n are both non-negative integers"""
    while n!=0:
        m, n = n, m%n
    return m

gcd(427, 154)
```




    7



#### The Extended Euclidean Algorithm


```python
def exgcd(m, n):
    r=[m, n]
    x=[1, 0]
    y=[0, 1]
    i=1
    while r[i]!=0:
        i+=1
        q=r[i-2]//r[i-1]
        x+=[x[i-2]-q*x[i-1],]
        y+=[y[i-2]-q*y[i-1],]
        r+=[r[i-2]%r[i-1],]
    return (r[i-1], x[i-1], y[i-1])
exgcd(101, 1120)
```




    (1, -499, 45)



#### The Modular Exponentiation Algorithm: Given positive integers P, E and n, this algorithm computes the remainder when $P^E$ is divided by $n$.


```python
def ME(P, E, n):
    r2=1
    p=P
    e=E
    while e!=0:
        Q=e//2
        R=e%2
        r1=p**2%n
        if R==1: r2=(r2*p)%n
        p=r1
        e=Q
    return r2

ME(582, 621,1189)
```




    90



#### Check Matrix Row Decoding Algorithm


```python
def CMRD(codeword, generatorMatrix):
    A=generatorMatrix
    w=codeword
    k=len(A)
    n=len(A[0])
    J=np.copy(A[:, k:])
    A_star=np.append(J, np.eye(len(J[0]), dtype=int), axis=0)
    print(A_star)
    s=(w.dot(A_star))%2
    print(s)
    if sum(s)==0: return w[:k]
    if list(s) in A_star.tolist():
        i=np.where(np.all(A_star==s,axis=1))
        w[i]=(w[i]+1)%2
        return w[:k]
    if list(s) not in A_star.tolist(): return "unknown"
    
A=np.array(([1, 0, 0, 1, 0, 1, 0], [0, 1, 0, 1, 1, 0, 1], [0, 0, 1, 0, 1, 1, 1]))
w1=np.array([0, 0, 1, 0, 1, 1, 1])
w2=np.array([1, 0, 1, 1, 1, 0, 0])
w3=np.array([0, 1, 1, 1, 0, 1, 0])
w4=np.array([1, 0, 0, 0, 1, 1, 1])
w5=np.array([1, 1, 0, 0, 0, 1, 0])
#CMRD(w5, A)

#ex 3.6, 29
B=np.array(([1, 0, 1, 1, 0], [0, 1, 0, 1, 1])) # Generator matrix
c=np.array([1, 0, 1, 1, 0]) # received word
CMRD(c, B)
```

    [[1 1 0]
     [0 1 1]
     [1 0 0]
     [0 1 0]
     [0 0 1]]
    [0 0 0]





    array([1, 0])



### Chapter 4

#### Euler circuit Algorithm


```python
V=['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'J']
Ed={'a':['A', 'B'], 'c':['B', 'E'], 'f':['E', 'D'], 'b':['D', 'A'], 'd':['E', 'C'], 'e':['C', 'F'], 'g':['F', 'E'], 'h':['E', 'G'], 'k':['H', 'G'], 'm':['H', 'J'], 'l':['J', 'H'], 'j':['H', 'E']}

def EulerCircuit(V, Ed): 
    E1=list(Ed.keys())
    E2=[Ed[i] for i in Ed]
    U=random.choice(V)  
    R=[i for i in E2 if U in i]    
    #print(R)

    st=random.choice(R)
    ind=E2.index(st)
    C={}
    #print(C)

    if st[0]!=U: st=st[::-1]
    C[E1[ind]]=st
    del E1[ind]
    del E2[ind]
    #print(E1)
    #print(E2)

    while st[1]!=U:
        u=st[1]
        R=[i for i in E2 if u in i]
        st=random.choice(R)
        ind=E2.index(st)
        if st[0]!=u: st=st[::-1]
        C[E1[ind]]=st
        del E1[ind]
        del E2[ind]

    while len(E1)!=0 and len(E2)!=0:
        E21=sympy.flatten(E2)
        E3=list(C.keys())
        E4=[C[i] for i in C]
        E41=sympy.flatten(E4)
        L=[] # store the vertices whose edges are not listed in C
        L=list(set([i for i in E41 if E21.count(i)>0]))
        #print(L)
        u= random.choice(L)
    
        R=[i for i in E2 if u in i]    
        st=random.choice(R)
        ind=E2.index(st)
        P={}
    
        if st[0]!=u: st=st[::-1]
        P[E1[ind]]=st
        del E1[ind]
        del E2[ind]
    
        while st[1]!=u:
            u1=st[1]
            R=[i for i in E2 if u1 in i]
            st=random.choice(R)
            ind=E2.index(st)
            if st[0]!=u1: st=st[::-1]
            P[E1[ind]]=st
            del E1[ind]
            del E2[ind]
    
        x=list(P.keys())
        y=[P[i] for i in P]
        z=[i for i in E4 if i[1]==u]
        #print(E3)
        #print(E4)
        #print(x, y, z)
        ra=random.choice(z)
        k1=E4.index(ra)
        E3[k1+1:k1+1]=x
        E4[k1+1:k1+1]=y
        C={}
        for i in range(len(E3)): C[E3[i]]=E4[i]
        #print(P)
    
    return C

#EulerCircuit(V, Ed)

Ed={'a':['U', 'V'], 'b':['U', 'V'], 'c':['U', 'A'], 'd':['A', 'V'], 'e':['U', 'V']}
V=['A', 'U', 'V']
print(Ed)
EulerCircuit(V, Ed)
```

    {'a': ['U', 'V'], 'b': ['U', 'V'], 'c': ['U', 'A'], 'd': ['A', 'V'], 'e': ['U', 'V']}





    {'a': ['V', 'U'],
     'b': ['U', 'V'],
     'e': ['V', 'U'],
     'c': ['U', 'A'],
     'd': ['A', 'V']}



#### Breadth-First Search Algorithm


```python
#Ed=[['S', 'A'], ['S', 'B'], ['A', 'E'], ['E', 'C'], ['A', 'C'], ['C', 'B'], ['F', 'E'], ['F', 'H'], ['C', 'H'], ['H', 'I'], ['I', 'J'], ['J', 'G'], ['G', 'D'], ['D', 'B']]
#V=['S', 'A', 'B', 'E', 'F', 'H', 'I', 'J', 'G', 'D', 'B', 'C']
#start='S'
#end='I'

Ed=[['S', 'A'], ['S', 'D'], ['D', 'B'], ['G', 'D'], ['B', 'G'], ['E', 'C'], ['E', 'F'], ['C', 'F'], ['E', 'G'], ['G', 'H'], ['F', 'H'], ['F', 'T'], ['H', 'I'], ['T', 'I']]
V=['S', 'A', 'D', 'B', 'G', 'E', 'C', 'F', 'G', 'H', 'I', 'T']
start='S'
end='T'

def BFSA(Ed, V, start, end):
    st=[start]
    L={st[0]:[0, '-']}

    k=0

    while len(V)>1:
        k+=1
        st1=[]
        for s in st:
            del V[V.index(s)]
            I=[j for j in Ed if (j[0]==s or j[1]==s)]
            for i in I:
                del Ed[Ed.index(i)]
            I1=[i[::-1] if i[1]==s else i for i in I]
            I2=[i for i in I1 if (i[0] in st and i[1] not in st) or (i[0] not in st and i[1] in st) ]
            for [i, j] in I2:
                L[j]=[k, s]
                st1+=[j, ]
        st=list(set(st1))
   
    print(L)
    
    path=end
    pr=L[end][1]
    while pr!='-':
        path+=pr
        pr=L[pr][1]
        
    return path[::-1]

BFSA(Ed, V, start, end)
```

    {'S': [0, '-'], 'A': [1, 'S'], 'D': [1, 'S'], 'B': [2, 'D'], 'G': [2, 'D'], 'E': [3, 'G'], 'H': [3, 'G'], 'C': [4, 'E'], 'F': [4, 'H'], 'I': [4, 'H'], 'T': [5, 'F']}





    'SDGHFT'



#### Dijkstra's Algorithm


```python
#Ed=[['S', 'A', 3], ['S', 'B', 1], ['C', 'A', 2], ['C', 'B', 3], ['D', 'B', 5], ['A', 'B', 1], ['C', 'E', 3], ['D', 'C', 1], ['D','E', 1]]
#V=['A', 'S', 'B', 'D', 'C', 'E']
#st='S'
#end='E'

##Ex 4.3, 6
#Ed=[['S', 'C', 2], ['S', 'E', 4], ['E', 'C', 1], ['C', 'F', 3], ['C', 'D', 5], ['F', 'E', 1], ['F', 'G', 2], ['D', 'F', 3], ['D', 'G', 1], ['D', 'H',1], ['G', 'H', 3], ['A', 'H', 3], ['E', 'J', 2], ['G', 'J', 3]]
#V=['S', 'C', 'D', 'E', 'F', 'G', 'H', 'A', 'J']
#st='S'
#end='A'

##Ex 4.3, 7
Ed=[['S', 'C', 3], ['S', 'E', 2], ['S', 'H', 1], ['C', 'E', 1], ['E', 'H', 1], ['F', 'C', 3], ['F', 'H', 2], ['F', 'D', 2], ['C', 'D', 2], ['F', 'B', 3], ['B', 'H', 5], ['G', 'D', 1], ['G', 'B', 1], ['G', 'A', 2], ['A', 'D', 5], ['A', 'B', 4]]
V=['S', 'C', 'E', 'H', 'D', 'F', 'G', 'B', 'A']
st='S'
end='A'

def DA(Ed, V, st, end):
    """Each of the entries in Ed has form: ['vertex1', 'vertex2', weight of the edge joining vertex1 and vertex2]"""
    E1=[]
    E2=[]
    for i in Ed:
        E1+=[[i[0], i[1]], ]
        E2+=[i[2], ]
    P={st:[0, '-']}
    V1=V[:]
    del V1[V1.index(st)]
    temp={}
    I=[]
    for i in V1:
        if [i, st] in E1:
            ind=E1.index([i, st])
            temp[i]=[E2[ind], st]
            I+=[ind,]
        
        elif [st, i] in E1:
            ind=E1.index([st, i])
            temp[i]=[E2[ind], st]
            I+=[ind,]
        
        elif (not [i, st] in E1) or (not [st, i] in E1):
            temp[i]=[oo, st]

    for ind in sorted(I, reverse=True):
        del E1[ind]
        del E2[ind]

    t1=list(temp.keys())
    t2=[temp[i] for i in temp]

    while len(t2)!=0:
        temp1={}
        I=[]
        Min=min(t2)
        Ind=t2.index(Min)
        st_old=st
        st=t1[Ind]
        label_st=Min
        P[st]=label_st
        del V1[V1.index(st)]
    
    
        for i in V1:
            if [i, st] in E1:
                old_label=temp[i]
                o1=old_label[0]
                o2=old_label[1]
                ind=E1.index([i, st])
                if o1<=label_st[0]+E2[ind]: temp1[i]=old_label
                else:
                    Minimum=min([o1, label_st[0]+E2[ind]])
                    temp1[i]=[Minimum, st]
                    I+=[ind,]
        
            elif [st, i] in E1:
                old_label=temp[i]
                o1=old_label[0]
                o2=old_label[1]
                ind=E1.index([st, i])
                if o1<=label_st[0]+E2[ind]: temp1[i]=old_label
                else:
                    Minimum=min([o1, label_st[0]+E2[ind]])
                    temp1[i]=[Minimum, st]
                    I+=[ind,]
        
            elif (not [i, st] in E1) or (not [st, i] in E1):
                temp1[i]=temp[i]
    
    
        for ind in sorted(I, reverse=True): 
            del E1[ind]   
            del E2[ind]
        temp=temp1
    
        t1=list(temp.keys())
        t2=[temp[i] for i in temp]

    path=end
    pr=P[end][1]
    if P[end][0]==oo: return 'No shortest path exists'
    while pr!='-':
        path+=pr
        pr=P[pr][1]
    print(P)        
    return path[::-1]
        
DA(Ed, V, st, end) 
    
    
```

    {'S': [0, '-'], 'H': [1, 'S'], 'E': [2, 'S'], 'F': [3, 'H'], 'C': [3, 'S'], 'D': [5, 'F'], 'G': [6, 'D'], 'B': [6, 'H'], 'A': [8, 'G']}





    'SHFDGA'



052d9fec3f4231dec7fa5bac6abeed6f71ad6f4a
ipynb
Jupyter Notebook
discrete math.ipynb
indrag49/Discrete-Mathematics
f9da43b6fb6e465f2249226fe025bb7fb2e810e0
MIT
discrete math.ipynb
indrag49/Discrete-Mathematics
f9da43b6fb6e465f2249226fe025bb7fb2e810e0
MIT
discrete math.ipynb
indrag49/Discrete-Mathematics
f9da43b6fb6e465f2249226fe025bb7fb2e810e0
MIT
Qwen/Qwen-72B
1. YES
2. YES