CS 170 HW 6
Algorithms代写 1 Study GroupList the names and SIDs of the members in your study group. If you have no collaborators, write “none”.
1 Study Group
List the names and SIDs of the members in your study group. If you have no collaborators, write “none”.
2 2-SAT Algorithms代写
In the 2SAT problem, you are given a set of clauses, where each clause is the disjunction (OR) of two literals (a literal is a Boolean variable or the negation of a Boolean variable).
You are looking for a way to assign a value true or false to each of the variables so that all clauses are satisfified that is, there is at least one true literal in each clause. For example, heres an instance of 2SAT:
(x1∨ x2) ∧ (x1 ∨ x3) ∧ (x1 ∨ x2) ∧ (x3 ∨ x4) ∧ (x1 ∨ x4)
This instance has a satisfying assignment: set x1, x2, x3, and x4 to true, false, false, and true, respectively.
The purpose of this problem is to lead you to a way of solving 2SAT effiffifficiently by reducing it to the problem of fifinding the strongly connected components of a directed graph. Given an instance I of 2SAT with n variables and m clauses, construct a directed graph GI = (V, E) as follows.
- GI has 2n nodes, one for each variable and its negation.
- GI has 2m edges: for each clause (α ∨ β) of I (where α, β are literals), GI has an edge from from the negation of α to β, and one from the negation of β to α.
Note that the clause (α β) is equivalent to either of the implications α⇒ β or β⇒ α. In this sense, GI records all implications in I.
3 Perfect Matching on Trees
A perfect matching in an undirected graph G = (V, E) is a set of edges E‘ ⊆ E such that for every vertex v ∈ V , there is exactly one edge in E‘ which is incident to v.
Give an algorithm which fifinds a perfect matching in a tree, or reports that no such matching exists. Describe your algorithm, prove that it is correct and analyse its running time.
4 Huffffman Coding Algorithms代写
In this question we will consider how much Huffffman coding can compress a fifile F of m characters taken from an alphabet of n = 2k characters x0, x1, … , xn-1 (each character appears at least once).
(a) Let S(F) represent the number of bits it takes to store F without using Huffffman coding (i.e., using the same number of bits for each character). Represent S(F) in terms of m and n.
(b) Let H(F) represent the number of bits used in the optimal Huffffman coding of F. We defifine the effiffifficiency E(F) of a Huffffman coding on F as E(F) := S(F)/H(F). For each m and n describe a fifile F for which E(F) is as small as possible.
(c) For each m and n describe a fifile F for which E(F) is as large as possible. How does the largest possible effiffifficiency increase as a function of n? Give you answer in big-O notation.
5 Minimum Spanning k-Forest Algorithms代写
Given a graph G(V, E) with nonnegative weights, a spanning k-forest is a cycle-free collection of edges F ⊆ E such that the graph with the same vertices as G but only the edges in F has k connected components. For example, consider the graph G(V, E) with verticesV = {A, B, C, D, E} and all possible edges. One spanning 2-forest of this graph is F = {(A, C),(B, D),(D, E)}, because the graph with vertices V and edges F has components {A, C}, {B, D, E}.
The minimum spanning k-forest is defifined as the spanning k-forest with the minimum total edge weight. (Note that when k = 1, this is equivalent to the minimum spanning tree). In this problem, you will design an algorithm to fifind the minimum spanning k-forest. For simplicity, you may assume that all edges in G have distinct weights.
(a) Algorithms代写
Defifine a j-partition of a graph G to be a partition of the vertices V into j (non-empty) sets. That is, a j-partition is a list of j sets of vertices Π = {S1, S2 . . . Sj} such that every Si includes at least one vertex, and every vertex in G appears in exactly one Si. For example, if the vertices of the graph are {A, B, C, D, E}, one 3-partition is to split the vertices into the sets Π = {{A, B}, {C}, {D, E}}.
Defifine an edge (u, v) to be crossing a j-partition Π = {S1, S2 . . . Sj} if the set in Π containing u and the set in Π containing v are difffferent sets. For example, for the 3-partition Π = {{A, B}, {C}, {D, E}}, an edge from A to C would cross Π.
Show that for any j-partition Π of a graph G, if j > k then the lightest edge crossing Π must be in the minimum spanning k-forest of G.
(b) Give an effiffifficient algorithm for fifinding the minimum spanning k-forest.
Please give a 3-part solution.
其他代写：homework代写 java代写 matlab代写 program代写 project代写 essay作业代写 finance代写 python代写 report代写 paper代写 assignment代写 加拿大代写 作业代写 作业加急 英国代写 北美作业代写
