In this thesis two questions are addressed. First is the question of the time complexity of an algorithm gathering information on a tree with unknown topology. The tree is known to have maximum depth $D$ and maximum degree $\Delta$. This has been an open problem since being asked by Chlamtac and Kutten in 1985. This thesis resolves the question with upper and lower bounds that are essentially tight. The second question this dissertation addresses is what proportion of graphs have a fixed type of spectrum. We show that at most a $2^{-c n^{3/2}}$ proportion of graphs on $n$ vertices have integral spectrum. This improves on previous results of Ahmadi, Alon, Blake, and Shparlinski, who in 2009 showed that the proportion of such graphs was exponentially small.

Given an equation, the integers [n] = {1,2,...,n} as inputs, and the colors red and blue, how can we color [n] in order to minimize the number of monochromatic solutions to the equation, and what is the minimum? The answer is only known for a handful of equations, but much progress has been made on improving upper and lower bounds on minima for various equations. A well-studied characteristic of an equation, which has its roots in graph Ramsey theory, is to determine if the minimum number of monochromatic solutions can be achieved (asymptotically) by uniformly random colorings. Such equations are called common. Our main result is that no 3-term equations are common. We also provide a lower bound for a specific class of 3-term equations and give results for a variety of other types of equations.