Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSE 101 Winter 2024

Homework 1

Due: Thursday 1/18 at 11:59pm

1.  (10 points)

[The purpose of this problem is to review a few concepts we will need in this class: asymptotic notation, recurrence relations and induction]

Let T be defined by the recurrence relation:

T(0) = 0 ,     T(n) = 2T(n − 1) + 2n    for  all  n ≥ 1

(a) Prove that T(n) = Ω(2n ) using induction.

(b) Prove that T(n) = O(3n ) using induction.

2.  (14 points)

[This problem is designed to give a concrete example of a graph with n vertices that has exponentially many paths between two of its vertices (in terms of n). This is important later when we start looking for paths with specific properties (shortest paths, paths of even or odd length, paths that avoid certain vertices, etc.) Some of you will be tempted to say “Search all paths.....” but this may require an exponential runtime. It is important to note that DFS, BFS,. . . do not search all paths since these algorithms are polynomial time.]

Let T(n) be the nth triangle  chain graph. It is defined recursively:

. T(0) is the single vertex A0 .

.  For n > 0, T(n) is defined to be the graph T(n − 1) along with the two vertices An, Bn and the directed edges: (An , Bn ), (Bn , An −1), (An , An −1). (See picture.)

(a) How many vertices does T(n) have? (Justify your answer using a recurrence relation.)

(b)  How many edges does T(n) have? (Justify your answer using a recurrence relation.)

(c)  How many different paths are there from An to A0 in T(n)? (Justify your answer using a recurrence relation.)

[For example, in the case of T(2), how many paths are there from A2  to A0 ?]

(d)  Let P(N) be the number of paths there are from one side to the other of a triangle chain graph with N vertices. Determine the big-Theta bound of P(N). (Justify your answer.)

3.  (10 points)

[This main motivation for this problem is to see that even if the data is given to you in a matrix form, you may still need to change  the data so that you can use a graph algorithm to solve a problem. Also, once you create the graph, how big do you expect it to be. And finally, how to change the input in order to handle extra restrictions.]

Suppose you are playing a board game where you are given an n × n playing board. This board is given to you as a matrix of the values {0, 1, 2}. If you land on a 0 square, you are trapped forever. If you land on a 1 square then you can move 1 square in any of the 4 cardinal directions. If you land on a 2 square then you can move 2 squares in any of the 4 cardinal directions.

(You would like to know if it is possible to travel from the top-left corner to the bottom-right corner following these rules.)

For example, with the given graph below, there is a way to get from the top-left corner to the bottom right by following the rules of the game:

(a)  How would you design a graph based on this n×n matrix such that each valid sequence of moves corresponds to a path in the graph? (what are the vertices?, when are vertices connected by an edge? Are the edges directed or undirected?)

(b)  In the worst case, how many vertices and how many edges would this graph have?  (in terms of n?)

(c) What algorithm would you use on your graph to answer the question: “is it possible to travel from the top-left corner to the bottom-right corner by following the rules of the game?

(You should give as high-level description. No proof of correctness or runtime analysis necessary.)

4.  (10 points)

[The main motivation for this problem is to see what a reduction algorithm looks like. Also, in this problem, you will practice writing a bi-directional proof for an algorithm that solves a decision problem.] Given a directed graph G with vertex weights wv  ∈ {0, 1} (in other words, each vertex is either labeled with 0 or 1), and vertices s and t, Determine if there is a path in G from s to t such that the binary sequence of vertex weights in the path is of the form 0n 1m  for any m,n ≥ 1.  (This means that s must be labeled with 0 and t must be labeled with 1. This is a requirement for a valid input.)

For example, the algorithm should output FALSE for the first graph because there is not any path from s to t that follows the pattern: 0n 1m. The algorithm should output TRUE for the second graph because of the path: s,D,C,A,t.

Consider the following algorithm that claims to solve this problem:

Note that valid inputs must be {0, 1} labeled directed graphs with s labeled 0 and t labeled 1.

Algorithm Description:

Input: a {0, 1}-labeled directed graph G, a vertex s of G that is labeled 0 and a vertex t of G that is labeled 1

Create a graph G′ by removing all edges that go from a 1-labeled vertex to a 0-labeled vertex. Run graphsearch on G′ starting from s. If t is visited then return TRUE. Otherwise return FALSE

Either prove this algorithm is correct or disprove it with a counter-example.

(NOTE: graphsearch is an algorithm that takes a graph G and a vertex s and returns a list of vertices that are reachable from s by a  directed path in G. You do not have to prove the correctness of graphsearch, we will do this in class.)

(Hint: your proof must show that the algorithm correctly returns TRUE when the input has the desired property and correctly returns FALSE when the input does not have the desired property. This means you must do a bi-directional proof.)