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

5th International Symposium on IT in Medicine and Education, ITME 2013

作者： Zheng, Yunping Sarem, Mudar School of Computer Science and Engineering South China University of Technology 510006 Guangzhou China School of Software Engineering Huazhong University of Science and Technology 430074 Wuhan China

ISBN: (纸本)9789400776173

The ACM/ICPC (ACM International Collegiate Programming Contest) is famous as the world's largest and highest level of international collegiate programming contest. In this paper, by considering some problems of the traditional teaching mode of the "design and analysis of algorithms" (which is abbreviated as "algorithms"), we propose a new ACM/ICPC-based teaching reform mode of the "algorithms". Some principles and characteristics of the exercises based on the ACM/ICPC are presented. And, some merits and features of our reform mode are analyzed. Also, by giving the shortcomings of the ACM online judging system, the corresponding reason and the solving strategy are presented. The ACM/ICPC-based teaching reform mode of the "algorithms" cultivates the students' interest in participating in the ACM/ICPC, greatly improves the initiative and enthusiasm to learn "algorithms", and strengthens cultivation of the team spirit and creative ability. Our proposed reform mode improves the teaching quality, which achieves the obvious effect. Also, our mode was highly praised and generally welcomed by students. Therefore, it has some demonstrated functions for teaching reform of the "algorithms". © Springer Science+Business Media Dordrecht 2014.

关键词： ACM design and analysis of algorithms ICPC Teaching reform and exploration Traditional teaching mode

来源：评论

学校读者我要写书评

暂无评论

Dynamic Convex Hulls for Simple Paths

引用

DISCRETE & COMPUTATIONAL GEOMETRY 2025年 1-36页

作者： Brewer, Bruce Brodal, Gerth Stolting Wang, Haitao Univ Utah Kahlert Sch Comp Salt Lake City UT 84112 USA Aarhus Univ Dept Comp Sci Aabogade 34 DK-8200 Aarhus N Denmark

