The complexity of certain incremental code generation problems

This paper looks at the complexity of four different incremental problems. The following are the problems considered: (1) Interval partitioning of a flow graph (2) Breadth first search (BFS) of a directed graph (3) Lexicographic depth first search (DFS) of a directed graph (4) Constructing the postorder listing of the nodes of a binary tree. The last problem arises out of the need for incrementally computing the Sethi-Ullman (SU) ordering [1] of the subtrees of a tree after it has undergone changes of a given type. These problems are among those that claimed our attention in the process of our designing algorithmic techniques for incremental code generation. BFS and DFS have certainly numerous other applications, but as far as our work is concerned, incremental code generation is the common thread linking these problems. The study of the complexity of these problems is done from two different perspectives. In [2] is given the theory of incremental relative lower bounds (IRLB). We use this theory to derive the IRLBs of the first three problems. Then we use the notion of a bounded incremental algorithm [4] to prove the unboundedness of the fourth problem with respect to the locally persistent model of computation. Possibly, the lower bound result for lexicographic DFS is the most interesting. In [5] the author considers lexicographic DFS to be a problem for which the incremental version may require the recomputation of the entire solution from scratch. In that sense, our IRLB result provides further evidence for this possibility with the proviso that the incremental DFS algorithms considered be ones that do not require too much of preprocessing.

Complexity of distance paired-domination problem in graphs

Suppose G = (V, E) is a simple graph and k is a fixed positive integer. A subset D subset of V is a distance k-dominating set of G if for every u is an element of V. there exists a vertex v is an element of D such that d(G)(u, v) <= k, where d(G)(u, v) is the distance between u and v in G. A set D subset of V is a distance k-paired-dominating set of G if D is a distance k-dominating set and the induced subgraph GD] contains a perfect matching. Given a graph G = (V, E) and a fixed integer k > 0, the MIN DISTANCE k-PAIRED-DOM SET problem is to find a minimum cardinality distance k-paired-dominating set of G. In this paper, we show that the decision version of MIN DISTANCE k-PAIRED-DOM SET iS NP-complete for undirected path graphs. This strengthens the complexity of decision version Of MIN DISTANCE k-PAIRED-DOM SET problem in chordal graphs. We show that for a given graph G, unless NP subset of DTIME (n(0)((log) (log) (n)) MIN DISTANCE k-PAIRED-Dom SET problem cannot be approximated within a factor of (1 -epsilon ) In n for any epsilon > 0, where n is the number of vertices in G. We also show that MIN DISTANCE k-PAIRED-DOM SET problem is APX-complete for graphs with degree bounded by 3. On the positive side, we present a linear time algorithm to compute the minimum cardinality of a distance k-paired-dominating set of a strongly chordal graph G if a strong elimination ordering of G is provided. We show that for a given graph G, MIN DISTANCE k-PAIRED-DOM SET problem can be approximated with an approximation factor of 1 + In 2 + k . In(Delta(G)), where Delta(G) denotes the maximum degree of G. (C) 2012 Elsevier B.V All rights reserved.

On the Parameterized Complexity of the Maximum Edge 2-Coloring Problem

We investigate the parameterized complexity of the following edge coloring problem motivated by the problem of channel assignment in wireless networks. For an integer q >= 2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. This problem is NP-hard for q >= 2, and has been well-studied from the point of view of approximation. Our main focus is the case when q = 2, which is already theoretically intricate and practically relevant. We show fixed-parameter tractable algorithms for both the standard and the dual parameter, and for the latter problem, the result is based on a linear vertex kernel.

On the Parameterized Complexity of Finding Separators with Non-Hereditary Properties

We study the problem of finding small s-t separators that induce graphs having certain properties. It is known that finding a minimum clique s-t separator is polynomial-time solvable (Tarjan in Discrete Math. 55:221-232, 1985), while for example the problems of finding a minimum s-t separator that induces a connected graph or forms an independent set are fixed-parameter tractable when parameterized by the size of the separator (Marx et al. in ACM Trans. Algorithms 9(4): 30, 2013). Motivated by these results, we study properties that generalize cliques, independent sets, and connected graphs, and determine the complexity of finding separators satisfying these properties. We investigate these problems also on bounded-degree graphs. Our results are as follows: Finding a minimum c-connected s-t separator is FPT for c=2 and W1]-hard for any ca parts per thousand yen3. Finding a minimum s-t separator with diameter at most d is W1]-hard for any da parts per thousand yen2. Finding a minimum r-regular s-t separator is W1]-hard for any ra parts per thousand yen1. For any decidable graph property, finding a minimum s-t separator with this property is FPT parameterized jointly by the size of the separator and the maximum degree. Finding a connected s-t separator of minimum size does not have a polynomial kernel, even when restricted to graphs of maximum degree at most 3, unless .

