检索结果-内蒙古大学图书馆

On the Advice Complexity of Online Matching on the Line

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2024年第3期26卷

作者： Csaba, Bela Nagy-Gyorgy, Judit Univ Szeged Szeged Hungary

We consider the matching problem on the line with advice complexity. We give a 1-competitive online algorithm with advice complexity n - 1 , and show that there is no 1-competitive online algorithm reading less than n - 1 bits of advice. Moreover, for each 0 < k < n we present a c(n/k)-competitive online algorithm with advice complexity O(k(log N + log n)) where n is the number of servers, N is the distance of the minimal and maximal servers, and c(n) is the complexity of the best online algorithm without advice.

关键词： Computer Science data structures and algorithms

来源：评论

学校读者我要写书评

暂无评论

Enrich a data structures course with parallelism

Enrich a data structures course with parallelism

引用

IEEE Frontiers in Education Conference (FIE)

作者： Cheng, Qiong Univ North Carolina Charlotte Charlotte NC 28223 USA

ISBN: (纸本)9781728189611

This Research to Practice Work in Progress paper develops an adaptive learning module aimed at enriching data structures and algorithms courses (CS2/DS) with introductory parallel computing. We emphasize exploitable shared-memory parallelism with the intention of teaching students to decompose a problem or its underlying big data structure into parts that can execute effectively in many- or multi-core processes. The module can set up conditional mastery paths and differentiate assignments for individual students automatically. The adaptive learning reflects the student-directed learning by doing and so fits naturally into the conventional CS2/DS courses. We conducted a 50-minute learning session in an adaptive learning CS2/DS class for a group of 56 students in the Fall 2019 semester. The experimental results, from two surveys executed before and after the session, was successful in engaging students, instigating students' interest in parallel computing, and improving the students' awareness and appreciation. The module can be extended to support other parallel computing concepts, such as critical section, race condition, and multi-thread synchronization and cooperation techniques. As a side benefit, we would like to show that adaptive learning prepares students, gets students to engage, and enhances their performance.

关键词： adaptive learning personalized learning parallel computing parallelism data/task decomposition data structures and algorithms

来源：评论

学校读者我要写书评

暂无评论

Quantum Speedup and Mathematical Solutions of Implementing Bio-Molecular Solutions for the Independent Set Problem on IBM Quantum Computers

IEEE TRANSACTIONS ON NANOBIOSCIENCE

引用

IEEE TRANSACTIONS ON NANOBIOSCIENCE 2021年第3期20卷 354-376页

作者： Chang, Weng-Long Chen, Ju-Chin Chung, Wen-Yu Hsiao, Chun-Yuan Wong, Renata Vasilakos, Athanasios V. Natl Kaohsiung Univ Sci & Technol Dept Comp Sci & Informat Engn Kaohsiung 80778 Taiwan Nanjing Univ Dept Comp Sci & Technol Nanjing 210023 Peoples R China Univ Technol Sydney Sch Elect & Data Engn Ultimo NSW 2007 Australia Fuzhou Univ Coll Math & Comp Sci Fuzhou 350116 Peoples R China Lulea Univ Technol Dept Comp Sci Elect & Space Engn S-97187 Lulea Sweden

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.

关键词： Electron tubes DNA Computer science Quantum computing Computers Roads Urban areas data structures and algorithms independent-set problem molecular algorithms molecular computing quantum algorithms quantum computing

来源：评论

学校读者我要写书评

暂无评论

Application of Blended Learning in data structures and algorithms Course Teaching

Application of Blended Learning in Data Structures and Algor...

引用

2013教育技术与信息系统国际会议

作者： Xiaojing Liu Xiaoying Wang Rui Wang Department of Computer Technology and Application Qinghai University

data structures and algorithms course is a core foundation stone in a computer science curriculum. But there are many complicated algorithms in it. In order to help students to master the algorithms, this paper describes the use of blended learning in data structures and algorithms course teaching. This blended learning model is realized as a combination of teaching methods mixed, project-based teaching, E-learning, course experiment and design mixed, process evaluation and overall evaluation. From the obtained results with performed experimental evaluation, the realized blended learning model may provide more effective and efficient educational experience.

关键词： blended learning E-learning data structures and algorithms project-based teaching

来源：评论

学校读者我要写书评

暂无评论

Algorithm Visualization and the Elusive Modality Effect 2021

Algorithm Visualization and the Elusive Modality Effect

引用

17th Annual ACM Conference on International Computing Education Research (ICER)

