A model and a taxonomy to characterize pointer manipulations are introduced, along with an instrumentation technology that leverages them to provide students with immediate reports of pointer errors in C++ programs. Data collected from CS2 student assignments show that the vast majority of student pointer errors either would not have been noticed at all, or would have been detected only much later in execution, if this infrastructure were not used. Possible applications of the underlying technology--both to conduct long-term educational research into students' understanding of pointers, and to improve pedagogy directly--are discussed.

Currently there is a serious conceptual and technical gap between ideas emphasized in object-oriented programming and ideas as taught in algorithms courses. We suggest both a paradigm for "re-expressing" algorithms in terms of classes and objects, and a set of criteria relative to which the quality of such re-expressions can be evaluated. A detailed example is provided for re-expressing the algorithmic idea of sorting.

Summarizes an approach for introducing component-based software engineering (CBSE) early in the undergraduate computer science curriculum, and an evaluation of the impact of the approach at two institutions. Principles taught include a modular style of software development, an emphasis on human understanding of component behavior even while using formal specifications, and the importance of maintainability, as well as classical issues such as efficiency analysis and reasoning. Qualitative and quantitative evaluations of student outcomes and end-to-end changes in student attitudes show mostly positive results that are statistically significant, confirming that: (1) it is possible to teach CBSE principles without displacing "classical" principles usually taught in introductory courses, (2) students can understand and reuse formally specified components without knowing their implementations, and (3) student attitudes towards software engineering can be altered in directions heretofore often assumed to be difficult to achieve.

Abstraction is one of the cornerstones of software development and is recognized as a fundamental and essential principle to be taught as early as CS1/CS2. Abstraction supposedly can enhance students' ability to reason and think. Yet we often hear complaints about the inability of CS undergraduates to do that. Do we supply students with the tools they need to reach their potential to think carefully and to reason rigorously about software behavior? Typically we do not, but as educators there are techniques we can use to help our students develop such skills starting in CS1/CS2.

When teaching certain CS topics (e.g., abstract data types, operating systems), the instructor tries to make clear the distinction between the "client" perspective and the "implementer" perspective. But when teaching some programming language features and related programming techniques, this dichotomy often is not respected as strongly as it should be. We illustrate this with a discussion of how to teach recursion, comparing a traditional approach with one that is careful not to blur the distinctions between client view and implementer view. The latter better supports new learners in the creation of a sound and consistent mental model for developing and reasoning about programs that involve recursion.

First-year computer science students need to see clearly that computer science as a discipline has an important intellectual role to play and that it offers deep philosophical questions, much like the other hard sciences and mathematics; that CS is not "just programming". An appropriate intellectual focus for CS1/CS2 can be built on the foundations of systems thinking and mathematical modeling, as these principles are manifested in a component-based software paradigm. We outline some of the main technical features of this approach to CS1/CS2 and report preliminary observations from our experience with it.

Two important objectives when designing a specification for a reusable software component are understandability and utility. For a typical component defining a new abstract data type, a significant common factor affecting both of these objectives is the choice of a mathematical model of the (state space of the) ADT, which is used to explain the behavior of the ADT's operations to potential clients. There are subtle connections between the expressiveness of this mathematical model and the functions computable using the operations provided with the ADT, giving rise to interesting issues involving the two complementary system theoretic principles of "observability" and "controllability". The paper discusses problems associated with formalizing intuitively stated observability and controllability principles in accordance with these tests. Although the example we use for illustration is simple, the analysis has implications for the design of reusable software components of every scale and conceptual complexity.

