Lab 6: Dynamic Programming, Project, and Pathfinder

Part 0: Project Topic.

If any of the following are true, do not proceed until you have clarified each item:

  1. You do not have a project topic.
  2. You have not read Lekan’s feedback on your topic.
  3. You aren’t sure what your topic actually is, at a high level.

Part 1: Proofs

Prove the following:

  1. (Direct Proof Warmup) Prove that every odd integer is the difference of two square numbers.
  2. (Proof by Contradiction Warmup) Prove that there is no largest rational number.
  3. Prove or disprove, that, if n^2 is odd, then n is odd.
  4. In logic, the contrapositive of a statement p\Rightarrow q is defined as \neg q \Rightarrow \neg p. Prove or disprove that the contrapositive of a statement is equivalent to the original statement.
  5. (Extension) In logic, the inverse of a statement p\Rightarrow q is defined as \neg p \Rightarrow \neg q. Prove or disprove that the inverse of a statement is equivalent to the original statement.
  6. Prove or disprove that sqrt(3) is irrational.
  7. r is a rational number. i is an irrational number. Prove or disprove that r + i is irrational.
  8. (Extension) For a,b\in \Re, prove or disprove that a^2 + b^2 \geq 2ab.
  9. Prove or disprove that every natural number divisible by 10 is the sum of two primes.
  10. Prove or disprove that x^3+x+1=0 has no rational sotlusions for x
  11. (Extension) Prove or disprove that x^3+x^2+1=0 has no rational solutions for x.
  12. Prove or disprove that every non-zero rational number is the product of two irrational numbers.
  13. (Extension) If f,g:X\rightarrow Y and f and g are both injective, then prove or disprove that f composed with g is also injective.
  14. Prove or disprove that S(n)=\displaystyle\sum_{i=0}^n (i\cdot (i+1) \cdot (i+2))=\frac{n(n+1)(n+2)(n+3)}{4}.
  15. (Extension) (Challenge) Show that 2! \cdot 4!\cdot 6! \cdots (2n)! \geq ((n+1)!)^n.
  16. (Extension) (Challenge) The Tower of Hanoi game is one where you have three posts and n disks, originally all on one pole. They are arranged with the largest disk at the bottom, and each disk above it smaller than the disk below. Your goal is to move all the disks to another pole, with the only move being to take the top disk off of any stack, and placing it on another stack, with the restriction that a disk can only go on either an empty stack, or a stack with only larger disks. Prove that this game always has a solution for disks. How many moves are required given an initial stack of n disks?
  17. (Extension) (Super extreme challenge) Catalan numbers come up in random situations. For example, given n pairs of parentheses, let T_n be the number of ways they can be arranged in a valid mathematical expression. For example, with n = 3, there are 5 ways to rearrange the parentheses: ((())),(())(),(((()),(()()), and ()()(), so T_3=5 . We define T_0=1. Show that T_n = \frac{1}{n+1} {2n \choose n}.

Part 2: Bellman-Ford and Dynamic Programming

  1. Describe three real-life situations where Bellman-Ford will work and Dijkstra’s will not.
  2. (Challenging, but please give this a try. For this problem and #3 only, feel free to work in as large a group as you would like.) Sequence alignment is, informally, the process of taking two strings, and finding how similar they are by aligning them, matching letter to letter between the strings as best you can.For example, the alignment between “abbbaabbbbaab” and “ababaaabbbbbab” might look something like
    ab-bbaa–bbbb-aab
    aba-baaabbbbba-b
    where the ‘-’ characters represent gaps in the alignment. Notice that most letters are lined up between the two strings. Devise a non-dynamic programming algorithm to align two strings, putting in gaps when they do not match, but minimizing the number of gaps needed. Your algorithm need not (and probably will not) be efficient. Now, repeat, using a dynamic programming algorithm.Sequence alignment is used for many applications, but especially in computational biology, when long strands of DNA or RNA or proteins need to be aligned to find how similar two strands are.

    If you give up, check out

  3. (Extension) (Even more challenging) In real life, we don’t care as much about the length of a gap so much as the fact that there was a gap. We also align “incorrectly” every so often if it makes the overall alignment better. For example, aaaabaa and aaaacaa might align without any gaps, even though b and c are misaligned. So, with these two new rules, to determine how good an alignment is, we can give each alignment a score. In this new development, an aligned string that looks like ‘aba–aab’ will not be scored much different from aba——aab’. But the strings ‘aba—aab’ and ‘a-ba-a-ab’ will have very different scores. Specifically, we define a gap start penalty of \alpha, and a gap extension penalty of \gamma. An alignment counts as 1 point, a gap start penalty is -1 points, and a gap extension penalty is -0.2 points. A mismatch is scored using the function m(\ell_1, \ell_2), where \ell_1, \ell_2 are two characters, and m returns the score (probably negative) when those two characters are “misaligned” together. Using this new definition, devise a dynamic programming algorithm to calculate the alignment(s) with the highest score.

Part 3: Project Scoping

Here, we give you some guidance in researching more about your project. Please answer these in a blog post (categorized with Student and Submissions), but each one is supposed to be a starting point for more research. If some of these don’t apply, that’s ok. If a lot of these don’t apply, come talk to me.

  1. Describe the history of your topic. What were the motivating factors behind the discovery, invention, derivation, or prominence of your topic? Why was it first relevant? Is it still relevant today? If so, why? Were there predecessors that your topic tried to better or complement?
  2. What other fields or topics are related to yours? How have they influenced each other? How is yours similar or different?
  3. If you have a technical topic, what is the mathematical basis? Does it use concepts in linear algebra? Calculus? If there’s anything you don’t understand here, mention it.
  4. Who are the current experts in the field? Where do they work? Are these academics or commercial entities?
  5. What sources have you found that will help you understand deeply what you are studying. Where are these sources from? Are they reputable? Are there any other sources you would like, but can’t get hold of?
  6. What are you looking to accomplish in depth in this project? In other words, what are you going to focus on? Is it reasonable that you can finish it in a week? Hit Lekan up if you need help with this part.
  7. So you essentially have a week before we’re going to start doing final checks to see if you’re nearly done and on track to finish, and you have one week and three days before the presentation. So, write down a daily plan for what you want to have done. There will be a significant programming assignment on Thursday and Friday, and on all other days, you can expect to have about 1.5-2 hours of non-project lab time, although, as usual, I will give extra problems, so if you are interested, you can always do more. You all know that programming tends to always take longer than expected, so be reasonable in your plan. Plan on being completely done with your project by Tuesday night. Then you will have Wednesday for polishing and fixing last-minute bugs.
  8. Finally, your presentation will be about 15 minutes per person (not per team). Think about what parts of your research you will present at your presentation, and how you will teach some of these complex topics. This will give you a good idea of what you may want to work on later in the week if you feel crammed for time, and need to prioritize. If you want to try out parts of your presentation on classmates, or the counselors, make sure to do that in advance so you have time to modify your presentation.

Part 4: Catch Up

Starting tomorrow, there will be a new programming project, so catch up with all your work in the last week. The amount of work will be high for the next 2 days, but will then drop off a bit, to make time for your project.

For Pathfinder, a few things if you want to spice it up after you are done with implementing Dijkstra’s:

  • Clean up the user interface. Make it more intuitive to use.
  • Show the shortest found path in a different color.
  • Implement A*.

Remember to submit Pathfinder and any other code that you’ve done. This is both so that we can help you improve, and also for when we write you your evaluations at the end! The submission instructions are here: http://lekanwang.com/epgy/ai/2011/s2/2011/07/submitting-code/

One response to “Lab 6: Dynamic Programming, Project, and Pathfinder”

  1. Lab 8: Decision Trees and Learning Theory

    [...] have completed your blog post for Project Scoping. Lab 6, part [...]

Leave a Reply