Kernelization complexity of possible winner and coalitional manipulation problems in voting

In the POSSIBLE WINNER problem in computational social choice theory, we are given a set of partial preferences and the question is whether a distinguished candidate could be made winner by extending the partial preferences to linear preferences. Previous work has provided, for many common voting rules, fixed parameter tractable algorithms for the POSSIBLE WINNER problem, with number of candidates as the parameter. However, the corresponding kernelization question is still open and in fact, has been mentioned as a key research challenge 10]. In this paper, we settle this open question for many common voting rules. We show that the POSSIBLE WINNER problem for maximin, Copeland, Bucklin, ranked pairs, and a class of scoring rules that includes the Borda voting rule does not admit a polynomial kernel with the number of candidates as the parameter. We show however that the COALITIONAL MANIPULATION problem which is an important special case of the POSSIBLE WINNER problem does admit a polynomial kernel for maximin, Copeland, ranked pairs, and a class of scoring rules that includes the Borda voting rule, when the number of manipulators is polynomial in the number of candidates. A significant conclusion of our work is that the POSSIBLE WINNER problem is harder than the COALITIONAL MANIPULATION problem since the COALITIONAL MANIPULATION problem admits a polynomial kernel whereas the POSSIBLE WINNER problem does not admit a polynomial kernel. (C) 2015 Elsevier B.V. All rights reserved.

Teachers and pupils: educational experiences and school based responses to the conflict in Northern Ireland

This article describes a study which examined (a) the impact of the political conflict on teachers' and ppils' experiences of education in Northern Ireland and (b) the impact of curricular-based interventions designed to support the ppils and reduce prejudice. The focus of the second part of the article is on the prejudice reduction initiatives identified. A total of 44 staff and 78 pupils spread across 8 schools participated and both teachers' and ppils' perspectives were identified, the latter being an extremely important dimension which has rarely been addressed in previous studies of this area. The findings, which highlight the complexity of the impact of the political conflict, are considered to have both practical and theoretical implications for prejudice reduction programs.

A method for analysing operational complexity in supply chains

This paper proposes a method for analysing the operational complexity in supply chains by using an entropic measure based on information theory. The proposed approach estimates the operational complexity at each stage of the supply chain and analyses the changes between stages. In this paper a stage is identified by the exchange of data and/or material. Through analysis the method identifies the stages where the operational complexity is both generated and propagated (exported, imported, generated or absorbed). Central to the method is the identification of a reference point within the supply chain. This is where the operational complexity is at a local minimum along the data transfer stages. Such a point can be thought of as a ‘sink’ for turbulence generated in the supply chain. Where it exists, it has the merit of stabilising the supply chain by attenuating uncertainty. However, the location of the reference point is also a matter of choice. If the preferred location is other than the current one, this is a trigger for management action. The analysis can help decide appropriate remedial action. More generally, the approach can assist logistics management by highlighting problem areas. An industrial application is presented to demonstrate the applicability of the method.

The Ontario Municipal Freedom of Information and Protection of Individual Privacy Act: an analysis of its application to school boards