Balcázar, Book, and Schöning introduced the extended low hierarchy based on the $\Sigma $-levels of the polynomial-time hierarchy as follows: for $k \geqslant 1$, level k of the extended low hierarchy is the set $EL_k^{P,\Sigma } = \{ A|\Sigma _k^P (A) \subseteq \Sigma _{k - 1}^P (A \oplus {\text{SAT}})\} $. Allender and Hemachandra and Long and Sheu introduced refinements of the extended low hierarchy based on the $\Delta $- and $\Theta $-levels, respectively, of the polynomial-time hierarchy: for $k \geqslant 2$, level k, $EL_k^{P,\Delta } = \{ A|\Delta _k^P (A) \subseteq \Delta _{k - 1}^P (A \oplus {\text{SAT}})\} $ and $EL_k^{P,\Theta } = \{ A|\Theta _k^P (A) \subseteq \Theta _{k - 1}^P (A \oplus {\text{SAT}})\} $. This paper shows that the extended low hierarchy is properly infinite by showing, for $k \geqslant 2$, that $EL_k^{P,\Sigma } \subsetneq EL_{k + 1}^{P,\Theta } \subsetneq EL_{k + 1}^{P,\Delta } \subsetneq EL_{k + 1}^{P,\sum } $. The proofs use the circuit lower bound techniques of Håstad and Ko. As corollaries to the constructions, for $k \geqslant 2$, oracle sets $B_k $, $C_k $, and $D_k $, such that ${\operatorname{PH}}(B_k ) = \Sigma _k^P (B_k ) \supsetneq \Delta _k^P (B_k )$, ${\operatorname{PH}}(C_k ) = \Delta _k^P (C_k ) \supsetneq \Theta _k^P (C_k )$, and ${\operatorname{PH}}(D_k ) = \Theta _k^P (D_k ) \supsetneq \sum _{k - 1}^P (D_k )$ are obtained.

A restricted relativization of NP, denoted ${\text{NP}}_B ( \cdot )$,was introduced in [SIAM J. Comput., 13 (1984), pp. 461– 487] in the study of positive relativizations on the ${\text{P}} = ?{\text{ NP}}$ question. The ${\text{NP}}_B ( \cdot )$ restriction allows nondeterministic polynomial-time oracle machines to query only polynomially many strings in its computation trees. In this paper we compare the language classes ${\text{NP}}_B (A)$, relative to arbitrary sets A, with the language classes $\text{NP}(S)$, relative to sparse sets S, showing that it is not always possible to obtain a class specified by ${\text{NP}}_B (A)$ as an $\text{NP}(S)$ class and vice versa. As a corollary to these results, we prove that there is a sparse set S such that for all tally sets T, $S \not\equiv_T^{\text{SN}} T$. This implies that the relationship established in [5] that for every sparse set S there is a tally set T such that $S \equiv _T^{\text{NP}} T$ cannot be improved to any of the strong nondeterministic polyn...

We present a relatively simple proof of a result from Homer (1986) showing that if nonrecursive sets cannot be minimal for honest polynomial-time Turing reducibility (⩽ h T -minimal), then P ≠ NP . As a corollary to our proof, we strengthen Homer's result by showing, without assuming that P ≠ NP , that there are ⩽ h T -minimal sets for all tally sets. We also consider the converse of Homer's result, providing some evidence that the nonexistence of ⩽ h T -minimal sets may folow from P ≠ NP in an interesting way. Finally, we consider structural and/or computability properties of sets that cannot be ⩽ h T -minimal.

Article Free Access Share on A note on one-way functions and polynomial-time isomorphisms Authors: K I Ko Department of Computer Science, University of Houston, Houston, Tx and Mathematical Sciences Research Institute, Berkeley, Ca. Department of Computer Science, University of Houston, Houston, Tx and Mathematical Sciences Research Institute, Berkeley, Ca.View Profile , T J Long Department of Computer and Information Science, The Ohio State University, Columbus, Oh. Department of Computer and Information Science, The Ohio State University, Columbus, Oh.View Profile , D Z Du Mathematical Sciences Research Institute, Berkeley, Ca. Mathematical Sciences Research Institute, Berkeley, Ca.View Profile Authors Info & Claims STOC '86: Proceedings of the eighteenth annual ACM symposium on Theory of computingNovember 1986 Pages 295–303https://doi.org/10.1145/12130.12160Published:01 November 1986Publication History 4citation223DownloadsMetricsTotal Citations4Total Downloads223Last 12 Months12Last 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 SiteeReaderPDF

