Tagged Questions

Questions requesting papers in the literature on specific, narrow issues.

learn more… | top users | synonyms

0
votes
0answers
4 views

Hierarchical reinforcement learning exploration methods

One of the extensions to hierarchical reinforcement learning is change the degree of randomness that is applied while choosing an action. It is possible to increase the randomness to encourage ...
0
votes
0answers
8 views

Reference for Motivation of WSN Localization in 3D

I need references to motivate the reader about 3D Wireless Sensor Network Localization problem. I have found many references about 2D WSN localization, however, there is a lack of 3D WSN Localization ...
0
votes
0answers
9 views

Advance computer networks [on hold]

There are some topics I am unable to find on internet and in the below mentioned three books(Which are my course Reference books) B.A. Forouzan, Data Communications and Networking, McGraw Hill. A.S. ...
1
vote
1answer
65 views

Algorithms online problems

I'm trying in vain to find some online (classical) algorithms problems to deeply exercise "complexity" and maybe see (even try) mathematical demonstrations. As far as I can see, the sites that I ...
0
votes
0answers
13 views

Proving corectness of imperative program [closed]

I would like to ask for some recommendation on books covering topic of proving imperative program correctness. Since I am studying on my own It would be ideal if it has exercises best with answers or ...
2
votes
2answers
44 views

Is single-source single-destination shortest path problem easier than its single-source all-destination counterpart?

Dijkstra's algorithm (wiki) and Bellman-Ford (wiki) algorithm are two typical algorithms for the single-source shortest path problem. Both of them compute distances for all nodes from source $s$. ...
0
votes
0answers
49 views

Logic and Functional programming

I have a subject Introduction to logic and functional programming but the course is not provided in detail. This is the provided course. Introduction to declarative programming paradigms. The ...
3
votes
1answer
43 views

Where does the terminology of open addressing resp. closed hashing come from?

One of the basic methods of hashing is called "Open addressing, or closed hashing" according to wikipadia (and several books). Why the names "open" and "closed", and why these seemingly contradictory ...
1
vote
0answers
35 views

References for wearable e-health systems for biosignal based health monitoring [closed]

Ubiquitous computing refers to "information technology and computer power, which in principle pervade all everyday objects" (see Friedewald and Raabe, 2010). A similar form is wearable computing, ...
2
votes
1answer
75 views

Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary ...
1
vote
1answer
22 views

Semantic information collections on the web. (Semantic Wikipedia)

There are lots of technologies supporting semantic information markup even as wiki software. I am wondering if there is any kind of broad information collection project like Wikipedia which features ...
2
votes
1answer
52 views

What is the lower bound for finding the third largest in a set of $n$ elements?

The problem is easy to describe: What is the lower bound for finding the third largest in a set of $n$ elements? Particularly, do we have to know both the largest and the second largest for ...
1
vote
0answers
17 views

A reference for pseudocode for Monge-Elkan algorithm?

Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm or a single class Java/C implementation? I have access to original two papers, but they do not show the ...
0
votes
1answer
43 views

Reference request for coding Knight's Tour

Could someone give an easily accessible reference containing an algorithm that could be conveniently implemented into a code for computing Knight's Tour (preferably also with fairly good efficiency)?
0
votes
0answers
22 views

Patent-free algorithm for labeling a MRF/CRF

At the moment I'm implementing a video segmentation algorithm for moved foreground / background. In the literature often a graph-cut algorithm is used, which is patented by US6973212. Are there any ...
0
votes
0answers
13 views

Is there an application area that sensors are on planes and we know the local positions of the sensors, but not the global positions?

I am currently writing the motivation of my thesis. And the answer to this question is very crucial for me: I am working on wireless sensor networks. Say that, there are a number of planes, for ...
9
votes
3answers
91 views

Recipe book for SAT encodings?

SAT solvers are getting more and more efficient in solving large instances and are being used as back-ends in various contexts. Every time one wants to use them to solve a problem in a specific ...
1
vote
0answers
14 views

Equivalence of data-flow analysis, abstract interpretation and type inference?

@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of ...
1
vote
0answers
20 views

Given a set of sets and a storage area, find an order that minimizes the sum of the differences between each set and the storage area

This problem is based on an order picking problem with a forward area. The problem description is as follows. We have a warehouse with a set of items $I$ and a forward area $F$ of size $k$. Each ...
3
votes
1answer
51 views

Maximum minimal set coverage

Suppose we are given a universal set $U$ and a family of subsets of $U$, denoted by $F$ (elements in $F$ are subsets of $U$). We assume that all elements in $F$ can cover $U$, i.e., $U\subseteq ...
2
votes
0answers
39 views

Recent Garbage collection survey paper

Many years ago I read a GC survey paper that was updated every few years with advances; I tried to find such a paper today to point a questioner on Stackoverflow at. However all I can find is very ...
4
votes
0answers
34 views

Languages recognized by finite state automata of polynomially growing size

In the course of my research (condensed matter physics stuff), I stumbled over the following concept: The class of regular languages can be defined via finite state machines (FSM): A language $L$ ...
7
votes
0answers
50 views

Exponential analogue of NC?

Nick's Class (NC) is the class of problems that can be decided in poly-log time using a polynomial number of processors. I want to know about the exponential analogue, which would cover problems that ...
3
votes
0answers
27 views

Term for index-like data structures

There's a class of data structures where you preprocess some other data structure in order to answer queries about it more efficiently. That includes trivial things like sorting/hashing, less trivial ...
2
votes
0answers
25 views

Difficulty of Integer Linear Programming vs. Mixed Integer Linear Programming

