# CS 4104 Homework Assignment 2

[ad_1]

CS 4104

Homework Assignment 2

Given: September 3, 2019 Due: September 13, 2019

General directions. The point value of each problem is shown in [ ]. Each solution must

include all details and an explanation of why the given solution is correct. In particular,

write complete sentences. A correct answer without an explanation is worth

no credit. The completed assignment must be submitted on Canvas as a PDF by 5:00

PM on September 13, 2019. No late homework will be accepted.

Digital preparation of your solutions is mandatory. Use of LATEX is optional, but

encouraged. No matter how you prepare your homework, please include your name.

Use of LATEX (optional, but encouraged).

• Retrieve this LATEX source file, named homework2.tex, from the course web site.

• Rename the file _solvehw2.tex, For example, for the instructor,

the file name would be heath_solvehw2.tex.

• Use a text editor (such as vi, emacs, or pico) to accomplish the next three steps.

• Uncomment the line

% setboolean{solutions}{True}

in the document preamble by deleting the %.

• Find the line

renewcommand{author}{Lenwood S. Heath}

and replace the instructor’s name with your name.

• Enter your solutions where you find the LATEX comments

% PUT YOUR SOLUTION HERE

• Generate a PDF and turn it in on Canvas by 5:00 PM on September 13, 2019.

2 Homework Assignment 2 September 3, 2019

Comment. This assignment should be more challenging than Homework Assignment 1,

so please start working on it early. It continues the use of writing in complete sentences

and writing in formal mathematical notation and begins the use of drawing digitally, in this

case to draw graphs without and with weights on vertices. As usual, pay careful attention

to the directions and ask questions on Piazza or at office hours.

It will be helpful to draw small examples of graphs to gain intuition of what is being

defined.

If you use LATEX, you can find many useful LATEX examples in the .tar files for the

lecture notes for things like pseudocode and formally stating a problem.

[60] 1. For each integer n satisfying n ≥ 1, let Vn = {v1, v2, . . . , vn} be a set of n vertices.

Let k be an integer satisfying 0 ≤ k ≤ n − 1. The n, k-braid is the undirected graph

Gn,k = (Vn,En,k) where

En,k = {(vi, vj) | i 6= j and |j − i| ≤ k}.

A free set in Gn,k is a set U ⊆ Vn such that no two vertices in U are adjacent. U is a

maximal free set if it is not possible to add a vertex to U and continue to have a free set.

A weight function on Gn,k is a function w : Vn → N, where N = {0, 1, 2, . . .}. If U ⊆ Vn,

then w(U) = Pvi2U w(vi).

A. Draw G7,2, and insert your drawing into your solutions. For this drawing,

you do not need vertex weights. List three maximal free sets for G7,2.

B. The Free Set problem takes as an instance a braid Gn,k and a weight

function w on Gn,k and returns as a solution a free set U such that w(U) is

maximum among all free sets in Gn,k. State the Free Set problem in the

formal instance/solution format that we use in class.

C. Figure 1 contains pseudocode for a greedy algorithm Greedy-Free-Set

that attempts to solve the Free Set problem. Draw an instance Gn,k,w of

Free Set for which Greedy-Free-Set does not return a correct solution.

(Here, you need to assign weights to vertices in your drawing.) Explain

your result, and include your drawing in your solution PDF.

D. Use the dynamic programming paradigm from class to develop a dynamic

programming algorithm to solve the Free Set problem for the special case

where k = 1. Give CLRS pseudocode for your algorithm. You may skip

the backtrace step. Give the £ asymptotic worst-case time complexity for

your algorithm.

E. Use the dynamic programming paradigm from class to develop a dynamic

programming algorithm to solve the Free Set problem for the special case

where k = 2. Give CLRS pseudocode for your algorithm. You may skip

the backtrace step. Give the £ asymptotic worst-case time complexity for

your algorithm.

September 3, 2019 Homework Assignment 2 3

Greedy-Free-Set(Gn,k,w)

1 // Gn,k is the n, k-braid, and w is a weight function on Gn,k.

2 // We attempt to return a free set U in Gn,k of maximum weight.

3 U = ∅

4 X = Vn

5 while X 6= ∅

6 select vi ∈ X of maximum weight w(vi)

7 U = U ∪ {vi}

8 delete vi and all neighbors of vi from X

9 return U

Figure 1: Pseudocode for a greedy algorithm for the Free Set problem.

The post CS 4104 Homework Assignment 2 appeared first on mynursinghomeworks.

[ad_2]

Source link