We have transformed our first programming course from an introduction to programming, to an introduction to Computer Science. We have done this in part by broadening the topics discussed. We now incorporate discussion of social topics like privacy and humanitarian technology, and "big ideas in CS" like how the Internet and databases work. We have also embedding many of our programming examples in applications from fields like biology and psychology. The other major feature of this course is that we have separated teaching problem-solving from teaching a programming language. In lecture, we discuss problem-solving with high-level programming constructs like conditionals and loops, using only pseudocode. In our new lab section, students are taught how to translate those ideas into C++ code. This allows us to free the initial learning of problem-solving from the complications of a language like C++. A unique feature of these changes is that it is possible to offer multiple different labs, in different languages, in conjunction with the same lecture section. It is our intention to start offering labs in different languages starting in Fall 2016.

This paper introduces and studies two notions of easy sets without hard subsets: i) 𝒞-hollow sets are defined to be sets in P that have no 𝒞 – P subsets for (presumably) superclasses 𝒞 of P such as NP, PSPACE, E, NE, RE, etc.; and ii) 𝒞-scant sets are defined to be sets in P that have no many-one 𝒞-complete subsets. These sets complement well-studied objects in complexity such as P-printable sets, immune sets and complexity cores. First, characterizations of 𝒞-hollow sets and 𝒞-scant sets are obtained in terms of universally easy sets, introduced and studied in [7] as an automatic method for generating easy instances of intractable problems. Second, the following results regarding existence of 𝒞-hollow sets are obtained: infinite NP-hollow tally (equivalently, P-printable) sets exist iff some nondeterministic time complexity class equals its deterministic counterpart; in contrast, infinite E/NE/RE-hollow sets do not exist. Finally, it is shown that P-printable-immune sets in P are 𝒞-scant for E and NE.

We introduce a complexity-theoretic model for studying computational security of binary image watermarking systems. Our model restricts algorithms used by the sender and the attacker to the class /spl Hscr/ of hiding functions. These are efficiently computable functions that preserve visual fidelity of the input image. Security of watermarking systems is to be established with complexity results about hiding functions. We also survey current theories of vision and propose an automata-theoretic model for visual fidelity called c-similarity. Finally we propose a candidate for /spl Hscr/ based on c-similarity and show that it is robust and contains infinitely many functions computable in polynomial time.

We describe the design and implementation of a program called sim to measure similarity between two C computer programs. It is useful for detecting plagiarism among a large set of homework programs. This software is part of a project to construct tools to assist the teaching of computer science.

We show that every many-one complete set for NEXP (co-NEXP) has an infinite subset in P. We also show that every many-one complete set for EXP has anonsparseinfinite subset in P iff annihilating functions do not exist.

The authors study some decision questions concerning two-way counter machines and obtain the strongest decidable results to date concerning these machines. In particular, it is shown that the emptiness, containment, and equivalence (ECE for short) problems are decidable for two-way counter machines whose counter is reversal-bounded (i.e., the counter alternates between increasing and decreasing modes at most a fixed number of times). This result is used to give a simpler proof of a recent result which shows that the ECE problems for two-way reversal-bounded pushdown automata accepting bounded languages (i.e., subsets of $w_{1}^{*} \dotsc w_{k}^{*}$ for some nonnull words $w_{1}, \dotsc , w_{k}$) are decidable. Other applications concern decision questions about simple programs. Finally, it is shown that nondeterministic two-way reversal-bounded multicounter machines are effectively equivalent to finite automata on unary languages, and hence their ECE problems are decidable also.