szf0EnsD

1\documentclass[11pt,twoside]{article}
2
3\usepackage{amssymb}
4\usepackage{amsmath}
5\usepackage{latexsym}
6\usepackage{color}
7\usepackage{graphics}
8\usepackage{xspace}
9
10% Commands for special characters
11\newcommand{\mybackslash}{\char'134}
12\newcommand{\myleftbracket}{\char'173}
13\newcommand{\myrightbracket}{\char'175}
14\newcommand{\mypercent}{\char'045}
15\newcommand{\myunderscore}{\char'137}
16
17% The 'ifthen' package supports Boolean flags
18\usepackage{ifthen}
19% The 'solutions' flag determines whether this is the original handout
20%    or a solution
21\newboolean{solutions}
22\setboolean{solutions}{False}  % Default is original handout
23
24% Uncomment the next line before starting on the solutions
25\setboolean{solutions}{True}
26
27\newcommand{\coursenumber}{CS 5114}
28\newcommand{\coursetitle}{Theory of Algorithms}
29\newcommand{\docdate}{March 25, 2022}
30\newcommand{\duedate}{April 1, 2022}
31\newcommand{\homeworknumber}{6}
32
33% The document title depends on whether these are solutions
34\ifthenelse{\boolean{solutions}}{% Then
35\newcommand{\doctitle}{Solutions to Homework Assignment \homeworknumber}
36}{% Else
37\newcommand{\doctitle}{Homework Assignment \homeworknumber}
38}
39
40% The document date depends on whether these are solutions
41\ifthenelse{\boolean{solutions}}{% Then
42\renewcommand{\docdate}{\duedate}
43}{% Else
44}
45
46% If you are the author, so put your name here
47\renewcommand{\author}{Sai Venkat R Banda}
48
49\pagestyle{myheadings}
50\markboth{\hfill\doctitle\hfill\docdate}{\docdate\hfill\doctitle\hfill}
51
52\addtolength{\textwidth}{1.00in}
53\addtolength{\textheight}{1.00in}
54\addtolength{\evensidemargin}{-1.00in}
55\addtolength{\oddsidemargin}{-0.00in}
56\addtolength{\topmargin}{-.50in}
57\setlength{\footskip}{0pt}
58
59\newcommand{\polyreduce}{\leq_{\mathrm{P}}}
60
61\newcounter{problem}
62\setcounter{problem}{0}
63\newcommand{\problem}[1]{%
64\refstepcounter{problem}\noindent\textbf{[#1] \arabic{problem}.}}
65
66\newcommand{\solution}{\bigskip\hrule\bigskip}
67\newcommand{\problembreak}{\bigskip\hrule\bigskip}
68
69\renewcommand{\theenumi}{\textbf{\Alph{enumi}}}
70\renewcommand{\theenumii}{\textbf{\roman{enumii}}}
71
72\newcommand{\emptystring}{\lambda}
73
74% Pseudocode comment symbol
75\newcommand{\comment}{\textbf{//}\ \ }
76
77% Pseudocode line numbering
78\newcounter{pseudocode}
79\newcommand{\firstline}{\setcounter{pseudocode}{0}\linenumber}
80\newcommand{\linenumber}{\refstepcounter{pseudocode}\thepseudocode}
81\newcommand{\pseudoindent}{\hspace*{26pt}}
82
83\newcommand{\nil}{\mbox{\textsc{nil}}\xspace}
84
85% Mathematical symbols
86\newcommand{\grid}{\mathcal{G}}  % Grid graph
87\newcommand{\integers}{\mathbb{Z}}  % Integers
88\newcommand{\naturals}{\mathbb{N}}  % Natural numbers
89\newcommand{\reals}{\mathbb{R}}  % Real numbers
90
91% Probability
92\newcommand{\expect}[1]{\mathbf{E}\left[#1\right]}
93\newcommand{\prob}[1]{\mathrm{Pr}\left[#1\right]}
94\newcommand{\var}[1]{\mathrm{Var}\left[#1\right]}
95
96% Logic
97\newcommand{\NOT}[1]{\neg #1}
98\newcommand{\AND}{\wedge}
99\newcommand{\OR}{\vee}
100\newcommand{\clause}[1]{\left(#1\right)}
101
102\newlength{\problemoffset}
103\setlength{\problemoffset}{0.5in}
104
105% Decision problem macro
106% A command for formatting decision problems a la Garey and Johnson
107\newcommand{\decision}[3]{%     \decision{NAME}{INSTANCE}{QUESTION}
108\begin{list}{}{
109\setlength{\leftmargin}{\problemoffset}
110\setlength{\rightmargin}{\problemoffset}
111\setlength{\parsep}{0pt}
112\setlength{\itemsep}{2pt}
113\setlength{\topsep}{\itemsep}
114\setlength{\partopsep}{\itemsep}
115}
116\item
117{\textsc{#1}}
118\item
119{INSTANCE: #2}
120\item
121{QUESTION: #3}
122\end{list}
123}
124
125% Optimization problem macro
126\newcommand{\optimization}[3]{%  \optimization{NAME}{INSTANCE}{SOLUTION}
127\begin{list}{}{
128\setlength{\leftmargin}{\problemoffset}
129\setlength{\rightmargin}{\problemoffset}
130\setlength{\parsep}{0pt}
131\setlength{\itemsep}{2pt}
132\setlength{\topsep}{\itemsep}
133\setlength{\partopsep}{\itemsep}
134}
135\item
136{\rule{0pt}{14pt}\textsc{#1}}
137\item
138{INSTANCE: #2}
139\item
140{SOLUTION: #3}
141\end{list}
142}
143
144\newcommand{\reaches}{\leadsto}
145
146% Table layout
147\newcommand{\toprule}{\rule[11pt]{0pt}{2pt}}
148\newcommand{\bottomrule}{\rule[-6pt]{0pt}{0pt}}
149\newenvironment{raggedpars}[1][2.0in]{%
150\begin{minipage}[t]{#1}\raggedright\toprule}%
151{\bottomrule\end{minipage}}
152
153% Dynamic programming macros
154\newlength{\arrowwidth}
155\setbox3=\hbox{$\nwarrow$}
156\setlength{\arrowwidth}{\wd3}
157\newcommand{\optnwarrow}[1]{\if1#1\nwarrow%
158\else\rule{\arrowwidth}{0pt}\fi}
159\newcommand{\optuparrow}[1]{\if1#1\uparrow%
160\else\rule{\arrowwidth}{0pt}\fi}
161\newcommand{\optleftarrow}[1]{\if1#1\leftarrow%
162\else\rule{\arrowwidth}{0pt}\fi}
163% Use \tablebox to specify any combination of arrows, plus the value
164\newcommand{\tablebox}[4]{%
165\setlength{\arraycolsep}{0.0pt}%
166\begin{array}{cc}%
167\optnwarrow{#1} & \optuparrow{#2} \\%
168\optleftarrow{#3} & #4%
169\end{array}%
170}
171% Use \tableboxred to specify any combination of arrows, plus the value
172% The value will be red; arrows are made red if 2 used instead of 1
173\newcommand{\optnwarrowred}[1]{\if1#1\nwarrow%
174\else\if2#1\textcolor{red}{\nwarrow}\else\rule{\arrowwidth}{0pt}\fi\fi}
175\newcommand{\optuparrowred}[1]{\if1#1\uparrow%
176\else\if2#1\textcolor{red}{\uparrow}\else\rule{\arrowwidth}{0pt}\fi\fi}
177\newcommand{\optleftarrowred}[1]{\if1#1\leftarrow%
178\else\if2#1\textcolor{red}{\leftarrow}\else\rule{\arrowwidth}{0pt}\fi\fi}
179\newcommand{\tableboxred}[4]{%
180\setlength{\arraycolsep}{0.0pt}%
181\begin{array}{cc}%
182\optnwarrowred{#1} &%
183\optuparrowred{#2} \\%
184\optleftarrowred{#3} &%
185\textcolor{red}{#4}%
186\end{array}%
187}
188
189% Definitions for this homework
190\newcommand{\spanningtrees}{\mathcal{T}}
191\newcommand{\find}{\texttt{Find}\xspace}
192\newcommand{\makeunionfind}{\texttt{MakeUnionFind}\xspace}
193\newcommand{\union}{\texttt{Union}\xspace}
194\newcommand{\unionfind}{\texttt{Union-Find}\xspace}
195
196% definitions for the DNA alphabet
197\newcommand{\A}{\mathrm{A}}
198\newcommand{\C}{\mathrm{C}}
199\newcommand{\G}{\mathrm{G}}
200\newcommand{\T}{\mathrm{T}}
201\newcommand{\blank}{\mbox{\textcolor{red}{-}}}
202
203\begin{document}
204
205\thispagestyle{empty}
206
207\begin{center}
208\begin{tabular}{lcr}
209\multicolumn{3}{c}{\Large\textbf{\coursenumber}}
210\\[0.04in]
211\multicolumn{3}{c}{\Large\textbf{\doctitle}}
212% If these are solutions, then include the author's (student's) name
213\ifthenelse{\boolean{solutions}}{% Then
214\\[0.04in]\multicolumn{3}{c}{\large\textbf{\author}}
215}{} % Else omit
216% If these are solutions, then the date is the due date
217\ifthenelse{\boolean{solutions}}{% Then
218\\[0.10in]\multicolumn{3}{c}{\duedate}
219}{% Else, put given and due dates
220\\[0.10in]
221\textbf{Given:} \docdate
222& \hspace*{1.0in} &
223\textbf{Due:} \duedate
224}
225\end{tabular}
226\end{center}
227
228% If these are solutions, then we do not include the directions
229\ifthenelse{\boolean{solutions}}{} % No directions
230{
231% Original document includes directions
232\begingroup % This allows an argument that contains multiple paragraphs
233\paragraph{General directions.}
234The point value of each problem is shown in [ ].
235Each solution must include all details and
236an explanation of why the given solution is correct.
237\textbf{In particular,
238write complete sentences.}
239A correct answer without an explanation is worth no credit.
240The completed assignment must be submitted on Canvas as a PDF by 5:00 PM
241on \duedate.
242\textbf{No late homework will be accepted.}
243
244\paragraph{Digital preparation of your solutions
245using \LaTeX\ is required.}
246Also,
247any figures drawn to include in your solutions
248must be drawn in a drawing program,
249not scanned and inserted as, say, a scanned png file.
250\textbf{If you must submit homework late due to illness,
251then please email the instructor and the GTA before the due date.}
252Follow the instructions below.
253
254\paragraph{Steps for use of \LaTeX\ (required).}
255\begin{enumerate}
256\item Retrieve the \texttt{tar} file
257named \texttt{homework\homeworknumber.tar}
258from the course web site.
259\item Extract the \LaTeX\ source file
260named
261\texttt{homework\homeworknumber.tex}
262from the \texttt{tar} file;
263there may be other files to extract as well.
264\item Rename the file
265\textit{$<$Your VT PID$>$}\texttt{{\myunderscore}solvehw\homeworknumber.tex}.
266For example,
267for the instructor,
268the file name would be
269\texttt{heath{\myunderscore}solvehw\homeworknumber.tex}.
270\item
271Use a \textbf{text editor}
272(such as \texttt{vi}, \texttt{emacs}, or \texttt{pico})
273to accomplish the next three steps\footnote{%
274As an alternative,
275try the Overleaf website
276for editing your \LaTeX\ file.
277Just use the university-supported
278service at \texttt{https://www.overleaf.com/}.}
279
280\begin{enumerate}
281
282\item
283Uncomment the line
284
285\texttt{{\mypercent} 
286{\mybackslash}setboolean{\myleftbracket}solutions{\myrightbracket}%
287{\myleftbracket}True{\myrightbracket}}
288
289in the document preamble by deleting the \texttt{\mypercent}.
290
291\item
292Find the line
293
294\texttt{{\mybackslash}renewcommand%
295{\myleftbracket}{\mybackslash}author{\myrightbracket}%
296{\myleftbracket}Lenwood S. Heath{\myrightbracket}}
297
298and replace the instructor's name with your name.
299
300\item
301Enter your solutions where you find
302the \LaTeX\ comments
303
304\texttt{{\mypercent} PUT YOUR SOLUTION HERE}
305
306\end{enumerate}
307
308\item
309Generate a PDF and upload it to Canvas by 5:00 PM on \duedate.
310\end{enumerate}
311\endgroup
312
313\problembreak
314
315\newpage
316
317}
318
319\problem{30}
320See Chapter 26 lecture notes
321for the definition of the \textsc{Maximum-Flow} problem.
322
323The \textsc{Max-Flow Decision} problem is
324\decision{Max-Flow Decision}%
325{Flow network $G=(V,E)$ with capacity function $c:V\times V\to\naturals$;
326source $s\in V$; sink $t\in V$; bound $K\geq0$.}
327{Is there a flow $f$ in $G$ with $|f|\geq K$?}
328
329As discussed in class,
330one needs an encoding function $\rho$
331that will encode an arbitrary instance $(V,E,c,s,t,K)$
332of \textsc{Max-Flow Decision} as a binary string.
333In this exercise,
334you develop such an encoding.
335
336{\bfseries
337\begin{enumerate}
338
339\item
340Explain how you will encode each of $V$, $E$, $c$, $s$, $t$, and $K$
341as a binary string.
342
343\item
344Explain how you will combine these encodings
345to obtain the desired encoding function $\rho$.
346
347\item
348Encode the following {\normalfont\textsc{Max-Flow Decision}} instance
349using your $\rho$:
350\begin{eqnarray*}
351V
352& = &
353\{s,a,b,t\}
354\\
355E
356& = &
357\{(s,a),(s,b),(a,b),(a,t),(b,t)\}
358\\
359c
360& = &
361\left(
362\begin{array}{cccc}
3630 & 57 & 9 & 0 \\
3640 & 0 & 34 & 5 \\
3650 & 0 & 0 & 4 \\
3660 & 0 & 0 & 0
367\end{array}
368\right)
369\\
370K
371& = &
3728.
373\end{eqnarray*}
374
375\item
376Give pseudocode for {\normalfont\textsc{Decode}},
377the decoding algorithm for $\rho$
378that takes a binary string and returns an instance $(V,E,c,s,t,K)$.
379
380\end{enumerate}
381}
382
383\solution
384
385% PUT YOUR SOLUTION HERE
386
387\problembreak
388
389\newpage
390
391\problem{30}
392Recall the \textsc{CNF-Sat} problem:
393\decision{CNF-Sat}%
394{Boolean formula $\phi(x_1,x_2,\ldots,x_n)$ in CNF.}%
395{Is $\phi$ satisfiable?}
396If the answer for an instance $\phi$ is \textsc{Yes},
397then we might also like an example of a satisfying truth assignment.
398
399{\bfseries
400Suppose you are given a subroutine {\normalfont\textsc{Answer-CNF-SAT}}
401that solves the {\normalfont\textsc{CNF-Sat}} problem.
402Design an algorithm {\normalfont\textsc{Satisfying-CNF-SAT}}
403that takes an instance $\phi$,
404that uses the subroutine {\normalfont\textsc{Answer-CNF-SAT}}
405some number of times,
406and that returns a satisfying true assignment for $\phi$,
407if one exists.
408Give pseudocode for your algorithm.
409Let $C(n)$ be the worst-case number of calls
410to {\normalfont\textsc{Answer-CNF-SAT}}
411required in an execution of {\normalfont\textsc{Satisfying-CNF-SAT}}.
412Give a $O$ upper bound on $C(n)$.
413
414Hint: Develop adequate notation for $\phi$.
415Return {\normalfont\nil} if there is no satisfying assignment for $\phi$.
416}
417
418\solution
419
420Solution:
421
422From the instance we can see that there are a total of n variables.
423
424Therefore total number of truth table rows covering all the n variables is $2^n$.
425
426For each row in the row, we need to check if that row is satisfiable using $Answer-CNF-SAT$.
427
428Assuming $Answer-CNF-SAT$ takes linear time to verify if current row in truth table is valid, our algorithm takes exponential time (in worst case) i.e, $O(2^n*n)$ to find if $\phi$ is $satisfiable$.
429
430\begin{tabbing}
431\textsc{Boolean isSatisfiable}$(\phi, solution)$ \\
432
433\firstline \qquad\=
434 $Satisfying-CNF-SAT-Solution = \mbox{\textsc{getSatisifiableTruthValues}}(\phi)$
435 
436\\
437\linenumber\>
438\textbf{if} \= $\mbox{\textsc{solution}} = \emptyset$ 
439\\
440\linenumber\>
441\>\textbf{return} $false$
442
443\\
444\linenumber\>
445\textbf{else} 
446\\
447\linenumber\>
448\>\textbf{return} $true$
449
450\end{tabbing}
451  
452  
453\begin{tabbing}
454
455\textsc{String getSatisifiableTruthValues}$(\phi)$ \\
456
457\firstline \qquad \= 
458$total = getTotalNumberOfVariablesInPhi(\phi)$ \\
459
460\linenumber \> 
461$possibleTruthValues = 2^{total}$ \\
462
463\linenumber \> 
464\textbf{for}  \= $number = 0$ , $number < possibleTruthValues$, $number += 1$ \\
465
466\linenumber \>  
467\>$truthValueEncoding = getTruthValueFromNumber(number, total)$ \\
468
469\linenumber \>
470\> \textbf{if} \= $Answer-CNF-SAT(\phi, truthValueEncoding)$ is $true$\\
471
472\linenumber \>
473\>\> \textbf{return} $truthValueEncoding$ \\
474
475\linenumber \>
476\textbf{return} $\emptyset$ \\
477
478\end{tabbing}
479
480\begin{tabbing}
481\textsc{String getTruthValueFromNumber}$(num, len)$ \\
482
483\firstline \qquad\=
484 $s = 00..$ // create a string of 0s of length len
485 
486\\
487\linenumber\>
488index = 0 \\
489 
490\linenumber\>
491\textbf{while} \= $\mbox{\textsc{num}} > 0$ \\
492
493
494\linenumber \>
495\> \textbf{if} \=$\mbox{\textsc{num mod 2}}$ is $1$\\
496
497\linenumber\>
498\>\> $s[index] = 1$ \\
499
500\linenumber\>
501\> index += 1 \\
502
503\linenumber\>
504\textbf{return} num
505
506\end{tabbing}
507
508Time complexity for this algorithm is $O(2^n*n)$.
509
510If the answer exists, $solution$ contains the truth value as 0, 1 encoded string. 
511
512\problembreak
513
514
515\end{document}
516