class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def dijkstra(g, source): """Return distance where distance[v] is min distance from source to v.

This will return a dictionary distance.

g is a Graph object.
source is a Vertex object in g.
"""
unvisited = set(g)
distance = dict.fromkeys(g, float('inf'))
distance[source] = 0

while unvisited != set():
    # find vertex with minimum distance
    closest = min(unvisited, key=lambda v: distance[v])

    # mark as visited
    unvisited.remove(closest)

    # update distances
    for neighbour in closest.get_neighbours():
       if neighbour in unvisited:
           new_distance = distance[closest] + closest.get_weight(neighbour)
           if distance[neighbour] > new_distance:
               distance[neighbour] = new_distance

return distance

g = Graph() print('Undirected Graph') print('Menu') print('add vertex <key>') print('add edge <src> <dest> <weight>') print('shortest <source vertex key>') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        weight = int(do[4])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest, weight)
                g.add_edge(dest, src, weight)
            else:
                print('Edge already exists.')

elif operation == 'shortest':
    key = int(do[1])
    source = g.get_vertex(key)
    distance = dijkstra(g, source)
    print('Distances from {}: '.format(key))
    for v in distance:
        print('Distance to {}: {}'.format(v.get_key(), distance[v]))
    print()

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def get_topological_sorting(graph): """Return a topological sorting of the DAG. Return None if graph is not a DAG.""" tlist = [] visited = set() on_stack = set() for v in graph: if v not in visited: if not get_topological_sorting_helper(v, visited, on_stack, tlist): return None return tlist

def get_topological_sorting_helper(v, visited, on_stack, tlist): """Perform DFS traversal starting at vertex v and store a topological sorting of the DAG in tlist. Return False if it is found that the graph is not a DAG. Uses set visited to keep track of already visited nodes.""" if v in on_stack:

    # graph has cycles and is therefore not a DAG.
    return False

on_stack.add(v)
for dest in v.get_neighbours():
    if dest not in visited:
        if not get_topological_sorting_helper(dest, visited, on_stack, tlist):
            return False
on_stack.remove(v)
visited.add(v)
tlist.insert(0, v.get_key()) # prepend node key to tlist
return True

g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('topological') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest)
            else:
                print('Edge already exists.')

elif operation == 'topological':
    tlist = get_topological_sorting(g)
    if tlist is not None:
        print('Topological Sorting: ', end='')
        print(tlist)
    else:
        print('Graph is not a DAG.')

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __len__(self):
    return len(self.vertices)

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def floyd_warshall(g): """Return dictionaries distance and next_v.

distance[u][v] is the shortest distance from vertex u to v.
next_v[u][v] is the next vertex after vertex v in the shortest path from u
to v. It is None if there is no path between them. next_v[u][u] should be
None for all u.

g is a Graph object which can have negative edge weights.
"""
distance = {v:dict.fromkeys(g, float('inf')) for v in g}
next_v = {v:dict.fromkeys(g, None) for v in g}

for v in g:
    for n in v.get_neighbours():
        distance[v][n] = v.get_weight(n)
        next_v[v][n] = n

for v in g:
     distance[v][v] = 0
     next_v[v][v] = None

for p in g: 
    for v in g:
        for w in g:
            if distance[v][w] > distance[v][p] + distance[p][w]:
                distance[v][w] = distance[v][p] + distance[p][w]
                next_v[v][w] = next_v[v][p]

return distance, next_v

def print_path(next_v, u, v): """Print shortest path from vertex u to v.

next_v is a dictionary where next_v[u][v] is the next vertex after vertex u
in the shortest path from u to v. It is None if there is no path between
them. next_v[u][u] should be None for all u.

u and v are Vertex objects.
"""
p = u
while (next_v[p][v]):
    print('{} -> '.format(p.get_key()), end='')
    p = next_v[p][v]
print('{} '.format(v.get_key()), end='')

g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest> <weight>') print('floyd-warshall') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        weight = int(do[4])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest, weight)
            else:
                print('Edge already exists.')

elif operation == 'floyd-warshall':
    distance, next_v = floyd_warshall(g)
    print('Shortest distances:')
    for start in g:
        for end in g:
            if next_v[start][end]:
                print('From {} to {}: '.format(start.get_key(),
                                                end.get_key()),
                        end = '')
                print_path(next_v, start, end)
                print('(distance {})'.format(distance[start][end]))

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key

    # dictionary containing destination vertices mapped to the weight of the
    # edge with which they are joined to this vertex
    self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

class Queue: def __init__(self): self.items = []

def is_empty(self):
    return self.items == []

def enqueue(self, data):
    self.items.append(data)

def dequeue(self):
    return self.items.pop(0)

def find_shortest_paths(src): """Returns tuple of two dictionaries: (parent, distance)

parent contains vertices mapped to their parent vertex in the shortest
path from src to that vertex.
distance contains vertices mapped to their shortest distance from src.
"""
parent = {src: None}
distance = {src: 0}

visited = set()
q = Queue()
q.enqueue(src)
visited.add(src)
while not q.is_empty():
    current = q.dequeue()
    for dest in current.get_neighbours():
        if dest not in visited:
            visited.add(dest)
            parent[dest] = current
            distance[dest] = distance[current] + 1
            q.enqueue(dest)
return (parent, distance)

g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('shortest <vertex key>') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest)
            else:
                print('Edge already exists.')

elif operation == 'shortest':
    key = int(do[1])
    src = g.get_vertex(key)
    parent, distance = find_shortest_paths(src)

    print('Path from destination vertices to source vertex {}:'.format(key))
    for v in parent:
        print('Vertex {} (distance {}): '.format(v.get_key(), distance[v]),
              end='')
        while parent[v] is not None:
            print(v.get_key(), end = ' ')
            v = parent[v]
        print(src.get_key()) # print source vertex

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_vertex_exist(self, key):
    return key in self.vertices

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def display(self):
    print('Vertices: ', end='')
    for v in self:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in self:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))

def __len__(self):
    return len(self.vertices)

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def mst_krusal(g): """Return a minimum cost spanning tree of the connected graph g.""" mst = Graph() # create new Graph object to hold the MST

if len(g) == 1:
    u = next(iter(g)) # get the single vertex
    mst.add_vertex(u.get_key()) # add a copy of it to mst
    return mst

