This paper reflects on the 1976 paper by Thomas McCabe that defined the cyclomatic complexity of computer programs. The reflection first describes the context in which the paper was written and the relevance of the paper to issues of the period. Second, the cyclomatic complexity metric is described and illustrated. Third, the impact of cyclomatic complexity is reviewed: in directly related areas the impact is deep, highly visible and time-tested; in adjacent areas there is a clear influence of McCabe’s work; in software engineering as a whole there is a lasting legacy. A short interview with and a biography of Thomas McCabe are given.

Collaborative learning has proven to be a productive approach across domains including computer science. Especially for novices, collaboration among learners with diverse experiences, values, and knowledge can be especially effective. However, there is limited research on how collaborative interactions among learners from different undergraduate disciplines manifest during the learning of computational concepts. This qualitative study investigates interaction among learners in small interdisciplinary student groups in an undergraduate computational thinking (CT) class. In analyzing the social interactions of cohort members, the Differentiating Overt Learning Activities (DOLA) framework developed by Chi was used as a starting point. Several themes (e.g. explain-to-other, self-monitor, connect/plan) suggested by Chi’s overt activities framework emerged naturally in the observations. However, several categories that were not explicitly stated in the DOLA framework also emerged. These are: asking a shallow question versus asking an elaborate question, socializing, being confused or expressing frustration, self-talk, and struggle. Analysis of interactions between cohort members revealed that most of the group interactions were active in nature. Barriers to collaborative learning were accentuated when peers were novices. Students who lacked knowledge of computational concepts found it hard to contribute to a discussion, hindering learning, whereas students who had better conceptual understanding were constructive in their interactions, elaborated on a topic, made connections with previous problems, and displayed self-awareness about their understanding.

Programming tasks provide an opportunity for students to improve their problem-solving skills (PSS). However, when programming tasks are challenging, students could become demotivated and lose the opportunity to improve PSS in the process. To scaffold the difficulty of programming tasks and better motivate students to enhance PSS via coding, this paper introduces PDL (Problem Description Language). Given the natural-language description of a combinatorial optimization problem (COP), PDL requires students to describe (i) inputs, (ii) constraints, (iii) the optimization objective, and (iv) outputs, based on their problem comprehension. PDL then validates each problem description by (1) compiling a solution program from the description and (2) executing the generated program with predefined test cases. Based on the compiling and testing results, PDL provides feedback to students, and assists students to adjust their problem comprehension and improve problem descriptions.

This demo introduces attendees to Pedal, a Python framework that streamlines the process of authoring semi-automated feedback on students? Python code. As a pure Python package, Pedal is compatible with a wide range of autograding platforms, including GradeScope, VPL, WebCAT, and BlockPy - as long as the platform allows package installation, Pedal should work. Pedal is a collection of modular program analysis tools exposed with a declarative interface, built around a centralized infrastructure. These tools include a sandboxed execution environment for running students' code with enhanced tracebacks, pattern matching syntax for specifying common student mistakes, basic type inference and flow analysis, random question pools, and a library of over 60 high-level, pedagogically-oriented assertions. Pedal's model for these tools synthesizes the detection of conditions and their instructor-mediated responses, encapsulated into dedicated feedback functions that can be tracked and modified as first-class objects. Our goal is to elevate Feedback with Software Engineering and Instructional Design practices, to become a central part of your course's development rather than an afterthought. Our toolchain also includes command lines utilities for unit testing your feedback to verify behavior and analyze collected programming snapshot data. Our hope is that adoptees will find that Pedal expands the power of their autograder and opens new avenues of research.

Pattern-based feedback detects incorrect code patterns in students' programs and provides feedback that can be personalized to the details of the matched code. Currently, a high level of instructor effort is required because the pattern detection must be expressed using complex programmatic interfaces. A specification language for pattern-based feedback is presented that mitigates this cost. Examples from actual student code illustrate the language's design and expressiveness. The language's implementation and testing is briefly described. Reflections are given on the the language design, where it is effectively used, and lessons learned from experience with its use. While our implementation is targeted at Python, other programming languages could be targeted using a similar approach.

This paper describes Pedal, an innovative approach to the automated creation of feedback given to students in programming classes. Pedal is so named because it supports the PEDAgogical goals of instructors and is an expandable Library of components motivated by these goals. Pedal currently comes with components for type inferencing, flow analysis, pattern matching, and unit testing to provide an instructor with a rich set of resources to use in authoring and prioritizing feedback. The larger vision is the loosely-coupled architecture whose components can be readily expanded or replaced. The Pedal library components are motivated by a study of contemporary automated feedback systems and our own experience. Pedal's components are described and examples are given of Pedal-based feedback from three different introductory classes at two different universities. The integration of Pedal into several programming and autograding environments is briefly described.

