Introduction to algorithms class. Please show your work. And please DO NOT copy any solutions to this problem that may already exist on Chegg Study.

A walk of length k in a graph is a sequence of vertices vo, V1, ... , Vk such that v is a neighbor of vi+1 for i = 0, 1, 2, ...,k - 1. Suppose the product of two n x n matrices can be computed in time O(n^) for a constant w > 2. Give an algorithm that counts the number of walks of length k in a graph with n vertices in time O(nW log k). HINT: If A is the adjacency matrix, prove that the (i, j)'th entry of Ak is exactly the number of walks of length k that start at i and end at j. Repeatedly square the adjacency matrix to compute Ak. A walk of length k in a graph is a sequence of vertices vo, V1, ... , Vk such that v is a neighbor of vi+1 for i = 0, 1, 2, ...,k - 1. Suppose the product of two n x n matrices can be computed in time O(n^) for a constant w > 2. Give an algorithm that counts the number of walks of length k in a graph with n vertices in time O(nW log k). HINT: If A is the adjacency matrix, prove that the (i, j)'th entry of Ak is exactly the number of walks of length k that start at i and end at j. Repeatedly square the adjacency matrix to compute Ak