Due: Monday, November 27.
Let S(n) be the number of length n strings of 0's and 1's that do not have two consecutive 1's. Define S(1) and S(2) and S(3). Then write a recurrence that defines S(n) for larger values of n.
Suppose that T(n) = 3T(⌊n/4⌋) + n. Expand this recurrence and extrapolate to what the expanded form will be after k steps. Then, by choosing a suitable value of k, find a solution for T(n) to withing a constant factor.
A nuclear reactor has created 10 grams of a radioactive isotope. Every hour 1% of what is left decays. Let R(n) be the amount of the isotope that is left after n hours. What is R(0)? Write a recurrence for R(n). Solve the recurrence.
What does it mean for a graph to be connected?
What is a connected component of a graph?
What is the definition of a cycle in a simple graph?
What is the definition of a tree?
What is the definition of the reflexive transitive closure of a relation R?
How can you find the reflexive transitive closure M* of 0-1 matrix M?
Describe an algorithm that, given directed graph G and a pair of vertices u and v in G, computes the number of directed paths in from u to v in G that have length 2.
A subgraph of graph G is obtained by removing zero or more edges and zero or more vertices from G. When a vertex v is removed, all edges incident on v must also be removed.
The High Degree Subgraph problem is as follows.
Input. A simple graph G and a positive integer k.
Question. Does G have a subgraph with at least one vertex where all of the vertices have degree at least k?
Give an algorithm that solves the High Degree Subgraph problem by writing, in clear and simple pseudo-code, a definition of function hds(G, k), which returns true if G has a nonempty subgraph where every vertex has degree at least k, and returns false otherwise.
There is a simple, efficient algorithm. Do not give an algorithm that tries all subgraphs, as that is extremely slow. Do not waste time describing details of computations that are clearly easy to carry out. Just say what the computations do. For example, you can say to find a vertex of degree < k if one exists.