# get all the edges in a list
edges = []
for v in g:
    for n in v.get_neighbours():
        # avoid adding two edges for each edge of the undirected graph
        if v.get_key() < n.get_key():
            edges.append((v, n))

# sort edges
edges.sort(key=lambda edge: edge[0].get_weight(edge[1]))

# initially, each vertex is in its own component
component = {}
for i, v in enumerate(g):
    component[v] = i

# next edge to try
edge_index = 0

# loop until mst has the same number of vertices as g
while len(mst) < len(g):
    u, v = edges[edge_index]
    edge_index += 1

    # if adding edge (u, v) will not form a cycle
    if component[u] != component[v]:

        # add to mst
        if not mst.does_vertex_exist(u.get_key()):
            mst.add_vertex(u.get_key())
        if not mst.does_vertex_exist(v.get_key()):
            mst.add_vertex(v.get_key())
        mst.add_edge(u.get_key(), v.get_key(), u.get_weight(v))
        mst.add_edge(v.get_key(), u.get_key(), u.get_weight(v))

        # merge components of u and v
        for w in g:
            if component[w] == component[v]:
                component[w] = component[u]

return mst

g = Graph() print('Undirected Graph') print('Menu') print('add vertex <key>') print('add edge <src> <dest> <weight>') print('mst') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        weight = int(do[4])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest, weight)
                g.add_edge(dest, src, weight)
            else:
                print('Edge already exists.')

elif operation == 'mst':
    mst = mst_krusal(g)
    print('Minimum Spanning Tree:')
    mst.display()
    print()

elif operation == 'display':
    g.display()
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def display(self):
    print('Vertices: ', end='')
    for v in self:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in self:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))

def __len__(self):
    return len(self.vertices)

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def mst_prim(g): """Return a minimum cost spanning tree of the connected graph g.""" mst = Graph() # create new Graph object to hold the MST

# if graph is empty
if not g:
    return mst

# nearest_neighbour[v] is the nearest neighbour of v that is in the MST
# (v is a vertex outside the MST and has at least one neighbour in the MST)
nearest_neighbour = {}
# smallest_distance[v] is the distance of v to its nearest neighbour in the MST
# (v is a vertex outside the MST and has at least one neighbour in the MST)
smallest_distance = {}
# v is in unvisited iff v has not been added to the MST
unvisited = set(g)

u = next(iter(g)) # select any one vertex from g
mst.add_vertex(u.get_key()) # add a copy of it to the MST
unvisited.remove(u)

# for each neighbour of vertex u
for n in u.get_neighbours():
    if n is u:
        # avoid self-loops
        continue
    # update dictionaries
    nearest_neighbour[n] = mst.get_vertex(u.get_key())
    smallest_distance[n] = u.get_weight(n)

# loop until smallest_distance becomes empty
while (smallest_distance):
    # get nearest vertex outside the MST
    outside_mst = min(smallest_distance, key=smallest_distance.get)
    # get the nearest neighbour inside the MST
    inside_mst = nearest_neighbour[outside_mst]

    # add a copy of the outside vertex to the MST
    mst.add_vertex(outside_mst.get_key())
    # add the edge to the MST
    mst.add_edge(outside_mst.get_key(), inside_mst.get_key(),
                 smallest_distance[outside_mst])
    mst.add_edge(inside_mst.get_key(), outside_mst.get_key(),
                 smallest_distance[outside_mst])

    # now that outside_mst has been added to the MST, remove it from our
    # dictionaries and the set unvisited
    unvisited.remove(outside_mst)
    del smallest_distance[outside_mst]
    del nearest_neighbour[outside_mst]

    # update dictionaries
    for n in outside_mst.get_neighbours():
        if n in unvisited:
            if n not in smallest_distance:
                smallest_distance[n] = outside_mst.get_weight(n)
                nearest_neighbour[n] = mst.get_vertex(outside_mst.get_key())
            else:
                if smallest_distance[n] > outside_mst.get_weight(n):
                    smallest_distance[n] = outside_mst.get_weight(n)
                    nearest_neighbour[n] = mst.get_vertex(outside_mst.get_key())

return mst

g = Graph() print('Undirected Graph') print('Menu') print('add vertex <key>') print('add edge <src> <dest> <weight>') print('mst') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        weight = int(do[4])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest, weight)
                g.add_edge(dest, src, weight)
            else:
                print('Edge already exists.')

elif operation == 'mst':
    mst = mst_prim(g)
    print('Minimum Spanning Tree:')
    mst.display()
    print()

elif operation == 'display':
    g.display()
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

class Queue: def __init__(self): self.items = []

def is_empty(self):
    return self.items == []

def enqueue(self, data):
    self.items.append(data)

def dequeue(self):
    return self.items.pop(0)

def display_bfs(vertex): """Display BFS Traversal starting at vertex.""" visited = set() q = Queue() q.enqueue(vertex) visited.add(vertex) while not q.is_empty(): current = q.dequeue() print(current.get_key(), end=' ') for dest in current.get_neighbours(): if dest not in visited: visited.add(dest) q.enqueue(dest)

g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('bfs <vertex key>') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest)
            else:
                print('Edge already exists.')

elif operation == 'bfs':
    key = int(do[1])
    print('Breadth-first Traversal: ', end='')
    vertex = g.get_vertex(key)
    display_bfs(vertex)
    print()

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

class Graph: def __init__(self):

    # dictionary containing keys that map to the corresponding vertex object
    self.vertices = {}

def add_vertex(self, key):
    """Add a vertex with the given key to the graph."""
    vertex = Vertex(key)
    self.vertices[key] = vertex

def get_vertex(self, key):
    """Return vertex object with the corresponding key."""
    return self.vertices[key]

def __contains__(self, key):
    return key in self.vertices

def add_edge(self, src_key, dest_key, weight=1):
    """Add edge from src_key to dest_key with given weight."""
    self.vertices[src_key].add_neighbour(self.vertices[dest_key], weight)

def does_edge_exist(self, src_key, dest_key):
    """Return True if there is an edge from src_key to dest_key."""
    return self.vertices[src_key].does_it_point_to(self.vertices[dest_key])

def __iter__(self):
    return iter(self.vertices.values())

class Vertex: def __init__(self, key): self.key = key self.points_to = {}

def get_key(self):
    """Return key corresponding to this vertex object."""
    return self.key

def add_neighbour(self, dest, weight):
    """Make this vertex point to dest with given edge weight."""
    self.points_to[dest] = weight

