Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Homework Assignment #4 - DP & Graph

CSE 310 Fall 2022

PART 1 - Dynamic Programming (Longest Common Subsequence) (2 + 2 pts)

Use the Dynamic Programming-based LCS-LENGTH algorithm introduced in class to figure out an LCS of sequences

X = < 1, 0, 0, 1, 0, 1, 0, 1 > and

Y = < 0, 1, 0, 1, 1, 0, 1, 1, 0 > 

A. Show us the fulfilled 9x10 table c that keeps track of the LSC length at the final state..

B. Recall we also briefly talked about that we may use another identically dimensioned table b to construct an actual LCS. Show us the final 9x10 table b that shows how you construct an LCS of X and Y step by step. (Just the final table, and there are more than one correct answers)

PS. You could work on Question B first and then Question A would be pretty obvious.

PART 2 - Prim's and Kruskal's MST (2.5 + 2.5 pts)

 

A. Use Prim's algorithm (the node-oriented method) to find the minimal spanning tree for the above undirected weighted graph. Use the nodes' alphabetical order to break ties. List down the order of the edges being added. PS. You may start at any node because this will not alter the final result.

B. Use Kruskal's algorithm (the edge-oriented method) to find the minimal spanning tree for the above undirected weight graph. Use the nodes' alphabetical order to break ties. List down the order of the edges being added.

PART 3 - Single Source Shortest Paths with Dijkstra's (5 + 1 pts)

 

A. Use Dijkstra's to find out the shortest paths from Node a to all others and the corresponding paths taken. You may use the following empty table or those in the appendix as a template. Row Visited is to help you to identify whether the node is part of the selection. PS. You only need to show us the states at Iteration 0, Iteration 1, Iteration 2, Iteration 3, and Iteration Final tables.

E.g. At the Initialization stage, the table would look like:

Nodes

a

b

c

d

e

f

g

h

z

Visited

False

False

False

False

False

False

False

False

False

Distance

INF

INF

INF

INF

INF

INF

INF

INF

INF

Parent

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

NIL

B. Give us an example to show that Dijkstra's does NOT work with negative edge weights.

Appendix - Full template for PART 3 Question A

Iteration 0

Nodes

a

b

c

d

e

f

g

h

z

Visited

 

 

 

 

 

 

 

 

 

Distance

 

 

 

 

 

 

 

 

 

Parent

 

 

 

 

 

 

 

 

 

Iteration 1

Nodes

a

b

c

d

e

f

g

h

z

Visited

 

 

 

 

 

 

 

 

 

Distance

 

 

 

 

 

 

 

 

 

Parent

 

 

 

 

 

 

 

 

 

Iteration 2

Nodes

a

b

c

d

e

f

g

h

z

Visited

 

 

 

 

 

 

 

 

 

Distance

 

 

 

 

 

 

 

 

 

Parent

 

 

 

 

 

 

 

 

 

Iteration 3

Nodes

a

b

c

d

e

f

g

h

z

Visited

 

 

 

 

 

 

 

 

 

Distance

 

 

 

 

 

 

 

 

 

Parent

 

 

 

 

 

 

 

 

 

Final

Nodes

a

b

c

d

e

f

g

h

z

Visited

 

 

 

 

 

 

 

 

 

Distance

 

 

 

 

 

 

 

 

 

Parent