We consider the planar dynamic convex hull problem. In the literature, solutions exist supporting the insertion and deletion of points in poly-logarithmic time and various queries on the convex hull of the current set of points in logarithmic time. If arbitrary insertion and deletion of points are allowed, constant time updates and fast queries are known to be impossible. This paper considers two restricted cases where worst-case constant time updates and logarithmic time queries are possible. We assume all updates are performed on a deque (double-ended queue) of points. The first case considers the monotonic path case, where all points are sorted in a given direction, say horizontally left-to-right, and only the leftmost and rightmost points can be inserted and deleted. The second case assumes that the points in the deque constitute a simple path. Note that the monotone case is a special case of the simple path case. For both cases, we present solutions supporting deque insertions and deletions in worst-case constant time and standard queries on the convex hull of the points in O(logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(\log n)$$\end{document} time, where n is the number of points in the current point set. The convex hull of the current point set can be reported in O(h+logn)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(h+\log n)$$\end{document} time, where h is the number of edges of the convex hull. For the one-sided monotone path case, where updates are only allowed on one side, the reporting time can be reduced to O(h), and queries on the convex hull are supported in O(logh)\documentclas

关键词： Dynamic convex hull Convex hull queries Simple paths Path updates Deque Theory of computation Computational geometry design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Overlap matching

引用

INFORMATION AND COMPUTATION 2003年第1期181卷 57-74页

作者： Amir, A Cole, R Hariharan, R Lewenstein, M Porat, E IBM Corp Thomas J Watson Res Ctr Yorktown Hts NY 10598 USA Bar Ilan Univ Dept Comp Sci IL-52900 Ramat Gan Israel Georgia Tech Coll Comp Atlanta GA 30332 USA NYU Courant Inst Math Sci Dept Comp Sci New York NY 10012 USA Indian Inst Sci CSA Dept Bangalore 560012 Karnataka India

We propose a new paradigm for string matching, namely structural matching. In structural matching, the text and pattern contents are not important. Rather, some areas in the text and pattern, such as intervals, are singled out. A "match" is a text location where a specified relation between the text and pattern areas is satisfied. In particular we define the structural matching problem of overlap (parity) matching. We seek the text locations where all overlaps of the given pattern and text intervals have even length. We show that this problem can be solved in time O(n log m), where the text length is n and the pattern length is m. As an application of overlap matching, we show how to reduce the string matching with swaps problem to the overlap matching problem. The string matching with swaps problem is the problem of string matching in the presence of local swaps. The best deterministic upper bound known for this problem was O(nm(1/3) log m log sigma) for a general alphabet Sigma, where sigma = min(m, \Sigma\). Our reduction provides a solution to the pattern matching with swaps problem in time 0 (n log m log a). (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： design and analysis of algorithms combinatorial algorithms on words pattern matching pattern matching with swaps non-standard pattern matching

来源：评论

学校读者我要写书评

暂无评论

The weight-constrained maximum-density subtree problem and related problems in trees

引用

JOURNAL OF SUPERCOMPUTING 2010年第3期54卷 366-380页

作者： Hsieh, Sun-Yuan Chou, Ting-Yu Natl Cheng Kung Univ Dept Comp Sci & Informat Engn Tainan 701 Taiwan

Given a tree T = (V, E) of n nodes such that each node v is associated with a value-weight pair (val(v), w(v)), where value val(v) is a real number and weight w(v) is a non-negative integer, the density of T is defined as Sigma(v is an element of V) val(v)/Sigma(v is an element of V) w(v). A subtree of T is a connected subgraph (V', E') of T, where V' subset of V and E' subset of E. Given two integers w(min) and w(max), the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T' = (V', E') satisfying w(min) <= Sigma(v is an element of V')w(v) <= W-max. In this paper, we first present an O(w(max)n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O (w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S subset of V, we also present an O(w(max)(2)n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.

关键词： design and analysis of algorithms Maximum-density paths Maximum-density Steiner trees Maximum-density subtrees NP-completeness Pseudo-polynomial time algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimal semi-online algorithms for machine covering

引用

THEORETICAL COMPUTER SCIENCE 2007年第1期372卷 69-80页

作者： Tan, Zhiyi Wu, Yong Zhejiang Univ Dept Math State Key Lab CAD&CG Hangzhou 310027 Peoples R China

This paper investigates the semi-online machine covering problems on m >= 3 parallel identical machines. Three different semi-online versions are studied and optimal algorithms are proposed. We prove that if the total processing time of all jobs or the largest processing time of all jobs is known in advance, the competitive ratios of the optimal algorithms are both m - 1. If the total processing time and the largest processing time of all jobs are both known in advance, the competitive ratios of the optimal algorithms are 3 when m = 3, and m - 2 when m >= 4. (c) 2006 Elsevier B.V. All rights reserved.

关键词： scheduling design and analysis of algorithms semi-online competitive ratio

来源：评论

学校读者我要写书评

暂无评论

On efficient algorithms for bottleneck path problems with many sources

引用

OPTIMIZATION LETTERS 2024年第5期18卷 1273-1283页

作者： Kaymakov, Kirill V. Malyshev, Dmitry S. Coleman Tech LLC 40 Mira Ave Moscow 129090 Russia Natl Res Univ Higher Sch Econ Lab Algorithms & Technol Networks Anal 136 Rodionova Str Nizhnii Novgorod 603093 Russia

For given edge-capacitated connected graph and two its vertices s and t, the bottleneck (or maxmin\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\max \min $$\end{document}) path problem is to find the maximum value of path-minimum edge capacities among all paths, connecting s and t. It can be generalized by finding the bottleneck values between s and all possible t. These problems arise as subproblems in the known maximum flow problem, having applications in many real-life tasks. For any graph with n vertices and m edges, they can be solved in O(m) and O(t(m, n)) times, respectively, where t(m,n)=min(m+nlog(n),m alpha(m,n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$t(m,n)=\min (m+n\log (n),m\alpha (m,n))$$\end{document} and alpha(center dot,center dot)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha (\cdot ,\cdot )$$\end{document} is the inverse Ackermann function. In this paper, we generalize of the bottleneck path problems by considering their versions with k sources. For the first of them, where k pairs of sources and targets are (offline or online) given, we present an O((m+k)log(n))\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O((m+k)\log (n))$$\end{document}-time randomized and an O(m+(n+k)log(n))\documentclass[12pt]{minimal} \usepa

关键词： design and analysis of algorithms Computational complexity Bottleneck path problem

来源：评论

学校读者我要写书评

暂无评论

Real Two Dimensional Scaled Matching

引用

ALGORITHMICA 2009年第3期53卷 314-336页

作者： Amir, Amihood Butman, Ayelet Lewenstein, Moshe Porat, Ely Bar Ilan Univ Ramat Gan Israel Johns Hopkins Univ Baltimore MD USA Holon Acad Inst Technol Holon Israel

Scaled Matching refers to the problem of finding all locations in the text where the pattern, proportionally enlarged according to an arbitrary real-sized scale, appears. Scaled matching is an important problem that was originally inspired by Computer Vision. Finding a combinatorial definition that captures the concept of real scaling in discrete images has been a challenge in the pattern matching field. No definition existed that captured the concept of real scaling in discrete images, without assuming an underlying continuous signal, as done in the image processing field. We present a combinatorial definition for real scaled matching that scales images in a pleasing natural manner. We also present efficient algorithms for real scaled matching. The running times of our algorithms are as follows. For T, a two-dimensional nxn text array, and P, an mxm pattern array, we find in T all occurrences of P scaled to any real value in time O(nm (3)+n (2) mlog m).

关键词： design and analysis of algorithms Combinatorial algorithms on words Pattern matching Scaled pattern matching Approximate pattern matching Generalized pattern matching

来源：评论

学校读者我要写书评

暂无评论

Scheduling orders for multiple product types to minimize total weighted completion time

引用

DISCRETE APPLIED MATHEMATICS 2007年第8期155卷 945-970页

作者： Leung, Joseph Y. -T. Li, Haibing Pinedo, Michael New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA NYU Stern Sch Business New York NY 10012 USA

We consider the problem of scheduling orders for multiple different product types in an environment with in dedicated machines in parallel. The objective is to minimize the total weighted completion time. Each product type is produced by one and only one of the in dedicated machines;that is, each machine is dedicated to a specific product type. Each order has a weight and may also have a release date. Each order asks for certain amounts of various different product types. The different products for an order can be produced concurrently. Preemptions are not allowed. Even when all orders are available at time 0, the problem has been shown to be strongly NP-hard for any fixed number ( >= 2) of machines. This paper focuses on the design and analysis of efficient heuristics for the case without release dates. Occasionally, however, we extend our results to the case with release dates. The heuristics considered include some that have already been proposed in the literature as well as several new ones. They include various static and dynamic priority rules as well as two more sophisticated LP-based algorithms. We analyze the performance bounds of the priority rules and of the algorithms and present also an in-depth comparative analysis of the various rules and algorithms. The conclusions from this empirical analysis provide insights into the trade-offs with regard to solution quality, speed, and memory space. (C) 2006 Elsevier B.V. All rights reserved.

关键词： order scheduling approximation algorithms design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Algorithm for Identifying the Maximum Detour Hinge Vertices of a Permutation Graph

引用

IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES 2015年第6期E98A卷 1161-1167页

作者： Honma, Hirotoshi Nakajima, Yoko Igarashi, Yuta Masuyama, Shigeru Kushiro Coll Natl Inst Technol Dept Informat Engn Kushiro Hokkaido 0840916 Japan Kushiro Natl Coll Technol Elect Informat Syst Engn Course Kushiro Hokkaido 0840916 Japan Toyohashi Univ Technol Dept Comp Sci & Engn Toyohashi Aichi 4418580 Japan

A hinge vertex is a vertex in an undirected graph such that there exist two vertices whose removal makes the distance between them longer than before. Identifying hinge vertices in a graph can help detect critical nodes in communication network systems, which is useful for making them more stable. For finding them, an Omicron(n(3)) time algorithm was developed for a simple graph, and, linear time algorithms were developed for interval and permutation graphs, respectively. Recently, the maximum detour hinge vertex problem is defined by Honma et al. For a hinge vertex u in a graph, the detour degree of u is the largest value of distance between any pair of x and y (x and y are adjacent to u) by removing u. A hinge vertex with the largest detour degree in G is defined as the maximum detour hinge vertex of G. This problem is motivated by practical applications, such as network stabilization with a limited cost, i.e., by enhancing the reliability of the maximum detour hinge vertex, the stability of the network is much improved. We previously developed an Omicron(n(2)) time algorithm for solving this problem on an interval graph. In this study, we propose an algorithm that identifies the maximum detour hinge vertex on a permutation graph in Omicron(n(2)) time, where n is the number of vertices in the graph.

关键词： design and analysis of algorithms intersection graphs maximum detour hinge vertex problem permutation graph

来源：评论

学校读者我要写书评

暂无评论

On the algorithmic aspects of discrete and lexicographic Helly-type theorems and the discrete LP-type model

引用

SIAM JOURNAL ON COMPUTING 2008年第1期38卷 1-45页

作者： Halman, Nir MIT Dept Civil & Environm Engn Cambridge MA 02139 USA

Helly's theorem says that, if every d+1 elements of a given finite set of convex objects in R-d have a common point, there is a point common to all of the objects in the set. In discrete Helly theorems the common point should belong to an a priori given set. In lexicographic Helly theorems the common point should not be lexicographically greater than a given point. Using discrete and lexicographic Helly theorems we get linear time solutions for various optimization problems. For this, we introduce the DLP-type (discrete linear programming-type) model, and provide new algorithms that solve in randomized linear time fixed-dimensional DLP-type problems. For variable-dimensional DLP-type problems, our algorithms run in time subexponential in the combinatorial dimension. Finally, we use our results in order to solve in randomized linear time problems such as the discrete p-center on the real line, the discrete weighted 1-center problem in R-d with either l(1) or l(infinity) norm, the standard (continuous) problem of finding a line transversal for a totally separable set of planar convex objects, a discrete version of the problem of finding a line transversal for a set of axis-parallel planar rectangles, and the (planar) lexicographic rectilinear p-center problem for p = 1, 2, 3. These are the first known linear time algorithms for these problems. Moreover, we use our algorithms to solve in randomized subexponential time various problems in game theory, improving upon the best known algorithms for these problems.

关键词： Helly-type theorems LP-type model design and analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：