def get_neighbours(self):
    """Return all vertices pointed to by this vertex."""
    return self.points_to.keys()

def get_weight(self, dest):
    """Get weight of edge from this vertex to dest."""
    return self.points_to[dest]

def does_it_point_to(self, dest):
    """Return True if this vertex points to dest."""
    return dest in self.points_to

def dfs(v, pre, post): """Display DFS traversal starting at vertex v. Stores pre and post times in dictionaries pre and post.""" dfs_helper(v, set(), pre, post, [0])

def dfs_helper(v, visited, pre, post, time): """Display DFS traversal starting at vertex v. Uses set visited to keep track of already visited nodes, dictionaries pre and post to store discovered and finished times and the one-element list time to keep track of current time.""" visited.add(v) time[0] = time[0] + 1 pre[v] = time[0] print('Visiting {}... discovered time = {}'.format(v.get_key(), time[0])) for dest in v.get_neighbours(): if dest not in visited: dfs_helper(dest, visited, pre, post, time) time[0] = time[0] + 1 post[v] = time[0] print('Leaving {}... finished time = {}'.format(v.get_key(), time[0]))

g = Graph() print('Menu') print('add vertex <key>') print('add edge <src> <dest>') print('dfs <vertex key>') print('display') print('quit')

while True: do = input('What would you like to do? ').split()

operation = do[0]
if operation == 'add':
    suboperation = do[1]
    if suboperation == 'vertex':
        key = int(do[2])
        if key not in g:
            g.add_vertex(key)
        else:
            print('Vertex already exists.')
    elif suboperation == 'edge':
        src = int(do[2])
        dest = int(do[3])
        if src not in g:
            print('Vertex {} does not exist.'.format(src))
        elif dest not in g:
            print('Vertex {} does not exist.'.format(dest))
        else:
            if not g.does_edge_exist(src, dest):
                g.add_edge(src, dest)
            else:
                print('Edge already exists.')

elif operation == 'dfs':
    key = int(do[1])
    print('Depth-first Traversal: ')
    vertex = g.get_vertex(key)
    pre = dict()
    post = dict()
    dfs(vertex, pre, post)
    print()

elif operation == 'display':
    print('Vertices: ', end='')
    for v in g:
        print(v.get_key(), end=' ')
    print()

    print('Edges: ')
    for v in g:
        for dest in v.get_neighbours():
            w = v.get_weight(dest)
            print('(src={}, dest={}, weight={}) '.format(v.get_key(),
                                                         dest.get_key(), w))
    print()

elif operation == 'quit':
    break

def bubble_sort(array): n = len(array)

for i in range(n):
    # Create a flag that will allow the function to
    # terminate early if there's nothing left to sort
    already_sorted = True

    # Start looking at each item of the list one by one,
    # comparing it with its adjacent value. With each
    # iteration, the portion of the array that you look at
    # shrinks because the remaining items have already been
    # sorted.
    for j in range(n - i - 1):
        if array[j] > array[j + 1]:
            # If the item you're looking at is greater than its
            # adjacent value, then swap them
            array[j], array[j + 1] = array[j + 1], array[j]

            # Since you had to swap two elements,
            # set the `already_sorted` flag to `False` so the
            # algorithm doesn't finish prematurely
            already_sorted = False

    # If there were no swaps during the last iteration,
    # the array is already sorted, and you can terminate
    if already_sorted:
        break

return array

def insertion_sort(array):

# Loop from the second element of the array until
# the last element
for i in range(1, len(array)):
    # This is the element we want to position in its
    # correct place
    key_item = array[i]

    # Initialize the variable that will be used to
    # find the correct position of the element referenced
    # by `key_item`
    j = i - 1

    # Run through the list of items (the left
    # portion of the array) and find the correct position
    # of the element referenced by `key_item`. Do this only
    # if `key_item` is smaller than its adjacent values.
    while j >= 0 and array[j] > key_item:
        # Shift the value one position to the left
        # and reposition j to point to the next element
        # (from right to left)
        array[j + 1] = array[j]
        j -= 1

    # When you finish shifting the elements, you can position
    # `key_item` in its correct location
    array[j + 1] = key_item

return array

def merge(left, right):

# If the first array is empty, then nothing needs
# to be merged, and you can return the second array as the result
if len(left) == 0:
    return right

# If the second array is empty, then nothing needs
# to be merged, and you can return the first array as the result
if len(right) == 0:
    return left

result = []
index_left = index_right = 0

# Now go through both arrays until all the elements
# make it into the resultant array
while len(result) < len(left) + len(right):
    # The elements need to be sorted to add them to the
    # resultant array, so you need to decide whether to get
    # the next element from the first or the second array
    if left[index_left] <= right[index_right]:
        result.append(left[index_left])
        index_left += 1
    else:
        result.append(right[index_right])
        index_right += 1

    # If you reach the end of either array, then you can
    # add the remaining elements from the other array to
    # the result and break the loop
    if index_right == len(right):
        result += left[index_left:]
        break

    if index_left == len(left):
        result += right[index_right:]
        break

return result

def merge_sort(array):

# If the input array contains fewer than two elements,
# then return it as the result of the function
if len(array) < 2:
    return array

midpoint = len(array) // 2

# Sort the array by recursively splitting the input
# into two equal halves, sorting each half and merging them
# together into the final result
return merge(
    left=merge_sort(array[:midpoint]),
    right=merge_sort(array[midpoint:]))

from random import randint

def quicksort(array):

# If the input array contains fewer than two elements,
# then return it as the result of the function
if len(array) < 2:
    return array

low, same, high = [], [], []

# Select your `pivot` element randomly
pivot = array[randint(0, len(array) - 1)]

for item in array:
    # Elements that are smaller than the `pivot` go to
    # the `low` list. Elements that are larger than
    # `pivot` go to the `high` list. Elements that are
    # equal to `pivot` go to the `same` list.
    if item < pivot:
        low.append(item)
    elif item == pivot:
        same.append(item)
    elif item > pivot:
        high.append(item)

# The final result combines the sorted `low` list
# with the `same` list and the sorted `high` list
return quicksort(low) + same + quicksort(high)

Radix sort in Python

Using counting sort to sort the elements in the basis of significant places

def countingSort(array, place): size = len(array) output = [0] size count = [0] 10

# Calculate count of elements
for i in range(0, size):
    index = array[i] // place
    count[index % 10] += 1