In Canada freedom of information must be viewed in the context of governing -- how do you deal with an abundance of information while balancing a diversity of competing interests? How can you ensure people are informed enough to participate in crucial decision-making, yet willing enough to let some administrative matters be dealt with in camera without their involvement in every detail. In an age when taxpayers' coalition groups are on the rise, and the government is encouraging the establishment of Parent Council groups for schools, the issues and challenges presented by access to information and protection of privacy legislation are real ones. The province of Ontario's decision to extend freedom of information legislation to local governments does not ensure, or equate to, full public disclosure of all facts or necessarily guarantee complete public comprehension of an issue. The mere fact that local governments, like school boards, decide to collect, assemble or record some information and not to collect other information implies that a prior decision was made by "someone" on what was important to record or keep. That in itself means that not all the facts are going to be disclosed, regardless of the presence of legislation. The resulting lack of information can lead to public mistrust and lack of confidence in those who govern. This is completely contrary to the spirit of the legislation which was to provide interested members of the community with facts so that values like political accountability and trust could be ensured and meaningful criticism and input obtained on matters affecting the whole community. This thesis first reviews the historical reasons for adopting freedom of information legislation, reasons which are rooted in our parliamentary system of government. However, the same reasoning for enacting such legislation cannot be applied carte blanche to the municipal level of government in Ontario, or - ii - more specifially to the programs, policies or operations of a school board. The purpose of this thesis is to examine whether the Municipal Freedom of Information and Protection of Privacy Act, 1989 (MFIPPA) was a neccessary step to ensure greater openness from school boards. Based on a review of the Orders made by the Office of the Information and Privacy Commissioner/Ontario, it also assesses how successfully freedom of information legislation has been implemented at the municipal level of government. The Orders provide an opportunity to review what problems school boards have encountered, and what guidance the Commissioner has offered. Reference is made to a value framework as an administrative tool in critically analyzing the suitability of MFIPPA to school boards. The conclusion is drawn that MFIPPA appears to have inhibited rather than facilitated openness in local government. This may be attributed to several factors inclusive of the general uncertainty, confusion and discretion in interpreting various provisions and exemptions in the Act. Some of the uncertainty is due to the fact that an insufficient number of school board staff are familiar with the Act. The complexity of the Act and its legalistic procedures have over-formalized the processes of exchanging information. In addition there appears to be a concern among municipal officials that granting any access to information may be violating personal privacy rights of others. These concerns translate into indecision and extreme caution in responding to inquiries. The result is delay in responding to information requests and lack of uniformity in the responses given. However, the mandatory review of the legislation does afford an opportunity to address some of these problems and to make this complex Act more suitable for application to school boards. In order for the Act to function more efficiently and effectively legislative changes must be made to MFIPPA. It is important that the recommendations for improving the Act be adopted before the government extends this legislation to any other public entities.

The relation of attentional, emotional, and social regulation to cognitive competence, from infancy to school entry

