Homework 1

General Comments

For full credit, provide context for each problem, show all calculations, and justify all answers by providing enough comments to explain your reasoning.
Homework assignments must be very neatly written or typeset (e.g. using Word or OpenOffice).
You can get up to 50% credit on a problem if you get significant outside assistance. Thus, if you are totally stuck on a problem it might be worth getting help. However, you must indicate any assistance/collaboration (See the Homework Assistance section on the Policies page). Failure to do so could result in a failing grade for the course! Note that getting help from the Help Center or me does not count as significant outside assistance, but talking with your classmates or searching on the Internet does!
If a problem asks for an algorithm, you should give the most efficient algorithm you can find to ensure full credit. You should also specify the complexity of the algorithm with justification, whether or not the problem asks for it.

(12) Consider the problem of finding the common elements from 2 ordered lists A and B which contain no repeated elements. For instance, if A has 2,3,4,6,7 and B has 3,4,5,6,8, then the output would be 3,4,6. Assume A has n elements and B has m elements.
1. Describe an algorithm to solve this problem with as few comparisons as possible.
2. What is the largest number of comparisons that your algorithm uses? Your answer should be a formula involving n and m.
3. How would you modify your algorithm if the lists are not ordered?
4. What is the largest number of comparisons that this second algorithm uses?
(12) Consider the scenario from the first problem, but instead of finding the common elements, we want to create a list that combines all of the elements that are on either list (removing duplicates). So in our example above the output would be 2,3,4,5,6,7,8. Answer questions (a) through (d) from the previous question for this problem.
Questions to ponder, but not to be submitted: What changes in the previous 2 problems and your algorithms for them if repeated values are allowed on the lists? Does it make each problem easier or harder to solve? What complications arise?