Typical CS 1 classes are about many things. The problems and examples are drawn from a variety of domains, with a goal of teaching a computational problem-solving approach and specific language constructs. Many CS 1 courses begin with writing programs that perform simple calculations, transition to more substantial simulations or games in the middle, and perhaps one or two SIGCSE Nifty Assignments at the end. In this panel, we explore the 'strongly-themed' approach in which many of the programs and examples used in the course come from a single domain which provides a theme for the course.

We introduce a new approach for implementing cryptographic arithmetic in short high-level code with machine-checked proofs of functional correctness. We further demonstrate that simple partial evaluation is sufficient to transform into the fastest-known C code, breaking the decades-old pattern that the only fast implementations are those whose instruction-level steps were written out by hand. These techniques were used to build an elliptic-curve library that achieves competitive performance for 80 prime fields and multiple CPU architectures, showing that implementation and proof effort scales with the number and complexity of conceptually different algorithms, not their use cases. As one outcome, we present the first verified high-performance implementation of P-256, the most widely used elliptic curve. implementations from our library were included in BoringSSL to replace existing specialized code, for inclusion in several large deployments for Chrome, Android, and CloudFlare.

We present the curriculum and evaluation of a pilot Biology-themed CS1 course offering at a large public university. Inspired by Harvey Mudd's CS 5 Green, we adapt CS1 + Bio to fit the needs of our student body, which is much more typical for those US institutions that produce the bulk of the nation's CS undergraduate degrees. This course was team-taught by a computer science professor and a biology professor, and combined typical CS1 topics with relevant biology content. Our initial offering attracted students who would not otherwise have taken CS1, and was the only one of our three CS1 courses where more students reported planning to major in CS after the course than before it.

We present the curriculum, pilot offering, and initial evaluation of a CS + Law based CS 1 course that was team taught by a Computer Science professor and a law school professor. Relevant legal topics were interwoven through the course.

We administered the Verbal IQ (VIQ) part of the Wechsler Preschool and Primary Scale of Intelligence (WPPSI-III) to the ConceptNet 4 artificial intelligence (AI) system. The test questions (e.g. “Why do we shake hands?”) were translated into ConceptNet 4 inputs using a combination of the simple natural language processing tools that come with ConceptNet together with short Python programs that we wrote. The question answering used a version of ConceptNet based on spectral methods. The ConceptNet system scored a WPPSI-III VIQ that is average for a four-year-old child, but below average for 5–7 year olds. Large variations among subtests indicate potential areas of improvement. In particular, results were strongest for the Vocabulary and Similarities subtests, intermediate for the Information subtest and lowest for the Comprehension and Word Reasoning subtests. Comprehension is the subtest most strongly associated with common sense. The large variations among subtests and ordinary common sense strongly suggest that the WPPSI-III VIQ results do not show that “ConceptNet has the verbal abilities of a four-year-old”. Rather, children’s IQ tests offer one objective metric for the evaluation and comparison of AI systems. Also, this work continues previous research on psychometric AI.

Relational reinforcement learning (RRL) combines traditional reinforcement learning (RL) with a strong emphasis on a relational (rather than attribute-value) representation. Earlier work used RRL on a learning version of the classic Blocks World planning problem (a version where the learner does not know what the result of taking an action will be) and the Tetris game. Learning results based on the structure of training examples were obtained, such as learning in a mixed 3–5 block environment and being able to perform in a 3 or 10 block environment. Here, we instead take a function approximation approach to RL for the Blocks World problem. We obtain similar learning accuracies, with better running times, allowing us to consider much larger problem sizes. For instance, we can train on 15 blocks and then perform well on worlds with 100–800 blocks–using less running time than the relational method required to perform well for 3–10 blocks.

No abstract available.

There are often problems when students enter a course with widely different experience levels with key course topics. If the material is covered too slowly, those with greater experience get bored and lose interest. If the material is covered too quickly, those with less experience get lost and feel incompetent. This problem with incoming students of our Computer Science Major led us to create CS 0.5: an introductory Computer Science course to target those CS majors who have little or no background with programming. Our goal is to provide these students with an engaging curriculum and prepare them to keep pace in future courses with those students who enter with a stronger background.

