Search

Computational thinking, defined as a way of thinking that can be applied to various fields that require problem-solving skills, has become prevalent in education. Students, i.e., future specialists, have to be prepared for complex thinking competence, necessary for solving business and societal problems, for which a combination of mathematical thinking and computational thinking is essential. The preliminary premise is that there is a correlation between ability in specific mathematical and computational fields. Therefore, this paper aims to highlight the significance of investigating the relations between those fields from linguistic point of view. In order to better understand the relationship between abilities in specific mathematical and computational fields, this paper presents an analysis of a new approach, namely, developing hypotheses for exploring the relationship between metalanguages of different fields of Mathematics and Computer Science. Additionally, the paper describes the first stage of a study on a doctoral level in an attempt to suggest possible statistical analyses suitable for testing hypotheses based on meta-analysis of the current literature. [ABSTRACT FROM AUTHOR]

What is computational explanation? Many accounts treat it as a kind of causal explanation. I argue against two more specific versions of this view, corresponding to two popular treatments of causal explanation. The first holds that computational explanation is mechanistic, while the second holds that it is interventionist. However, both overlook an important class of computational explanations, which I call limitative explanations. Limitative explanations explain why certain problems cannot be solved computationally, either in principle or in practice. I argue that limitative explanations are not plausibly understood in either mechanistic or interventionist terms. One upshot of this argument is that there are causal and non-causal kinds of computational explanation. I close the paper by suggesting that both are grounded in the notion of computational implementation. [ABSTRACT FROM AUTHOR]

