For each problem: list important details of the given problem and explain why/how it is important; come up with a few examples (test cases) that you think are representative of the problem; describe a brute force solution (no need to implement your brute force method). Implement a solution--in a language of your choice--that is better than the brute force solution. Provide source files, and a README file which describes how you run your code, and test cases that show your code works; what is the time complexity, space complexity? How did you come up with those complexities?

a. String Rotation.

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 rotation of s1 using only one call to isSubstring (e.g., waterbottle is a rotation of erbottlewat).

b. Connected Components.

Show that we can use a depth-first search of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify depth-first search so that it assigns to each vertex v an integer label v.cc between 1 and k, where k is the number of connected components of G, such that u.cc=v.cc if and only if u and v are in the same connected component.