#1

Given two numbers represented as strings, return multiplication of the numbers as a string.

Note:
* The numbers can be arbitrarily large and are non-negative.
* Converting the input string to integer is NOT allowed.
* You should NOT use internal library such as BigInteger.

$ java MultiplyStrings 1 0
0
$ java MultiplyStrings 1 1
1
$ java MultiplyStrings 100 10
1000
$ java MultiplyStrings 99 88
8712
$ java MultiplyStrings 1234567890 1234567890
1524157875019052100
$ java MultiplyStrings 12345678909999 11111111111111
137174210111098628257898889
$ java MultiplyStrings 298374091823740981273409817324 182374981237409817234099182374
54415969398083955415924144796721184778955953290573100647176

#2

Describe a family of graphs with V vertices and E edges for which the worst-case running time of Dijkstra’s algorithm is achieved. Describe a small graph and walk through each part of Dijkstra’s algorithm and explain why this input is so bad. Don’t simply execute the algorithm on your graph. Explain line by line how each part of the algorithm is impacted by this worst case graph.

#3

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

Note:
* Your runtime must be $O(n \log k)$ and explain why in your memo.txt
* You may assume k is always valid, 1 ≤ k ≤ array’s length.

$ java KthLargestElement k [array]

//Given k = 2 and array [3,2,1,5,6,4]
$ java KthLargestElement 2 3 2 1 5 6 4
5
//Given k = 5 and array [8,7,6,5,4,3,2,1]
$ java KthLargestElement 5 8 7 6 5 4 3 2 1
4
//Given k = 1 and array [8,7,6,5,4,3,2,1]
$ java KthLargestElement 1 8 7 6 5 4 3 2 1
8
//Given k = 2 and array [3,2,3]
$ java KthLargestElement 2 3 2 3
3

#4

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

Here is some starting code:

public static void main(String[] args) throws Exception {

if (args.length > 0){
	//using java8 magic
	int[] in = Arrays.stream(args).map(String::trim).mapToInt(Integer::parseInt).toArray();
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
}else{
		
	{
	int [] in = new int[]{1,1,2,2,3};
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
	}
	
	{
	int [] in = new int[]{1,1,2,3,3};
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
	}
	
	{
	int [] in = new int[]{1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8 };
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
	}
	
	{
	int [] in = new int[]{10, 10, 17, 17, 18, 18, 19, 19, 21, 21, 23};
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
	}
	
	{
	int [] in = new int[]{1, 3, 3, 5, 5, 7, 7, 8, 8, 9, 9, 10, 10};
	System.out.println(Arrays.toString(in) + " " + findsingle(in));
	}
}

}

/**
 * Find and return single element in a sorted array of numbers 
 * where every value except one appears exactly twice; the 
 * remaining value appears only once.
 * 
 * @param a Sorted array
 * @return element without a pair
 */
static int findsingle(int[] a) throws Exception{

	// Some sample lines. Feel free to remove them.
	if (a.length == 1) return a[0];
	if (a.length == 2) throw new Exception("No single");
	
	return 0;
}

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