# Lab 6: Big-O and Project Scoping

Part I: Project Topic!

If any of the following are true, please do not do anything else before resolving it.

1. You do not have a topic.
2. You have a topic, but have not posted the half-page to a page of preliminary research to the blog.
3. You have posted to the blog, but Lekan has not yet commented on your post.
4. You do not have an idea for a significant implementation.

Near the end of the lab period, as you are hopefully scoping out your project further, Lekan and the counselors will walk around and talk with each group.

Part I: Dynamic Programming and Graph Search

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 the process of taking two strings, and finding how similar they are by aligning them. For example, the alignment between abbbaabbbbaab and ababaaabbbbbab might look something like
ab-bbaa–bbbbaab
aba-baaabbbbba-b
where the ‘-’ characters represent gaps in the alignment. 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 definitely 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.
3. (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. To determine how good an alignment is, we can give alignments scores. So, 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. Using this new definition, devise a dynamic programming algorithm to calculate the alignment(s) with the highest score.

Part II: Big-O and Search

1. Bubblesort is well-known as one of the first sorting algorithms that first-time programmers tend to use to sort a list before they have learned about Big-O and algorithmic complexity. Bubblesort works by iterating through a list, and swapping pairs if they are out of order. After one pass, more passes are taken, swapping adjacent values each time, until eventually the list is sorted. This is also perhaps the easiest sort to implement. Implement it. What is its Big-O?
2. Look up mergesort on Wikipedia. It will probably tell you that it’s O(log(N)). Show yourself why it is O(log(N)).
3. Pick one of the non-deterministic searches we covered today. What is its runtime Big-O? Would you use this search in the following situations? Explain.
1. A robot navigating its way across campus.
2. A precision spacecraft that must exit the atmosphere at the correct velocity within a very small error.
3. Routing on the internet.
4. Google searching through its search indexes to find web pages matching your search.
5. Twitter searching through its databases to find tweets that were tweeted in the last few seconds or minutes.

Part III: Project Scoping

Here, we give you some guidance in researching more about your project. Please answer these in a vignette, 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? 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 academic or commercial?
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 is your significant implementation? Is it reasonable that you can finish it in a week? Have you gotten it checked off by Lekan?
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 Monday night.
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. 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.

Part IV: Catch Up

Starting tomorrow, there will be a new programming project, so catch up with all your work in the last week, do some recursion problems or other problems if any of the foundational topics like data structures or proofs don’t make sense.

Remember to submit your recursion problems and your 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. Submission instructions, as before, is here: http://lekanwang.com/ai-epgy/2011/06/code-submission-instructions/