Search

Data structures such as sets, lists, and arrays are fundamental in mathematics and computer science, playing a crucial role in numerous real-life applications. These structures represent a variety of entities, including solutions, conditions, and objectives. In scenarios involving large datasets, eliminating duplicate elements is essential to reduce complexity and enhance performance. This paper introduces a novel algorithm that uses logarithmic prime numbers to efficiently sort data structures and remove duplicates. The algorithm is mathematically rigorous, ensuring correctness and providing a thorough analysis of its time complexity. To demonstrate its practicality and effectiveness, we compare our method with existing algorithms, highlighting its superior speed and accuracy. An extensive experimental analysis across one thousand random test problems shows that our approach significantly outperforms two alternative techniques from the literature. By discussing the potential applications of the proposed algorithm in various domains, including computer science, engineering, and data management, we illustrate its adaptability through two practical examples in which our algorithm solves the problem more than 3 × 10 4 and 7 × 10 4 times faster than the existing algorithms in the literature. The results of these examples demonstrate that the superiority of our algorithm becomes increasingly pronounced with larger problem sizes. [ABSTRACT FROM AUTHOR]

There can be many reasons why students fail to answer correctly to summative tests in advanced computer science courses: often the cause is a lack of prerequisites or misconceptions about topics presented in previous courses. One of the ITiCSE 2020 working groups investigated the possibility of designing assessments suitable for differentiating between fragilities in prerequisites (in particular, knowledge and skills related to introductory programming courses) and advanced topics. This paper reports on an empirical evaluation of an instrument focusing on data structures, among those proposed by the ITiCSE working group. The evaluation aimed at understanding what fragile knowledge and skills the instrument is actually able to detect and to what extent it is able to differentiate them. Our results support that the instrument is able to distinguish between some specific fragilities (e.g., value vs. reference semantics), but not all of those claimed in the original report. In addition, our findings highlight the role of relevant skills at a level between prerequisite and advanced skills, such as program comprehension and reasoning about constraints. We also suggest ways to improve the questions in the instrument, both by improving the distractors of the multiple-choice questions, and by slightly changing the content or phrasing of the questions. We argue that these improvements will increase the effectiveness of the instrument in assessing prerequisites as a whole, but also to pinpoint specific fragilities. [ABSTRACT FROM AUTHOR]

To explain why, in scientific problem solving, a diagram can be "worth ten thousand words," Jill Larkin and Herbert Simon (1987) relied on a computer model: two representations can be "informationally" equivalent but differ "computationally," just as the same data can be encoded in a computer in multiple ways, more or less suited to different kinds of processing. The roots of this proposal lay in cognitive psychology, more precisely in the "imagery debate" of the 1970s on whether there are image-like mental representations. Simon (1972, 1978) hoped to solve this debate by thoroughly reducing the differences between forms of mental representations (e.g., between images and sentences) to differences in computational efficiency; to carry out this reduction, he borrowed from computer science the concepts of data type and of data structure. I argue that, in the end, his account amounted to nothing more than characterizing representations by the fast operations on them. This analysis then allows me to assess what Simon's approach actually achieves when transported from psychology to the study of scientific representations, as in Larkin and Simon (1987): it allows comparing, not representations in and of themselves, but rather the computational roles they play in particular problem-solving processes—that is, representations together with a particular way of using them. [ABSTRACT FROM AUTHOR]

The realm of education is witnessing a burgeoning array of AI applications, with one noteworthy addition being Chatbot technology. This innovation has been harnessed to streamline both teaching and administrative functions. This paper introduces HexBot, a Chatbot meticulously crafted to enhance the learning journey of students enrolled in a data structures course at an esteemed educational institution. The development of HexBot entailed an exhaustive exploration of cutting-edge practices, methodologies, and apt tools. Additionally, a comprehensive user survey was conducted to ascertain preferences and requirements pertaining to the Chatbot's utilization for this specific purpose. HexBot was successfully implemented on the SnatchBot platform and seamlessly integrated into a dedicated Telegram channel. Encouragingly, the outcomes underscore its efficacy in empowering college students to independently access precise information about data structures within the realm of computer science, thereby obviating the necessity for human intervention. [ABSTRACT FROM AUTHOR]

