# Implement an Algorithm and Test Code Projects.

Note the following: a) Upload your code, solu ons, test code, explana ons, and i/o snapshots, all in one le in the blackboard. b) You should always try to write the most e cient code. c) Each ques on is of 5 marks. Total = 50 marks 1) Assume you have a method “isSubstring” which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rota on of s1 using only one call to isSubstring (note that “waterbo le” is a rota on of “erbo lewat”). 2) Write an e cient method to determine if a string has all unique characters. Then nd its me complexity. Finally, look at the following code which also nds if a string has all unique characters, and compare its me complexity with yours. Run it and explain in simple English how the following code is working. public class MyClass { public sta c void main(String args[]) { System.out.println(isUniqueChars(“something”)); } public sta c boolean isUniqueChars(String str) { int checker = 0; for (int i = 0; i < str.length(); ++i) { int val = str.charAt(i) – ‘a’; if ((checker & (1 0) return false; checker |= (1 a[j] and i < j Example: The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3). tt ti ti ti fi tt ti fi ti fi fi ti ffi ti ti fi fi fi ti ti ti ti ti ti ffi Now, modify MergeSort to nd Inversion Count in an array. 10) Write the following func ons asympto cally in non-decreasing order. Also, if two func ons are asympto cally similar, group them together. (note: ‘^’ means power, so 2^n means 2n). ti ti ti ti 5n, 4 lg n, 2lg n, 4 lg lg n, n4, n1/2 lg4 n, (lg n)5lg n, nlg n, 5n, 4n^4, 44^n, 55^n, 55n, nn^1/5, nn/4, (n/4)n/4.