Recent research on the sources of cognitive competence in infancy and early childhood has highlighted the role of social and emotional factors (for example, Lewis, 1993b). Exploring the roots of competence requires a longitudinal and multivariate approach. To deal with the resulting complexity, potentially integrative theoretical constructs are required. One logical candidate is self-regulation. Three key developmental questions were the focus of this investigation. 1) Does infant self-regulation (attentional, emotional, and social) predict preschool cognitive competence? 2) Does infant self-regulation predict preschool self-regulation? 3) Does preschool self-regulation predict concurrent preschool cognitive competence? One hundred preschoolers (46 females, 54 males; mean age = 5 years, 11 months) who had participated at 9- and/ or 12-months of age in an object permanence task were recruited to participate in this longitudinal investigation. Each subject completed four scales of the WPPSI-R and two social cognitive tasks. Parents completed questionnaires about their preschoolers' regulatory behaviours (Achenbach's Child Behavior Checklist [1991] and selected items from Eisenberg et ale [1993] and Derryberry & Rothbart [1988]). Separate behavioural coding systems were developed to capture regulatory capabilities in infancy (from the object permanence task) and preschool (from the WPPSIR Block Design). Overall, correlational and multiple regression results offered strong affirmative answers to the three key questions (R's = .30 to .38), using the behavioural observations of self-regulation. Behavioural regulation at preschool substantially predicted parental reports of regulation, but the latter variables did not predict preschool competence. Infant selfregulation and preschool regulation made statistically independent contributions to competence, even though regulation at Time 1 and Time 2 ii were substantially related. The results are interpreted as supporting a developmental pathway in which well-regulated infants more readily acquire both expertise and more sophisticated regulatory skills. Future research should address the origins of these skills earlier in infancy, and the social contexts that generate them and support them during the intervening years.

A qualitative study of curriculum and instructional efforts in relation to high stakes federal and district policies in one low-performing elementary school

Les enjeux liés aux politiques éducatives ont considérablement changé au cours des dernières décennies. Ces changements sont liés, entre autres, à l’accroissement de l’imputabilité et de la reddition de compte qui est devenue une caractéristique importante des réformes curriculaires et pédagogiques. Les politiques à enjeux élevés exercent une pression énorme sur les districts et les écoles états-unienne afin qu’ils augmentent le rendement des élèves en utilisant des systèmes de conséquences (Hall & Ryan, 2011; Loeb & Strunk, 2007). Ces politiques envoient de puissants messages sur l'importance de certaines matières scolaires au détriment d'autres - circonscrivant les exigences en termes de compétences et de connaissances. La langue maternelle d’enseignement et les mathématiques sont devenues des mesures centrales sur lesquelles reposent l’évaluation et le degré de performance des districts et des écoles. Conséquemment, les administrateurs de districts et les directions d’écoles ont souvent recours à des réformes curriculaires et pédagogiques comme moyen d'augmenter le rendement des élèves dans les matières scolaires visées par ces politiques. Les politiques contraignent les acteurs scolaires de concentrer les ressources sur les programmes curriculaires et les évaluations, le développement professionnel, et la prise de décision pilotée par les données (Anagnostopoulos & Ruthledge, 2007; Honig & Hatch, 2004; Spillane, Diamond, et al., 2002; Weitz White & Rosenbaum, 2008). Cette thèse examine la manière dont les politiques à enjeux élevés opèrent quotidiennement dans les interactions et les pratiques au sein des écoles. Nous analysons plus particulièrement les différents messages provenant de la politique transmis aux acteurs scolaires sur les manières d'apporter des changements substantiels dans le curriculum et l'enseignement. Nous élargissons l’analyse en prenant en compte le rôle des administrateurs de district ainsi que des partenaires universitaires qui façonnent également la manière dont certains aspects des messages provenant des politiques sont transmis, négociés et/ou débattus et d’autres sont ignorés (Coburn & Woulfin, 2012). En utilisant l’analyse de discours, nous examinons le rôle du langage comme constituant et médiateur des interactions sociales entre les acteurs scolaires et d’autres parties prenantes. De telles analyses impliquent une investigation approfondie d’un nombre d’étude de cas limité. Les données utilisées dans cette thèse ont été colligées dans une école primaire états-unienne du mid-West. Cette étude de cas fait partie d’une étude longitudinale de quatre ans qui comprenait huit écoles dans les milieux urbains entre 1999 et 2003 (Distributed Leadership Studies, http://www.distributedleadership.org). La base de données analysée inclut des observations de réunions formelles et des entrevues auprès des administrateurs du district, des partenaires universitaires, de la direction d’école et des enseignants. En plus de l’introduction et de la problématique (chapitre 1) et de discussion et conclusion (chapitre 5), cette thèse comprend un ensemble de trois articles interdépendants. Dans le premier article (chapitre 2), nous effectuons une recension des écrits portant sur le domaine de l’implantation de politiques (policy implementation) et la complexité des relations locales, nationales et internationales dans les systèmes éducatifs. Pour démystifier cette complexité, nous portons une attention particulière à la construction de sens des acteurs scolaires comme étant une dimension clé du processus de mise en œuvre des réformes. Dans le deuxième article (chapitre 3), nous cherchons à comprendre les processus sociaux qui façonnent les réponses stratégiques des acteurs scolaires à l’égard des politiques du district et de l’état et en lien avec la mise en œuvre d’un curriculum prescrit en mathématiques. Plus particulièrement, nous explorons les différentes situations dans lesquelles les acteurs scolaires argumentent au sujet des changements curriculaires et pédagogiques proposés par les administrateurs de district et des partenaires universitaires afin d’augmenter les résultats scolaires en mathématiques dans une école à faible performance. Dans le troisième article (chapitre 4), nous cherchons à démystifier les complexités liées à l’amélioration de l’enseignement dans un environnement de politiques à enjeux élevés. Pour ce faire, nous utilisons l'interaction entre les notions d'agentivité et la structure afin d'analyser la manière dont les conceptions d’imputabilité et les idées qui découlent de l'environnement politique et les activités quotidiennes jouent dans les interactions entre les acteurs scolaires concernant sur l’enseignement de la langue maternelle. Nous explorons trois objectifs spécifiques : 1) la manière dont les politiques à enjeux élevés façonnent les éléments de l’enseignement qui sont reproduits et ceux qui sont transformés au fil du temps ; 2) la manière dont la compréhension des leaders de l’imputabilité façonne les aspects des messages politiques que les acteurs scolaires remarquent à travers les interactions et les conversations et 3) la manière les acteurs scolaires portent une attention particulière à certaines messages au détriment d’autres. Dans le dernier chapitre de cette thèse, nous discutons les forces et les limites de l’analyse secondaire de données qualitatives, les implications des résultats pour le domaine d’études de l’implantation de politiques et les pistes futures de recherches.

The status and barriers to the implementation and continuation of the school gardening projects in Germany, Nigeria and the United States of America

In drawing a conclusion for this study, care must be taken in generalizing findings since the population of students and teachers investigated were limited to certain levels in the different schools and countries. This study recognized some complexity of the factors underlying the status of school gardening instruction and activities in Germany, Nigeria and the U.S. as inadequate time for decision-making in the process of gardening, motivation of teachers and students. This was seen as the major impediments that influenced the status of gardening in the three countries. However, these factors were considered to have affected students’ mode of participation in the school gardening projects. This research finding suggests that the promotion and encouragement of students in gardening activities will promote vegetable production and increasing the numbers of practical farmers. Gardening has the potential to create opportunities for learning in an environment where children are able to experience nature first hand and to use the shared experience for communication (Bowker & Tearle, 2007). Therefore, the need for students to be encouraged to participate in gardening programs as the benefit will not only reduce the rate of obesity currently spreading among youths, but will contribute to the improve knowledge on science subjects. To build a network between community, parents and schools, a parent’s community approach should be used as the curriculum. The community approach will tighten the link between schools; community members, parents, teachers and students. This will help facilitate a better gardening projects implementation. Through a close collaboration, teachers and students will be able to identify issues affecting communities and undertake action learning in collaboration with community organizations to assess community needs and plan the implementation strategies as parents are part of the community. The sense of efficacy is a central factor in motivational and learning processes that govern educational improvement, standard and performance on complex tasks of both teachers and students. Dedication and willingness are the major stimulator and achievement of a project. Through a stimulator and provision of incentives and facilities, schools can achieve the best in project development. Teachers and principals should be aware that students are the lever for achieving the set goals in schools. Failure to understand what students need will result in achieving zero result. Therefore, it is advised that schools focus more on how to lure students to work through proper collaboration with the parents and community members. Principals and teachers should identify areas where students need to be corrected, helping them to correct the problem will enable them be committed in the schools’ programs.

Considering the Moral Complexity of Adolescents in Divided Societies

This paper focuses on adolescents who live in divided societies and how they navigate those divisions as they develop as civic actors. The study sites are Northern Ireland, South Africa, and the United States. In each setting we collected surveys, conducted focus groups with teachers and students, and followed students through the 9th and 10th grades in a case study classroom. In all locales, the students used materials from Facing History and Ourselves, and their teachers had participated in workshops on using those materials. In this paper we follow a case study student from the United States who provides a particularly complex look at issues of division and ethical civic development. The student, Pete, is a white immigrant from South Africa, studying in a multi-ethnic and multi-racial school in the United States. He confronts his South African legacies in the context of a foreign school system, which is working to help U.S. students confront their own legacies. Across two, one-semester, citizenship classes, Pete shows us the tension between an academic stance and a moral/emotional stance. When moral dilemmas become complex for him, he begins to lose his ability to judge. Teacher support and guidance is critical to help students like Pete learn to hold their moral ground, while understanding why others act as they do.

Is virtuality close enough to reality? A comparison of the effectiveness of simulations with traditional laboratory activities in a high school biology class

Some schools do not have ideal access to laboratory space and supplies. Computer simulations of laboratory activities can be a cost-effective way of presenting experiences to students, but are those simulations as effective at supplementing content concepts? This study compared the use of traditional lab activities illustrating the principles of cell respiration and photosynthesis in an introductory high school biology class with virtual simulations of the same activities. Additionally student results were analyzed to assess if student conceptual understanding was affected by the complexity of the simulation. Although all student groups posted average gain increases between the pre and post-tests coupled with positive effect sizes, students who completed the wet lab version of the activity consistently outperformed the students who completed the virtual simulation of the same activity. There was no significant difference between the use of more or less complex simulations. Students also tended to rate the wet lab experience higher on a motivation and interest inventory.

Evolution of sensory complexity recorded in a myxobacterial genome.

Myxobacteria are single-celled, but social, eubacterial predators. Upon starvation they build multicellular fruiting bodies using a developmental program that progressively changes the pattern of cell movement and the repertoire of genes expressed. Development terminates with spore differentiation and is coordinated by both diffusible and cell-bound signals. The growth and development of Myxococcus xanthus is regulated by the integration of multiple signals from outside the cells with physiological signals from within. A collection of M. xanthus cells behaves, in many respects, like a multicellular organism. For these reasons M. xanthus offers unparalleled access to a regulatory network that controls development and that organizes cell movement on surfaces. The genome of M. xanthus is large (9.14 Mb), considerably larger than the other sequenced delta-proteobacteria. We suggest that gene duplication and divergence were major contributors to genomic expansion from its progenitor. More than 1,500 duplications specific to the myxobacterial lineage were identified, representing >15% of the total genes. Genes were not duplicated at random; rather, genes for cell-cell signaling, small molecule sensing, and integrative transcription control were amplified selectively. Families of genes encoding the production of secondary metabolites are overrepresented in the genome but may have been received by horizontal gene transfer and are likely to be important for predation.