Binary search trees (BSTs) are one of the most important data structures in the field of computer science. We may easily write a parallel construction program of a BST by extending the sequential algorithm straightly. However, in such conventional approaches, the order of nodes inserted into a BST is determined dynamically, depending on the occasional state of the parallel thread execution. It results in a BST with a different structure (node position) generated on every execution of the parallel program. On the other hand, we have been developing parallel construction schemes of the BST with the same structure as a BST generated by the sequential algorithm. One is the speculatively parallel construction of a BST. And another is the purely (non-speculatively) parallel construction, but it was derived through the concept of thread-level speculation. This paper evaluates the performances of those construction schemes on several types of shared-memory multiprocessors. For the large enough size of BST, our new parallel programs can construct a BST with always the same structure on a little lower or sometimes higher performance than the program that makes a BST with a different structure on every execution. And in contrast with the general expectation that simply enlarging the size of parallel tasks increases misspeculation and damages the performance, we found that it sometimes enhances the performance of speculatively parallel execution. [ABSTRACT FROM AUTHOR]

The article discusses the Sustainable Development Goals (SDGs) of the United Nations, which were adopted by all member states in 2015. These goals aim to address pressing global issues such as poverty, health, education, inequality, economic growth, climate change, and environmental preservation. The article suggests that the field of modeling, particularly in computer science and software engineering, can play a significant role in understanding and predicting the impact of changes related to these goals. It emphasizes the need for robust and integrated models that can capture the complexity and interactions of the SDGs, and calls for further research and development in this area. [Extracted from the article]

This two-part comprehensive survey is devoted to a computing framework most commonly known under the names Hyperdimensional Computing and Vector Symbolic Architectures (HDC/VSA). Both names refer to a family of computational models that use high-dimensional distributed representations and rely on the algebraic properties of their key operations to incorporate the advantages of structured symbolic representations and distributed vector representations. Notable models in the HDC/VSA family are Tensor Product Representations, Holographic Reduced Representations, Multiply-Add-Permute, Binary Spatter Codes, and Sparse Binary Distributed Representations but there are other models too. HDC/VSA is a highly interdisciplinary field with connections to computer science, electrical engineering, artificial intelligence, mathematics, and cognitive science. This fact makes it challenging to create a thorough overview of the field. However, due to a surge of new researchers joining the field in recent years, the necessity for a comprehensive survey of the field has become extremely important. Therefore, amongst other aspects of the field, this Part I surveys important aspects such as: known computational models of HDC/VSA and transformations of various input data types to high-dimensional distributed representations. Part II of this survey [84] is devoted to applications, cognitive computing and architectures, as well as directions for future work. The survey is written to be useful for both newcomers and practitioners. [ABSTRACT FROM AUTHOR]

Knowledge graphs (KGs) are useful data structures for the integration, retrieval, dissemination, and inference of information in various information domains. One of the main challenges in building KGs is the extraction of named entities (nodes) and their relations (edges), particularly when processing unstructured text as it has no semantic descriptions. Generating KGs from texts written in Spanish represents a research challenge as the existing structures, models, and strategies designed for other languages are not compatible in this scenario. This paper proposes a method to design and construct KGs from unstructured text in Spanish. We defined lexical patterns to extract named entities and (non) taxonomic, equivalence, and composition relations. Next, named entities are linked and enriched with DBpedia resources through a strategy based on SPARQL queries. Finally, OWL properties are defined from the predicate relations for creating resource description framework (RDF) triples. We evaluated the performance of the proposed method to determine the degree of elements extracted from the input text and to assess their quality through standard information retrieval measures. The evaluation revealed the feasibility of the proposed method to extract RDF triples from datasets in general and computer science domains. Competitive results were observed by comparing our method regarding an existing approach from the literature. [ABSTRACT FROM AUTHOR]

This article presents a simple yet effective method for computing geodesic distances on triangle meshes. Unlike the popular window propagation methods that partition mesh edges into intervals of varying lengths, our method places evenly-spaced, source-independent Steiner points on edges. Given a source vertex, our method constructs a Steiner-point graph that partitions the surface into mutually exclusive tracks, called geodesic tracks. Inside each triangle, the tracks form sub-regions in which the change of distance field is approximately linear. Our method does not require any pre-computation, and can effectively balance speed and accuracy. Experimental results show that with 5 Steiner points on each edge, the mean relative error is less than 0.3 $\%$ % for common 3D models used in the graphics community. We propose a set of effective filtering rules to eliminate a large amount of useless broadcast events. For a 1000K-face model, our method runs 10 times faster than the conventional Steiner point method that examines a complete graph of Steiner points in each triangle. We also observe that using more Steiner points increases the accuracy at only a small extra computational cost. Our method works well for meshes with poor triangulation and non-manifold configuration, which often poses challenges to the existing PDE methods. We show that geodesic tracks, as a new data structure that encodes rich information of discrete geodesics, support accurate geodesic path and isoline tracing, and efficient distance query. Our method can be easily extended to meshes with non-constant density functions and/or anisotropic metrics. [ABSTRACT FROM AUTHOR]