作者： Zavgorodniaia, Albina Tilantera, Artturi Korhonen, Ari Seppala, Otto Hellas, Arto Sorva, Juha Aalto Univ Espoo Finland

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.

关键词： modality effect verbal redundancy effect data structures and algorithms algorithm visualization algorithm animation Dijkstra's algorithm replication

来源：评论

学校读者我要写书评

暂无评论

Building a Motivating and Autonomy Environment to Support Adaptive Learning

Building a Motivating and Autonomy Environment to Support Ad...

引用

IEEE Frontiers in Education Conference (FIE)

作者： Cheng, Qiong Benton, David Quinn, Andrew Univ North Carolina Charlotte Charlotte NC 28223 USA

ISBN: (纸本)9781665438513

This Innovative Practice Full paper presents an effort on fostering student motivation and autonomy in support of adaptive learning. Higher education has been transformed by digital technology to be more interactive, self-paced, and adaptive to students. But this technology presupposes that students possess autonomy and are innately well motivated. Unfortunately, many students entering college lack motivation and self-control. These dispositions retard self-paced adaptive learning and limit the effectiveness of imparting improved adaptability in this technology. Taking inspiration from the self-determination theory, we investigated, in the context of adaptive learning, the importance of nurturing student autonomy and enhancing student situated motivation. In this paper, we present our experiential study in a gateway core course of computer science, in which adaptive preparation and learning pedagogy has been adopted for four semesters, one semester without motivating support and others with this support. By comparing and analyzing student engagement and performance over these four semesters, we observe that nurturing student autonomy and enhancing motivation are critical factors in maximizing the effectiveness of adaptive learning.

关键词： data structures and algorithms growth mindset self-determination theory adaptive learning active learning

来源：评论

学校读者我要写书评

暂无评论

Differentiated Assessments for Advanced Courses that Reveal Issues with Prerequisite Skills: A Design Investigation 20

Differentiated Assessments for Advanced Courses that Reveal ...

引用

25th Annual Conference on Working Group Reports on Innovation and Technology in Computer Science Education (ITiCSE-WGR)

作者： Nelson, Greg L. Stromback, Filip Korhonen, Ari Begum, Marjahan Blamey, Ben Jin, Karen H. Lonati, Violetta MacKellar, Bonnie Monga, Mattia Univ Washington Paul G Allen Sch Comp Sci & Engn Seattle WA 98195 USA Linkoping Univ Dept Comp & Informat Sci Linkoping Sweden Aalto Univ Dept Comp Sci Espoo Finland Copenhagen Business Sch Dept Management Soc & Commun Copenhagen Denmark Uppsala Univ Dept Informat Technol Uppsala Sweden Univ New Hampshire Dept Appl Engn & Sci Manchester NH USA Univ Milan Dept Comp Sci Lab CINI Informat & Scuola Milan Italy St Johns Univ Div Comp Sci Math & Sci Queens NY USA

ISBN: (纸本)9781450382939

Computing learners may not master basic concepts, or forget them between courses or from infrequent use. Learners also often struggle with advanced computing courses, perhaps from weakness with prerequisite concepts. One underlying challenge for researchers and instructors is determining the reason why a learner gets an advanced question wrong. Was the wrong answer because the learner lacked prerequisite skills, has not mastered the advanced skill, or some combination of the two? We contribute a design investigation into how to create differentiated questions which diagnose prerequisite and advanced skills at the same time. We focused on tracing and related skills as prerequisites, and on advanced object-oriented programming, concurrency, algorithm and data structures as the advanced skills. We conducted an inductive qualitative analysis of existing assessment questions from instructors and from a concept inventory with a validity argument (the Basic data structures Inventory). We found dependencies on a variety of prerequisite knowledge and mixed potential for diagnosing difficulties with prerequisites. Inspired by this analysis, we developed examples of differentiated assessments and reflected on design principles for creating/modifying assessments to better assess both advanced and prerequisite skills. Our example differentiated assessment questions and methods help enable research into how prerequisites skills affect learning of advanced concepts. They also may help instructors better understand and help learners with varying prerequisite knowledge, which may improve equity of learning outcomes. Our work also raises theoretical questions about what assessments really assess and how separate advanced topics and prerequisite skills are.

关键词： computer science education assessment prerequisite skills concurrency data structures and algorithms advanced object-oriented programming tracing educational design research differentiated assessment

来源：评论

学校读者我要写书评

暂无评论

