1. FindSingle You are given a sorted array of numbers where every value except one appears exactly twice; the remaining value appears only once. Design a sublinear algorithm for finding which value appears only once. Argue that your solution is not O(n). The method is called int findsingle(int[] a). Solve this problem using divide and conquer and explain in a memo.txt why your solution is divide and conquer. Hint: write out some examples and look for patterns.

Here are sample inputs:

$java FindSingle 1 1 2 2 3 4 4 5 5 6 6 7 7 8 8
3
$java FindSingle 10 10 17 17 18 18 19 19 21 21 23
23
$java FindSingle 1 3 3 5 5 7 7 8 8 9 9 10 10
1

Start with the file FindSingle.java here: https://github.com/ieee8023/cs310-summer2015

2. EditDistance Given two words word1 and word2, implement the Needleman-Wunsch string alignment algorithm to match the two strings and output the minimum edit distance. Set the delta and alpha in your code. Name your file EditDistance.java and have it take two strings as arguments. The following examples has alpha as [[0,1],[1,0]] and delta = 2. So alpha[a,b] = 1.

$java EditDistance aabba aabba
0
$java EditDistance aaa aba
1
$java EditDistance aaaaaaaa abbaaaaa
2
$java EditDistance aaaaaaaa abbbaaaaa
4
$java EditDistance aaaaaaaa abaaabaaaa
4
$java EditDistance aaaaaaaaabbbbbbbb bbbbbbbbaaaaaaaaa
16

3. LargestRectangleArea Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram. Solve this problem using dynamic programming and explain in a memo.txt why your solution is dynamic programming.

$java LargestRectangleArea 2 1 5 6 2 3
10
$java LargestRectangleArea 2 2 5 6 2 3 3
14
$java LargestRectangleArea 4 4 2 1 2 3 3
8
$java LargestRectangleArea 1 2 3 4 5 6 7 8
20
$java LargestRectangleArea 1 2 3 4 3 2 1
10

Due: 7/21 @5pm. Submit the code to users in a hw4 folder. Each question is 3 points and then 1 points for how easy it is to grade.