这是一份CMU卡内基梅隆大学的随机过程Design and Analysis of Algorithms代考成功案例。
Problem 1. True or False. [44 points] (11 parts)
Circle $\mathbf{T}$ or $\mathbf{F}$ for each of the following statements to indicate whether the statement is true or false, respectively, and briefly explain why. Your justification is worth more points than your true-or-false designation.
(a) T F [4 points] If problem $A$ can be reduced to 3SAT via a deterministic polynomialtime reduction, and $A \in \mathrm{NP}$, then $A$ is NP-complete.
(b) $\mathbf{T} \mathbf{F}[4$ points] Let $G=(V, E)$ be a flow network, i.e., a weighted directed graph with a distinguished source vertex $s$, a sink vertex $t$, and non-negative capacity $c(u, v)$ for every edge $(u, v)$ in $E$. Suppose you find an $s$ – $t$ cut $C$ which has edges $e_{1}, e_{2}, \ldots, e_{k}$ and a capacity $f$. Suppose the value of the maximum $s$ – $t$ flow in $G$ is $f$.
Now let $H$ be the flow network obtained by adding 1 to the capacity of each edge in $C$. Then the value of the maximum $s$ – $t$ flow in $H$ is $f+k$.
(c) $\mathbf{T} \mathbf{F}[4$ points $]$ Let $A$ and $B$ be optimization problems where it is known that $A$ reduces to $B$ in polynomial time. Additionally, it is known that there exists a polynomial-time 2 -approximation for $B$. Then there must exist a polynomialtime 2-approximation for $A$.
(d) $\mathbf{T} \mathbf{F}[4$ points] There exists a polynomial-time 2-approximation algorithm for the general Traveling Salesman Problem.
Problem 2. Taming Max-Cut [10 points] A CUT, in a graph $G=(V, E)$, is a partition of $V$ into two non-intersecting sets $A, B$. An edge is said to be in the cut if one of its end points is in $A$ and the other is in $B$. In the MAX-CUT problem, the objective is to maximize the number of edges in the cut. We intend to design an approximation scheme for MAX-CUT. Consider the following scheme. Every vertex $v \in V$ is assigned to $A, B$ uniformly at random.
(a) What is the probability that $e \in E$ is in the cut?
(b) What is the expected number of edges in the cut?
Solution: With probability $1 / 2$, one vertex of $e$ is assigned to a set different from the other. Thus, the probability that $e$ is in the cut is $1 / 2$.
Use an indicator variable for every edge with probability of success(being in the cut) being 1/2. Since, the variables are identical and independent, each experiment is a Bernouli experiement. The expected number of successes among the $|E|$ Bernouli trails is $|E| / 2$. Thus, the expected number of edges in the cut is $|E| / 2$.
Problem 3. Traveling with the salesman. [20 points] In the traveling-salesman problem, a salesman must visit $n$ cities. Modeling the problem as a complete graph on $n$ vertices, we can say that the salesman wishes to make a tour or a hamiltonian cycle, visiting each city exactly only once and finishing at the city he starts from. The salesman incurs a nonnegative integer $\operatorname{cost} c(i, j)$ to travel from city $i$ to city $j$, and the salesman wishes to make a tour whose total cost is minimum, where the total cost is the sum of the individual costs along the edges of the tour.
(a) Formulate the traveling salesman problem as a language.
$$
\mathrm{TSP}=
$$
(b) Prove that TSP $\in N P$.
Solution:
$\mathrm{TSP}=\left{\langle n, c, k>| \begin{array}{l}\text { A complete graph of } n \text { vertices with non-negative edge } \ \text { weights } c \text { has a hamiltonian cycle of cost at most } k .\end{array}\right}$
An instance $$ can be verified to be in TSP given a tour (a permutation of indices) as the certificate. The tour can be easily checked in poly-time to traverse every node exactly once and have a satisfying total cost.
real analysis代写analysis 2, analysis 3请认准UprivateTA™. UprivateTA™为您的留学生涯保驾护航。
概率论代考
离散数学代写
Overview
This core course covers good principles of algorithm design, elementary analysis of algorithms, and fundamental data structures. The emphasis is on choosing appropriate data structures and designing correct and efficient algorithms to operate on these data structures.
Learning outcomes
This is a first course in data structures and algorithm design. Students will:
- learn good principles of algorithm design;
- learn how to analyse algorithms and estimate their worst-case and average-case behaviour (in easy cases);
- become familiar with fundamental data structures and with the manner in which these data structures can best be implemented; become accustomed to the description of algorithms in both functional and procedural styles;
- learn how to apply their theoretical knowledge in practice (via the practical component of the course).
Synopsis
- Program costs: time and space. Worst case and average case analysis. Asymptotics and “big O” notation. Polynomial and exponential growth. Asymptotic estimates of costs for simple algorithms. Use of induction and generating functions. [2]
- Algorithm design strategies: top down design, divide and conquer. Application to sorting and searching and to matrix algorithms. Solution of relevant recurrence relations. [4]
- Data structures and their representations: arrays, lists, stacks, queues, trees, heaps, priority queues, graphs. [3]
- Introduction to discrete optimisation algorithms: dynamic programming, greedy algorithms, shortest path problems. [3]
- Graph algorithms: examples of depth-first and breadth-first search algorithms. Topological sorting, connected components. [3]
Syllabus
Basic strategies of algorithm design: top-down design, divide and conquer, average and worst-case criteria, asymptotic costs. Simple recurrence relations for asymptotic costs. Choice of appropriate data structures: arrays, lists, stacks, queues, trees, heaps, priority queues, graphs. Applications to sorting and searching, matrix algorithms, shortest-path and spanning tree problems. Introduction to discrete optimisation algorithms: dynamic programming, greedy algorithms. Graph algorithms: depth first and breadth first search.