The 33rd International Workshop On Combinatorial Algorithms (IWOCA 2022) was held at the University of Trier in Germany. This workshop covers a wide range of topics related to combinatorial algorithms. The special issue of the journal Algorithmica contains extended versions of selected papers from IWOCA 2022, which were nominated by the Program Committee and underwent a rigorous reviewing process. The special issue includes nine papers on various topics such as perfect matchings, algorithmic questions, and winner determination algorithms. One paper was chosen as the Best Paper of IWOCA 2022 and another as the Best Student Paper. The special issue is recommended for readers interested in exploring more papers from IWOCA 2022. [Extracted from the article]

Ride sharing has a tremendous potential to reduce the number of vehicles needed to serve a certain mobility demand. However, although ride sourcing services have flourished in recent years and are widely available worldwide (e.g. Uber, Didi, Lyft, Via), known ride sharing techniques still suffer severe scalability limitations, especially if the goal is combining multiple on-demand ride requests into a single trip within a large urban area. In the context of on-demand mobility systems, a complete enumeration of all candidate trip requests is unfortunately not a practical approach to find the optimal ride sharing solution. An efficient filtering approach is therefore needed in order to avoid both the storage of quadratic shortest-path lookup tables, as well as the exhaustive pairwise comparison of all mobility requests, with their GPS coordinates and time constraints. In this paper we present a ride sharing algorithm, which combined with the shareability networks method, is able to substantially speed up known approaches while only minimally impacting on the quality of the computed solution. The key building block is a novel locality filter, which allows to build a pruned version of the shareability network more efficiently in time and space than previous works. We corroborate this novel proposal with a large set of experiments executed over a dataset consisting of one month of trip requests (~106) performed in two different urban areas, namely Manhattan (NYC) and Singapore. Our experiments show that our approach achieves a $5\times $ speed-up, or even more during so-called “rush times”, and it is robust under different traffic conditions. [ABSTRACT FROM AUTHOR]

Any information is (transported as) a selection from an ordered set, which is the "domain" of the information. For example, any piece of digital information is a number sequence that represents such a selection. Its senders and receivers (with software) should know the format and domain of the number sequence in a uniform way worldwide. So far, this is not guaranteed. However, it can be guaranteed after the introduction of the new "Domain Vector" (DV) data structure: "UL plus number sequence". Thereby "UL" is a "Uniform Locator", which is an efficient global pointer to the machine-readable online definition of the number sequence. The online definition can be adapted to the application so that the DV represents the application-specific, reproducible features in a precise (one-to-one), comparable, and globally searchable manner. The systematic, nestable online definition of domains of digital information (number sequences) and the globally defined DV data structure have great technical potential and are recommended as a central focus of future computer science. [ABSTRACT FROM AUTHOR]

Representing a static set of integers S, | S | = n from a finite universe U = [ 1.. u ] is a fundamental task in computer science. Our concern is to represent S in small space while supporting the operations of rank and select on S; if S is viewed as its characteristic vector, the problem becomes that of representing a bit-vector, which is arguably the most fundamental building block of succinct data structures. Although there is an information-theoretic lower bound of B (n , u) = lg u n bits on the space needed to represent S, this applies to worst-case (random) sets S, and sets found in practical applications are compressible. We focus on the case where elements of S contain runs of| ℓ > 1 consecutive elements, one that occurs in many practical situations. Let C (n) denote the class of u n distinct sets of n elements over the universe [ 1.. u ] . Let also C g (n) ⊂ C (n) contain the sets whose n elements are arranged in g ≤ n runs of ℓ i ≥ 1 consecutive elements from U for i = 1 , ... , g , and let C g , r (n) ⊂ C g (n) contain all sets that consist of g runs, such that r ≤ g of them have at least 2 elements. This paper yields the following insights and contributions related to rank / select succinct data structures: We introduce new compressibility measures for sets, including: B 1 (g , n , u) = lg | C g (n) | = lg u - n + 1 g + lg n - 1 g - 1 , and B 2 (r , g , n , u) = lg | C g , r (n) | = lg u - n + 1 g + lg n - g - 1 r - 1 + lg g r , such that B 2 (r , g , n , u) ≤ B 1 (g , n , u) ≤ B (n , u) . We give data structures that use space close to bounds B 1 (g , n , u) and B 2 (r , g , n , u) and support rank and select in O (1) time. We provide additional measures involving entropy-coding run lengths and gaps between items, and data structures to support rank and select using space close to these measures. [ABSTRACT FROM AUTHOR]