# Calculate cumulative count
for i in range(1, 10):
    count[i] += count[i - 1]

# Place the elements in sorted order
i = size - 1
while i >= 0:
    index = array[i] // place
    output[count[index % 10] - 1] = array[i]
    count[index % 10] -= 1
    i -= 1

for i in range(0, size):
    array[i] = output[i]

Main function to implement radix sort

def radixSort(array):

# Get maximum element
max_element = max(array)

# Apply counting sort to sort elements based on place value.
place = 1
while max_element // place > 0:
    countingSort(array, place)
    place *= 10

data = [121, 432, 564, 23, 1, 45, 788] radixSort(data) print(data)

Counting sort in Python programming

def countingSort(array): size = len(array) output = [0] * size

# Initialize count array
count = [0] * 10

# Store the count of each elements in count array
for i in range(0, size):
    count[array[i]] += 1

# Store the cummulative count
for i in range(1, 10):
    count[i] += count[i - 1]

# Find the index of each element of the original array in count array
# place the elements in output array
i = size - 1
while i >= 0:
    output[count[array[i]] - 1] = array[i]
    count[array[i]] -= 1
    i -= 1

# Copy the sorted elements into original array
for i in range(0, size):
    array[i] = output[i]

data = [4, 2, 2, 8, 3, 3, 1] countingSort(data) print("Sorted Array in Ascending Order: ") print(data)

Bucket Sort in Python

def bucketSort(array): bucket = []

# Create empty buckets
for i in range(len(array)):
    bucket.append([])

# Insert elements into their respective buckets
for j in array:
    index_b = int(10 * j)
    bucket[index_b].append(j)

# Sort the elements of each bucket
for i in range(len(array)):
    bucket[i] = sorted(bucket[i])

# Get the sorted elements
k = 0
for i in range(len(array)):
    for j in range(len(bucket[i])):
        array[k] = bucket[i][j]
        k += 1
return array

array = [.42, .32, .33, .52, .37, .47, .51] print("Sorted Array in descending order is") print(bucketSort(array))

Selection sort in Python

def selectionSort(array, size):

for step in range(size):
    min_idx = step

    for i in range(step + 1, size):

        # to sort in descending order, change > to < in this line
        # select the minimum element in each loop
        if array[i] < array[min_idx]:
            min_idx = i

    # put min at the correct position
    (array[step], array[min_idx]) = (array[min_idx], array[step])

data = [-2, 45, 0, 11, -9] size = len(data) selectionSort(data, size) print('Sorted Array in Ascending Order:') print(data)

Dijkstra's Algorithm in Python

import sys

Providing the graph

vertices = [[0, 0, 1, 1, 0, 0, 0], [0, 0, 1, 0, 0, 1, 0], [1, 1, 0, 1, 1, 0, 0], [1, 0, 1, 0, 0, 0, 1], [0, 0, 1, 0, 0, 1, 0], [0, 1, 0, 0, 1, 0, 1], [0, 0, 0, 1, 0, 1, 0]]

edges = [[0, 0, 1, 2, 0, 0, 0], [0, 0, 2, 0, 0, 3, 0], [1, 2, 0, 1, 3, 0, 0], [2, 0, 1, 0, 0, 0, 1], [0, 0, 3, 0, 0, 2, 0], [0, 3, 0, 0, 2, 0, 1], [0, 0, 0, 1, 0, 1, 0]]

Find which vertex is to be visited next

def to_be_visited(): global visited_and_distance v = -10 for index in range(num_of_vertices): if visited_and_distance[index][0] == 0 \ and (v < 0 or visited_and_distance[index][1] <= visited_and_distance[v][1]): v = index return v

num_of_vertices = len(vertices[0])

visited_and_distance = [[0, 0]] for i in range(num_of_vertices-1): visited_and_distance.append([0, sys.maxsize])

for vertex in range(num_of_vertices):

# Find next vertex to be visited
to_visit = to_be_visited()
for neighbor_index in range(num_of_vertices):

    # Updating new distances
    if vertices[to_visit][neighbor_index] == 1 and \
            visited_and_distance[neighbor_index][0] == 0:
        new_distance = visited_and_distance[to_visit][1] \
            + edges[to_visit][neighbor_index]
        if visited_and_distance[neighbor_index][1] > new_distance:
            visited_and_distance[neighbor_index][1] = new_distance

    visited_and_distance[to_visit][0] = 1

i = 0

Printing the distance

for distance in visited_and_distance: print("Distance of ", chr(ord('a') + i), " from source vertex: ", distance[1]) i = i + 1

Kruskal's algorithm in Python

class Graph: def __init__(self, vertices): self.V = vertices self.graph = []

def add_edge(self, u, v, w):
    self.graph.append([u, v, w])

# Search function

def find(self, parent, i):
    if parent[i] == i:
        return i
    return self.find(parent, parent[i])

def apply_union(self, parent, rank, x, y):
    xroot = self.find(parent, x)
    yroot = self.find(parent, y)
    if rank[xroot] < rank[yroot]:
        parent[xroot] = yroot
    elif rank[xroot] > rank[yroot]:
        parent[yroot] = xroot
    else:
        parent[yroot] = xroot
        rank[xroot] += 1

#  Applying Kruskal algorithm
def kruskal_algo(self):
    result = []
    i, e = 0, 0
    self.graph = sorted(self.graph, key=lambda item: item[2])
    parent = []
    rank = []
    for node in range(self.V):
        parent.append(node)
        rank.append(0)
    while e < self.V - 1:
        u, v, w = self.graph[i]
        i = i + 1
        x = self.find(parent, u)
        y = self.find(parent, v)
        if x != y:
            e = e + 1
            result.append([u, v, w])
            self.apply_union(parent, rank, x, y)
    for u, v, weight in result:
        print("%d - %d: %d" % (u, v, weight))

g = Graph(6) g.add_edge(0, 1, 4) g.add_edge(0, 2, 4) g.add_edge(1, 2, 2) g.add_edge(1, 0, 4) g.add_edge(2, 0, 4) g.add_edge(2, 1, 2) g.add_edge(2, 3, 3) g.add_edge(2, 5, 2) g.add_edge(2, 4, 4) g.add_edge(3, 2, 3) g.add_edge(3, 4, 3) g.add_edge(4, 2, 4) g.add_edge(4, 3, 3) g.add_edge(5, 2, 2) g.add_edge(5, 4, 3) g.kruskal_algo()

