The OpenDSA Project seeks to provide complete instructional materials for data structures and algorithms (DSA) courses. Our vision for a highly interactive eTextbook involves the use of many algorithm visualizations (...
详细信息
The OpenDSA Project seeks to provide complete instructional materials for data structures and algorithms (DSA) courses. Our vision for a highly interactive eTextbook involves the use of many algorithm visualizations (AVs) and a wide range of interactive exercises with automated assessment. To realize this vision we require a mix of third-party and custom software components that make up a client/server-based web application. The massive amount content development required compels us to adopt an appropriate mix of open-source practices that will encourage broad contribution to the project. In this paper we describe the OpenDSA system architecture and the design goals that led to the present version of the system. (C) 2013 Elsevier B.V. All rights reserved.
In this paper, we propose a bio-molecular algorithm with O(n(2)) biological operations, O(2(n-1)) DNA strands, O(n) tubes and the longest DNA strand, O(n), for inferring the value of a bit from the only output satisfy...
详细信息
In this paper, we propose a bio-molecular algorithm with O(n(2)) biological operations, O(2(n-1)) DNA strands, O(n) tubes and the longest DNA strand, O(n), for inferring the value of a bit from the only output satisfying any given condition in an unsorted database with 2(n) items of n bits. We show that the value of each bit of the outcome is determined by executing our bio-molecular algorithm n times. Then, we show how to view a bio-molecular solution space with 2(n-1 )DNA strands as an eigenvector and how to find the corresponding unitary operator and eigenvalues for inferring the value of a bit in the output. We also show that using an extension of the quantum phase estimation and quantum counting algorithms computes its unitary operator and eigenvalues from bio-molecularsolution space with 2(n-1 )DNA strands. Next, we demonstratethat the value of each bit of the output solution can be determined by executing the proposed extended quantum algorithms n times. To verify our theorem, we find the maximum-sized clique to a graph with two vertices and one edge and the solution b that satisfies b(2) 1 (mod 15) and 1 < b < (15/2) using IBM Quantum's backend.
Here we describe the equational theorem prover Barcelona, in its version that participated in the CADE-13 ATP System Competition. The system was built on top of our toolkit of data structures and algorithms for automa...
详细信息
Here we describe the equational theorem prover Barcelona, in its version that participated in the CADE-13 ATP System Competition. The system was built on top of our toolkit of data structures and algorithms for automated deduction in first-order logic with equality and was devised mainly to test the performance of this toolkit.
Proposed is a new algorithmic approach to segmentation-based image coding. A good compromise is achieve between segmentations by quadtree-based decomposition and by free region-growing in terms of time complexity and ...
详细信息
Proposed is a new algorithmic approach to segmentation-based image coding. A good compromise is achieve between segmentations by quadtree-based decomposition and by free region-growing in terms of time complexity and scene adaptability. Encoding is to recursively partition an image into convex n-gons, 3 less-than-or-equal-to n less-than-or-equal-to 8, until the pixels in current n-gon satisfy a uniformity criterion. The recursive partition generates a valid segmentation by aligning the polygon boundaries with image edges. This segmentation is embedded into a binary tree for compact encoding of its geometry. The compressed image is sent as a labeled pointerless binary tree, and decoding is simply polygon filling. High-compression ratios are obtained by balancing the accuracy and geometric complexity of the image segmentation;a key issue for segmentation-based image coding that was not addressed before. Due to its tree structure, the new method is also suitable for progressive image coding.
Massive data streams are now fundamental to many data processing applications. For example, Internet routers produce large scale diagnostic data streams. Such streams are rarely stored in traditional databases and ins...
详细信息
Massive data streams are now fundamental to many data processing applications. For example, Internet routers produce large scale diagnostic data streams. Such streams are rarely stored in traditional databases and instead must be processed "on the fly" as they are produced. Similarly, sensor networks produce multiple data streams of observations from their sensors. There is growing focus on manipulating data streams and, hence, there is a need to identify basic operations of interest in managing data streams, and to support them efficiently. We propose computation of the Hamming norm as a basic operation of interest. The Hamming norm formalizes ideas that are used throughout data processing. When applied to a single stream, the Hamming norm gives the number of distinct items that are present in that data stream, which is a statistic of great interest in databases. When applied to a pair of streams, the Hamming norm gives an important measure of (dis)similarity: the number of unequal item counts in the two streams. Hamming norms have many uses in comparing data streams. We present a novel approximation technique for estimating the Hamming norm for massive data streams;this relies on what we call the "l(0) sketch" and we prove its accuracy. We test our approximation method on a large quantity of synthetic and real stream data, and show that the estimation is accurate to within a few percentage points.
Encouraging Reflection in Support of Learning datastructures Cheryl Resch, University of Florida Christina Gardner-McCune, University of Florida Contact: [email protected] Our research looks at using reflection in te...
详细信息
ISBN:
(纸本)9781450358903
Encouraging Reflection in Support of Learning datastructures Cheryl Resch, University of Florida Christina Gardner-McCune, University of Florida Contact: [email protected] Our research looks at using reflection in teaching data structures and algorithms (DSA) to promote meaningful learning. This poster examines the differences in reflections produced by two different programming assignments in DSA at the University of Florida. In the first assignment, students were asked to implement a line editor using a linked list and in the reflection prompt students were asked to reflect on the use of the assigned data structure and what they would do differently if they could do the assignment again. In this assignment, the dominant reflection was a simple recounting of material taught in class. In 15% of the reflections, students identified an implementation improvement that could be used. In 25% of the reflections, students identified non-technical issues such as time management when reflecting on what they would do differently if they had to do the assignment again. In the second assignment, students were asked to code Google's page-rank algorithm and were allowed to choose a graph implementation. They were asked to reflect on their implementation and what they would do differently if they could do the assignment again. In this assignment, the dominant reflection, ?%, was about the appropriateness of the chosen graph implementation compared to other implementations. In their reflection on what they would do differently, only 12% of the reflections mentioned non-technical issues. This data suggests that giving students an opportunity to decide the implementation approach and providing more specific reflection prompts produces more technical reflections. DOI: HTTPS://***/10.1145/3287324.3293802
Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C-Q...
详细信息
Given two finite partially ordered sets P and Q, we say that P is a chain minor of Q if there exists a partial function f from the elements of Q to the elements of P such that for every chain in P there is a chain C-Q in Q with the property that f restricted to C-Q is an isomorphism of chains C and C-Q. We give an algorithm to decide whether a partially ordered set P is a chain minor of a partially ordered set Q, which runs in time O(|Q| log |Q|) for every fixed partially ordered set P. This solves an open problem from the monograph by Downey and Fellows (Parameterized complexity. Springer, New York, 1999) who asked whether the problem was fixed parameter tractable.
In this paper, we propose a bio-molecular algorithm with O(n(2) + m) biological operations, O(2(n)) DNA strands, O(n) tubes and the longest DNA strand, O(n), for solving the independent-set problem for any graph G wit...
详细信息
In this paper, we propose a bio-molecular algorithm with O(n(2) + m) biological operations, O(2(n)) DNA strands, O(n) tubes and the longest DNA strand, O(n), for solving the independent-set problem for any graph G with m edges and n vertices. Next, we show that a new kind of the straightforward Boolean circuit yielded from the bio-molecular solutions with m NAND gates, (m+n x(n + 1)) AND gates and ((n x (n + 1))/2) NOT gates can find the maximal independent-set(s)to the independent-set problem for any graph G with m edges and n vertices. We show that a new kind of the proposed quantum-molecular algorithm can find the maximal independent set(s) with the lower bound Omega(2(n/2)) queries and the upper bound O(2(n/2)) queries. This work offers an obvious evidence for that to solve the independent-set problem in any graph G with m edges and n vertices, bio-molecular computers are able to generate a new kind of the straightforward Boolean circuit such that by means of implementing it quantum computers can give a quadratic speed-up. This work also offers one obvious evidence that quantum computers can significantly accelerate the speed and enhance the scalability of bio-molecular computers. Next, the element distinctness problem with input of n bits is to determine whether the given 2(n) real numbers are distinct or not. The quantum lower bound of solving the element distinctness problem is Omega(2(nx(2/3))) queries in the case of a quantum walk algorithm. We further show that the proposed quantum-molecular algorithm reduces the quantum lower bound to Omega((2(n/2))/(2(1/2))) queries. Furthermore, to justify the feasibility of the proposed quantum-molecular algorithm, we successfully solve a typical independent set problem for a graph G with two vertices and one edge by carrying out experiments on the backend ibmqx4 with five quantum bits and the backend simulator with 32 quantum bits on IBM's quantum computer.
In this paper, we study the relationship between the use of "crib sheets" or "cheat sheets" and performance on in-class exams. Our extensive survey of the existing literature shows that it is not d...
详细信息
In this paper, we study the relationship between the use of "crib sheets" or "cheat sheets" and performance on in-class exams. Our extensive survey of the existing literature shows that it is not decisive on the questions of when or whether crib sheets actually help students to either perform better on an exam or better learn the material. We report on our own detailed analysis for a body of crib sheets created for the final exam in a junior-level data structures and algorithms course. We wanted to determine whether there is any feature of the crib sheets that correlates to good exam scores. Exam performance was compared against a number of potential indicators for quality in a crib sheet. We have found that students performed significantly better on questions at the comprehension level of Bloom's taxonomy when their crib sheet contained good information on the topic, while performance on questions at higher levels of the taxonomy did not show correlation to crib sheet contents. We have also seen that students at certain levels of performance on the final exam (specifically, medium-to-high performance) did relatively better on certain questions than other students at that performance level when they had good coverage of that question's topic on their crib sheet.
The modality effect in multimedia learning suggests that pictures are best accompanied by audio explanations rather than text, but this finding has not been replicated in computing education. We investigate which inst...
详细信息
ISBN:
(纸本)9781450383264
The modality effect in multimedia learning suggests that pictures are best accompanied by audio explanations rather than text, but this finding has not been replicated in computing education. We investigate which instructional modality works best as an accompaniment for algorithm visualizations. In a randomized controlled trial, learners were split into three conditions who viewed an instructional video on Dijkstra's algorithm, with diagrams accompanied by audio, text, or both. We find neither a modality effect in favor of the audio condition nor a verbal redundancy effect in favor of using only a single modality rather than both. Taken together with earlier research, our findings suggest that the modality effect is difficult to apply reliably and computing educators should not rush to integrate audio into visualizations in expectation of the effect. We discuss theoretical viewpoints that future research should attend to;these include alternative part-explanations of the modality effect and attention-based models of working memory, among others.
暂无评论