ECE 241 – HOMEWORK 4

ECE 241 – HOMEWORK 4
Answer the following Question and upload your .py files to gradescope with
the naming scheme provided.
Example: (question1.py, question2.py, question3.py)
Questions
1. Longest Palindrome Problem: Dynamic Programming (30 points)
You are given a string of length greater than 0 and less than 1000. Find the Longest
palindrome. https://en.wikipedia.org/wiki/Palindrome
What is the run-time complexity of the solution?
The code template has been provided. All Answers should be provided in the code.
2. Farmer’s Fence (40 points) ( Greedy ) A farmer wants to build a fence
around his rectangular (a x b) field (see figure below). The planks that can be used to
build the fence are of length plankList = [1,5,10, 21, 25]. The corresponding colors of the
planks are plankColor = {1:'black',5:'red',10:'black',21:'green',25:'violet'}. Using dynamic
programing choose the least number of planks to make ‘a’ and ‘b’ dimension of the
rectangle.
Code template has been provided.

3. Tree Traversal (10 Points)
Tree/Graph traversal can be done in multiple ways. The basic methods of graph traversal
are Breadth First Search and Depth First Search.
https://en.wikipedia.org/wiki/Tree_traversal
https://en.wikipedia.org/wiki/Graph_traversal
In the Template provided, show which tree traversal method is best suited for each solution.
Note: the results won’t be shown in Gradescope, you will see the results and your total
score after due.
4. Dijkstra’s Algorithm (20 points):
Consider the following network. With the indicated link costs, use Djikstra’s shortestpath algorithm to compute the table of shortest paths from A to all other network nodes.
Show how the algorithm works by filling out the table below. Use column “N’” for “all
visited nodes in current step”, and each row for “distance and predecessor of each
destination node once a new node is visited”.
Your solution should be in a table format as shown below. You can submit images or pdf
files to gradescope.
A
B
C E
F
D
G
H
8
13
5
2
2
5
2
2
1
1
3
3
6
6
N’ D(B),
P(B)
D(C),
P(C)
D(D),
P(D)
D(E),
P(E)
D(F),
P(F)
D(G),
P(G)
D(H),
P(H)
A,