femz

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.

can you please elaborate

thanks guys, i actually don't know it atall. so,i waited to get more answer so i can compare

Kindly help with the following questions 1. Suppose that we have to distribute n indistinguishable apples between k dis- tinguishable baskets. How many ways can we do that? Please explain your answer. Provide solution to the question assuming that there are more apples than baskets and no basket is empty. 2. Suppose a social network contains a number of people, each of whom has one of two “opinions” (e.g. a preference for Mac versus PC). Each person is connected with a set of “friends”, some of the other people in the network. You can choose any person in the network and let them see the opinions of their friends, and if most of the friends have the same opinion, them the chosen person will change their opinion to the one shared by the majority of their friends. If there’s an equal split, you can choose their opinion. Assuming the network is connected, can we always find a sequence of people so as to ensure that they all end up with the same opinion?