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

CS 330, Spring 2024, Homework 2

Due on Wednesday 2/7 at 11:59 pm on Gradescope

Collaboration policy   Collaboration on homework problems is permitted, you are allowed to discuss each problem with at most 3 other students currently enrolled in the class. Before working with others on a problem, you should think about it yourself for at least 45 minutes. Finding answers to problems on the Web or from other outside sources (these include anyone not enrolled in the class) is strictly forbidden.

You must write up each problem solution by yourself without assistance, even if you collaborate with others to solve the problem. You must also identify your collaborators. If you did not work with anyone, you should write ”Collaborators: none.” It is a violation of this policy to submit a problem solution that you cannot orally explain to an instructor or TA.

Typesetting   Solutions should be typed and submitted as a PDF file on Gradescope. You may use any program you like to type your solutions. LATEX, or “Latex”, is commonly used for technical writing (overleaf.com is a free web-based platform for writing in Latex) since it handles math very well. Word, Google Docs, Markdown or other software are also fine.

Solution guidelines   For problems that require you to provide an algorithm, you must provide:

1. pseudocode and, if helpful, a precise description of the algorithm in English. As always, pseudocode should include

• A clear description of the inputs and outputs

• Any assumptions you are making about the input (format, for example)

• Instructions that are clear enough that a classmate who hasn’t thought about the prob-lem yet would understand how to turn them into working code. Inputs and outputs of any subroutines should be clear, data structures should be explained, etc.

If the algorithm is not clear enough for graders to understand easily, it may not be graded.

2. a proof of correctness,

3. an analysis of running time and space.

You may use algorithms from class as subroutines. You may also use facts that we proved in class.

You should be as clear and concise as possible in your write-up of solutions. A simple, direct analysis is worth more points than a convoluted one, both because it is simpler and less prone to error and because it is easier to read and understand.

1. Edge-to-Vertex Dual (10 points)

Consider an undirected graph G(V, E) with n nodes and m edges. We define the edge-to-vertex dual D(G) of G as follows: D(G) has one vertex for each edge in G, and two vertices in D(G) are connected by an edge if and only if the corresponding edges in G share a common vertex.

Figure 1: Example of a graph and its dual.

a) Determine the number of nodes in D(G) as a function of n and m. Give a one-line explanation.

b) Determine the number of edges in D(G) as a function of the degrees deg(v1), deg(v2), . . . , deg(vn) of the nodes in G. Prove your formula. Hint: Start by considering the edges induced in D(G) from the neighbors of a single node in G.

c) Use your result from b) to show that the number of edges in D(G) grows as O(m2)

Hint: Recall that a2 1 + · · · + a2 k ≤ (a1 + · · · + ak) 2 for all a1, . . . , ak ≥ 0.

d) Design an algorithm that takes as input G in the form of an adjacency list and returns the adjacency list of D(G). You may assume that all adjacency lists are implemented as nested hash tables. Analyze your algorithm’s runtime and space as a function of n and m (recall that these are the number of nodes and edges in the original graph). In 2 to 3 sentences, provide a brief explanation of why it accurately computes D(G).

2. Lily Pond (10 points)

Consider a square pond represented by a k × k grid, where water lilies may or may not grow on certain squares. A frog starts on the bottom-left square, and a fly rests on the top-right square; we assume throughout the problem that water lilies always grow on these two squares. The frog aims to catch the fly by reaching its square. The frog, however, is constrained to jumping only to adjacent squares with water lilies. Diagonal movements are not possible. For illustrative purposes, Figure 2 shows two instances of this problem.

Figure 2: Example instances of the problem.

You are given a k × k boolean array A that specifies which squares have water lilies on them. The square where the frog starts is denoted as (0, 0) and can be accessed through A[0][0]. Similarly, the square where the fly is positioned is indexed as (k − 1, k − 1) and accessed through A[k − 1][k − 1].

• (Warm-up: Do not hand in) What algorithm would you use to determine if there is a way for the frog to reach the fly? How can you think of the input as specifying a graph, and what algorithm from class could you then use?

In the following, we assume that the frog can reach the fly. You want to stop the frog from catching the fly; for this you can remove at most one water lily from the pond. Design an algorithm that returns True if you can stop the frog from reaching the fly by removing at most one lily from the pond and False otherwise. For full credit, the runtime of your algorithm should be O(k4) Reminder: Follow the solution guidelines on page 1.