The Sketch is a compact data structure useful for network measurements. However, to cope with the high speeds of the current data plane, it needs to be held in the small on-chip memory (SRAM). Therefore, the product of the counter size and the number of counters must be below a certain limit. With small counters, some will overflow. With large counters, the total number of counters will be small, but each counter will be shared by more flows, leading to poor accuracy. To address this issue, we propose a generic technique: self-adaptive counters (SEAD Counter). When the value of the counter is small, it works as a standard counter. When the value of the counter is large however, we increment it using a predefined probability, so as to represent this large value. Moreover, in the SEAD Counter, the probability decreases when the value increases. We show that this technique can significantly improve the accuracy of counters. This technique can be adapted to different circumstances. We theoretically analyze the improvements achieved by the SEAD Counter. We further show that our SEAD Counter can be extended to three typical sketches and Bloom filters. We conduct extensive experiments on three real datasets and one synthetic dataset. The experimental results show that, compared with the state-of-the-art, sketches using the SEAD Counter improve the accuracy by up to 13.6 times, while the Bloom filters using SEAD Counter can reduce the false positive rate by more than one order of magnitude. [ABSTRACT FROM AUTHOR]

In recent years, Industrial Internet of Things (IIoT) has gradually attracted the attention of the industry owing to its accurate time synchronization, communication accuracy, and high adaptability. As an important data structure, graphs are widely used in IIoT applications, where entities and their relationships can be expressed in the form of graphs. With the widespread adoption of IIoT and cloud computing, an increasing number of individuals or organizations are outsourcing their IIoT graph data to cloud servers to enjoy the unlimited storage space and fast computing service. To protect the privacy of graph data, graphs are usually encrypted before being outsourced. In this article, we propose a search pattern privacy system for approximate shortest distance query of encrypted graphs in IIoT. To realize search pattern privacy, we adopt two noncolluded cloud servers to accomplish different tasks. We leverage the first server to store the encrypted data and perform query operations, and use the second one to rerandomize the contents and shuffle the locations of the queried records. Before queries, we generate the trapdoors by using different random numbers. After queries, we ask the second server to rerandomize the contents of the records that the first server touched. In addition, we shuffle the physical locations of original records by inserting some fake records. In this way, all contents and physical locations of the touched records change, so that the first server cannot distinguish whether two queries are the same or not. To enhance the efficiency on the user side, we further improve this system by moving some heavy workloads from the user to the cloud. The security analysis and the performance evaluation show that our work is secure and efficient. [ABSTRACT FROM AUTHOR]

Contribution: Research has shown that computer science (CS) students who start programming assignments (PAs) early generally receive higher grades. This article presents and evaluates a gamification approach that utilizes software engineering tools to motivate CS students to start and finish PAs earlier. Background: CS can be difficult to learn because students often struggle with errors and how to properly test their code. For these reasons, it is essential that students start their PAs early. Furthermore, software engineering tools, such as version control and unit testing, are increasingly important for students to learn early in their career. Intended Outcomes: This gamification approach aims to motivate CS students to start and complete PAs earlier, as well as instill software engineering best practices. Application Design: To motivate students to start and finish assignments early, an open-source gamification system called the Leaderboard was developed. Using gamified points, the Leaderboard rewards students who pass PA unit tests well before the assignment is due. The system is fully automated using Github Classroom, a build server, and the Moodle learning management system. Findings: Results indicate students who used the Leaderboard did not start assignments significantly earlier; however, they finished assignments earlier, committed code more frequently, and passed more unit tests. The students found the Leaderboard to be motivating and passing unit tests was exciting for them. [ABSTRACT FROM AUTHOR]

