Task1:
1.Suppose you have some algorithm with the running time T=O(n2).
How much slower does this algorithm get when you:
(a) Double the input size
(b) Increase the input size by one?
2. How could either a Stack or a Queue be used to reverse strings of text?
Consider some string like, “This is a string of text”.
Create pseudo code to take in a string, insert each symbol into a stack/queue, using the
stack/queue generate the reverse string.
Provide only the pseudo code for this question.
3. Which data structure did you use for the previous question? A stack or queue?
Justify your answer. Explain why this structure would allow the reversal of a string while
the other data structure would not.
4.Prove the correctness of the insertion sort algorithm.
Hw7
Graph Algorithms
First, review the DFS and BFS algorithms from our textbook. Next, Review the provided Python Examples at the end of this homework document. These are 2 separate examples. One for BFS and one for DFS.
Part 1:
For both the DFS and BFS algorithms, answer the following:
– Describe this algorithm in your own words. What are the steps for searching any tree using these algorithms?
– Describe the trees that can be used with DFS and BFS. What are the limitations of these trees?
Part 2:
For both Python examples, answer the following:
– Describe the example code. What is it? What does it do?
– Give several screenshots for your program running in Idle. Run it, Demonstrate how it works.
– Change the DFS code to search for a different nodes. For example, it is currently searching for node ‘a’, change this to search for node ‘d’:
dfs(gdict, ‘a’)
to
dfs(gdict, ‘d’)
– Change the BFS code to search for a different nodes.
– Describe, in your own words, how this DFS and BFS search works in this Python example.
Part 3:
– First, draw some tree of exactly 21 uniquely named elements. Give a picture of this tree showing the elements and their connections. This tree should be unique and ORIGINAL. Create a new one.
– Next, change the code for DFS to represent this specific tree from your image.
– Show several different searches in Python. For each search, DRAW the operations that would occur in your tree during a DFS search.
Submit a document with your answers and pseudo code, screenshots, and Python source code to Canvas by the due date. Do not submit as Zip or archive.
DFS CODE:
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
# Check for the visisted and unvisited nodes
def dfs(graph, start, visited = None):
if visited is None:
visited = set()
visited.add(start)
print(start)
for next in graph[start] – visited:
dfs(graph, next, visited)
return visited
gdict = {
“a” : set([“b”,”c”]),
“b” : set([“a”, “d”]),
“c” : set([“a”, “d”]),
“d” : set([“e”]),
“e” : set([“a”])
}
dfs(gdict, ‘a’)
BFS CODE:
import collections
class graph:
def __init__(self,gdict=None):
if gdict is None:
gdict = {}
self.gdict = gdict
def bfs(graph, startnode):
# Track the visited and unvisited nodes using queue
seen, queue = set([startnode]), collections.deque([startnode])
while queue:
vertex = queue.popleft()
marked(vertex)
for node in graph[vertex]:
if node not in seen:
seen.add(node)
queue.append(node)
def marked(n):
print(n)
# The graph dictionary
gdict = {
“a” : set([“b”,”c”]),
“b” : set([“a”, “d”]),
“c” : set([“a”, “d”]),
“d” : set([“e”]),
“e” : set([“a”])
}
bfs(gdict, “a”)
