In this paper, we describe a CS+Social Science Python project that can be integrated directly into high school classrooms, enabling students to explore social science questions using computer science. The project uses the pandas library and Google Colab to give students an authentic experience with data science tools. We present teachers' experiences and students feedback from implementing the project in three high school classes, one non-STEM class and two AP CS classes. The project is designed to be simple enough for students with no CS background to succeed, but creative and open-ended enough to allow students with experience to develop their skills further. Students from both courses report the project was interesting and useful. Our work builds upon the body of literature examining ways to include CS in non-STEM high school courses, but also appears to fit well into CS curricula.

Racial and gender representation among computer science (CS) students continues to lag behind national demographics in the U.S. One way to improve students' interests in CS is to connect CS to other fields to expand students' perceptions of what constitutes CS. While CS+X programs, which combine CS and another field into a single interdisciplinary degree, are expanding at the undergraduate level, there is room to further expand related opportunities in K-12 spaces to encourage more students to pursue CS. To this end, in this experience report we present a new CS+X topics course for high school students that teaches about the intersections of CS with several non-STEM "+X" fields. The course was designed by a team of educators with experience in K-12 curriculum design and broadening participation programs. We piloted the course at a high school in Spring 2023 with 11 students. We present our course design and breakdown of decisions made during the course design process. Further, we provide results from our evaluation survey, featuring thematic analysis of students' commentary and a breakdown of course topics and components students favored. Our students reported that their interests in computing and understanding of computing's broad impacts on society improved. We provide a reflection on the course's future refinements and our plans for further testing of the course in more high school environments to prepare it for wider community adoption.

We introduce the boasting problem, wherein useful trends in historical ordinal data (rankings) are discovered. Claims of the form our object was ranked r or better in x of the last t time units, are formalized, and maximal claims (boasts) of this form are defined under two natural partial orders. For the first partial order, we give an efficient and optimal algorithm for finding all such maximal claims. For the second, we apply a classical result from computational geometry to achieve an algorithm whose running time is significantly more efficient than that of a naive one. Finally, we connect this boasting problem to a novel variation of the problem of finding optimized confidence association rules as originally posed by Fukuda, et al. [2], and give an efficient algorithm for solving a simplification of the new problem.

The problem of finding optimized support association rules for a single numerical attribute, where the optimized region is a union of k disjoint intervals from the range of the attribute, is investigated. The first polynomial time algorithm for the problem of finding such a region maximizing support and meeting a minimum cumulative confidence threshold is given. Because the algorithm is not practical, an ostensibly easier, more constrained version of the problem is considered. Experiments demonstrate that the best extant algorithm for the constrained version has significant performance degradation on both a synthetic model of patterned data and on real world data sets. Running the algorithm on a small random sample is proposed as a means of obtaining near optimal results with high probability. Theoretical bounds on sufficient sample size to achieve a given performance level are proved, and rapid convergence on synthetic and real-world data is validated experimentally.

We consider the index selection problem. Given either a fixed query workload or an unknown probability distribution on possible future queries, and a bound B on how much space is available to build indices, we seek to build a collection of indices for which the average query response time is minimized. We give strong negative and positive peformance bounds.Let m be the number of queries in the workload. We show how to obtain with high probability a collection of indices using space O(B ln m) for which the average query cost is optB, the optimal performance possible for indices using at most B total space. Moreover, this space relaxation is necessary: unless NP ⊆ nO(log log n), no polynomial time algorithm can guarantee average query cost less than M1--ε optB using space αB, for any constant α, where M is the size of the dataset. We quantify the error in performance introduced by running the algorithm on a sample drawn from a query distribution.

We study the learnability of read-k-satisfy-j (RkSj) DNF formulas. These are boolean formulas in disjunctive normal form (DNF), in which the maximum number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. After motivating the investigation of this class of DNF formulas, we present an algorithm that for any unknown RkSj DNF formula to be learned, with high probability finds a logically equivalent DNF formula using the well-studied protocol of equivalence and membership queries. The algorithm runs in polynomial time for $k\cdot j=O({\log n\over\log\log n})$, where n is the number of input variables.

We show that any monotone function with a read-k CNF representation can be learned in terms of its DNF representation with member-ship queries alone in time polynomial in the DNF size and n (the number of variables) as-suming k is some fixed constant. The problem is motivated by the well-studied open problem of enumerating all maximal independent sets of a given hypergraph. Our algorithm gives a solution for the bounded degree case and works even if the hypergraph is not input, but rather only queries are available as to which sets are independent. 1

