CS 512 Test 4

m4_divert(2) m4_define(_commentnesting, 0) m4_define(_begincomment,m4_dnl m4_ifelse(_commentnesting, 0, )) m4_define(_warning,m4_dnl _begincomment()This document was created by gen-_name.html Do not edit this document, edit gen-_name.html._endcomment()) m4_define(_hdrs, ) m4_define(_anchor_no, 0) m4_define(_abs, m4_ifelse(m4_eval($1 < 0), 1, m4_eval(-($1)), $1)) m4_define(hdr, _warning() $2 _warning() m4_ifelse(m4_eval($1 >= 0), 1, m4_define(`_hdrs', _hdrs`'_anchor_no$1m4_translit(`$2', `,', ))) m4_define(_anchor_no, m4_eval(_anchor_no + 1)) ) m4_define(usetag, _warning()$2_warning()) m4_define(puttag, _warning()$2_warning()) m4_changecom() m4_define(sps, $1^$2) m4_define(sbs, $1_$2) m4_define(,_warning()$1_warning()) m4_define(,_warning()$1_warning()) m4_define(itl,_warning()$1_warning()) m4_define(bld,_warning()$1_warning()) m4_define(hrf,_warning()$2_warning()) m4_define(mailat,_warning()hrf(mailto:$1,$1)_warning()) m4_define(nwsgrp, hrf(news:$1, $1)) m4_define(bookref, $1, $2. $3: $4, $5.) m4_define(i2m,m4_ifelse( $1,01,January, $1,02,February, $1,03,March, $1,04,April, $1,05,May, $1,06,June, $1,07,July, $1,08,August, $1,09,September, $1,10,October, $1,11,November,December)) m4_dnl $Revision: 1.5 $, $Date: 1999/12/09 19:16:32 $ CS 512 Test 4 hdr(2, Test 4 - Computational Complexity and Heuristic Algorithms) hdr(3, CS 512, Algorithm Design)

Define NP, NP hard, and NP complete problems. Is sorting an NP problem? Is it an NP hard problem? Is it an NP complete problem? Explain your answers.
A problem is an NP problem if it can be solved in polynomial time with an algorithm from the nondeterministic computation model. A problem itl(Q) is NP hard if every NP problem can be reduced to itl(Q). A problem is NP complete if it is NP hard and is an NP problem.
Sorting is an NP problem because it can be solved in polynomial time with an algorithm - quicksort, for example - from the nondeterministic computational model (although quicksort doesn't use the choice operator, it can still be considered a nondeterministic algorithm because the nondeterministic computation model is just the deterministic computation model with choice added). Sorting is NP hard if all NP problems can be reduced to sorting problems; nobody knows if sorting is NP hard. Because nobody knows if sorting is NP hard, nobody knows if sorting is NP complete.
Why is it we can say that any problem in P is also in NP?
A problem is in P if it can be solved by a deterministic algorithm in polynomial run-time. The nondeterministic model of computation is just the deterministic module of computation augmented with the choice operator, and so a deterministic algorithm can be thought of as a nondeterministic algorithm that doesn't use choice. This means any problem in P is also in NP.
Show a deterministic backtracking algorithm for sorting. Do not do any branch-and-bounding or any other optimizations, and do not use the choice operator; just show a pure backtracking algorithm for sorting.
The idea is to move each element in the array to every other element in the array and recurse on the other elements. Essentially, one sweep through the array represents a permutation of the elements of the array; this algorithm is equivalent to generating permutations.
```
bool backtrack_sort(a, size)

  if size = |a|
    return check_sorted(a)

  for i <- size to |a| - 1
    swap(acopy[size], acopy[i])
    if backtrack_sort(a, size + 1)
      return true
    swap(a[size], a[i])

  return false
```
Letting itl(T)(itl(n)) represent the backtrack_sort() run-time on an array of itl(n) elements, the for body runs in itl(T)(itl(n) - 1) time, and the for loop iteration count is bounded by itl(n), so itl(T)(itl(n)) = itl(n)itl(T)(itl(n) - 1), which unrolls into a Theta(itl(n)!) run-time.
The set partition problem accepts a set of integers and partitions the set into two subsets such that the sum of the integers in each subset are equal. Implement a greedy approximation algorithm to solve the set partition problem; that is, show an algorithm that uses greed to divide the input set into two approximately equal subsets.
One way to use greed in a partition is to always minimize the difference between the sums of the partition sets when moving an element from the input set to the partition sets. This is a strictly local optimization, depending only on the elements in the input set and the sums of the partition sets; that it leads to a non-optimal global solution can be seen by running the following algorithm on an input set consisting of itl(n) 1s and itl(n):
```
greedy_partition(S)

  s1 <- { }
  s2 <- { }

  do S != {}
    if sum(s1) >= sum(s2)
      pick s from S such that |sum(s1) - sum(s2) - s| is minimal
      assign s to s2
    else
      pick s from S such that |sum(s2) - sum(s1) - s| is minimal
      assign s to s1
    fi
    remove s from S
  od
```
Each pick can be done with a linear scan of S and the do iteration count is bounded by the size of S, leading to a Theta(sps(itl(n), 2)) run-time where itl(n) = |S|.

This page last modified on 29 i2m(10) 1999. m4_dnl $Revision: 1.2 $, $Date: 1999/03/12 17:36:48 $ m4_divert(1) m4_changequote({, }) {m4_define(tblfcntnts, _toc_tableit(}_hdrs{) _toc_down(_toc_ilevel, _toc_level) ) m4_define(_toc_tableit, m4_regexp($1, $[0-9]+$$[0-9]+$$[^]+$$.*$, m4_ifdef(_toc_level, , m4_define(_toc_level, m4_eval(\2 - 1)) m4_define(_toc_ilevel, _toc_level)) _toc_entry(\1, \2, \3) _toc_tableit(\4)) ) m4_define(_toc_down, m4_ifelse(m4_eval($1 < $2), 1, _toc_down($1, m4_eval($2 - 1))) ) m4_define(_toc_entry, m4_ifelse(m4_eval($2 > _toc_level),1,

m4_translit($2, , ,) ) }