This workshop presents an award-winning, NSF-funded, project-based curriculum for algorithm design that includes algorithmic strategies for intractable problems. This curriculum is a sequence of laboratory projects comprising increasingly sophisticated solvers for a single intractable problem, designed to integrate into existing, one-term, undergraduate courses that teach algorithm design and/or intractability without sacrificing traditional course content. The presenters have used the curriculum in the Design and Analysis of Algorithms course at their institution to help students tackle and appreciate intractability. This workshop presents versions of the curriculum centered on TSP, SAT and Sudoku. Attendees will receive adoption materials and access to an adopters' forum. NSF is funding the development, evaluation, dissemination and adoption of the curriculum. Potential adopters are encouraged to apply for funding to attend this workshop and SIGCSE 2014 at http://www.rowan.edu/~lobo/AlgosCurriculum. This material is based upon work supported by the National Science Foundation under Grant No. 1140753. Laptop optional.

We are designing a number of programming projects which utilize input/output devices, such as joysticks or a homebrewed board we call a MIPPET (Module for Input/Output Programming Projects Enhancing Teaching). These projects have been used or will be used in the closed labs of our CS1 course (taught in C++). The goal of these projects is to enhance student comprehension (by teaching objects with "real" objects) and student motivation (by providing "fun" projects). This paper focuses on an early project, where the student's program provides support for a human solving a maze.

Most theoretical models of inductive inference make the idealized assumption that the data available to a learner is from a single and accurate source. The subject of inaccuracies in data emanating from a single source has been addressed by several authors. The present paper argues in favor of a more realistic learning model in which data emanates from multiple sources, some or all of which may be inaccurate. Three kinds of inaccuracies are considered: spurious data (modeled as noisy texts), missing data (modeled as incomplete texts), and a mixture of spurious and missing data (modeled as imperfect texts). Motivated by the above argument, the present paper introduces and theoretically analyzes a number of inference criteria in which a learning machine is fed data from multiple sources, some of which may be infected with inaccuracies. The learning situation modeled is the identification in the limit of programs from graphs of computable functions. The main parameters of the investigation are: the kind of inaccuracy, the total number of data sources, the number of faulty data sources which produce data within an acceptable bound, and the bound on the number of errors allowed in the final hypothesis learned by the machine. Sufficient conditions are determined under which, for the same kind of inaccuracy, for the same bound on the number of errors in the final hypothesis, and for the same bound on the number of inaccuracies, learning from multiple texts, some of which may be inaccurate, is equivalent to learning from a single inaccurate text. The general problem of determining when learning from multiple inaccurate texts is a restriction over learning from a single inaccurate text turns out to be combinatorially very complex. Significant partial results are provided for this problem. Several results are also provided about conditions under which the detrimental effects of multiple texts can be overcome by either allowing more errors in the final hypothesis or by reducing the number of inaccuracies in the texts. It is also shown that the usual hierarchies resulting from allowing extra errors in the final program (results in increased learning power) and allowing extra inaccuracies in the texts (results in decreased learning power) hold. Finally, it is demonstrated that in the context of learning from multiple inaccurate texts, spurious data is better than missing data, which in turn is better than a mixture of spurious and missing data.

This paper provides positive and negative results on algorithmically synthesizing, from grammars and from decision procedures for classes of languages, learning machines for identifying, from positive data, grammars for the languages in those classes. In the process, the uniformly decidable classes of recursive languages that can be behaviorally correctly identified from positive data are surprisingly characterized by Angluin's 1980 Condition 2 (the subset principle for preventing overgeneralization) . 1 Introduction In the context of learning programs in the limit for functions [KW80, AS83, OSW86b], a variety of enumeration techniques [Gol67, BB75, Wie90, Ful90b] are important and ubiquitous. Here is the archetypal case. Suppose one has an r.e. set P of programs for computing total functions. One proceeds as follows. At each point that one is given data about an input function, one conjectures the first program, if any, listed in P that is correct on the data seen through that point....

Abstract A generator program for a computable function (by definition) generates an infinite sequence of programs all but finitely many of which compute that function. Machine learning of generator programs for computable functions is studied. To motivate these studies partially, it is shown that, in some cases, interesting global properties for computable functions can be proved from suitable generator programs which cannot be proved from any ordinary programs for them. The power (for variants of various learning criteria from the literature) of learning generator programs is compared with the power of learning ordinary programs. The learning power in these cases is also compared to that of learning limiting programs , i.e., programs allowed finitely many mind changes about their correct outputs.