### Question Description

I’m working on a algorithms & data structures multi-part question and need support to help me understand better.

1. Given a tree on n vertices, we can always find a single vertex whose removal leaves a forest in whichno tree has more than n/2 vertices. Suppose we use our divide-and-conquer algorithm to count the3-colourings of a tree on n vertices; about how long does it take? How fast can you compute theanswer?You can assume n is a power of 2 and the tree is always split into exactly two pieces of size n/2 (eventhough the two pieces together should have n − 1 vertices instead of n, since we removed a vertex tosplit the tree).

2. In the lecture, we saw that implementing Euclid’s algorithm on positive integers a and b with a > bby repeated subtraction takes Ω(a) time in the worst case but implementing it by mod takes O(log a)time, assuming subtraction and mod each take constant time. Now suppose subtracting two n-digitnumbers takes n time but taking their mod takes n2time; comparing two numbers takes time 1.About how much bigger does a have to be than b in order for it to be faster to compute a mod b withmod directly than with repeated subtraction?For example, if a = 1523 and b = 0427, then computing a mod b = 242 by repeated subtraction meanssubtracting 0427 from 1523 to get 1096 in 4 time units, checking 1096 is still bigger than 0427 in 1 timeunit, subtracting 0427 from 1096 to get 0669 in 4 time units, checking 0669 is still bigger than 0427 in 1time unit, subtracting 0427 from 0667 to get 0242 in 4 time units, and checking whether 0240 is biggerthan 0427 in 1 time unit (and finding it’s not). That takes a total of 4 + 1 + 4 + 1 + 4 + 1 = 15 timeunits, whereas computing a mod b = 242 directly takes 42 = 16 time units, so in this case repeatedsubtraction is faster.

3. Describe how to build a circuit consisting of AND, OR and NOT gates that takes two n-bit binarynumbers x and y and outputs then (n + 1)-bit binary number x + y. Your circuit should be a directedacyclic graph (a DAG) whose size is at most polynomial in n and whose depth is constant (where“depth” means the length of the longest directed path); the fan-in and fan-out are not bounded (where“fan-in” and “fan-out” mean the maximum in- and out-degree of any vertex).

4. Toom-3 is like Karatsuba’s algorithm but divides x and y into 3 parts each, and then multiplies themusing 5 multiplications of (n/3)-digit numbers, plus additions and subtractions. What is the maximumnumber of such multiplications that it could use while still be asymptotically faster than Karatsuba’salgorithm? Explain your answer.

5. Give a divide-and-conquer program for https://leetcode.com/problems/maximum-subarray (youdon’t have to pay for a membership!) and explain how to use your solution to solve https://leetcode.com/problems/maximum-sum-circular-subarray neatly.