Huffman Coding in python

string = 'BCAADDDCCACACAC'

Creating tree nodes

class NodeTree(object):

def __init__(self, left=None, right=None):
    self.left = left
    self.right = right

def children(self):
    return (self.left, self.right)

def nodes(self):
    return (self.left, self.right)

def __str__(self):
    return '%s_%s' % (self.left, self.right)

Main function implementing huffman coding

def huffman_code_tree(node, left=True, binString=''): if type(node) is str: return {node: binString} (l, r) = node.children() d = dict() d.update(huffman_code_tree(l, True, binString + '0')) d.update(huffman_code_tree(r, False, binString + '1')) return d

Calculating frequency

freq = {} for c in string: if c in freq: freq[c] += 1 else: freq[c] = 1

freq = sorted(freq.items(), key=lambda x: x[1], reverse=True)

nodes = freq

while len(nodes) > 1: (key1, c1) = nodes[-1] (key2, c2) = nodes[-2] nodes = nodes[:-2] node = NodeTree(key1, key2) nodes.append((node, c1 + c2))

nodes = sorted(nodes, key=lambda x: x[1], reverse=True)

huffmanCode = huffman_code_tree(nodes[0][0])

print(' Char | Huffman code ') print('----------------------') for (char, frequency) in freq: print(' %-4r |%12s' % (char, huffmanCode[char]))

Prim's Algorithm in Python

INF = 9999999

number of vertices in graph

V = 5

create a 2d array of size 5x5

for adjacency matrix to represent graph

G = [[0, 9, 75, 0, 0], [9, 0, 95, 19, 42], [75, 95, 0, 51, 66], [0, 19, 51, 0, 31], [0, 42, 66, 31, 0]]

create a array to track selected vertex

selected will become true otherwise false

selected = [0, 0, 0, 0, 0]

set number of edge to 0

no_edge = 0

the number of egde in minimum spanning tree will be

always less than(V - 1), where V is number of vertices in

graph

choose 0th vertex and make it true

selected[0] = True

print for edge and weight

print("Edge : Weight\n") while (no_edge < V - 1):

# For every vertex in the set S, find the all adjacent vertices
#, calculate the distance from the vertex selected at step 1.
# if the vertex is already in the set S, discard it otherwise
# choose another vertex nearest to selected vertex  at step 1.
minimum = INF
x = 0
y = 0
for i in range(V):
    if selected[i]:
        for j in range(V):
            if ((not selected[j]) and G[i][j]):  
                # not in selected and there is an edge
                if minimum > G[i][j]:
                    minimum = G[i][j]
                    x = i
                    y = j
print(str(x) + "-" + str(y) + ":" + str(G[x][y]))
selected[y] = True
no_edge += 1

The longest common subsequence in Python

Function to find lcs_algo

def lcs_algo(S1, S2, m, n): L = [[0 for x in range(n+1)] for x in range(m+1)]

# Building the mtrix in bottom-up way
for i in range(m+1):
    for j in range(n+1):
        if i == 0 or j == 0:
            L[i][j] = 0
        elif S1[i-1] == S2[j-1]:
            L[i][j] = L[i-1][j-1] + 1
        else:
            L[i][j] = max(L[i-1][j], L[i][j-1])

index = L[m][n]

lcs_algo = [""] * (index+1)
lcs_algo[index] = ""

i = m
j = n
while i > 0 and j > 0:

    if S1[i-1] == S2[j-1]:
        lcs_algo[index-1] = S1[i-1]
        i -= 1
        j -= 1
        index -= 1

    elif L[i-1][j] > L[i][j-1]:
        i -= 1
    else:
        j -= 1

# Printing the sub sequences
print("S1 : " + S1 + "\nS2 : " + S2)
print("LCS: " + "".join(lcs_algo))

S1 = "ACADB" S2 = "CBDA" m = len(S1) n = len(S2) lcs_algo(S1, S2, m, n)

Floyd Warshall Algorithm in python

The number of vertices

nV = 4

INF = 999

Algorithm implementation

def floyd_warshall(G): distance = list(map(lambda i: list(map(lambda j: j, i)), G))

# Adding vertices individually
for k in range(nV):
    for i in range(nV):
        for j in range(nV):
            distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j])
print_solution(distance)

Printing the solution

def print_solution(distance): for i in range(nV): for j in range(nV): if(distance[i][j] == INF): print("INF", end=" ") else: print(distance[i][j], end=" ") print(" ")

G = [[0, 3, INF, 5], [2, 0, INF, 4], [INF, 1, 0, INF], [INF, INF, 2, 0]] floyd_warshall(G)

''' Capacity of knapsack = W weight list : wt = [] price list : pr = [] No. of items = N ''' def kProfit(W,N,wt,pr,dp):

# Base Condition
if N==0 or W==0:
    return 0
# If sub problem is previously solved tehn return it.
if dp[N][W] is not None:
    return dp[N][W]
if wt[N-1] <= W:
    dp[N][W] = max(pr[N-1]+kProfit(W-wt[N-1],N-1,wt,pr,dp), kProfit(W,N-1,wt,pr,dp))
    return dp[N][W]
else:
    dp[N][W] = kProfit(W,N-1,wt,pr,dp)
    return dp[N][W]

if __name__ == '__main__': W = 11 wt = [1, 2, 5, 6, 7] pr = [1, 6, 18, 22, 28] N = len(pr)

# define DP array
dp = [[None] * (W + 1) for _ in range(N + 1)]
# Call for kProfit to calculate max profit
maxProfit = kProfit(W,N,wt,pr,dp)
print('Maximum Profit is : ',maxProfit)

def kProfit(W,N,wt,pr,dp):

# Base Condition
if N==0 or W==0:
    return 0
# If sub problem is previously solved tehn return it.
if dp[N][W] is not None:
    return dp[N][W]
if wt[N-1] <= W:
    dp[N][W] = max(pr[N-1]+kProfit(W-wt[N-1],N-1,wt,pr,dp), kProfit(W,N-1,wt,pr,dp))
    return dp[N][W]
else:
    dp[N][W] = kProfit(W,N-1,wt,pr,dp)
    return dp[N][W]

if __name__ == '__main__': W = 11 wt = [1, 2, 5, 6, 7] pr = [1, 6, 18, 22, 28] N = len(pr)

