C200 Programming Assignment ?
C200 Programming Assignment
Problem 1: Sierpinski Triangle
Assignment 12 Last Assignment
Introduction
In this homework, you’ll work on translating critical thinking to programming. The problems are
really fun–so, enjoy! Because this is the last assignment, some of the specifications for output
are not presented–you’ll need to follow the directions closely. Please start this assignment as
soon as possible.
• Add a new folder to your C200 folder named Assignment12. In this folder you’ll have the
following Python files:
– striangle.py
– bestgraph.py
– fullbfs.py
– pagerank.py
– huffman.py
– codd.py
• Make sure and commit your project and modules by 11pm, April 26th 2019.
As always, all the work should be your own. You will complete this before 11pm April 26th 2019.
You will submit your work by committing your code to your GitHub repository. You will not turn
anything in on canvas. If your timestamp is 11:01P or greater, the homework cannot be graded.
So do not wait until 10:58P to commit your solution. During the last week of classes, the servers
tend to become much slower–for safety’s sake, submit often. As always, all the work should be
your own!
Assignment 12 Last Assignment Page 3
Problem 1: Sierpinkski Triangle
The Polish mathematician Seirpinski is associated with a fractal pattern of an equilateral triangle
that is recursively drawn smaller within the larger triangle. One is shown below, the output of
the program you’ll write. Here is the simple algorithm:
Figure 1: A Sierpinkski Triangle. We’ve used random colors as we recursively draw smaller
triangles. This is what gives it the psychodelic look!
1 #def s(loc, width):
2 # if width > 1:
3 # Draw a triangle at loc using width
4 # s(top, width/2)
5 # s(L, width/2)
6 # s(R, width/2)
7 # else:
8 # return
9 #
10 # L,R are 1/2 distance on the original sides
Look at the following illustration (Fig. 3). The upper-left image is the first triangle drawn. We
can specify it completely by giving it the top coordinate and width, because it’s an equilateral
triangle. We make it easy and assume we want it to be as far left and up as possible. The
next step is to draw three smaller triangles (width is now half as much whose tops are pointed
to by the yellow arrows in the illustration on the right. We can easily find these values, again,
because this is an equilateral triangle. The third illustration is shows the recursion going deeper–
we continue drawing triangles yielding the final triangle (this time we used only two colors) to
the right.
Assignment 12 Last Assignment Page 4
Figure 2: Process of drawing the triangles. We redraw triangles with half the width using the
original top, and the midpoints of the left and right sides. The image is the output of the pgoram.
Figure 3: Placing of the triangles.
We can use pygame and Pythagorean’s Theorem to write a Python program that help us to
deteremine the tops (locations of the triangles).
We need to find z where w is some arbitrary width.
(w2)2 + z2 = w2 (1)
We use pygame.draw.polygon to draw a triangle. We need to give a surface, a color, three
points, and a non-zero value to indicate we don’t want it to fill. You’ll need to only complete the
recursive function and triangle function.
Assignment 12 Last Assignment Page 5
Listing 1: striangle.py
1 import pygame, sys
2 import math
3 from pygame.locals import *
4 import random as rn
5 pygame.init()
6
7 BLUE = (0,0,255)
8 WHITE = (255,255,255)
9
10 DISPLAYSURF = pygame.display.set_mode((500, 400), 0, 32)
11
12 pygame.display.set_caption(’S-Triangle’)
13
14 #INPUT takes a location loc = (x,y) pair of points and width
15 #RETURN 3 points of the equilateral triangle determined by loc and width
16 def triangle(loc,width):
17 #TO DO: Implement function
18
19 DISPLAYSURF.fill(WHITE)
20
21 #Draws Triangle
22 #(triangle(loc,w)) is a tuple of tuples...)
23 def draw_triangle(loc, w):
24 pygame.draw.polygon(DISPLAYSURF, BLUE , (triangle(loc,w)),1)
25
26 #INPUT location and width
27 #RETURN nothing -- follows algorithm
28 def s(loc,width):
29 #TO DO: Implement Function
30
31 s((0,0),440)
32
33 while True:
34 for event in pygame.event.get():
35 if event.type == QUIT:
36 pygame.quit()
37 sys.exit()
38 pygame.display.update()
Assignment 12 Last Assignment Page 6
Programming Problem 1: Siepinkski Triangle
• The starting code is in the file triangle.txt.
• My advice is to FIRST draw a single triangle – don’t begin with the recursion outright.
• Complete the functions above. Your output should look like the ones here or shown
on the web.
• For extra credit, display the triangle with random colors throughout the recursion.
• Put your code into a new module named striangle.py
Assignment 12 Last Assignment Page 7
Problem 2: Graph Class
In class we implemented a graph class. To instantiate the graph, we had to know the nodes a
priori. We didn’t have a way to mange the graph either–to delete information. We also learned
how to use linear algebra to find when one node is reachable from another.
1 class Graph:
2 def __init__(self,nodes):
3 self.nodes = nodes
4 self.edges = {}
5 for i in self.nodes:
6 self.edges[i] = []
7 def add_edge(self, pair):
8 start,end = pair
9 self.edges[start].append(end)
10 def children(self,node):
11 return self.edges[node]
12 def nodes(self):
13 return str(self.nodes)
14 def __str__(self):
15 return str(self.edges)
Here’s a small example to reinforce the concept.
Figure 4: A graph of order 4.
1 import numpy as np
2 a = np.zeros ((4,4),dtype = int)
3 a[0][1] = 1
4 a[1][2] = 1
5 a[2][3] = 1
6 print(a)
7 a = np.dot (a,a) + a
8 print(a)
Assignment 12 Last Assignment Page 8
9 a = np.dot (a,a) + a
10 print(a)
11
12 for i in range(0,4):
13 for j in range(0,4):
14 if not i == j:
15 print("{0} reaches {1}: {2}".format(i+1,j+1,bool(a[i][j])))
Session Output 1
[[0 1 0 0]
[0 0 1 0]
[0 0 0 1]
[0 0 0 0]]
[[0 1 1 0]
[0 0 1 1]
[0 0 0 1]
[0 0 0 0]]
[[0 1 2 2]
[0 0 1 2]
[0 0 0 1]
[0 0 0 0]]
1 reaches 2: True
1 reaches 3: True
1 reaches 4: True
2 reaches 1: False
2 reaches 3: True
2 reaches 4: True
3 reaches 1: False
3 reaches 2: False
3 reaches 4: True
4 reaches 1: False
4 reaches 2: False
4 reaches 3: False
Assignment 12 Last Assignment Page 9
Change
• Allow the user add edges (x,y) when x is not currently in the graph. Return 1 if
successful and -1 if the edge already exists.
• Add a method add_node(n) that simply adds a new node. Return 1 if successful
and -1 if the node already exists.
• Add a method del_node(n) that deletes a node and any edges associated with it.
Return 1 if successulf and -1 if no node existed to delete
• Add a method del_edge((x,y)) that deletes the edge. Return 1 if successful and -1
if no edge existed to delete.
• Add a method reachable(x,y) that returns True if there exists a path from node x to
node y, and False if no path exists. Use the transitive closure operation to determine
this. You can use the numpy dot method or use your own matrix multiplication
function you previously wrote.
• Put your code in a module named bestgraph.py
• At this point, don’t worry about the size of the graphs–they won’t be more than 20
or so nodes.
• For extra credit, use a table to save your graph. You should be able to open the
table and create the graph as well.
Assignment 12 Last Assignment Page 10
Problem 3: BFS
For the following problem, use your graph class from above. In class we studied BFS. Although
we discussed the algorithm, we didn’t provde the code. In the graph above, the BFS will visit
Figure 5: A graph of order 8.
all nodes if starting with 1; however, any other node will not lead to all nodes being visited. BFS
actually keeps track of not only visited nodes, but unvisited. Unvisited nodes are the nodes that
are in the graph, but the BFS doesn’t visit them when the visited doesn’t change.
For example, u = f1; 2; 3; 4; 5; 6; 7; 8g (u is unvisited). We do a BFS(G, 5). We’ll see: 5,6,7,4
or 5,6,4,7 (either one). If v = f5; 6; 7; 4g, then we must look at u v = f1; 2; 3; 8g. You can use
the BFS shown in lecture as a starting point–you must obviously include a queue class.
1 def bfsfull(g,node):
2 #TO DO: Implement function
3
4 g = Graph([1,2,3,4,5,6,7,8])
5 elst = [(1,2),(1,3),(2,8),(3,5),(3,4),(5,6),(6,4),(6,7)]
6 for i in elst:
7 g.add_edge(i)
8 print(g.edges)
9 bfsfull(g,5)
Assignment 12 Last Assignment Page 11
Session Output
{1: [2, 3], 2: [8], 3: [5, 4],
4: [], 5: [6], 6: [4, 7], 7: [], 8: []}
We start at 5; 6 is the only child. Then 4,7. We pick randomly 1; 2,3 are children and 8 last.
Programming Problem 3: BFS
• Complete the function.
• Put your code for this problem in a new module named fullbfs.py.
Assignment 12 Last Assignment Page 12
Problem 4: Page Rank
Page Rank is currently one of the most significant algorithms, because it’s the way Google
(>90% of search engine market share) ranks pages. The actual current algorithm is much
more complex, but fundamentally works as we’ll show here. You’ll write a Python program to
rank some pages. What you’ll be happy to know is that you already possess the knowledge to
determine this–matrix multiplication.
Figure 6: HTML pages (blue numbered boxes) and links denoted by arrows. Page 0 has, for
example, a link to page 3 highlighted in yellow. Page 0 also links to 2 and 1.
The next step is to create a stochastic matrix. In this kind of matrix, the rows representing