Construction Problems | String (Computer Science) | Integer

of 10
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Documents

Published:

Views: 14 | Pages: 10

Extension: PDF | Download: 0

Share
Description
CONSTRUCTION
Tags
Transcript
  CONSTRUCTION PROBLEMS VIPUL NAIK Abstract.  In this article, I describe the general problem of constructing configurations subject tocertain conditions, and the use of techniques like “greedy algorithms” to construct such configurations 1.  The pivotal role of construction problems 1.1.  Construction, existence and enumeration.  The general situation of combinatorics could besummarized as follows: We are given a general kind of configuration and we are asked to determinewhether there are any configurations of that general kind that satisfy certain particular constraints. Wecould have:(1) The  construction   problem which asks for an algorithm or method to construct a configurationsatisfying the constraints(2) The  existence   problem which simply asks for an answer to whether a configuration exists(3) The  enumeration   problem which asks for the total number of configurationsSkill at solving the construction problem helps both with the existence problem and the enumerationproblem, as follows: ã  If we are able to actually construct  a   configuration, we can in particular prove that it exists. ã  If we are able to devise an algorithm that constructs  all   configurations, and we can measure thenumber of times that algorithm outputs a configuration, then we have counted the number of configurations.Thus, construction problems in combinatorics, apart from being important in their own right, alsohelp with existential and enumeration problems.2.  Construction by induction 2.1.  Construction by induction: the idea.  Let  C  n  be the set of   all   configurations of “size”  n . Then,construction by induction uses a listing of the elements of   C  n − 1  to obtain a listing of the elements of   C  n .There are two possibilities for this. One is that we  first   pick a configuration of “size”  n − 1 (that is,an element of   C  n − 1 ) and then make some further choices and decisions to obtain a configuration of size n  (that is, an element of   C  n ). Note that since we could make these choices in multiple ways, we mayhave more than one configuration of size  n  corresponding to the configuration of size  n − 1.The other approach is to start off with a (as yet unspecified) configuration of size  n , make some choicesand decisions and then reach the situation where we have to choose a configuration of size  n − 1.Let’s look at each of these methods.2.2.  Top-down construction.  In a  top-down   construction, we start with trying to construct the con-figuration of size  n , make a few choices, and then reach down to the situation where we have to select aconfiguration of size  n − 1.Let’s take the example where the “configuration” of “size”  n  is an arbitrary permutation of the set { 1 , 2 ,...,n } . In this context,  C  n  is the set of all permutations on  n  letters, while  C  n − 1  is the set of allpermutations on  n − 1 letters.A permutation here is described by a “word” with the first letter being where 1 goes, the second letterbeing where 2 goes, and so on. Thus, the elements of   C  n  are words of length  n  (with all letters distinctand drawn from 1 to  n ) while the elements of   C  n − 1  are words of length  n − 1 (with all letters distinctand drawn from 1 to  n − 1).Then, in order to describe a particular configuration of size  n , we start out by specifying the firstletter (that is, the image of 1 under the permutation). There are  n  choices for this. Once we have made c  Vipul Naik, B.Sc. (Hons) Math and C.S., Chennai Mathematical Institute. 1  this choice, we can strip off the first letter and get a word of length  n − 1 with distinct letters drawnfrom 1 to  n , except the first letter.The number of ways of choosing such words equals the numbers of ways of choosing words of length n − 1 with letters drawn from 1 to  n − 1 (by simply relabelling). This corresponds to the cardinality of  C  n − 1 , and we get: | C  n |  =  nC  n − 1 Top-down approaches are typically more  local   in nature since the initial local choices have to be made before   fixing the configuration of size  n − 1. In other words, when following a top-down approach, wecannot  a priori   know the global impact.In the case of permutations that is not a problem, because whatever choice we make for the first letter,the behaviour for the remaining  n − 1 letters is qualitatively similar.2.3.  Bottom-up construction.  In  bottom-up  construction, we start by constructing the configurationof size  n − 1, and then from that we proceed to construct the configuration of size  n .That is, for very element  c  ∈  C  n − 1  we try various ways of augmebnting  c  to obtain an element of   C  n .Bottom-up approaches are typically more  global   in nature since here the local choices have to be made after   fixing the configuration (hence we can make them more intelligently).3.  A bottom-up problem: convolutions 3.1.  Problem statement.  Here’s a (rather hard) problem which is best solved bottom-up: Problem 1  (Romanian TST 2002) .  Consider words of length  n  in four letters:  a ,  b ,  c  and  d . Definea convolution in a word as a contiguous repetition of the same block, for instance  aa  is a convolution andso is  abab . Call a word  convolution-free   if it does not contain any convolutions. Prove that the numberof convolution-free words of length  n  is at least 2 n .3.2.  Exploration of this problem.  We first set this problem within the framework of “configurations”and “constraints”: ã  The  configurations   here are the strings of length  n  with letters drawn from  a ,  b ,  c  and  d ã  The  constraint   is that of being convolution-free, viz there is no convolution  anywhere   in the word.We want to show that there are lots of configurations (namely at least 2 n ) of length  n .In order to use induction, let’s first try to understand how convolution-free words of length  n  arerelated to convolution-free words of smaller length. : ã  Let  w  be a string of length  n  and  v  be a contiguous substring of   w . Then any convolution in  v gives a convolution in  w . ã  Hence, if   w  is convolution-free, so is every contiguous substring of   w . ã  In particular, if   w  is convolution-free, then the substring obtained by stripping off the last letterof   w , is also convolution-free.This means that to construct all the convolution-free words of length  n , it suffices to first constructall convolution-free words of length  n − 1, and then try each of the four possibilities for the last letter.3.3.  Some notation.  For our convenience, we’ll let  C  n  denote the set of all convolution-free wordsof length  n , and  D n  denote the set of all words of length  n  whose initial segment of length  n  −  1 isconvolution-free.To be able to manipulate strings (words) effectively, we’ll define the following notation for substrings.Whenever  n  ≥  m + k − 1, define  i m,k  as the map that takes a string of length  n  and outputs the contiguoussubstring of length  k  starting at the  m th place. Then, the fact that every contiguous substring of aconvolution-free word is convolution-free, can be expressed via the fact that  i m,k  maps  C  n  to inside  C  k .3.4.  How many will work?  Here’s the question: given a convolution-free word of length  n − 1, howmany possibilities are there for the last letter so that the new word is again convolution-free?Answer: It could be as large as 3 and as low as 0.For instance, if the word so far is  abc , then any of the letters  a ,  b , or  d  can be added.On the other hand, if the word so far is  babcbabdbabcbab  then  none   of the letters works. 2  3.5.  What’s the algorithm?  Let’s look again at the procedure for obtaining convolution-free words of length  n . ã  First, list all the elements of   C  n − 1 , viz all the convolution-free words of length  n − 1. ã  Using this, list all the elements of   D n . Recall that  D n  is the set of words of length  n  whose initialsegment of length  n − 1 is convolution-free.  | D n |  = 4 | C  n − 1 |  because all we do is try appendingeach of the four letters to each element of   C  n − 1 . ã  Try every word that arises by attaching a letter at the end to a convolution-free word of length n − 1. For this word, check that it is convolution-free.If the initial segment of   n − 1 letters is convolution-free, then any convolution in the new word musthave been  introduced   by the last letter – hence one of the blocks must contain the last letter. This forcesthe following picture:The last  k  letters are a repeat of the  k  letters just before them (here  k  ≤  n/ 2).Put in symbols, this is the same as: ∀  w  ∈  D n  \ C  n , ∃ k  ≤  n/ 2 such that  i m − 2 k +1 ,k ( w ) =  i m − k +1 ,k ( w )Let’s think of it as a filter. We send to this filter an element in  D n . The filter checks, for each  k , if thelast  k  letters are a repeat of the  k  letters that come before them. If this happens, the word is “filteredout” by the filter.Thus, to find out how many candidates get filtered in, we can calculate how many candidates getfiltered out.Let  F  n  denote the set of candidates that are filtered out by this process. In other words,  F  n  =  D n \ C  n .Then, we have: F  n  =  1 ≤ k ≤ n/ 2 F  n,k where  F  n,k  is the set of those candidates that are rejected because the last  k  letters are a repeat of the  k  letters before them.In symbols: F  n,k  =  { w  ∈  D n | i m − 2 k +1 ,k ( w ) =  i m − k +1 ,k ( w ) } 3.6.  Cardinality bounding.  To get a bound on the size of   F  n , it suffices to get a bound on the size of  F  n,k  for each  k . Let’s look closely at a word  w  ∈  F  n,k .By assumption, the initial segment of   w  of length  n − 1 is convolution-free, hence, since  k  ≥  1, theinitial segment of   w  of length  n − k  is convolution-free. Further, once we fix the first  n − k  letters, thelast  k  are anyway fixed (since they are a repeat of earlier letters). Hence, we have an injective map: i 1 ,n − k  :  F  n,k  →  C  n − k which just strips the last  k  coordinates.In particular: | F  n,k | ≤ | C  n − k | Thus: | F  n | ≤  k | F  n,k | = ⇒ | F  n | ≤  k | C  n − k | = ⇒ | C  n | ≥ | D n |−  k | C  n − k | = ⇒  t n  ≥  4 t n − 1  −  k t n − k 3  3.7.  The final step.Claim.  For any  n  ≥  2,  t n  ≥  2 t n − 1 Proof.  Let us assume that the result holds inductively. Then we have: t n − 1  ≥  2 t n − 2  ≥  2 2 t n − 3  ... Thus in general: t n − k  ≤  t n − 1 2 n − 1 − k Plugging this in the inequality for  t n , we get: t n  ≥  4 t n − 1  − t n − 1 (1 + 12 + 12 2  ... )= ⇒  t n  ≥  4 t n − 1  − 2 t n − 1 = ⇒  t n  ≥  2 t n − 1 We are using lots of loose inequalities here (for instance, the actual summation is only a finite one butwe are extending it to an infinite summation so that we can apply the formula for summing a geometricprogression).   3.8.  Learning and value from this proof.  This proof brings out many ideas:(1) The nature of the constraints and dependencies encourages a bottom-up construction: In theproblem of finding convolution-free words, a top-down approach is less natural, because there arelots of dependencies (in fact, there are dependencies all over the place). Hence, it is hard to makeone’s  initial   choices wisely without knowing how the rest of the word looks like. A bottom-upapproach, where one starts off with a convolution-free word of length  n − 1 and  then   tries to plugin the last letter, thus takes the dependencies into account more effectively.(2) For any  specific   configuration of size  n − 1, we cannot predict how many configurations of size n  we can construct from it. However, we can count (or at least bound) the  total   number of configurations that get rejected.(3) When trying to prove a lower bound on a combinatorial quantity, it is sometimes more helpfulto inductively prove a lower bound on the growth rate. For instance, in this problem, we startedoff with trying to prove  t n  >  2 n , but found it easier to prove that  t n  ≥  2 t n − 1 .4.  Greedy algorithms for existential problems 4.1.  The core idea.  Suppose we have a notion of configurations for every size  n , and we are asked todetermine whether there exists a configuration of that size  n . Then, the top-down approach will say:make some initial choices, and then come down to the problem of constructing a configuration of size n − 1.Suppose now that there  does   exist a configuration of size  n . Then there are two possibilities: ã  Our initial choices are wise and they help us hit a configuration ã  Our initial choices are unwise and they do not help us hit a configurationOn the other hand, suppose there does not exist a configuration of size  n . Then there is only onepossibility: our initial choices do not help us hit a configuration.Thus, if our initial choices lead to a correct configuration, we have solved the existence problempositively. However, if our initial choices do  not   yield a correct configuration, we cannot be sure whetheror not there exists a correct configuration. The problem is that our initial choices  may have been bad  .This leads us to the question: Can we use some local heuristic to ensure that our initial choicesare always the  best  , that is, that if there is a correct configuration, then there will also be a correctconfiguration yielded by our initial choices? 4
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks
SAVE OUR EARTH

We need your sign to support Project to invent "SMART AND CONTROLLABLE REFLECTIVE BALLOONS" to cover the Sun and Save Our Earth.

More details...

Sign Now!

We are very appreciated for your Prompt Action!

x