The feedback given to novice programmers can be substantially improved by delivering advice focused on learners' cognitive misconceptions contextualized to the instruction. Building on this idea, we present Misconception-Driven Feedback (MDF); MDF uses a cognitive student model and program analysis to detect mistakes and uncover underlying misconceptions. To evaluate the impact of MDF on student learning, we performed a quasi-experimental study of novice programmers that compares conventional run-time and output check feedback against MDF over three semesters. Inferential statistics indicates MDF supports significantly accelerated acquisition of conceptual knowledge and practical programming skills. Additionally, we present descriptive analysis from the study indicating the MDF student model allows for complex analysis of student mistakes and misconceptions that can suggest improvements to the feedback, the instruction, and to specific students.

Data science keeps growing in popularity as an introductory computing experience, in which students answer real-world questions by processing data. Armed with carefully prepared pedagogical datasets, computing educators can contextualize assignments and projects in societally meaningful ways, thereby benefiting students' long-term professional careers. However, integrating data science into introductory computing courses requires that the datasets be sufficiently complex, follow appropriate organizational structure, and possess ample documentation. Moreover, the impact of a data science context on students' motivation remains poorly understood. To address these issues, we have created an open-sourced manual for developing pedagogical datasets (freely available at https://think.cs.vt.edu/pragmatics). Structured as a collection of patterns, this manual shares the expertise that we have gained over the last several years, collecting and curating a large collection of real-world datasets, used in a dozen of universities worldwide. We also present new evidence confirming the efficacy of integrating data science in an introductory computing course. As a significant extension of our ongoing work, this study not only validates existing positive assessment, but also provides fine-grained nuance to the potential of data science as a motivational educational element.

Collaborative learning can help reduce the anxiety level of learners, improve understanding and thus create a positive atmosphere for learning. This study analyzes students' collaborative learning experiences within small interdisciplinary "cohorts" while learning computational thinking in a university-level class. The cohort allows students from different disciplines to contribute diverse perspectives, socially interact with each other and in turn create situations where two or more students learn together. This study uses both qualitative and quantitative means to explore students' collaborative learning experiences. Ethnographically-informed qualitative data using Stahl's collaborative framework is analyzed. The analysis revealed that most students found the cohort model to be valuable in learning computational thinking by allowing them to ask about and explain problems, especially with students from different disciplines who perceive and explain a problem differently. Quantitative data from a multi-term survey complements and confirms the findings from the qualitative data. Our study helps to inform those teaching foundational computing concepts to a diverse audience of learners.

This paper reports on a systematic method used to improve an existing unit of instruction. The method is distinctive in combining steps of instructional design with "knowledge components" from a cognitively-based framework of learning. Instructional design is used to develop assessment instruments that incorporate information about student misconceptions. The method uses the assessment instruments to evaluate student performance and learning gains, while statistical analysis evaluates the quality of the instruments themselves using measures of difficulty and discrimination. Fine-grain insight into possible improvements is enabled by the knowledge components implicated by the assessment. The method is illustrated and evaluated by applying it to a unit of instruction on collection-based iteration in a computational thinking class. Data gathered during this evaluation highlights a number of opportunities within the unit to refine the instruction.

Introductory non-major learners face the challenge of mastering programming fundamentals while remaining sufficiently motivated to engage with the computing discipline. In particular, multi-disciplinary students struggle to find relevance in traditional computing curricula that tend to either emphasize abstract concepts, focus on entertainment (e.g., game and animation design), or rely on decontextualized settings. To address these issues, this demo introduces BlockPy, a web-based environment for Python (https://blockpy.com). The most powerful feature of BlockPy is a dual text/block view that beginners can freely move between, using advanced Mutual Language Translation techniques. The environment contextualizes introductory programming with data science by integrating real-world data including weather reports, classic book statistics, and historical crime data. A fusion of Blockly and Skulpt, the entire interface runs locally with no need for server sandboxing. BlockPy is also a platform for interactive, guided practice problems with automatic feedback that scaffolds learners. This demo will walk through the novel features of BlockPy's environment, including the instructor's perspective of creating new problems and how BlockPy can be embedded in modern LTI-compatible learning management systems. BlockPy is available online for free and is open-sourced on GitHub. This material is based on work supported by the NSF under Grants No. DGE-0822220, DUE-1444094, and DUE-1624320.

To successfully bring introductory computing to non-CS majors, one needs to create a curriculum that will appeal to students from diverse disciplines. Several educational theories emphasize the need for introductory contexts that align with students' long-term goals and are perceived as useful. Data Science, using algorithms to manipulate real-world data and interpreting the results, has emerged as a field with cross-disciplinary value, and has strong potential as an appealing context for introductory computing courses. However, it is not easy to find, clean, and integrate datasets that will satisfy a broad variety of learners. The CORGIS project (https://think.cs.vt.edu/corgis) enables instructors to easily incorporate data science into their classroom. Specifically, it provides over 40 datasets in areas including history, politics, medicine, and education. Additionally, the CORGIS infrastructure supports the integration of new datasets with simple libraries for Java, Python, and Racket, thus empowering introductory students to write programs that manipulate real data. Finally, the CORGIS web-based tools allow learners to visualize and explore datasets without programming, enabling data science lessons on day one. We have incorporated CORGIS assignments into an introductory course for non-majors to study their impact on learners' motivation, with positive initial results. These results indicate that external adopters are likely to find the CORGIS tools and materials useful in their own pedagogical pursuits.

A key retention issue when educating computing novices is ensuring that the frustrations of mastering programming fundamentals do not demotivate and discourage students from studying the discipline. In particular, non-CS majors often struggle to find relevance in traditional computing curricula that tend to either emphasize abstract concepts, focus on non-practical entertainment (e.g., game and animation design), or rely on decontextualized settings. To address these issues, this paper introduces BlockPy, a block-based environment for Python (http://www.blockpy.com). BlockPy is a web-based, open-access programming environment that supports introductory programming with an emphasis on data science. It promotes long-term transfer by scaffolding an introduction to textual programming (Python) through a block-based programming view, ideal for beginners of any background. By supporting the latest Learning Tools Interoperability (LTI) standards, BlockPy is designed to support both informal learners and formal class settings. Specifically, it can be configured to provide guiding feedback for its interactive programming problems, so as to support learners at their own pace. The results from a pilot study of the initial deployment and utilization of BlockPy indicate the potential of the environment to address many of the problems faced by novice learners.

This paper describes the design and initial assessment of a general education course in computational thinking for non-computer science majors. The key elements of the course include multidisciplinary cohorts to achieve learning across contexts, multiple languages/tools, including block-based and textual programming languages, repeated exposure to the underlying computational ideas in different forms, and student-defined projects using real world ("big") data to heighten motivation through self-directed contextualized learning. The preliminary multi-methods assessment shows that the course engendered high levels of motivation, achieved key objectives for learning in and across contexts, largely affirmed the choice of languages/tools, and supported, though less strongly than anticipated, the motivational effects of real-world data

Computational thinking (CT) is increasingly seen as a core literacy skill for the modern world on par with the longestablished skills of reading, writing, and arithmetic. To promote the learning of CT at a young age we capitalized on children's interest in play. We designed RabBit EscApe, a board game that challenges children, ages 610, to orient tangible, magnetized manipulatives to complete or create paths. We also ran an informal study to investigate the effectiveness of the game in fostering children's problemsolving capacity during collaborative game play. We used the results to inform our instructional interaction design that we think will better support the learning activities and help children hone the involved CT skills. Overall, we believe in the power of such games to challenge children to grow their understanding of CT in a focused and engaging activity.

Many Android vulnerabilities share a root cause of malicious unauthorized applications executing without user's consent. In this paper, we propose the use of a technique called process authentication for Android applications to overcome the shortcomings of current Android security practices. We demonstrate the process authentication model for Android by designing and implementing our runtime authentication and detection system referred to as DroidBarrier. Our malware analysis shows that DroidBarrier is capable of detecting real Android malware at the time of creating independent processes. A

This paper points out the need in modern operating system kernels for a process authentication mechanism, where a process of a user-level application proves its identity to the kernel. Process authentication is different from process identification. Identification is a way to describe a principal; PIDs or process names are identifiers for processes in an OS environment. However, the information such as process names or executable paths that is conventionally used by OS to identify a process is not reliable. As a result, malware may impersonate other processes, thus violating system assurance. We propose a lightweight secure application authentication framework in which user-level applications are required to present proofs at runtime to be authenticated to the kernel. To demonstrate the application of process authentication, we develop a system call monitoring framework for preventing unauthorized use or access of system resources. It verifies the identity of processes before completing the requested system calls. We implement and evaluate a prototype of our monitoring architecture in Linux. The results from our extensive performance evaluation show that our prototype incurs reasonably low overhead, indicating the feasibility of our approach for cryptographically authenticating applications and their processes in the operating system.

In this paper a meta-model for information flow control is defined using the foundation of Barker's access control meta-model. The purposes for defining this meta-model is to achieve a more principled understanding of information flow control, to compare information flow control and access control at an abstract level, and to explore how information flow control and access control might be composed to yield a rich new set of ideas and systems for controlling the dissemination of sensitive information. It is shown that it is possible to define a meta-model for information flow control, that such a model is more complex compared to the access control meta-model, and that the meta-models for information flow control and access control can be composed in a conceptually straightforward way.

Main stream operating system kernels lack a strong and reliable mechanism for identifying the running processes and binding them to the corresponding executable applications. In this paper, we address the identification problem by proposing a novel secure application identification model in which user-level applications are required to present identification proofs at run time to be authenticated to the kernel. In our model, applications are supplied with unique secret keys. The secret key of an application is registered with a trusted kernel at the installation time and is used to uniquely authenticate the application. We present a protocol for the secure authentication of applications. Additionally, we develop a system call monitoring architecture that uses our model to verify the identity of applications when making designated system calls. Our system call monitoring can be integrated with existing mandatory access control systems to enforce application-level access rights. We implement and evaluate a prototype of our monitoring architecture in Linux as device drivers with no modification of the kernel. The results from our extensive performance evaluation shows that our prototype incurs low overhead, indicating the feasibility of our approach for cryptographically identifying and authenticating applications in the operating system.

Experience with the first offering of a computational thinking course for computer science (CT4CS) students is reported. The course is grounded in student interaction with fundamental, recurring concepts suggested by comparison with two sets of computer science principles. By using specialized, freely available tools and physical simulations it is possible to provide concrete, tangible learning experiences that neither require knowledge of nor the overhead of programming. Student end-of-term reflections indicate that the course deepened and broadened their understanding of computer science even when they had previously encountered a topic, and improved their computer science vocabulary.

Public key infrastructures suffer from usability and security problems associated with the request for and secure management of end user credentials. Online credential repositories provide mechanisms to ease these shortcomings but pose attractive targets for attacks due to the accumulation of credentials and the need for remote access to these credentials. Through the extension of an existing credential repository with a cryptographic coprocessor for secure storage of credentials an increase in the security of the service can be achieved. This higher security permits the use of online credential repositories with a wide variety of certificates without violating certification authority regulations. Also, the improved performance afforded by hardware support improves the scalability of a centralized credential storage.

We introduce the Symphony framework, a software abstraction layer that can sit on top of grid systems. Symphony provides a unified API for grid application developers and offers a graphical user interface for rapid collaborative development and deployment of grid applications and problem solving environments through compositional modeling following the data-flow paradigm. Symphony meta-programs and program components can be distributed, reused and modified. Together with Symphony a new security model is developed that extends existing security architectures to allow for collaboration of grid developers and users in permanent as well as ad-hoc working groups.

Abstract As the power of computational Grids increases, there is a corresponding need for better usability for large and diverse communities. The focus in this paper is on supporting multidisciplinary communities of scientists and engineers. We discuss requirements for Grid computing environments (GCEs) in this context, and describe several core support technologies developed to meet these requirements. Our work extends the notion of a programming environment beyond the compile–schedule–execute paradigm, to include functionality such as collaborative application composition, information services, and data and simulation management. Systems designed for five different applications communities are described. These systems illustrate common needs and characteristics arising in multidisciplinary communities and motivate a high‐level design framework for building GCEs that meet those needs. Copyright © 2002 John Wiley & Sons, Ltd.

This paper shows how to perform concurrent and distributed automatic garbage collection of objects possessing their own thread of control. The relevance of garbage collection and active objects to distributed applications is briefly discussed and the specific model of active objects used in the paper is explained. The collector is comprised of independent local collectors, one per node, and a distributed global collector. The mutator (application), the local collectors and the global collector run concurrently. An important part of this paper is the detailed presentation of the algorithms necessary to achieve correct concurrent operation among the collectors and between the collectors and the mutator. The collector builds on previous algorithms for taking snapshots in distributed systems and for detecting termination.>

Distributed automatic garbage collection of objects possessing their own thread of control is discussed. The relevance of garbage collection and concurrent objects to distributed applications is briefly discussed, and the specific model of concurrent objects used is explained. The collector comprises a collection of independent local collectors, one per node, loosely coupled to a distributed global collector. The mutator (application), the local collectors, and the global collector run concurrently. The synchronization necessary to achieve correct and efficient concurrent operation between the collectors is presented. One interesting aspect of the distributed collector is the termination algorithm.>

Little or no empirical validation exists for many of software engineering's basic assumptions. While some of these assumptions are intuitive, the need for scientific experimentation remains clear. Several assumptions are made about the factors affecting software reuse, and in particular, the role of the object-oriented paradigm. This paper describes the preliminary results of a controlled experiment designed to evaluate the impact of the object-oriented paradigm on software reuse. The experiment concludes that (1) the object-oriented paradigm substantially improves productivity, although a significant part of this improvement is due to the effect of reuse, (2) reuse without regard to language paradigm improves productivity, (3) language differences are far more important when programmers reuse than when they do not, and (4) the object-oriented paradigm has a particular affinity to the reuse process.

The authors show how to perform real-time automatic garbage collection of objects possessing their own thread of control. Beyond its interest as a novel real-time problem, the relevance of automatic management and concurrent objects to real-time applications is briefly discussed. The specific model of concurrent objects used in the paper is explained. A definition of real-time garbage collection is given and an algorithm satisfying this definition is described. An analysis of the relationship between latency, memory overhead and system size shows that this approach is immediately feasible for low-performance real-time systems or multiprocessor real-time systems with a dedicated processor for garbage collection. Future improvements in the collector's performance are outlined.>

Inheritance is a valuable mechanism which enhances reusability and maintainability of software. A language design based on the actor model of concurrent computation faces a serious problem arising from the interference between concurrency and inheritance. A similar problem also occurs in other concurrent object-oriented languages. In this paper, we describe problems found in existing concurrent object-oriented languages. We present a solution which is based on a concept called behavior abstraction.

This paper reports on a modest study which relates seven different software complexity metrics to the experience of maintenance activities performed on a medium size software system. Three different versions of the system that evolved over a period of three years were analyzed in this study. A major revision of the system, while still in its design phase, was also analyzed.

One aspect of network design is the extent to which memory is shared among the processing elements. In this paper a model with limited sharing (only two processors connected to each memory) is analyzed and its performance compared with the performance of two other models that have appeared in the literature. One of these is a model of multiple processors sharing a single memory; the other model considers a multiprocessor configuration in which each processor has its own dedicated memory. The tasks processed by these networks are described by both time and memory requirements. The largest-memory-first (LMF) scheduling algorithm is employed and its performance with respect to an enumerative optimal scheduling algorithm is bounded. On the basis of this measure we conclude that memory sharing is only desirable on very small networks and is disadvantageous on networks of larger size.

Abstract The design and analysis of the structure of software systems has typically been based on purely qualitative grounds. In this paper we report on our positive experience with a set of quantitative measures of software structure. These metrics, based on the number of possible paths of information flow through a given component, were used to evaluate the design and implementation of a software system (the UNIX operating system kernel) which exhibits the interconnectivity of components typical of large‐scale software systems. Several examples are presented which show the power of this technique in locating a variety of both design and implementation defects. Suggested repairs, which agree with the commonly accepted principles of structured design and programming, are presented. The effect of these alterations on the structure of the system and the quantitative measurements of that structure lead to a convincing validation of the utility of information flow metrics.

Structured design methodologies provide a disciplined and organized guide to the construction of software systems. However, while the methodology structures and documents the points at which design decisions are made, it does not provide a specific, quantitative basis for making these decisions. Typically, the designers' only guidelines are qualitative, perhaps even vague, principles such as "functionality," "data transparency," or "clarity." This paper, like several recent publications, defines and validates a set of software metrics which are appropriate for evaluating the structure of large-scale systems. These metrics are based on the measurement of information flow between system components. Specific metrics are defined for procedure complexity, module complexity, and module coupling. The validation, using the source code for the UNIX operating system, shows that the complexity measures are strongly correlated with the occurrence of changes. Further, the metrics for procedures and modules can be interpreted to reveal various types of structural flaws in the design and implementation.

The study of abstract models of computer systems using deterministic methods has produced sigmficant insight into the behavior of such systems in recent years This paper considers a model of a minicomputer network which consists of an arbitrary number of identical processors Each processor in the network has a fixed, though possibly different sized, private memory The network processes a set of tasks with known execution times and memory requirements One of the problems a designer of such a network must solve is to determine the memory sizes for such a system Algorithms to determine the memory configuration are presented and analyzed using worst-case bounds and computer s~mulation KEY WORDS AND PHRASES deterministic models, design algorithms, system configuration, computer networks, multiprocessor systems CR CATE(,ORIES 4 32, 5 39 General

This paper considers a model of a computing system with several independent but identical processors, each with a private memory of limited, and possibly different, storage capacity. The tasks are assumed to have known resource demands expressed as processing times and memory requirements. Several scheduling strategies are evaluated by worst-case performance bounds and simulation results. Both preemptive and nonpreemptive scheduling are considered. An optimal preemptive algorithm is given to find the shortest schedule for a task set with no precedence constraints.