The evolution of smart contracts in recent years inspired a crucial question: do smart contract evaluation protocols provide the required level of privacy when executing contracts on the blockchain? The Hawk (IEEE S&P '16) paper introduces a way to solve the problem of privacy in smart contracts by evaluating the contracts off-chain, albeit with the trust assumption of a manager. To avoid the partially trusted manager altogether, a novel approach named zkHawk (IEEE BRAINS '21) explains how we can evaluate the contracts privately off-chain using a multi-party computation (MPC) protocol instead of trusting said manager. This paper dives deeper into the detailed construction of a variant of the zkHawk protocol titled V-zkHawk using formal proofs to construct the said protocol and model its security in the universal composability (UC) framework (FOCS '01). The V-zkHawk protocol discussed here does not support immediate closure, i.e., all the parties (n) have to send a message to inform the blockchain that the contract has been executed with corruption allowed for up to t parties, where t < n . In the most quintessential sense, the V-zkHawk is a variant because the outcome of the protocol is similar (i.e., execution of smart contract via an MPC function evaluation) to zkHawk, but we modify key aspects of the protocol, essentially creating a small trade-off (removing immediate closure) to provide UC (stronger) security. The V-zkHawk protocol leverages joint Schnorr signature schemes, encryption schemes, Non-Interactive Zero-Knowledge Proofs (NIZKs), and commitment schemes with Common Reference String (CRS) assumptions, MPC function evaluations, and assumes the existence of asynchronous, authenticated broadcast channels. We achieve malicious security in a dishonest majority setting in the UC framework. [ABSTRACT FROM AUTHOR]

• Eulerian trails are classical and important objects in theoretical computer science field. • Enumeration of Eulerian trails is known to be #P-complete. • Although the existence of an algorithm with linear time per output is known, the existence of a faster algorithm is open. • This paper shows optimal algorithms for Eulerian trails which run in constant time per solution on average. In this paper, we consider enumeration problems for edge-distinct and vertex-distinct Eulerian trails. Two Eulerian trails are said to be edge-distinct if the edge sequences are not identical, and they are said to be vertex-distinct if the vertex sequences are not identical. To solve these problems, we propose optimal enumeration algorithms that run in O (N + m) total time, where N is the number of solutions and m is the number of edges in an input connected graph. The proposed algorithms are based on the reverse search technique introduced by [Avis and Fukuda, DAM 1996], and the push-out amortization technique introduced by [Uno, WADS 2015]. [ABSTRACT FROM AUTHOR]

The minimum connected dominating set (MCDS) problem consists of selecting a minimum set of vertices from an undirected graph, such that each vertex not in this set is adjacent to at least one of the vertices in it, and the subgraph induced by this vertex set is connected. This paper presents a fast vertex weighting (FVW) algorithm for solving the MCDS problem, which integrates several distinguishing features, such as a vertex weighting-based local search with tabu and perturbation strategies to help the search to jump out of the local optima, as well as a search space reduction strategy to improve the search efficiency. Computational experiments on four sets of 112 commonly used public benchmark instances, as well as 15 newly introduced sparse instances, show that FVW is highly competitive compared with the state-of-the-art algorithms in the literature despite its simplicity. FVW improves the previous best-known results for 20 large public benchmark instances while matching the best-known results for all but 2 of the remaining ones. Several ingredients of FVW are investigated to demonstrate the importance of the proposed ideas and techniques. Summary of Contribution: As a challenging classical NP-hard problem, the minimum connected dominating set (MCDS) problem has been studied for decades in the areas of both operations research and computer science, although there does not exist an exact polynomial algorithm for solving it. Thus, the new breakthrough on this classical NP-hard problem in terms of the computational results on classical benchmark instances is significant. This paper presents a new fast vertex weighting local search for solving the MCDS problem. Computational experiments on four sets of 112 commonly used public benchmark instances show that fast vertex weighting (FVW) is able to improve the previous best-known results for 20 large instances while matching the best-known results for all but 2 of the remaining instances. Several ingredients of FVW are also investigated to demonstrate the importance of the proposed ideas and techniques. [ABSTRACT FROM AUTHOR]

Low-rank matrix completion, which aims to recover a matrix with many missing values, has attracted much attention in many fields of computer science. A low-rank matrix fitting (LMaFit) method has been proposed for fast matrix completion recently. However, this method cannot converge accurately on matrices of real-world images. For improving the accuracy of LMaFit method, an improved low-rank matrix fitting (ILMF) method based on the weighted L 1 , p norm minimization is proposed in this paper, where the L 1 , p norm is the summation of the p -power (0 < p < 2) of L 1 norms of rows in a matrix. In the proposed method, i.e. the ILMF method, the incomplete matrix that may be corrupted by noises is decomposed into the summation of a low-rank matrix and a noise matrix at first. Then, a weighted L 1 , p norm minimization problem is solved by using an alternating direction method for improving the accuracy of matrix completion. Experimental results on real-world images show that the ILMF method has much better performances in terms of both the convergence accuracy and convergence speed than the compared methods. [ABSTRACT FROM AUTHOR]

A coreset of an input set is its small summarization, such that solving a problem on the coreset as its input, provably yields the same result as solving the same problem on the original (full) set, for a given family of problems (models/classifiers/loss functions). Coresets have been suggested for many fundamental problems, for example, in machine/deep learning, computer vision, databases, and theoretical computer science. This introductory paper was written following requests regarding the many inconsistent coreset definitions, lack of source code, the required deep theoretical background from different fields, and the dense papers that make it hard for beginners to apply and develop coresets. The article provides folklore, classic, and simple results including step‐by‐step proofs and figures, for the simplest (accurate) coresets. Nevertheless, we did not find most of their constructions in the literature. Moreover, we expect that putting them together in a retrospective context would help the reader to grasp current results that usually generalize these fundamental observations. Experts might appreciate the unified notation and comparison table for existing results. Open source code is provided for all presented algorithms, to demonstrate their usage, and to support the readers who are more familiar with programming than mathematics. This article is categorized under:Algorithmic Development > Structure DiscoveryFundamental Concepts of Data and Knowledge > Big Data MiningTechnologies > Machine Learning [ABSTRACT FROM AUTHOR]

In this paper, the parallel machine scheduling problem with DeJong's learning effect, is addressed. The objective function to be minimized is the makespan. This problem is proofed to be NP-Hard in the strong sense. This is the challenging theoretical side of the studied problem. Furthermore, several real-life situations in manufacturing and computer science are modeled using the current problem. Several algorithms intended to solve the studied problem within a reasonable computing time are proposed in literature. Among these algorithms the exact methods, which failed to solve the studied problem to optimality even for small size instances. In this paper several new heuristics and meta-heuristics are proposed. These heuristics are classified into three types. The first type is based on Longest Processing Time (LPT) rule. The innovation is the modification of the LPT rule in a way to cope efficiently with the learning effect concept, by randomizing the selection of the next scheduled job. The second type of heuristics, is taking advantage of an exact Branch and Bound algorithm, developed originally for the classical parallel machine scheduling problem. The contribution for this kind of heuristics is lying in the modification of the processing time values, according to a prefixed selected functions. The third type of methods is based in an adaptation of the Genetic Algorithm to the learning effect concept. This adaptation consists in enlarging the area of selection of the parameters values. To assess the performance and the efficiency of the proposed heuristics, a newly developed lower bound is proposed. This lower bound is based on a relaxation of the studied problem, which allows to obtain a minimum cost flow problem. Finally, an extensive experimental study is conducted over a benchmark test problems. The obtained results provide strong evidence that the proposed procedures outperform the earlier existing ones. • Modeling the learning effect in parallel machine scheduling problem. • Development of dispatching rules based heuristics. • Development of heuristics based on the resolution of NP-Hard problems. • Development of new tight lower bounds based on the maximum allowed position. • Caring out an extensive experimental study that confirms the efficiency of the proposed procedures. [ABSTRACT FROM AUTHOR]

This paper addresses a problem of global optimization in a non-Archimedean fuzzy metric space context without fuzzy P-property. Specifically, it concerns the determination of the fuzzy distance between two subsets of a non-Archimedean fuzzy metric space. Our approach to solving this problem is to find an optimal approximate solution to a fixed point equation. This approach has been well studied within a category of problems called proximity point problems. We explore some new types of (ψ − ϕ) -weak proximal contractions and investigate the existence of the unique best proximity point for such kinds of mappings. Subsequently, some fixed point results for corresponding contractions are proved, and some illustrative examples are presented to support the validity of the main results. Moreover, an interesting application in computer science, particularly in the domain of words has been provided. Our work is a fuzzy generalization of the proximity point problem by means of fuzzy fixed point method. [ABSTRACT FROM AUTHOR]

A graph structure is a useful tool in solving the combinatorial problems in different areas of computer science and computational intelligence systems. In this paper, we introduce the concept of cubic soft graph, complete cubic soft graph, (internal, external) cubic soft graphs and investigate some of their properties. Then we deal with fundamental operations, union, intersection, Cartesian product, composition of cubic soft graphs and illustrate these notions by several examples. We prove that cubic soft graphs under these operations are also a cubic soft graph. Finally, we describe an application of cubic soft graphs in decision making. [ABSTRACT FROM AUTHOR]

Reviewing is the most important step in the quality accreditation of scientific works, requires the professional expertise of the reviewer as well as there is no conflict of interest in the evaluation process. However, we also acknowledge that reviewers have limited knowledge, experience and opinions about the work of others, so they may misinterpret the author's point of view, leading to the rejection of excellent scientific work or a potentially successful project proposal. Manually selecting reviewers can lead to bias and time-consuming. To solve these problems, we have developed a support system for selecting a group of reviewers to evaluate a particular problem, such as a proposal or a research paper. Our support system consists of three main modules: data collection, reviewer identification and group prediction of reviewers. The Data Collection module collects data from a variety of sources to create the scientist profile database. The reviewer identification module recognizes reviewers on a specific topic. The reviewer prediction module provides a group of exp reviewers to evaluate a submitted paper or a proposal. Experiments on the DBLP computer science bibliography dataset showed that our system achieves better results in terms of accuracy in comparison to other methods. [ABSTRACT FROM AUTHOR]

• First survey of relevant research activities on Digital Calibration Certificate-DCC. • A thorough analysis of both the calibration process and the calibration certificate. • Modeling the calibration process, the calibration certificate life-cycle. • Identifying Calibration use-cases and stakeholders. • Advantages and disadvantages of various potential DCC formats. Calibration Certificates (CC) are essential for maintaining the accuracy of measurement instruments, which in turn are necessary to maintain the quality of products and services. Such certificates are mainly used in legal metrology for quality audits, accreditation and examination processes; and also in the operational metrology to adjust measurement results according to device uncertainty. Paper-based CC (PCC) or a digital copy of the paper format has been successfully used for this purpose for many decades. However, the PCC starts to fail short with the emergence of new technologies and applications that require automated creation, processing and updates of the calibration certificates. The last years have witnessed an intense effort on digital transformation in metrology and especially developing Digital Calibration Certificates (DCC). Until recently, we noticed the lack of agreement on the nature and the usage of such important new metrology artifacts as well as some repetition in the work by different researchers. To help reaching a minimum consensus on the subject, we present in this paper, a thorough analysis of the calibration certificate and the calibration process. Besides that, we aim by this work to provide an overview of the carried research on that point to help peer researchers to view the big picture and to avoid wasting their efforts in repeating same work on same ideas. Consequently, they can recognize the peer researchers and organizations working on the same topics, find available resources, identify research gaps and identify the best potential directions of their efforts as well. Finally, our paper aims also to establish a bridge between the metrological concepts and information technology concepts such that more computer science researchers can be involved in solving the problem. [ABSTRACT FROM AUTHOR]

Non-overlapping codes are a set of codewords in $\bigcup _{n \ge 2} \mathbb {Z}_{q}^{n}$ , where $\mathbb {Z}_{q} = \{0,1, {\dots },q-1\}$ , such that the prefix of each codeword is not a suffix of any codeword in the set, including itself; and for variable-length codes, a codeword does not contain any other codeword as a subword. In this paper, we investigate a generic method to generalize binary codes to $q$ -ary ones for $q > 2$ , and analyze this generalization on the two constructions given by Levenshtein (also by Gilbert; Chee, Kiah, Purkayastha, and Wang) and Bilotta, respectively. The generalization on the former construction gives large non-expandable fixed-length non-overlapping codes whose size can be explicitly determined; the generalization on the latter construction is the first attempt to generate $q$ -ary variable-length non-overlapping codes. More importantly, this generic method allows us to utilize the generating function approach to analyze the cardinality of the underlying $q$ -ary non-overlapping codes. The generating function approach not only enables us to derive new results, e.g., recurrence relations on their cardinalities, new combinatorial interpretations for the constructions, and the superior limit of their cardinalities for some special cases, but also greatly simplifies the arguments for these results. Furthermore, we give an exact formula for the number of fixed-length words that do not contain the codewords in a variable-length non-overlapping code as subwords. This thereby solves an open problem by Bilotta and induces a recursive upper bound on the maximum size of variable-length non-overlapping codes. [ABSTRACT FROM AUTHOR]

This paper concerns quantum heuristics that are able to extend the domain of quantum computing defining a promising way in the large number of well-known classical algorithms. Quantum approximate heuristics take advantage of alternation between one Hamiltonian defining the problem to solve and one mixing Hamiltonian. The adiabatic theorem initially defines in quantum physic allow to compute a solution for the Schrödinger equation, but the foundation of this methods requires strong skill in physics and mathematics. Our main objectives in this paper are at first to provide an algorithm-based presentation (as close as possible of the classical computer science community in operational research practice) of the adiabatic optimization and secondly to give a comprehensive resolution of the well-known SAT problem. This presentation gives opportunities to provide a concise but explicit analysis of the adiabatic capability to define a new efficient operational research trend. Our experiments encompass numerical evaluations on both simulator and on real quantum computer provided by IBM. Numerical evaluations using the QLM library meet the Qiskit evaluations. This contribution is at the crossroad of physic and computer science in the sense it proves the capabilities of quantum concepts to define a new and promising research trends in optimization. [ABSTRACT FROM AUTHOR]

Since Wing Communications of the ACM, 49, 33–35, (2006) popularized computational thinking (CT) as a skill for every student, it has gained significant traction as an approach to bring computer science tools and practices into K-12 classrooms. At the same time, teachers often see the relevance of CT as a tool to introduce problem solving and thinking strategies in the classroom. Despite the increasing use of CT in K-12, questions remain about its role in supporting teaching and learning of disciplinary ideas. While CT can be used to bring computer science to all students, we believe that it can serve a bigger purpose to explicitly teach metacognitive strategies, which play a significant role in academic outcomes. In the paper, we discuss the connections between CT and metacognition and how CT could support the development of metacognition in K-12 classrooms. [ABSTRACT FROM AUTHOR]

Robotics activities engage students in critical and computational thinking, problem solving, and collaboration, as well as engineering and computer science. By integrating robotics into disciplinary courses, educators offer these opportunities to a wider range of students. However, teachers may be less likely to use new technology without evidence that it can support their teaching and student learning. This paper presents two descriptive case studies as a 'proof of concept' for integrating robotics construction activities into disciplinary courses. They focus on teachers' motivation for integration, and how they used robotics to support disciplinary goals. [ABSTRACT FROM AUTHOR]

Computational thinking (CT), which is a cognitive skill used to solve problems with computational solutions, has drawn increasing attention among researchers and practitioners due to the growing recognition of CT competence as a 21st century skill. Collaboration is commonly integrated into CT education to facilitate novice learning, but there is inadequate knowledge regarding the influences of collaboration in CT education. This meta‐analysis examined the overall effects on the cognitive, social and affective competencies of collaborative versus individual problem solving in CT through programming. We identified 33 publications involving 4717 learners, which allowed for 220 effect size comparisons. We found a medium effect size (Hedges' g = 0.562; p < 0.001) in favour of collaborative problem solving on cognitive learning outcomes and a small effect size (Hedges' g = 0.316; p < 0.01) on affective learning outcomes using a random‐effects model. Categorical moderator analysis revealed the moderating effects of educational level, programming environment, study duration, grouping method and group size. The competency model that was generated from the synthesized literature on collaborative computational problem solving yielded insights into the learning design and assessment of relevant activities. Practitioner notesWhat is already known about the topic?Although professional programming usually requires collaboration to accomplish common goals in the work environment, programming is predominantly taught on an individual basis in educational settings.Some intervention studies have reported inconsistent learning outcomes (positive and negative) from integrating collaborative problem solving (CPS) into programming education.There is a need for further scrutiny and exploration of the role of collaboration in the process of learning to program.What does this paper add?Our meta‐analysis showed that CPS is an effective pedagogical tool for developing students' cognitive, affective and social competencies.The moderator analysis revealed that CPS in programming has cognitive benefits irrespective of grouping method, group size and educational levels; however, there is a need for caution in regard to designing collaborative problem‐solving activities for different programming environments and durations.The model generated from the literature synthesis can yield insights into better assessing and designing collaborative problem‐solving activities.Implications for practice and/or policy?Integrating CPS into programming education can prepare students with 21st century skills.Social and affective competencies are crucial to students' learning capacity, which is an issue that needs to be better assessed.Future studies could look more rigorously into the effects of CPS in visual programming and robotics programming among younger age groups, such as primary or middle school students. [ABSTRACT FROM AUTHOR]

This paper presents a game-design workshop built around a digital art installation featuring video games displayed over a real-world skyscraper to stimulate students' interest in computer science and a study testing its short-term effects on improving middle school students' computational thinking (CT) skills and attitudes towards computing. Following a STEAM approach, the workshop aimed to engage participants in age-appropriate activities that focus on CT skills through the lens of creating their own game. A web-based game design interface that allows students to code and play games as simulated on a skyscraper was developed to support the workshop's core activities. The web environment also featured step-by-step tutorials and fully functional games to promote the accessibility of the learning materials for a diverse body of students and educators around the globe. The results of the study indicated that the workshop helped students improve their CT skills and differentially influence their attitudes towards computing. In particular, the workshop experience led students from underserved community districts to lower their attitude ratings, whereas the reverse pattern was observed for students from more affluent districts. The workshop reportedly informed students' perception of computing as a profession and their appreciation of the analytical effort required for developing functional games. Qualitative analysis of artifact-based interviews indicated that students could begin to make abstractions and devise algorithms by associating variables through conditional statements while solving problems related to game development. Interview analysis also revealed that students took pride in the effort that they made during the workshop. [ABSTRACT FROM AUTHOR]

Modernization of the educational content in the field of Computer science, or IT subjects, in the conditions of Czech primary schools is a relatively widely discussed topic today, as the educational content as well as the teaching methods of IT subjects at primary schools often remain more or less unchanged for many years. However, a completely different situation can be observed abroad, where, for many years, prominent experts have been making proposals to change the concept of teaching so that pupils are not only educated to become active technology users, but are also encouraged to try to devise their own procedures, propose tools for solving specific problems and develop the so-called computational thinking. So, what does the specific educational content of IT subjects at the 1st and 2nd stage of Czech primary schools look like? Which IT topics are actually taught? Are there any topics in teaching that are not embedded or accentuated in the curriculum documents? We will try to answer these questions in the submitted paper, which presents some partial outputs of the conducted research focused primarily on the issue of the acceptance of educational content of IT subjects taught at primary schools. [ABSTRACT FROM AUTHOR]

• Censoring outliers in a dataset with a class of CES distribution has been considered. • Cost function is formulated by maximum likelihood setting with two different penalties. • An efficient and low complexity algorithm is proposed guaranteeing the convergence. • Proposed algorithm generalizes FMCD to be applicable to non-Gaussian distributions. • Proposed algorithms exhibit satisfactory performance in non-Gaussian environments. In this paper, we discuss the problem of censoring outliers in a dataset with a class of complex elliptically symmetric (CES) distribution, which has various engineering applications. To this end, the regularized cost function is formulated by the maximum likelihood (ML) setting. Since the ML estimation of the free outlier subset requires solving a combinatorial problem, an efficient and low complexity algorithm is proposed that guarantees the convergence to a stationary point. Two independent and dependent penalty terms to the selected subset are considered. The conventional generalized inner product (GIP) and the submodular minimization approaches are employed in the derivation of the proposed algorithm in the independent and dependent cases, respectively. The dependent case improves performance by slightly increasing complexity. As a special case for Gaussian assumption and using a non-regularized cost function, the proposed algorithm reduces to the fast minimum covariance determinant (FMCD) algorithm, which has impressive efficiency and received considerable attention in statistics and computer science. Hence, the proposed algorithm extends/generalizes the FMCD to be applicable to the non-Gaussian distributions. The simulation results highlight that the proposed algorithms exhibit satisfactory performance in CES environments. [ABSTRACT FROM AUTHOR]

Boolean Satisfiability problem (SAT) plays a prominent role in many domains of computer science and artificial intelligence due to its significant importance in both theory and applications. Algorithms for solving SAT problems can be categorized into two main classes: complete algorithms and incomplete algorithms (typically stochastic local search (SLS) algorithms). SLS algorithms are among the most effective for solving uniform random SAT problems, while hybrid algorithms achieved great breakthroughs for solving hard random SAT (HRS) problem recently. However, there is a lack of algorithms that can effectively solve both uniform random SAT and HRS problems. In this paper, a new SLS algorithm named SelectNTS is proposed aiming at solving both uniform random SAT and HRS problem effectively. SelectNTS is essentially an improved probability selection based local search algorithm, the core of which includes new clause and variable selection heuristics: a new clause weighting scheme and a biased random walk strategy are utilized to select a clause, while a new probability selection strategy with the variation of configuration checking strategy is used to select a variable. Extensive experimental results show that SelectNTS outperforms the state-of-the-art random SAT algorithms and hybrid algorithms in solving both uniform random SAT and HRS problems effectively. [ABSTRACT FROM AUTHOR]