I have recently been working on an applied project where I have to solve optimization problems. I have found that it is much easier to solve an integer linear program (ILP) as opposed to a ...
3
votes
0answers
36 views

Status of Research Problems in Motwani and Raghavan

One nice aspect of Motwani and Raghavan's classic textbook, Randomized Algorithms, is that the notes for many chapters include open questions marked as "research problems." However, the textbook is ...
1
vote
0answers
38 views

Teaching computer science in developing countries - any literature?

I've been teaching computer science in a developing country and I've seen how the everyday challenges are very different from what I was used to. The students are different. The teachers are ...
1
vote
1answer
22 views

Reference proof for Second-Order Logic captures Polynomial-Time Hierarchy

I'm looking for a complete proof of $\mathrm{PH=SO}$. The (admittedly few) textbooks and papers i've looked at all either state that it's a corollary from Fagin's Theorem, or leave it as an exercise ...
1
vote
1answer
24 views

Feasibility of linear inequalities with binomial variables

I have a system of linear inequalities of the form $A^t x <= b$ where each of the $x_i$'s is a binary variable in $\{0, 1\}$. Are there any known fast and practical algorithms that can find a ...
2
votes
2answers
34 views

Method for measuring the 'similarity' between FSA grammars?

I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic ...
0
votes
0answers
7 views

Hierarchical learning in a non-static environment

I've been reading about hierarchical reinforcement learning (HRL), in particular it's application to a simple delivery task as show here. While reading the paper, I noticed that the environment ...
2
votes
0answers
14 views

Has hierarchical learning been embodied in a robot before?

I've been reading about hierarchical reinforcement learning (HRL) and it's applications. A well-written literature review on the subject can be found here. However, I was wondering if research has ...
8
votes
2answers
195 views

Are there established complexity classes with real numbers?

A student recently asked me to check an NP-hardness proof for them. They performed a reduction along the lines of: I reduce this problem $P'$ that is known to be NP-complete to my problem $P$ ...
5
votes
2answers
207 views

Direct NP-Complete proofs

I'm just starting to learn about NP-completeness. While I understand that reducibility plays a key role in this, I'm astonished how few problems I've been able to find who's proof that they are ...
0
votes
0answers
28 views

A bound for the minimum vertex cover of scale-free graphs

For a complete graph, the size of minimum vertex cover is $n-1$. I was wondering whether there exist an upper bound (or an expected value or upper bound) for the size of minimum vertex cover for ...
3
votes
0answers
56 views

What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of ...
5
votes
1answer
50 views

Base conversion puzzle

Here's an old puzzle: Let $s$ be a string of decimal digits ($s[i] \in \{0,\dotsc, 9\}$). Define a function $f(s)$ as follows: Interpret $s$ as a decimal number, $n_{10}$, and convert $n$ to its ...
4
votes
3answers
96 views

Most time-optimal parallel algorithms to calculate the determinant and inverse of a matrix

I am writing a numeric library to exploit GPU massive parallelism and one of the implemented primitives is a matrix class. Naturally I require a determinant and inverse function for this class and I ...
4
votes
1answer
25 views

Probabilistic hardness of approximation or solution of NP-hard optimization problems under a probabilistic generative model for input data

So in biology (DNA sequences), sequence alignment is a generalization of longest common subsequence where an alignment of two sequences is scored typically with a linear function of how many spaces ...
3
votes
0answers
63 views

Algorithms that are similar to Dynamic TIme Warping

Dynamic time warping (DTW) is an algorithm in time series analysis for measuring similarity between two temporal sequences which may vary in time or speed. Here are some explanations of DTW: Dynamic ...
4
votes
2answers
114 views

what would be the drawbacks of lecturing two programming languages simultaneously?

One colleage came with the idea/comment that it would be useful to lecture two programming languages, eg. Java and Scheme, at the same time while lecturing an Introduction to Programming course aimed ...
2
votes
1answer
155 views

Practical Page-Replacement Algorithms

Could anyone suggest other page replacement algorithms that are applicable to the real world aside from FIFO, Second Chance (Clock), Enhanced Second Chance and Random?
3
votes
0answers
30 views

Monograph or survey paper on smoothed analysis of algorithms

The paper by Spielman and Teng, Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time (JACM 51(3):385–463, 2004), won a Gödel award in 2008. Since then, has ...
-2
votes
1answer
41 views

from when do we have the field of computer vision? [closed]

when was the field of computer vision created and what are the disciplines that gave birth to it? I would appreciate it if you could give some web references that have the answer.
0
votes
0answers
30 views

Connections between reflection/introspection and metacognition

I would like to know if the notions of reflection and introspection in programming languages have prompted research in other fields other than computer science. I have found Cantwell's thesis, but I ...
5
votes
1answer
119 views

Are there current benchmarks for algorithms solving Travelling Salesman?

I'm researching the travelling salesman problem and looking for data regarding the current state of affairs regarding solutions and performance. So far the only data I've states that the current ...
5
votes
0answers
40 views

Bounded existential polymorphism

In Pierce's "Types and Programing Languages" he, at the very end, presents the most powerful system in the book: $F^{\omega}_{<:}$. He, however, does not explain how bounded existential ...
1
vote
1answer
67 views

Video lectures on type systems

For my job, I need to pick up a working understanding of the implementation of type systems (in particular, how to write typing rules based on a design document). I've been given a copy of Types and ...
-3
votes
1answer
63 views

Min-max selection sort

Is there already modified version of selection sort that works like this pseudocode: ...
2
votes
2answers
95 views

Which textbook can I use after a high school CS course? [closed]

I just finished the AP Computer Science course in high school and since my school does not have any further classes, I was thinking about getting a textbook and continuing my study. APCS goes through ...