Recent advances in network representation learning have enabled significant improvement in the link prediction task, which is at the core of many downstream applications. As an increasing amount of mobility data become available because of the development of location-based technologies, we argue that this resourceful mobility data can be used to improve link prediction tasks. In this paper, we propose a novel link prediction framework that utilizes user offline check-in behavior combined with user online social relations. We model user offline location preference via a probabilistic factor model and represent user social relations using neural network representation learning. To capture the interrelationship of these two sources, we develop an anchor link method to align these two different user latent representations. Furthermore, we employ locality-sensitive hashing to project the aggregated user representation into a binary matrix, which not only preserves the data structure but also improves the efficiency of convolutional network learning. By comparing with several baseline methods that solely rely on social networks or mobility data, we show that our unified approach significantly improves the link prediction performance. Summary of Contribution: This paper proposes a novel framework that utilizes both user offline and online behavior for social link prediction by developing several machine learning algorithms, such as probabilistic factor model, neural network embedding, anchor link model, and locality-sensitive hashing. The scope and mission has the following aspects: (1) We develop a data and knowledge modeling approach that demonstrates significant performance improvement. (2) Our method can efficiently manage large-scale data. (3) We conduct rigorous experiments on real-world data sets and empirically show the effectiveness and the efficiency of our proposed method. Overall, our paper can contribute to the advancement of social link prediction, which can spur many downstream applications in information systems and computer science. [ABSTRACT FROM AUTHOR]

TRIM is a recommended command to deliver data invalidation information of the file system to flash storage. It is issued on both system level and device level. Since it can reduce the number of data copies during device-level garbage collection (DGC), TRIM has been widely used to improve the endurance and performance of mobile devices. Contrary to the common belief, this work identifies that the default TRIM scheme has both merit and drawback to the performance of mobile devices, especially in flash-friendly file system (F2FS), which is a commonly used file system in mobile devices. On one hand, TRIM can reduce garbage collection migration to prolong the flash lifetime as well as improving I/O throughput; On the other hand, TRIM may induce I/O contentions. This article proposes a new TRIM scheme, iTRIM, to distribute the timing overheads to system idle time. To further reduce I/O contention and improve I/O performance, the design of iTRIM considers the TRIM size, and the logical addresses’ pattern of victim invalidated data. Experimental results show that iTRIM can minimize I/O contentions while retaining the benefits of the default TRIM scheme for endurance and performance. [ABSTRACT FROM AUTHOR]

This study employs Google trends and data from the web of science to evaluate the popularity, growth, and impacts of visual analytics (VA) as a research field and data science technique. The paper undertakes quantitative analyses and visualization of the temporal trends, from VA's emergence in 2000 to the end of 2019. The trend analysis helps to forecast future growth in the research and practice of VA. The study highlights four outcomes. First, there is a robust direct relationship among the variables, including VA's growth on the Google trends, the scientific literature production (SLP), and usage of the published documents. Second, the SLP's growth pattern highlights VA's popularity as an emerging field with an overall annual increase of 17.4%. The high citation counts of the published scholarship indicate a significant impact and a continuous growth of the VA field. Third, VA contributes to diverse disciplines other than computer science and information systems, from business and economics to engineering, healthcare, biomedical and chemical sciences, and arts and humanities. VA helps researchers and practitioners in multidisciplinary fields analyze multidimensional data, enhance data visualization, knowledge discovery, generating insights, and make informed decisions. On the reverse, other disciplines contribute to propelling VA's popularity through research productivity, usage, and citation impacts. Finally, a trend analysis predicts sustained future growth of VA technology in research and practice to dissect and sensemaking of the increasingly massive and complex data structures, which is now the norm in many fields. [ABSTRACT FROM AUTHOR]

• Study the minsum k -sink problems on dynamic flow path networks for the confluent/non-confluent flow model. • Develop algorithms which run in almost linear time regardless of the number of sinks k. • Improve upon the previous results for the same problem with the confluent flow model. • Provide the first polynomial time algorithm for the problem with the non-confluent flow model. • The main theoretical contribution is to construct novel data structures for solving subproblems in polylogarithmic time. We address the facility location problems on dynamic flow path networks. A dynamic flow path network consists of an undirected path with positive edge lengths, positive edge capacities, and positive vertex weights. A path can be considered as a road, an edge length as the distance along the road and a vertex weight as the number of people at the site. An edge capacity limits the number of people that can enter the edge per unit time. In the dynamic flow network, given particular points on edges or vertices, called sinks , all the people evacuate from the vertices to the sinks as quickly as possible. The problem is to find the location of sinks on a dynamic flow path network in such a way that the aggregate evacuation time (i.e., the sum of evacuation times for all the people) to sinks is minimized. We consider two models of the problem: the confluent flow model and the non-confluent flow model. In the former model, the way of evacuation is restricted so that all the people at a vertex have to evacuate to the same sink, and in the latter model, there is no such restriction. In this paper, for both the models, we develop algorithms which run in almost linear time regardless of the number of sinks. It should be stressed that for the confluent flow model, our algorithm improves upon the previous result by Benkoczi et al. [Theoretical Computer Science, 2020], and one for the non-confluent flow model is the first polynomial time algorithm. [ABSTRACT FROM AUTHOR]