2D Generalization of Fractional Cascading on Axis-aligned Planar Subdivisions 61

2D Generalization of Fractional Cascading on Axis-aligned Pl...

引用

61st IEEE Annual Symposium on Foundations of Computer Science (FOCS)

作者： Afshani, Peyman Cheng, Pingan Aarhus Univ Dept Comp Sci Aarhus Denmark

ISBN: (纸本)9781728196213

Fractional cascading is one of the influential and important techniques in data structures, as it provides a general framework for solving a common important problem: the iterative search problem. In the problem, the input is a graph G with constant degree. Also as input, we are given a set of values for every vertex of G. The goal is to preprocess G such that when we are given a query value q, and a connected subgraph pi of G, we can find the predecessor of q in all the sets associated with the vertices of pi. The fundamental result of fractional cascading, by Chazelle and Guibas, is that there exists a data structure that uses linear space and it can answer queries in O(log n + vertical bar pi vertical bar) time, at essentially constant time per predecessor [15]. While this technique has received plenty of attention in the past decades, an almost quadratic space lower bound for "two-dimensional fractional cascading" by Chazelle and Liu in STOC 2001 [17] has convinced the researchers that fractional cascading is fundamentally a one-dimensional technique. In two-dimensional fractional cascading, the input includes a planar subdivision for every vertex of G and the query is a point q and a subgraph pi and the goal is to locate the cell containing q in all the subdivisions associated with the vertices of pi. In this paper, we show that it is actually possible to circumvent the lower bound of Chazelle and Liu for axis-aligned planar subdivisions. We present a number of upper and lower bounds which reveal that in two-dimensions, the problem has a much richer structure. When G is a tree and pi is a path, then queries can be answered in O (log n + vertical bar pi vertical bar + min{vertical bar pi vertical bar root log n;alpha(n) root vertical bar pi vertical bar log n}) time using linear space where alpha is an inverse Ackermann function;surprisingly, we show both branches of this bound are tight, up to the inverse Ackermann factor. When G is a general graph or when pi i

关键词： Fractional Cascading Computational Geometry data structures and algorithms

来源：评论

学校读者我要写书评

暂无评论

Assessing How Pre-requisite Skills Affect Learning of Advanced Concepts 20

Assessing How Pre-requisite Skills Affect Learning of Advanc...

引用

25th Conference on Innovation and Technology in Computer Science Education

作者： Nelson, Greg L. Stromback, Filip Korhonen, Ari Albluwi, Ibrahim Begum, Marjahan Blamey, Ben Jin, Karen H. Lonati, Violetta MacKellar, Bonnie Monga, Mattia Univ Washington Seattle WA 98195 USA Linkoping Univ Linkoping Sweden Aalto Univ Espoo Finland Princeton Univ Princeton NJ 08544 USA Copenhagen Business Sch Copenhagen Denmark Uppsala Univ Uppsala Sweden Univ New Hampshire Manchester NH USA Univ Milan Milan Italy St Johns Univ Queens NY USA

ISBN: (纸本)9781450368742

Students often struggle with advanced computing courses, and comparatively few studies have looked into the reasons for this. It seems that learners do not master the most basic concepts, or forget them between courses. If so, remedial practice could improve learning, but instructors rightly will not use scarce time for this without strong evidence. Based on personal observation, program tracing seems to be an important pre-requisite skill, but there is yet little research that provides evidence for this observation. To investigate this, our group will create theory-based assessments on how tracing knowledge affects learning of advanced topics, such as data structures, algorithms, and concurrency. This working group will identify relevant concepts in advanced courses, then conceptually analyze their pre-requisites and where an imagined student with some tracing difficultieswould encounter barriers. The group will use this theory to create instructor-usable assessments for advanced topics that also identify issues caused by poor pre-requisite knowledge. These assessments may then be used at the start and end of advanced courses to evaluate to what extent students' difficulties with the advanced course originate from poor pre-requisite knowledge.

关键词： computer science education concurrency data structures and algorithms tracing

来源：评论

学校读者我要写书评

暂无评论

Encouraging Reflection in Support of Learning data structures 19

Encouraging Reflection in Support of Learning Data Structure...

引用

Proceedings of the 50th ACM Technical Symposium on Computer Science Education

作者： Cheryl Resch Christina Gardner-McCune University of Florida Gainesville FL USA

ISBN: (纸本)9781450358903

Encouraging Reflection in Support of Learning data structures 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

关键词： problem solving data structures and algorithms keywords: reflection

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：