It is known that a k-term DNF can have at most $2^k - 1$ prime implicants and that this bound is sharp. We determine all k-term DNF having the maximal number of prime implicants. It is shown that a DNF is maximal if and only if it corresponds to a nonrepeating decision tree with literals assigned to the leaves in a certain way. We also mention some related results and open problems.

No abstract available.

No abstract available.

No abstract available.

In 2001, the ACM and the IEEE-CS published Computing Curricula 2001 which contains curriculum recommendations for undergraduate programs in computer science. That report also called for additional discipline-specific volumes for each of computer engineering, information systems, and software engineering. In addition, it called for an Overview Volume to provide a synthesis of the various volumes. The Computing Curricula 2004 Task Force undertook the job of fulfilling the latter charge. The purpose of this session is to present the recently completed work of that Task Force, now known as Computing Curricula 2005 (CC2005), and to generate discussion among, and feedback from SIGCSE members about ongoing and future work.

A revision algorithm is a learning algorithm that identifies the target concept, starting from an initial concept. Such an algorithm is considered efficient if its complexity (in terms of the measured resource) is polynomial in the syntactic distance between the initial and the target concept, but only polylogarithmic in the number of variables in the universe. We give efficient revision algorithms in the model of learning with equivalence and membership queries. The algorithms work in a general revision model where both deletion and addition revision operators are allowed. In this model one of the main open problems is the efficient revision of Horn formulas. Two revision algorithms are presented for special cases of this problem: for depth-1 acyclic Horn formulas, and for definite Horn formulas with unique heads.

An access control design can be viewed as a three layered entity: the general access control model; the parameterization of the access control model; and the initial users and objects of the system before it goes live. The design of this three-tiered mechanism can be evaluated according to two broad measures, the expressiveness versus the complexity of the system. In particular, the question arises: What security properties can be expressed and verified? We present a general access control model which can be parameterized at the second layer to implement (express) any of the standard Discretionary Access Control (DAC) models. We show that the safety problem is decidable for any access control model implemented using our general access control model. Until now, all general access control models that were known to be sufficiently expressive to implement the full range of DAC models had an undecidable safety problem. Thus, given our model all of the standard DAC models (plus many others) can be implemented in a system in which their safety properties are decidable.

No abstract available.

In the fall of 1998, the ACM Education Board and the Educational Activities Board of the IEEE Computer Society appointed representatives to a joint task force to prepare Computing Curricula 2001 (CC2001). The CC2001 report is the current installment in a series of reports on the undergraduate computer science curriculum that began in 1968 and was then updated in 1978 and 1991 [1, 6]. The computer science volume of the CC2001 report was presented to the community in a series of three public drafts, followed by a final report approved by the governing boards of the ACM and the Computer Society. The purpose of this panel is to discuss strategies for implementing the recommendations of the final report in a wide variety of institutions.

This paper examines how monitoring power consumption signals might breach smart-card security. Both simple power analysis and differential power analysis attacks are investigated. The theory behind these attacks is reviewed. Then, we concentrate on showing how power analysis theory can be applied to attack an actual smart card. We examine the noise characteristics of the power signals and develop an approach to model the signal-to-noise ratio (SNR). We show how this SNR can be significantly improved using a multiple-bit attack. Experimental results against a smart-card implementation of the Data Encryption Standard demonstrate the effectiveness of our multiple-bit attack. Potential countermeasures to these attacks are also discussed.

Given a Boolean formula that is not quite right, how does one fix it?That is, if a given formula differs from an unknown target formula, what is the complexity of revising the given formula?The tools available for determining the revisions are queries to membership and equivalence oracles, namely, questions of the form: "Is this an instance of the target formula," and "Is this hypothesis equivalent to the target formula?"In the latter case, if the answer is "No," the oracle returns an instance that is true for exactly one of the hypothesis and the target.For Horn sentences that require only deletion revisions, a revision algorithm is given that is polynomial in the number of clauses of the formula and the minimum number of deletions needed.For 2-term monotone DNF formulas, a revision algorithm is given that is polynomial in the minimum number of necessary deletions and additions and the logarithm of the number of variables.Previous work addressed deletion-only revisions to 2-term unate DNF formulas. WilIEat := VeryBland OR ((NOT vegetables) AND bland AND Meat).Then, though you use the initial theory as a general guide, you happen to observe the preschooler consume a full pound

