Cynamic programming min cost

There are n trading posts along a river. At any of the posts you can rent a canoe to be returned at any other post downstream. (It is next to impossible to paddle against the current.) For each possible departure point i and each possible arrival point j the cost of a rental from i to j is known. However, it can happen that the cost of renting for i to j is higher that the total cost of a series of shorter rentals. In this case you can return the first canoe at some post k between i and j and continue your journey in a second canoe. There is no extra charge for changing canoes in this way. Give an efficient algorithm to determine the minimum cost of a trip by canoe for each possibl... click for more

Several Problems

(See attached file for full problem description with proper symbols) --- 2. Let f(x) = x2 +1 and g(x) = {x+1, x> =3; x-1, x<3 so both f and g map R into Find the formula for a. (f+g)(x) b. (f .g)(x) c. (f o g)(x) d. (g o f)(x) 3. Let A = {a,b,c,d} and B = {1,2,3} and let f : A  B be a function . Let g : Z  2Z, where 2Z = {0,+-2,+-4,+-6 …} a. Could f be one to one? Must f be one to one? Explain b. Could f be onto? Must f be onto? Explain c. Could g be one to one? Must g be one to one? Explain d. Could g be onto? Must g be onto? Explain 4. Let ≡ be the relation on Z given by n ≡ m mod 5 iff 5|(n-m). Show that equivalence mod 5 is an equivalen... click for more

Graph proof

Let G be an undirected graph, and let T be the spanning tree genereted by a depth-first search of G. Prove that an edge of G that has no corresponding edge in T cannot join nodes in differect branches of the tree, but must necessarily join some node v to one of its ancestors in T.

Discrete mathematics questions

(See attached file for full problem description with proper symbols and equations) --- 1)Prove that for any non-empty sets A x (B-C) = (AxB)-(AxC) 2) Let a,b be integers and m a positive integer. Prove that: ab = [(a mod m ) * (b mod m) mod m ] 3)Prove or disprove (a mod m) + (b mod m) = (a+b) mod m for all integers a and b whenever m is a positive integer. 4) prove that floor(n/2) * ceiling(n/2) = floor (n2/4) 5) For any integer n show that 7n+1 and 15n+2 are relatively prime 6) By induction show that 1*2*3 + 2*3*4 +…n(n+1)(n+2) = n(n+1)(n+2)(n+3)/4 ---

Discrete mathematics

Proper walk through of following proofs required ( for a better understanding ) --- 1) Prove that if n is an odd integer then n2 = 1 mod 8 ( I suppose I would need to examine the case where k is odd and k is even.. but I am getting stuck along the way..) 2) Prove that 5n+3 is divisible by 4 for all integers n>=0 I can't seem to complete this properly I get to something in the likes of 5k+5k+3 and I don't know what to do next.. I need a proper walk through ---