Baker, Gill, and Solovay constructed sparse sets A and B such that P( A ) ≠ NP( A ) and NP( B ) ≠ co-NP( B ). In contrast to their results, we prove that P = NP if and only if for every tally language T , P( T ) = NP( T ), and that NP = co-NP if and only if for every tally language T , NP( T ) = co-NP( T ). We show that the polynomial hierarchy collapses if and only if there is a sparse set S such that the polynomial hierarchy relative to S collapses. Similar results are obtained for several other complexity classes.

A restricted relativization of NP, denoted ${\text{NP}}_B ( \cdot )$,was introduced in [SIAM J. Comput., 13 (1984), pp. 461– 487] in the study of positive relativizations on the ${\text{P}} = ?{\text{ NP}}$ question. The ${\text{NP}}_B ( \cdot )$ restriction allows nondeterministic polynomial-time oracle machines to query only polynomially many strings in its computation trees. In this paper we compare the language classes ${\text{NP}}_B (A)$, relative to arbitrary sets A, with the language classes $\text{NP}(S)$, relative to sparse sets S, showing that it is not always possible to obtain a class specified by ${\text{NP}}_B (A)$ as an $\text{NP}(S)$ class and vice versa. As a corollary to these results, we prove that there is a sparse set S such that for all tally sets T, $S \not\equiv_T^{\text{SN}} T$. This implies that the relationship established in [5] that for every sparse set S there is a tally set T such that $S \equiv _T^{\text{NP}} T$ cannot be improved to any of the strong nondeterministic polynomial-time degrees. Finally, we strengthen a result appearing in [4] by showing that nondeterministic oracle programs for sets $B \in \Sigma _k^{\text{P}} - \Delta _k^{\text{P}} $, for $k \geqq 2$, must search through exponentially many strings (infinitely often) that are actually in the oracle set when using oracle sets from $\Sigma _{k - 1}^{\text{P}} $. As a consequence, sparse sets at some $\Sigma^{\text{P}} $ level of the polynomial-time hierarchy cannot be used as orcales for sets properly at the next $\Sigma^{\text{P}} $ level.

We show that several questions about the polynomial-time hierarchy can be answered by answering their counterparts for the polynomial-time hierarchy relativized to an arbitrary sparse oracle set. For each of these questions, the answer will be the same for the hierarchy relativized to S/sub 1/ as it will be for the hierarchy relativized to S/sub 2/ for any choice of S/sub 1/ and S/sub 2/ that are sparse sets, including the choice of S/sub 1/ being empty and S/sub 2/ being nonempty but sparse.

Consider the following open problems: (i) ${\text{P}} = ? {\text{ NP}}$ (ii) ${\text{NP}} = ? {\text{ co-NP}}$; (iii) ${\text{P}} = ? {\text{ PSPACE}}$; (iv) ${\text{NP}} = ? {\text{ PSPACE}}$. In this paper we study these four problems from a particular point of view. To illustrate our approach, consider the first problem. It is known that there exist recursive sets A and B such that ${\text{P}}(A) = {\text{NP}}(A)$ and ${\text{P}}(B) \ne {\text{NP}}(B)$. We study restrictions R on both the deterministic and also the nondeterministic polynomial time-bounded oracle machines such that the following holds: ${\text{P}} = {\text{NP}}$ if and only if for every set A, ${\text{P}}_R (A) = {\text{NP}}_R (A)$. The restrictions are “quantitative” in the sense that the size of the set of strings queried by the oracle in computations of a machine on an input is bounded by a polynomial in the length of the input. We study several different ways of specifying such quantitative restrictions, each of which has the desired property.

We prove that a class of functions (denoted by NPCPt), whose graphs can be accepted in non-deterministic polynomial time, can be evaluated in deterministic polynomial time if and only if γ-reducibility is equivalent to polynomial time many-one reducibility. We also modify the proof technique used to obtain part of this result to obtain the stronger result that if every γ-reduction can be replaced by a polynomial time Turing reduction then every function in NPCPt can be evaluated in deterministic polynomial time.