Article Free Access Share on PAC learning intersections of halfspaces with membership queries (extended abstract) Authors: Stephen Kwek Computer Science Department, University of Illinois, Urbana, IL Computer Science Department, University of Illinois, Urbana, ILView Profile , Leonard Pitt Computer Science Department, University of Illinois, Urbana, IL Computer Science Department, University of Illinois, Urbana, ILView Profile Authors Info & Claims COLT '96: Proceedings of the ninth annual conference on Computational learning theoryJanuary 1996 Pages 244–254https://doi.org/10.1145/238061.238109Published:01 January 1996Publication History 0citation219DownloadsMetricsTotal Citations0Total Downloads219Last 12 Months30Last 6 weeks4 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 SiteeReaderPDF

We study the learnability of Read-k-Satisfy-j (RkSj) DNF formulae. These are DNF formulae in which the maximal number of occurrences of a variable is bounded by k, and the number of terms satisfied by any assignment is at most j. We show that this class of functions is learnable in polynomial time, using Equivalence and Membership Queries, as long as k•j=O(logn/loglogn). Learnability was previously known only in case that both k and j are constants. We also present a family of boolean functions that have short (poly(n)) Read-2-Satisfy-1 DNF formulae but require CNF formulae of size > 2W(n). Therefore, our result does not seem to follow from the recent learnability result of [Bsh93].

One view of computational learning theory is that of a learner acquiring the knowledge of a teacher. We introduce a formal model of learning capturing the idea that teachers may have gaps in their knowledge. The goal of the learner is still to acquire the knowledge of the teacher, but now the learner must also identify the gaps. This is the notion of learning from a consistently ignorant teacher. We consider the impact of knowledge gaps on learning, for example, monotone DNF and d-dimensional boxes, and show that learning is still possible. Negatively, we show that knowledge gaps make learning conjunctions of Horn clauses as hard as learning DNF. We also present general results describing when known learning algorithms can be used to obtain learning algorithms using a consistently ignorant teacher.

Description logics, also called terminological logics, are commonly used in knowledge-based systems to describe objects and their relationships. We investigate the learnability of a typical description logic, CLASSIC, and show that CLASSIC sentences are learnable in polynomial time in the exact learning model using equivalence queries and membership queries (which are in essence, “subsumption queries”). We show that membership queries alone are insufficient for polynomial time learning of CLASSIC sentences. Combined with earlier negative results of Cohen and Hirsh showing that, given standard complexity theoretic assumptions, equivalence queries alone are insufficient (or random examples alone in the PAC setting are insufficient), this shows that both sources of information are necessary for efficient learning in that neither type alone is sufficient. In addition, we show that a modification of the algorithm deals robustly with persistent malicious two-sided classification noise in the membership queries with the probability of a misclassification bounded below 1/2.

The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the DFA found should accept or reject). Assuming that P ≠ NP, it is shown that for any constant k , no polynomial-time algorithm can be guaranteed to find a consistent DFA with fewer than opt k states, where opt is the number of states in the minimum state DFA consistent with the sample. This result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an NFA, a regular expression, or a regular grammar that is consistent with the sample. A similar nonapproximability result is presented for the problem of finding small consistent linear grammars. For the case of finding minimum consistent DFAs when the alphabet is not of constant size but instead is allowed to vary with the problem specification, the slightly stronger lower bound on approximability of opt (1-ϵ)log log opt is shown for any ϵ > 0.

A polynomial-time algorithm is presented for exactly learning the class of read-k disjoint DNF formulas—boolean formulas in disjunctive normal form where each variable appears at most k) and every assignment to the variables satisfies at most one term of F. The (standard) protocol used allows the learning algorithm to query whether a given assignment of boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned. We show that this result also applies for a generalization of read-k disjoint DNF which we call read-k sat-j DNF; these are DNF formulas in which every variable appears at most k times and every assignment satisfies at most j terms.

A general technique is developed to obtain nonlearnability results in the model of exact learning from equivalence and membership queries. The technique is applied to show that, assuming NP not=co-NP, there does not exist a polynomial-time membership and equivalence query algorithm for exactly learning read-thrice DNF formulas-boolean formulas in disjunctive normal form where each variable appears at most three times. This result adds evidence to the conjecture that DNF is hard to learn in the membership and equivalence query model.>