The theory revision, or concept revision, problem is to correct a given, roughly correct concept. Given the representation of an initial concept, one would like to obtain a representation of the target concept by applying revisions, that is, syntactic modifications such as the deletion of a variable or a term. We give efficient revision algorithms using membership and equivalence queries for 2term monotone DNF, monotone k-DNF, and readonce formulas. An example is given showing that some monotone DNF formulas cannot be revised efficiently. These results all assume that the revisions allowed are the replacements of a variable occurrence with a constant, which, for DNFs, corresponds to deletions of variables and terms. We also discuss a more general error model where besides deletions, additions are also allowed. 1 INTRODUCTION What the computational learning theory community calls a concept is often referred to as a theory elsewhere in artificial intelligence and logic....

One of the features that distinguishes digital libraries from traditional databases is new cost models for client access to intellectual property. Clients will pay for accessing data items in digital libraries, and we believe that optimizing these costs will be as important as optimizing performance in traditional databases. In this article we discuss cost models and protocols for accessing digital libraries, with the objective of determining the minimum cost protocol for each model. We expect that in the future information appliances will come equipped with a cost optimizer, in the same way that computers today come with a built-in operating system. This article makes the initial steps towards a thery and practice of intellectual property cost management.

Article Learning logic programs by using the product homomorphism method Share on Authors: Tamás Horváth Dept. of Applied Informatics, József A. University, H-6720 Szeged, Hungary Dept. of Applied Informatics, József A. University, H-6720 Szeged, HungaryView Profile , Robert H. Sloan Dept. of EE & Comp. Sci., U. Illinois at Chicago, 851 S. Morgan St. Rm 1120, Chicago, IL Dept. of EE & Comp. Sci., U. Illinois at Chicago, 851 S. Morgan St. Rm 1120, Chicago, ILView Profile , György Turán Dept. of Math., Stat., & Comp. Sci., U. Illinois at Chicago, Research Group on Artificial Intelligence, Hungarian Academy of Sciences Dept. of Math., Stat., & Comp. Sci., U. Illinois at Chicago, Research Group on Artificial Intelligence, Hungarian Academy of SciencesView Profile Authors Info & Claims COLT '97: Proceedings of the tenth annual conference on Computational learning theoryJuly 1997 Pages 10–20https://doi.org/10.1145/267460.267468Online:01 July 1997Publication History 6citation217DownloadsMetricsTotal Citations6Total Downloads217Last 12 Months2Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We investigate learning with membership and equivalence queries assuming that the information provided to the learner is incomplete. By incomplete we mean that some of the membership queries may be answered by “I don't know.” This model is a worst-case version of the incomplete membership query model of Angluin and Slonim. It attempts to model practical learning situations, including an experiment of Lang and Baum that we describe, where the teacher may be unable to answer reliably some queries that are critical for the learning algorithm.

We present a first report on our PARTS toolset for the automated static analysis of real-time systems. The PARTS toolset is based upon a timed extension of Petri nets.

The algorithm for pac learning k-DNF or k-CNF in the presence of malicious attribute noise in polynomial time claimed by Sloan [Slo88] does not work. It is currently open whether such an algorithm exists.

The problem of learning an integer lattice of ${\bf Z}^k $ in an on-line fashion is considered. That is, the learning algorithm is given a sequence of k-tuples of integers and predicts for each tuple in the sequence whether it lies in a hidden target lattice of ${\bf Z}^k $. The goal of the algorithm is to minimize the number of prediction mistakes. An efficient learning algorithm with an absolute mistake bound of $k + \lfloor k\log (n\sqrt k ) \rfloor $ is given, where n is the maximum component of any tuple seen. It is shown that this bound is approximately a $\log \log n$ factor larger than the lower bound on the worst case number of mistakes given by the VC dimension of lattices that are restricted to $\{ - n, \cdots ,0, \cdots ,n \}^k $. This algorithm is used to learn rational lattices, cosets of lattices, an on-line word problem for abelian groups, and a subclass of the commutative regular languages. Furthermore, by adapting the results of [D. Helmbold, R. Sloan, and M. K. Warmuth, Machine Learning, 5 (1990), pp. 165–196], one can efficiently learn nested differences of each of the above classes (e.g., concepts of the form $c_1 - (c_2 - (c_3 - (c_4 - c_5 )))$, where each $c_i $ is the coset of a lattice).