Jump to content

e(ho0n3

Senior Members
  • Content Count

    112
  • Joined

  • Last visited

Community Reputation

10 Neutral

About e(ho0n3

  • Rank
    Baryon
  1. It's been a while now and the [math][/math] tags are still not working. What's going on?!
  2. Hi everyone, I'm reading the paper "A Case for RAID" and I'm having difficulty understanding some of the calculations made. Example: So as X gets larger the above gets larger. This makes sense because it will take more time to repair more disks so the average number of second failures will grow. However, I'm not exactly sure how the formula is derived. Can anyone shed some light on this?
  3. How about graphing those functions of yours and seeing for yourself?
  4. I've attached a proof for all those interested. paths.pdf
  5. Thanks to a colleague of mine, I'm now aware of an error in my solution. Basically I didn't consider the repetition of the start and end vertices in the path. So... For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. One can pick j/2 - 1 vertices from M for the path P in mj/2 - 1 ways. The answer then is nj/2mj/2 - 1. Question 2 is similar to question 1 (except M and N are reversed), so the answer is mj/2nj/2 - 1. For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is (mn)(j + 1)/2 - 1. I'll post a proof by induction that my solution is correct later (if it is correct that is).
  6. Here is a simple statement which I've yet to prove satisfactorily: Adding/deleting loops, parallel edges and edges in series does not affect the planarity of a graph. If a graph is planar, then removing anything from it does not create any edge crossings, so the graph remains planar. If a graph is not planar, then adding anything to it will or will not create any edge crosssings, so the graph remains unplanar. Now I have to show that adding (removing) loops, parallel edges and edges in series does not affect the planarity of a(n) planar (unplanar respectively) graph. This is were I stopped. I'm trying to think of a good argument which shows that a planar graph remains planar after the addition of loops. I'm guessing I'll have to describe a process that can add loops without creating edge crossings. Any tips?
  7. 1. If Carl lied, then Dave is telling the truth. If Dave lied, then Carl is telling the truth. Since exactly one of them told the truth, Andy and Bob are liars. Hence Dave "did it". 2. Seems impossible if Carl, Bob, Andy and Dave are distinct persons. 3. If what Andy and Dave said is true, then Carl did it.
  8. Rings are groups with fancier properties. Fields are rings with more fancy properties. Algebras are even fancier and so on I think. Primarygun: I have a list of tough discrete maths. questions which I haven't answered yet. I can send it to you if you want to. Just PM me.
  9. I know what an adjancency matrix is. Actually, I asked this question because I need to derive the jth power adjencency matrix of K[m,n]. In other words, if A is the adjencency matrix of K[m,n], derive a formula for the members of Aj.
  10. According to my book, a path can have repeated vertices. A path with no repeated vertices is called a simple path.
  11. So much for that...I still believe this problem is solvable using a delta-epsilon argument.
  12. Let K[m,n] be a complete bipartite graph and let M and N be the set of vertices with |M| = m and |N| = n such that every edge is incident on one vertex in M and one vertex in N. I have three questions: 1. If v and w are in M, how many paths are there from v to w of length j? 2. If v and w are in N, how many paths are there from v to w of length j? 3. If v is in M and w is in N, how many paths are there from v to w of length j? For questions 1 and 2, if j is odd, the answer is 0. For question 3, if j is even, the answer is also 0. (I can prove this if anybody is interested). For question 1, assume j is even and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. How many odd-numbered index vertices are there? Easy, j/2. Once can choose j/2 vertices from N for the path P in nj/2 ways. How many even-numbered index vertices are there in P, excluding v[0] and v[j]? Easy, j/2 - 1. If v[0] = v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 1)j/2 - 1 ways. If v[0] ≠ v[j], one can pick j/2 - 1 vertices from M for the path P in (m - 2)j/2 - 1 ways. So the answer to question 1 is - nj/2(m - 1)j/2 - 1 if v[0] = v[j] - nj/2(m - 2)j/2 - 1 if v[0] ≠ v[j] Question 2 is similar to question 1 (except M and N are reversed), so the answer is - mj/2(n - 1)j/2 - 1 if v[0] = v[j] - mj/2(n - 2)j/2 - 1 if v[0] ≠ v[j] For question 3, assume j is odd and let P = (v[0], v[1], v[2], ..., v[j]) be a path from v = v[0] to w = v[j]. Notice that vertices with an odd-numbered index belong to N and those with an even-numbered index belong to M. There are (j + 1)/2 - 1 vertices having even index, excluding v[0]. There are also (j + 1)/2 - 1 vertices having odd index, excluding v[j]. Hence, the answer to the question is ((m - 1)(n - 1))(j + 1)/2 - 1. Am I correct here?
  13. You'll notice, if/when you take more maths. courses, that maths. books rarely make use of actual numbers. Mathematics isn't only about numbers. Haven't you studied any algorithms in your discrete maths. course?
  14. This is a no no. You can't use the Taylor series expansion because Taylor series are constructed using derivatives and derivatives automatically imply continuity. You destroy the purpose of this exercise by 'omitting' the proof. You're doing it again. Naturally, but if the point is an arbitrary point in the domain of the function in question, then it follows that the function in question is continuous in its domain.
  15. Yes they do repeat infinitely. If the numbers you use contain a finite number of digits, then you are not dealing with the reals, but rather a subset of them.
×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.