femz Posted November 10, 2016 Share Posted November 10, 2016 Let G be an n×n grid whose edges are labelled with natural numbers. Starting in the top-left corner, consider paths in G reaching the bottom-right corner by walking along edges either down or to the right. The weight of a path is the sum over all numbers encountered along the edges it traverses. Devise an algorithm in pseudo-code that computes the set of all weights of all paths reaching the bottom-right corner (you may assume standard set data structures and operations on them to be available). Give a rough estimation of the running time of your algorithm: is it polynomial, exponential, etc.? Justify your answer. Link to comment Share on other sites More sharing options...
BabcockHall Posted November 11, 2016 Share Posted November 11, 2016 What have you found so far? Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now