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,