Data clustering is one of the most fundamental techniques in exploratory data analysis. It is widely used for determining the underlying data structure, classifying natural data and compressing data in engineering, business management, social statistics, computer science, and medicine. Under the assumption that clusters are high density regions in the feature space separated by relatively low density neighbors, a novel approach is proposed for modeling any high dimensional clustering problem as a one-dimensional analysis of the probability distribution. First, a special path between two vertexes, namely eigenpath, is defined in this paper to represent their close connection. Second, we propose the connectedness index based on the eigenpath for quantitatively describing the connection between two vertexes. Third, the connectedness index is applied to the candidates of cluster centers and measures the connection between different candidates. Then an indicative curve can be drawn with the knowledge of connectedness index. This approach not only provides effective indicative curve for unknown data sets but also facilitates eliminating the curse of dimensionality partly as well as correctly recognizes arbitrary cluster forms and automatically excludes outliers. Extensive experiments showed the effectiveness and efficiency of the proposed approach. [ABSTRACT FROM AUTHOR]

We consider the problems of maintaining an approximate maximum matching and an approximate minimum vertex cover in a dynamic graph undergoing a sequence of edge insertions/deletions. Starting with the seminal work of Onak and Rubinfeld (in: Proceedings of the ACM symposium on theory of computing (STOC), 2010), this problem has received significant attention in recent years. Very recently, extending the framework of Baswana et al. (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2011) , Solomon (in: Proceedings of the IEEE symposium on foundations of computer science (FOCS), 2016) gave a randomized dynamic algorithm for this problem that has an approximation ratio of 2 and an amortized update time of O(1) with high probability. This algorithm requires the assumption of an oblivious adversary, meaning that the future sequence of edge insertions/deletions in the graph cannot depend in any way on the algorithm's past output. A natural way to remove the assumption on oblivious adversary is to give a deterministic dynamic algorithm for the same problem in O(1) update time. In this paper, we resolve this question. We present a new deterministic fully dynamic algorithm that maintains a O(1)-approximate minimum vertex cover and maximum fractional matching, with an amortized update time of O(1). Previously, the best deterministic algorithm for this problem was due to Bhattacharya et al. (in: Proceedings of the ACM-SIAM symposium on discrete algorithms (SODA), 2015); it had an approximation ratio of (2 + ε) and an amortized update time of O (log n / ε 2) . Our result can be generalized to give a fully dynamic O (f 3) -approximate algorithm with O (f 2) amortized update time for the hypergraph vertex cover and fractional hypergraph matching problem, where every hyperedge has at most f vertices. [ABSTRACT FROM AUTHOR]

This study conducted a comparative analysis on domestic and foreign computer science curriculum, in order to introduce the data structure education as a core foundation of computer science. The findings show that the scope and level of data structure contents included in elementary school software education are poorer than those in U.S.A and England. To resolve such a problem, it selected some data structure education factors and a Delphi survey about the importance of contents and the fitness of education periods were administered to experts. Although they responded that 'text information', 'array', 'stack' and 'queue' for linear structures', and 'tree' for non-linear structures are important, their opinions were different in education periods by its factors. The generalization of the findings may be limited, given that the analysis was based on the survey of some experts, but this study has an implication, in that it provides important information for improving elementary school software curriculum for the introduction of data structures. [ABSTRACT FROM AUTHOR]

This paper proposes a novel discriminative regression method, called adaptive locality preserving regression (ALPR) for classification. In particular, ALPR aims to learn a more flexible and discriminative projection that not only preserves the intrinsic structure of data, but also possesses the properties of feature selection and interpretability. To this end, we introduce a target learning technique to adaptively learn a more discriminative and flexible target matrix rather than the pre-defined strict zero-one label matrix for regression. Then, a locality preserving constraint regularized by the adaptive learned weights is further introduced to guide the projection learning, which is beneficial to learn a more discriminative projection and avoid overfitting. Moreover, we replace the conventional ‘Frobenius norm’ with the special $l_{2,1}$ norm to constrain the projection, which enables the method to adaptively select the most important features from the original high-dimensional data for feature extraction. In this way, the negative influence of the redundant features and noises residing in the original data can be greatly eliminated. Besides, the proposed method has good interpretability for features owing to the row-sparsity property of the $l_{2,1}$ norm. Extensive experiments conducted on the synthetic database with manifold structure and many real-world databases prove the effectiveness of the proposed method. [ABSTRACT FROM AUTHOR]