# define DP array
dp = [[None] * (W + 1) for _ in range(N + 1)]
# Call for kProfit to calculate max profit
maxProfit = kProfit(W,N,wt,pr,dp)
print('Maximum Profit is : ',maxProfit)

def subSum(arr,target): n = len(arr) dp = [[None]*(target+1) for _ in range(n+1)]

# Initialise DP array !!
# If no. of elements in arr are 0 then Target sum is not possible
# Target sum = 0 is always possible i.e, by keeping the array subset as null/phi.
for i in range(target+1):
    dp[0][i] = False
for j in range(n+1):
    dp[j][0] = True

# An element can be chosen only if sum is less han arr[i] else it cannot be included
for i in range(1,n+1):
    for j in range(target+1):
        if arr[i-1] <= j:
            dp[i][j] = dp[i-1][j-arr[i-1]] or dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]

return dp[n][target]

if __name__ == '__main__': arr = [0, 3, 2, 7, 1] target = 6 exists = subSum(arr,target) print('Subset with Target sum exists : ', str(exists))

def LCS(s1,s2,l1,l2): dp = [[None]*(l2+1) for _ in range(l1+1)]

# Initialise dp
# If length of any substring is 0 then length of LCS will be zero
# So dp[0][i] and dp[j][0] will be zero

for i in range(l1+1):
    dp[i][0] = 0
for j in range(l2+1):
    dp[0][j] = 0

# if s1[i] == s2[j] then increase by 1 else search in i-1 and j or i and j-1
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])

# dp[l1][l2] contains the length of LCS of s1 and s2
return dp[l1][l2]

if __name__ == '__main__': s1 = 'abbacdcba' s2 = 'bcdbbcaa' maxlen = LCS(s1,s2,len(s1),len(s2)) print("Length of LCS = ",maxlen)

def SubString(s1,s2,l1,l2):

dp = [[None]*(l2+1) for _ in range(l1+1)] 

# Initialise dp

# If length of any substring is 0 then length of LCS will be zero

# So dp[0][i] and dp[j][0] will be zero 

for i in range(l1+1):

    dp[i][0] = 0

for j in range(l2+1):

    dp[0][j] = 0


# If s1[i] == s2[j] then increase by 1 else dp[i][j] will be 0 as substring will break

for i in range(1,l1+1):

    for j in range(1,l2+1):

        if s1[i-1] == s2[j-1]:

            dp[i][j] = 1 + dp[i-1][j-1]

        else:

            dp[i][j] = 0


maximum = -9999

for i in dp:

    maximum = max(maximum,max(i))

return maximum

if __name__ == '__main__':

s1 = 'aabcdaf'

s2 = 'gbcdf'

maxlen = SubString(s1,s2,len(s1),len(s2))

print("Length of Longest Common Substring  = ",maxlen)

def LCS(s1,s2): l1 = len(s1) l2 = len(s2) dp = [[None]*(l2+1) for _ in range(l1+1)]

# Initialise dp
# If length of any substring is 0 then length of LCS will be zero
# So dp[0][i] and dp[j][0] will be zero

for i in range(l1+1):
    dp[i][0] = 0
for j in range(l2+1):
    dp[0][j] = 0

# if s1[i] == s2[j] then increase by 1 else search in i-1 and j or i and j-1
for i in range(1,l1+1):
    for j in range(1,l2+1):
        if s1[i-1] == s2[j-1]:
            dp[i][j] = 1 + dp[i-1][j-1]
        else:
            dp[i][j] = max(dp[i][j-1],dp[i-1][j])

# dp[l1][l2] contains the length of LCS of s1 and s2
return dp[l1][l2]

def LPS(s):

# Length of the Largest palindromic subsequence is equal to Longest Common Subsequence of string s and reversed(s)
srev = s[::-1]
return LCS(s,srev)

if __name__ == '__main__': s = 'agbdba' length = LPS(s) print(f'Length of the largest Palindromic Subsequence is {length}')

def LarRep(s,s1): n = len(s)

# dp array definition
dp = [[0]*(n+1) for _ in range(n+1)]

# initialisation of dp array
for i in range(1,n+1):
    for j in range(1,n+1):
        # increment count if index not same else chose max from previous sub problems
        if s[i - 1] == s1[j - 1] and i != j:
            dp[i][j] = 1 + dp[i - 1][j - 1]
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[n][n]

if __name__ == '__main__': s = 'aabebcdd' length = LarRep(s,s) print(f"Length of Largest Repeating Subsequence : {str(length)}")

import sys def minCoins(coins,price): n = len(coins)

# define dp array
dp  = [[None]*(price+1) for _ in range(n+1)]

# Initialise DP array
# If price = 0 then min coins needed = 0 considering null set. So dp[i][0] = 0.
# If no. of coins = 0 then we would need infinite coins to get to price. So dp[0][j] = inf -1 ("-1 to avoid overflow)

for j in range(price+1):
    dp[0][j] = sys.maxsize -1
for i in range(n+1):
    dp[i][0] = 0

# A coin can be selected only if its value is less than required price
for i in range(1,n+1):
    for j in range(1,price+1):
        if coins[i - 1] <= j:
            dp[i][j] = min(dp[i - 1][j], 1 + dp[i][j-coins[i-1]]);
        else:
            dp[i][j] = dp[i - 1][j];

return dp[n][price]

if __name__ == '__main__': coins = [1, 4, 6] price = 8 ch = minCoins(coins,price) print(f'Minimum number of coins required : {ch}')

def maxWays(coins,price): n = len(coins)

# Define dp array
dp = [[None]*(price+1) for _ in range(n+1)]

# Initialise dp Array.
# If No of coins available is 0 then there is no way to pay. So dp[0][j] = 0
# If price = 0 then it is possible to pay considering null set. So dp[i][0] = 1

for i in range(n+1):
    dp[i][0] = 1
for j in range(price+1):
    dp[0][j] = 0

# A coin can be used only if its value is less than the price so coin[i] <= price
# Now if a coin is chosen once then it can be included any number of times

for  i in range(1,n+1):
    for j in range(1,price+1):
        # check if coin[i] < price
        if coins[i-1] <= j:
            dp[i][j] = dp[i][j-coins[i-1]] + dp[i-1][j]
        else:
            dp[i][j] = dp[i-1][j]
return dp[n][price]

if __name__ == '__main__': coins = [1,2,3] price = 5 ch = maxWays(coins,price) print('Max Ways to Pay : ', ch)