A polynomial-time algorithm is presented for exactly learning the class of read-twice DNF formulas, i.e. Boolean formulas in disjunctive normal form where each variable appears at most twice. The (standard) protocol used allows the learning algorithm to query whether a given assignment of Boolean variables satisfies the DNF formula to be learned (membership queries), as well as to obtain counterexamples to the correctness of its current hypothesis which can be any arbitrary DNF formula (equivalence queries). The formula output by the learning algorithm is logically equivalent to the formula to be learned.>

An algorithm for learning the class of Boolean formulas that are expressible as conjunctions of Horn clauses is presented. (A Horn clause is a disjunction of literals, all but at most one of which is a negated variable). The algorithm uses equivalence queries and membership queries to produce a formula that is logically equivalent to the unknown formula to be learned. The amount of time used by the algorithm is polynomial in the number of variables and the number of clauses in the unknown formula.>

The distribution-independent model of concept learning from examples ("PAC-learning") due to Valiant [15] is investigated.It has been shown that the existence of an Occarn algorithm for a class of concepts is a sufficient condition for the PAC-learnability of that class [2, 3].(An Occam algorithm is a randomized polynomial-time algorithm that, when given as input a sample of strings of some unknown concept to be learned, outputs a small description of a concept that is consistent with the sample.)In this paper it is shown that for all concept classes satisfying a natural closure property the converse is also true; the PAC-learnability of the class implies the existence of an Occam algorithm for the class.This results in a complete combinatorial characterization of the PAC-learnability of a wide variety of concept classes.

The minimum consistent DFA problem is that of finding a DFA with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the DFA found should accept or reject). Assuming that P ≠ NP, it is shown that for any constant k, no polynomial time algorithm can be guaranteed to find a consistent DFA of size optk, where opt is the size of a smallest DFA consistent with the sample. This result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an NFA, a regular grammar, or a regular expression that is consistent with the sample. Similar hardness results are described for the problem of funding small consistent linear grammars.

Inductive inference machines construct programs for total recursive functions given only example values of the functions. Probabilistic inductive inference machines are defined, and for various criteria of successful inference, it is asked whether a probabilistic inductive inference machine can infer larger classes of functions if the inference criterion is relaxed to allow inference with probability at least p , (0 < p < 1) as opposed to requiring certainty. For the most basic criteria of success ( EX and BC ), it is shown that any class of functions that can be inferred from examples with probability exceeding 1/2 can be inferred deterministically, and that for probabilities p ≤ 1/2 there is a discrete hierarchy of inferability parameterized by p . The power of probabilistic inference strategies is characterized by equating the classes of probabilistically inferable functions with those classes that can be inferred by teams of inductive inference machines (a parallel model of inference), or by a third model called frequency inference.

The computational complexity of learning Boolean concepts from examples is investigated. It is shown for various classes of concept representations that these cannot be learned feasibly in a distribution-free sense unless R = NP. These classes include (a) disjunctions of two monomials, (b) Boolean threshold functions, and (c) Boolean formulas in which each variable occurs at most once. Relationships between learning of heuristics and finding approximate solutions to NP-hard optimization problems are given.

Article Free Access Share on On the learnability of Boolean formulae Authors: M. Kearns Harvard University Harvard UniversityView Profile , M. Li Harvard University Harvard UniversityView Profile , L. Pitt University of Illinois University of IllinoisView Profile , L. Valiant Harvard University Harvard UniversityView Profile Authors Info & Claims STOC '87: Proceedings of the nineteenth annual ACM symposium on Theory of computingJanuary 1987 Pages 285–295https://doi.org/10.1145/28395.28426Online:01 January 1987Publication History 157citation769DownloadsMetricsTotal Citations157Total Downloads769Last 12 Months62Last 6 weeks5 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 Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Inductive Inference Machines (IlMs) attempt to identify functions given only input-output pairs of the functions. Probabilistic IlMs are defined, as is the probability that a probabilistic IlM identifies a function with respect to two common identification criteria: EX and BC. Let ID denote either of these criteria. Then ID/sub prob/(p) is the family of sets of functions U for which there is a probabilistic IlM identifying every f /spl epsi/ U with probability /spl ges/ p. It is shown that for all positive integers n, ID/sub prob/(1/n) is properly contained in ID/sub prob/(1/(n+1)), and that this discrete hierarchy is the "finest" possible. This hierarchy is related to others in the literature.