Text indexing is a fundamental problem in computer science. The objective is to preprocess a text T, so that, given a pattern P, we can find all starting positions (or simply, occurrences) of P in T efficiently. In some cases, additional restrictions are imposed. We consider two variants, namely the non-overlapping indexing problem, and the range non-overlapping indexing problem. Given a text T having n characters, the non-overlapping indexing problem is defined as follows: pre-process T into a data structure, such that for any pattern P, containing |P| characters, we can report a set containing the maximum number of non-overlapping occurrences of P in T . Cohen and Porat (in: Algorithms and computation, 20th international symposium, ISAAC 2009, Honolulu, Hawaii. Proceedings, 2009) showed that by maintaining a linear space index in which the suffix tree of T is augmented with an O(n) word data structure, a query P can be answered in optimal time O (| P | + n o c c) , where nocc is the number of occurrences reported. We present the following new result. Let CSA (not necessarily a compressed suffix array) be an index of T that can compute (i) the suffix range of P in search (P) time, and (ii) a suffix array or an inverse suffix array value in t SA time. By using CSA alone, we can answer a query P in search (P) + sort (n o c c) + O (n o c c · t SA) time. The function sort (k) denotes the time for sorting k numbers in { 1 , 2 , ⋯ , n } . In the range non-overlapping indexing problem, along with the pattern P, two integers a and b, b ≥ a , are provided as input. The task is to report a set containing the maximum number of non-overlapping occurrences of P that lie within the range [a, b]. For any arbitrarily small positive constant ϵ , we present an O (n log ϵ n) word index with O (| P | + n o c c a , b) query time, where n o c c a , b is the number of occurrences reported. Our index improves upon the result of Cohen and Porat [6]. [ABSTRACT FROM AUTHOR]

One of the important non-linear data structures in Computer Science is graph. Most of the real life network, be it a road transportation network, or airlines network or a communication network etc., cannot be exactly transformed into a graph model, but into a Multigraphs model. The Multigraph is a topological generalization of the graph where multiple links (or edges/arcs) may exist between two nodes unlike in graph. The existing algorithms to extract the neutrosophic shortest path in a graph cannot be applied to a Multigraphs. In this paper a method is developed to extract the neutrosophic shortest path in a directed Multigraph and then the corresponding algorithm is designed. The classical Dijkstra's algorithm is applicable to graphs only where all the link weights are crisp, but we borrow this concept to apply to Multigraphs where the weights of the links are neutrosophic numbers (NNs). This new method may be useful in many application areas of computer science, communication networks, transportation networks, etc. in particular in those type of networks which cannot be modelled into graphs but into Multigraphs. [ABSTRACT FROM AUTHOR]

The accurate and efficient treatment of mutable data structures is one of the outstanding problem areas in automatic program verification and analysis. Shape analysis is a form of program analysis that attempts to infer descriptions of the data structures in a program, and to prove that these structures are not misused or corrupted. It is one of the more challenging and expensive forms of program analysis, due to the complexity of aliasing and the need to look arbitrarily deeply into the program heap. This article describes a method of boosting shape analyses by defining a compositional method, where each procedure is analyzed independently of its callers. The analysis algorithm uses a restricted fragment of separation logic, and assigns a collection of Hoare triples to each procedure; the triples provide an over-approximation of data structure usage. Our method brings the usual benefits of compositionality---increased potential to scale, ability to deal with incomplete programs, graceful way to deal with imprecision---to shape analysis, for the first time. [ABSTRACT FROM AUTHOR]