O(n^2) time

def max_profit_naive(prices): """ :type prices: List[int] :rtype: int """ max_so_far = 0 for i in range(0, len(prices) - 1): for j in range(i + 1, len(prices)): max_so_far = max(max_so_far, prices[j] - prices[i]) return max_so_far

O(n) time

def max_profit_optimized(prices): """ input: [7, 1, 5, 3, 6, 4] diff : [X, -6, 4, -2, 3, -2] :type prices: List[int] :rtype: int """ cur_max, max_so_far = 0, 0 for i in range(1, len(prices)): cur_max = max(0, cur_max + prices[i] - prices[i-1]) max_so_far = max(max_so_far, cur_max) return max_so_far

Python program for weighted job scheduling using Dynamic

Programming and Binary Search

Class to represent a job

class Job: def __init__(self, start, finish, profit): self.start = start self.finish = finish self.profit = profit

A Binary Search based function to find the latest job

(before current job) that doesn't conflict with current

job. "index" is index of the current job. This function

returns -1 if all jobs before index conflict with it.

The array jobs[] is sorted in increasing order of finish

time.

def binary_search(job, start_index):

# Initialize 'lo' and 'hi' for Binary Search
lo = 0
hi = start_index - 1

# Perform binary Search iteratively
while lo <= hi:
    mid = (lo + hi) // 2
    if job[mid].finish <= job[start_index].start:
        if job[mid + 1].finish <= job[start_index].start:
            lo = mid + 1
        else:
            return mid
    else:
        hi = mid - 1
return -1

The main function that returns the maximum possible

profit from given array of jobs

def schedule(job):

# Sort jobs according to finish time
job = sorted(job, key = lambda j: j.finish)

# Create an array to store solutions of subproblems.  table[i]
# stores the profit for jobs till arr[i] (including arr[i])
n = len(job)
table = [0 for _ in range(n)]

table[0] = job[0].profit

# Fill entries in table[] using recursive property
for i in range(1, n):

    # Find profit including the current job
    incl_prof = job[i].profit
    l = binary_search(job, i)
    if (l != -1):
        incl_prof += table[l]

    # Store maximum of including and excluding
    table[i] = max(incl_prof, table[i - 1])

return table[n-1]

def matrix_chain_order(p): n = len(p) - 1 m = [[float('inf')] n for _ in range(n)] s = [[0] n for _ in range(n)]

for i in range(n):
    m[i][i] = 0

for l in range(2, n+1):
    for i in range(n-l+1):
        j = i + l - 1
        for k in range(i, j):
            q = m[i][k] + m[k+1][j] + p[i] * p[k+1] * p[j+1]
            if q < m[i][j]:
                m[i][j] = q
                s[i][j] = k

return m, s

Python3 program to implement traveling salesman

problem using naive approach.

from sys import maxsize from itertools import permutations V = 4

implementation of traveling Salesman Problem

def travellingSalesmanProblem(graph, s):

# store all vertex apart from source vertex 
vertex = [] 
for i in range(V): 
    if i != s: 
        vertex.append(i) 

# store minimum weight Hamiltonian Cycle 
min_path = maxsize 
next_permutation=permutations(vertex)
for i in next_permutation:

    # store current Path weight(cost) 
    current_pathweight = 0

    # compute current path weight 
    k = s 
    for j in i: 
        current_pathweight += graph[k][j] 
        k = j 
    current_pathweight += graph[k][s] 

    # update minimum 
    min_path = min(min_path, current_pathweight) 

return min_path

Driver Code

if __name__ == "__main__":

# matrix representation of graph 
graph = [[0, 10, 15, 20], [10, 0, 35, 25], 
        [15, 35, 0, 30], [20, 25, 30, 0]] 
s = 0
print(travellingSalesmanProblem(graph, s))

Python3 program to solve Knight Tour problem using Backtracking

Chessboard Size

n = 8

def isSafe(x, y, board): ''' A utility function to check if i,j are valid indexes for N*N chessboard ''' if(x >= 0 and y >= 0 and x < n and y < n and board[x][y] == -1): return True return False

def printSolution(n, board): ''' A utility function to print Chessboard matrix ''' for i in range(n): for j in range(n): print(board[i][j], end=' ') print()

def solveKT(n): ''' This function solves the Knight Tour problem using Backtracking. This function mainly uses solveKTUtil() to solve the problem. It returns false if no complete tour is possible, otherwise return true and prints the tour. Please note that there may be more than one solutions, this function prints one of the feasible solutions. '''

# Initialization of Board matrix 
board = [[-1 for i in range(n)]for i in range(n)] 

# move_x and move_y define next move of Knight. 
# move_x is for next value of x coordinate 
# move_y is for next value of y coordinate 
move_x = [2, 1, -1, -2, -2, -1, 1, 2] 
move_y = [1, 2, 2, 1, -1, -2, -2, -1] 

# Since the Knight is initially at the first block 
board[0][0] = 0

# Step counter for knight's position 
pos = 1

# Checking if solution exists or not 
if(not solveKTUtil(n, board, 0, 0, move_x, move_y, pos)): 
    print("Solution does not exist") 
else: 
    printSolution(n, board)

def solveKTUtil(n, board, curr_x, curr_y, move_x, move_y, pos): ''' A recursive utility function to solve Knight Tour problem '''

if(pos == n**2): 
    return True

# Try all next moves from the current coordinate x, y 
for i in range(8): 
    new_x = curr_x + move_x[i] 
    new_y = curr_y + move_y[i] 
    if(isSafe(new_x, new_y, board)): 
        board[new_x][new_y] = pos 
        if(solveKTUtil(n, board, new_x, new_y, move_x, move_y, pos+1)): 
            return True

        # Backtracking 
        board[new_x][new_y] = -1
return False

Driver Code

if __name__ == "__main__":

# Function Call 
solveKT(n)

This code is contributed by AAKASH PAL

Python3 program to solve N Queen

Problem using backtracking

global N N = 4

def printSolution(board): for i in range(N): for j in range(N): if board[i][j] == 1: print("Q",end=" ") else: print(".",end=" ") print()

A utility function to check if a queen can

be placed on board[row][col]. Note that this

function is called when "col" queens are

already placed in columns from 0 to col -1.

So we need to check only left side for

attacking queens

def isSafe(board, row, col):

# Check this row on left side
for i in range(col):
    if board[row][i] == 1:
        return False

