Page
%P
-
Chapter and Conference Paper
On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
In the disjoint path allocation problem, we consider a path of L + 1 vertices, representing the nodes in a communication network. Requests for an unbounded-time communication between pairs of vertices arrive in a...
-
Book
-
Chapter
Introduction
At the beginning of this chapter, we define the concepts “metaphor” and “analogy” and we discuss their use as a teaching tool—both in general education and in computer science, in particular. We give an overvi...
-
Chapter
Strings and Sequences
In the last main chapter we deal with algorithms on strings and sequences. In the first section we consider two elementary data structures: the stack and the queue. We discuss the abundance of flawed metaphors...
-
Chapter
Computational Geometry
The second main chapter of this book is dedicated to problems from the area of computational geometry. We consider four different problems. First, we discuss the well-known use of the rubber band metaphor to f...
-
Chapter
Graph Algorithms
The first of the three main chapters of this book deals with two graph algorithms. First, we consider the single-source shortest path problem. For this problem, we present our original twist on the balls-and-s...
-
Chapter and Conference Paper
Advice Complexity of Online Coloring for Paths
In online graph coloring a graph is revealed to an online algorithm one vertex at a time, and the algorithm must color the vertices as they appear. This paper starts to investigate the advice complexity of thi...
-
Chapter and Conference Paper
Didactic Games for Teaching Information Theory
We developed a set of didactic games and activities that can be used to illustrate and teach various concepts from Information Theory. For each of the games and activities we list the topics it covers, give it...
-
Chapter and Conference Paper
Computational Complexity of Two-Dimensional Platform Games
We analyze the computational complexity of various two-dimensional platform games. We state and prove several meta-theorems that identify a class of these games for which the set of solvable levels is NP-hard,...
-
Chapter and Conference Paper
The Difficulty of Programming Contests Increases
In this paper we give a detailed quantitative and qualitative analysis of the difficulty of programming contests in past years. We analyze task topics in past competition tasks, and also analyze an entire prob...
-
Chapter and Conference Paper
Online Bandwidth Allocation
The paper investigates a version of the resource allocation problem arising in the wireless networking, namely in the OVSF code reallocation process. In this setting a complete binary tree of a given height n is ...
-
Chapter and Conference Paper
Approximating Rational Numbers by Fractions
In this paper we show a polynomial-time algorithm to find the best rational approximation of a given rational number within a given interval. As a special case, we show how to find the best rational number tha...