Partial shading condition (PSC) poses a significant challenge to solar power generation as it has a severe impact on the performance of photovoltaic (PV) systems, leading to a decrease in energy yield and reliability. Reconfiguration of PV arrays is a potential technique to deal with this challenge, however, reconfiguration techniques proposed in the past are restricted in their suitability for practical implementations in real-world installations as they are only optimal for specific shading patterns. To overcome this limitation, the article introduces a novel reconfiguration approach inspired by the circular array data structure, a commonly utilized tool in the realm of computer science. The proposed circular array transformation (CAT) technique shows great potential in mitigating the impact of partial shading (PS) and maximizing the overall power generation across a wider range of PSCs. The effectiveness of the proposed technique is validated through simulations and experimental studies conducted on a 5 × 5 PV array. Furthermore, the scalability of the proposed reconfiguration technique is verified through extensive simulations on a 9 × 9 PV array. Comparative analysis reveals that the proposed CAT rearrangement approach exhibits clear dominance and outperforms existing and recently published state-of-the-art reconfiguration methods. • A novel PV array reconfiguration strategy using circular array data structure for enhanced performance under PSCs. • A comprehensive survey of state-of-the-art reconfiguration techniques was conducted, highlighting their drawbacks. • A critical performance analysis of the proposed technique has been done. • Experimental validation were carried out to show its practical applicability. • When compared to newly proposed reconfiguration strategies, the proposed method performs superior. [ABSTRACT FROM AUTHOR]

Data structures courses commonly introduce topics involving high levels of abstraction and complexity, requiring significant effort from instructors and students to achieve positive teaching-learning outcomes. Despite the multiple studies that have occurred within the Computer Science Education (CS ED) community to understand the experiences that novice programmers may have when learning how to program, there is still a lack of exploration and research on understanding these experiences in scenarios different from firstyear Computer Science (CS) courses. Looking further from CS introductory courses, this paper presents the results of a pilot study that evaluated the interaction of a group of CS Colombian students with DStBlocks, which is a scaffolded block-based instructional technology created to ease linear data structures understanding. The findings and results of this pilot study are favorable, corresponding to tests centered on user experience and learning impact. [ABSTRACT FROM AUTHOR]

Data structure and algorithm is an important course in computer science and information technology programs, applied in almost all courses. Failure to master it will affect student's academic performance during study, getting job interviews, passing job interviews, and create an inefficient information technology worker. However, learning data structure is a worldwide problem because of its complex nature. Gameful visualization of data structures' algorithms has been gaining momentum as it resulted in increased motivation, engagement and learning outcome. But effectiveness of game-based learning could be hindered if improper learning strategies used. Instructional scaffold in game-based learning in the form of question prompts have been found to be the most effective way to scaffold self-learn in computer-based learning. Thus, a game-based learning of stack data structure using question prompts was designed, developed and tested based on an adopted model to help students understand the algorithms of stack's insert and delete operations for array implementation with gameplay that could create meaningful learning. A pre-game and post-game test was conducted to compare students' performance on the topic. Results indicated a generally positive outcome. [ABSTRACT FROM AUTHOR]

Approximate nearest neighbour (ANN) search is one of the most important problems in numerous computer science applications, including data mining, machine learning and computer vision. In this paper, we address the problem of ANN for high-dimensional binary vectors and we propose a simple yet powerful search method that is based on Random Binary Search Trees (RBST). Our method is validated on a dataset of 1.25M binary local feature descriptors obtained from a real-life image-based localisation system provided by Google as a part of Project Tango (now known as ARCore). The results of an extensive evaluation of our method performed on this dataset against the state-of-the-art ANN algorithms, such as Locality Sensitive Hashing, Uniform LSH and Multi-probe LSH, show the superiority of our method in terms of retrieval precision with a performance boost of over 20%. • Random Binary Search Trees (RBST) are a relatively simple yet powerful ANN method. • RBST give better or equal results to the competing hashing algorithms. • A powerful ANN method can be created by extending a simple data structure. • Techniques like the priority search are not needed to create a good ANN method. [ABSTRACT FROM AUTHOR]

Novelty detection is a fundamental biological problem that organisms must solve to determine whether a given stimulus departs from those previously experienced. In computer science, this problem is solved efficiently using a data structure called a Bloom filter. We found that the fruit fly olfactory circuit evolved a variant of a Bloom filter to assess the novelty of odors. Compared with a traditional Bloom filter, the fly adjusts novelty responses based on two additional features: the similarity of an odor to previously experienced odors and the time elapsed since the odor was last experienced. We elaborate and validate a framework to predict novelty responses of fruit flies to given pairs of odors. We also translate insights from the fly circuit to develop a class of distance- and time-sensitive Bloom filters that outperform prior filters when evaluated on several biological and computational datasets. Overall, our work illuminates the algorithmic basis of an important neurobiological problem and offers strategies for novelty detection in computational systems. [ABSTRACT FROM AUTHOR]