# Check upper diagonal on left side
for i, j in zip(range(row, -1, -1),
                range(col, -1, -1)):
    if board[i][j] == 1:
        return False

# Check lower diagonal on left side
for i, j in zip(range(row, N, 1),
                range(col, -1, -1)):
    if board[i][j] == 1:
        return False

return True

def solveNQUtil(board, col):

# Base case: If all queens are placed
# then return true
if col >= N:
    return True

# Consider this column and try placing
# this queen in all rows one by one
for i in range(N):

    if isSafe(board, i, col):

        # Place this queen in board[i][col]
        board[i][col] = 1

        # Recur to place rest of the queens
        if solveNQUtil(board, col + 1) == True:
            return True

        # If placing queen in board[i][col
        # doesn't lead to a solution, then
        # queen from board[i][col]
        board[i][col] = 0

# If the queen can not be placed in any row in
# this column col then return false
return False

This function solves the N Queen problem using

Backtracking. It mainly uses solveNQUtil() to

solve the problem. It returns false if queens

cannot be placed, otherwise return true and

placement of queens in the form of 1s.

note that there may be more than one

solutions, this function prints one of the

feasible solutions.

def solveNQ(): board = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]

if solveNQUtil(board, 0) == False:
    print("Solution does not exist")
    return False

printSolution(board)
return True

Driver Code

if __name__ == '__main__': solveNQ()

This code is contributed by Divyanshu Mehta

Python3 Program for Bad Character Heuristic

of Boyer Moore String Matching Algorithm

NO_OF_CHARS = 256

def badCharHeuristic(string, size): ''' The preprocessing function for Boyer Moore's bad character heuristic '''

# Initialize all occurrence as -1
badChar = [-1]*NO_OF_CHARS

# Fill the actual value of last occurrence
for i in range(size):
    badChar[ord(string[i])] = i;

# return initialized list
return badChar

def search(txt, pat): ''' A pattern searching function that uses Bad Character Heuristic of Boyer Moore Algorithm ''' m = len(pat) n = len(txt)

# create the bad character list by calling 
# the preprocessing function badCharHeuristic()
# for given pattern
badChar = badCharHeuristic(pat, m) 

# s is shift of the pattern with respect to text
s = 0
while(s <= n-m):
    j = m-1

    # Keep reducing index j of pattern while 
    # characters of pattern and text are matching
    # at this shift s
    while j>=0 and pat[j] == txt[s+j]:
        j -= 1

    # If the pattern is present at current shift, 
    # then index j will become -1 after the above loop
    if j<0:
        print("Pattern occur at shift = {}".format(s))

        ''' 
            Shift the pattern so that the next character in text
                aligns with the last occurrence of it in pattern.
            The condition s+m < n is necessary for the case when
            pattern occurs at the end of text
        '''
        s += (m-badChar[ord(txt[s+m])] if s+m<n else 1)
    else:
        '''
        Shift the pattern so that the bad character in text
        aligns with the last occurrence of it in pattern. The
        max function is used to make sure that we get a positive
        shift. We may get a negative shift if the last occurrence
        of bad character in pattern is on the right side of the
        current character.
        '''
        s += max(1, j-badChar[ord(txt[s+j])])

Driver program to test above function

def main(): txt = "ABAAABCD" pat = "ABC" search(txt, pat)

if __name__ == '__main__': main()

This code is contributed by Atul Kumar

(www.facebook.com/atul.kr.007)

Following program is the python implementation of

Rabin Karp Algorithm given in CLRS book

d is the number of characters in the input alphabet

d = 256

pat -> pattern

txt -> text

q -> A prime number

def search(pat, txt, q): M = len(pat) N = len(txt) i = 0 j = 0 p = 0 # hash value for pattern t = 0 # hash value for txt h = 1

# The value of h would be "pow(d, M-1)%q"
for i in range(M-1):
    h = (h*d) % q

# Calculate the hash value of pattern and first window
# of text
for i in range(M):
    p = (d*p + ord(pat[i])) % q
    t = (d*t + ord(txt[i])) % q

# Slide the pattern over text one by one
for i in range(N-M+1):
    # Check the hash values of current window of text and
    # pattern if the hash values match then only check
    # for characters one by one
    if p == t:
        # Check for characters one by one
        for j in range(M):
            if txt[i+j] != pat[j]:
                break
            else:
                j += 1

        # if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1]
        if j == M:
            print("Pattern found at index " + str(i))

    # Calculate hash value for next window of text: Remove
    # leading digit, add trailing digit
    if i < N-M:
        t = (d*(t-ord(txt[i])*h) + ord(txt[i+M])) % q

        # We might get negative values of t, converting it to
        # positive
        if t < 0:
            t = t+q

Driver Code

if __name__ == '__main__': txt = "GEEKS FOR GEEKS" pat = "GEEK"

# A prime number
q = 101

# Function Call
search(pat, txt, q)

This code is contributed by Bhavya Jain

Python3 program for KMP Algorithm

def KMPSearch(pat, txt): M = len(pat) N = len(txt)

# create lps[] that will hold the longest prefix suffix
# values for pattern
lps = [0]*M
j = 0 # index for pat[]

# Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps)

i = 0 # index for txt[]
while (N - i) >= (M - j):
    if pat[j] == txt[i]:
        i += 1
        j += 1

    if j == M:
        print("Found pattern at index " + str(i-j))
        j = lps[j-1]

    # mismatch after j matches
    elif i < N and pat[j] != txt[i]:
        # Do not match lps[0..lps[j-1]] characters,
        # they will match anyway
        if j != 0:
            j = lps[j-1]
        else:
            i += 1

Function to compute LPS array

def computeLPSArray(pat, M, lps): len = 0 # length of the previous longest prefix suffix

lps[0] = 0 # lps[0] is always 0
i = 1

# the loop calculates lps[i] for i = 1 to M-1
while i < M:
    if pat[i] == pat[len]:
        len += 1
        lps[i] = len
        i += 1
    else:
        # This is tricky. Consider the example.
        # AAACAAAA and i = 7. The idea is similar
        # to search step.
        if len != 0:
            len = lps[len-1]

            # Also, note that we do not increment i here
        else:
            lps[i] = 0
            i += 1

Driver code

if __name__ == '__main__': txt = "ABABDABACDABABCABAB" pat = "ABABCABAB" KMPSearch(pat, txt)

This code is contributed by Bhavya Jain