# Tutor profile: Charlie M.

## Questions

### Subject: Computer Science (General)

Given a colored Graph, $$G = \langle V,E,L \rangle$$, where each vertex may be colored with any number of colors from the set of colors $$C$$. $$V$$ is a set of vertices $$E \subseteq V \times V$$ is a set of edges $$L : V \to 2^C$$ is a labeling of each vertex to a set of it's colors A path, $$P \in V^*$$, of $$G$$, is any finite sequence of vertices such that each pair of adjacent vertices in $$P$$ are edges in $$G$$. Formally, for each $$1 \leq i < |P|$$, $$\langle p_i, p_{i+1} \rangle \in E$$. A simple path, is a path in which no vertex is repeated, other than possibly final vertex. $$\forall 1 < i < |P|, 1 \leq j < i. P_i \not = P_j$$ A mono-chromatic path is a path in which all vertices of the path share a common color. Formally, $$\exists c \in C. \forall 0 \leq i \leq |P|. c \in L(P_i)$$. Describe an algorithm to enumerate all simple mono-chromatic paths of G, argue it's correctness, and describe its asymptotic performance.

Let $$G_c$$ represent the sub-graph induced by $$\{v \in V : c \in L(v)\}$$ for each color $$c \in C$$. Now, we have reduced the problem of enumerating all simple mono-chromatic paths of G, to enumerating all simple paths of $$G_c$$ for each color, $$c$$. To enumerate simple paths, we may use any number of algorithms for systematically exploring a graph (i.e. Depth-First-Search and Breadth-First-Search). Here, I describe a solution using Depth-First-Search (DFS). Def Mono-Paths($$G$$) Paths($$G_c$$) for each $$c \in C$$ Def Paths($$G$$) Paths($$G$$, $$v$$, $$\epsilon$$) for each $$v \in V_G$$. Def Paths($$G$$, $$v$$, $$P$$) output $$ P \cdot v$$ if $$v \not\in P$$ then For each $$v'$$ s.t. $$\langle v, v' \rangle \in E_G$$ do Paths($$G$$, $$v'$$, $$P \cdot v$$) The above algorithm, outputs all mono-chromatic paths of $G$. We are assured that all paths output are mono-chromatic because we only output paths from graphs induced by each color of $$C$$. These paths must belong to $$G$$ as they belong to a subgraph of $$G$$. We produce all simple-paths of $$G_c$$: We start a depth-first-search for each vertex of $$G_c$$, output each path along the way, and we only stop exploring a path when the last vertex has already been visited before along the path. Thus we output only mono-chromatic simple paths, and all mono-chromatic simple paths. The algorithm runs in $$O(|C|*|V|!)$$, as we must output all simple paths and there are in the worst case factorially many paths in the number of vertices. However, we can tighten the bound in terms of the number of paths actually output $$O(|C|*d*n)$$ where d is the degree of the graph and n is the number of paths output. The maximum time between output of any two consecutive paths is no more than $$O(|V| + |E|)$$

### Subject: C++ Programming

What does the following C++ function do? Describe the space and runtime performance of the code. What kind of inputs does it work or not work well on? void mystery_func(std::vector<int>& a) { for (size_t i = 1; i < a.size(); ++i) { int tmp = a[i]; size_t j = i -1; while (j >= 0 && a[j] > tmp) { a[j+1] = a[j]; j--; } a[j+1] = a[i] } }

The function, myster_func, performs an in-place sort of the input vector a. The sort is better known as insertion sort, and has a worst-case runtime performance of O(n^2) (where n is the number of element in a) and uses a constant amount extra space. The worst-case runtime occurs with arrays that anti-sorted (sorted in decreasing order rather than increasing order). But the best case performance is achieved on already sorted or nearly sorted lists and runs in linear time (O(n)).

### Subject: Algebra

Sally, George, and Andrew all work together in Santa's Toy Shop producing hand-made toys. Every hour Sally and Andrew produce twice as many toys as George does. Andrew works quickly and in only an hour produces as many toys as Sally does in 45 minutes and George does in an hour. Every hour, George produces 3 toys less than what Sally would in 1/2 and Andrew would in an hour. In a 10 hour work day, how many toys does Sally, George, and Andrew make each?

This word problem wants us to find out how many toys each Sally, George, and Andrew make in 10 hours. Now we need to look for relevant information within the prompt. We are informed on how much each produces relative to the others: 1. Every hour Sally and Andrew produce twice as many toys as George does. 2. Andrew works quickly and in only an hour produces as many toys as Sally does in 45 minutes and George does in an hour. 3. Every hour, George produces 3 toys less than what Sally would in 1/2 and Andrew would in an hour. We then recognize that these individual sentences can be transformed into an equation, and we can solve by finding the solution to the produced system of equations. We first introduce variable names for the amount of toys each worker makes in an hour. S : toys per hour made by Sally G : toys per hour made by George A : toys per hour made by Andrew 1. S + A = 2G 2. A = (45/60)S + G = 3/4S + G 3. G = 1/2S + A - 3 Now we can solve for S, A, and G (via substitution method). We can start by taking equation 1 and substituting G using equation 3. S + A = 2(1/2S + A - 3) Substitute S + A = S + 2A - 6 Simplify S + A - S = S + 2A - 6 - S Subtract S from both sides to simplify and remove S from equation A = 2A - 6 Simplify A - 2A = 2A - 6 - 2A Subtract 2A from both sides -A = -6 Simplify A = 6 Multiply both sides by -1 to get A = 6 Now we can use the solution for A to solve for S and G. 1. S + 6 = 2G 2. 6 = 3/4S + G 3. G = 1/2S + 6 - 3 = 1/2S + 3 We can start by solving equation 1 for S and substituting into equation 2. Note that since we did not use equation 2 in the first step to solve for A, we must use equation 2. Otherwise, If we instead used equation 1 and 3 again, we would not make progress and find that we end up with an equation that simplifies to 0 = 0. S + 6 = 2G S = 2G - 6 6 = 3/4S + G 6 = 3/4(2G - 6) + G 6 = 3/2G - 9/2 + G 6 + 9/2 = 3/2G - 9/2 + G 21/2 = 5/2G 21/2 * 2/5 = 5/2G * 2/5 21/5 = G Now we can pick any equation involving S and solve for it using the values we found for A and G. Here we choose to start with equation 1. S + 6 = 2(21/5) S + 6 - 6 = 2(21/5) - 6 S = 42/5 - 6 S = 12/5 Now we know that: Sally makes 12/5 toys every hour, George makes 21/5 toys each hour, and Andrew makes 6 toys each hour. So, in 10 hours Sally makes (10 * 12/5) = 24 toys in 10 hours. George makes (10 * 21/5) = 42 toys in 10 hours. Andrew makes (10 * 6) = 60 toys in 10 hours. In 10 hours, Sally makes 24 toys, George makes 42 toys, and Andrew makes 60 toys.