Questions tagged [reference-request]

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

Filter by
Sorted by
Tagged with
16
votes
1answer
1k views

Universal simulation of Turing machines

Let $f$ be a fixed time-constructable function. The classical universal simulation result for TMs (Hennie and Stearns, 1966) states that there is a two-tape TM $U$ such that given the description of ...
9
votes
5answers
2k views

Standard or Top Text on Applied Graph Theory

I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the ...
14
votes
1answer
249 views

When did $LR(k)$ acquire the meaning "left-to-right scan, rightmost derivation?"

According to the Wikipedia article, the L in $LR(k)$ means "left-to-right scan", and the "R" means "rightmost derivation." However, in Knuth's original paper on $LR(k)$ grammars, he defines $LR(k)$ (...
2
votes
1answer
113 views

Where can I find the data of the computer experiments in the book "Neural Networks and Learning Machines"?

The book "Neural Networks and Learning Machines" by Simon Haykin has many computer experiments to which many exercises are related. But there seems to be no data for these experiments available online....
10
votes
1answer
257 views

Determining how similar a given string is to a collection of strings

I'm not sure if this question belongs here and I apologize if not. What I am looking to do is to develop a programmatic way in which I can probabilistically determine whether a given string "belongs" ...
4
votes
1answer
98 views

Canonical reference on agent-based computing

I am interested in exploring the world of BDI agents (software agents that possess "beliefs, desires, intentions", essentially the agent has knowledge of the world, a set of motivations, and carries ...
3
votes
0answers
111 views

Lossless Video Compression Pipeline

The only paper I can find about an implementation of a lossless video codec is an article by Michael Niedermayer which explains the FF1V compression pipeline. I'm wondering if anyone else has found ...
20
votes
1answer
1k views

Lock-free, constant update-time concurrent tree data-structures?

I've been reading a bit of the literature lately, and have found some rather interesting data-structures. I have researched various different methods of getting update times down to $\mathcal{O}(1)$ ...
4
votes
1answer
357 views

Is there a search engine over Artificial Intelligence and Machine Learning -related sites?

Sometimes it is necessary to dig into Artificial Intelligence or specifically Machine Learning problems to make a research. Common googling (in my own experience) usually doesn't help much due to a ...
39
votes
4answers
9k views

Worst case $O(n \ln n)$ in place stable sort?

I am having trouble finding good resources that give a worst case $O(n \ln n)$ in place stable sorting algorithm. Does anyone know of any good resources? Just a reminder, in place means it uses the ...
6
votes
1answer
632 views

Find string that minimizes the sum of the edit distances to all other strings in set

I have a set of strings $S$ and I am using the edit-distance (Levenshtein) to measure the distance between all pairs. Is there an algorithm for finding the string $x$ which minimizes the sum of the ...
23
votes
4answers
11k views

Book for algorithms beyond Cormen

I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations? NOTE: I asked ...
9
votes
3answers
1k views

Online Learning Resources for Discrete Mathematics

Are there any good Discrete mathematics learning web resources with problem sets?
4
votes
1answer
121 views

Expression Problem – looking for a similar standard problem

The Expression Problem, populated by Philip Wadler, is a often used to standard problem to evaluate programming languages. I think it is a very clear and popular example and I wonder if there are ...
5
votes
1answer
164 views

Complexity of space density and sequentiality

I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms. When we measure algorithms we tend to give the big-Oh notation ...
8
votes
1answer
741 views

Turing Machine-Like Formalism for The Actor Model

Turing machines have a formal symbol alphabet, state and transition-rules based description of how a computation is done. The Actor Model is sometimes mentioned as a more powerful computational-...
5
votes
1answer
2k views

Non-linear grammars

I look for information about grammars which can be described by a non-linear equation such as a quadratic equation: $\qquad \displaystyle G \to G G a \mid b$ or $\qquad \displaystyle G \to G G \mid ...
23
votes
3answers
1k views

Categorisation of type systems (strong/weak, dynamic/static)

In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear? In a sense ...
6
votes
2answers
184 views

Computing follow sets conservatively for a PEG grammar

Given a parsing expression grammar (PEG) grammar and the name of the start production, I would like to label each node with the set of characters that can follow it. I would be happy with a good ...
7
votes
1answer
152 views

voting scheme for peaceful coexistence

Many areas in the world suffer from conflicts between two groups (usually ethnic or religious). For the purpose of this question, I assume that most people of both sides want to live in peace, but ...
2
votes
2answers
178 views

Speech vs Music classification

I want to determine which parts of an audio file contain speech respectively music. I hope someone has a made something like this or can tell me where to start. Can you please suggest some method or ...
2
votes
1answer
2k views

Enumerating all the walks in a graph between a start vertex and a terminal vertex?

I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can ...
0
votes
2answers
176 views

Advanced placement CS A Exam

What would be the standard topics covered in an 'Advanced Placement Computer Science A' test? Is there any good study reference someone can share? Edit: Answer An adjustment for my search term ...
21
votes
3answers
3k views

How to read typing rules?

I started reading more and more language research papers. I find it very interesting and a good way to learn more about programming in general. However, there usually comes a section where I always ...
1
vote
2answers
820 views

Any very user friendly resources on the Baum-Welch algorithm?

I'd like to understand the Baum-Welch algorithm. I liked this video on the Forward-Backward algorithm so I'd like a similar one for Baum-Welch. I'm having trouble coming up with good resources for ...
9
votes
3answers
1k views

What is the branch of Computer Science that studies how Anti Virus programs work?

It is a trivial exercise in finite automata to show that there is no algorithm that can detect all the viruses, yet there are many software companies selling Anti Virus Software. Is there any part of ...
8
votes
0answers
231 views

Complexity of computer algebra for systems of trigonometric equations

As discussed in this question, I drafted a spec algorithm that hinges on finding a specific root of a system of trigonometric equations satisfying the following recurrence: $\qquad f_{p_0} = 0\\ \...
2
votes
1answer
353 views

Could someone suggest me a good introductory book or an article on graph clustering?

For my pet project I need to cluster some data which could be easily represented as graph, so I want to use this as an opportunity to educate myself and play with various algorithms. I'd prefer the ...
10
votes
1answer
656 views

Machine Learning algorithms based on "structural risk minimization"?

Which machine learning algorithms (besides SVM's) use the principle of structural risk minimization?
18
votes
1answer
530 views

Proving the (in)tractability of this Nth prime recurrence

As follows from my previous question, I've been playing with the Riemann hypothesis as a matter of recreational mathematics. In the process, I've come to a rather interesting recurrence, and I'm ...
103
votes
5answers
16k views

How not to solve P=NP?

There are lots of attempts at proving either $\mathsf{P} = \mathsf{NP} $ or $\mathsf{P} \neq \mathsf{NP}$, and naturally many people think about the question, having ideas for proving either direction....
16
votes
1answer
221 views

Polytime and polyspace algorithm for determining the leading intersection of n discrete monotonic functions

Some frontmatter: I'm a recreational computer scientist and employed software engineer. So, pardon if this prompt seems somewhat out of left field -- I routinely play with mathematical simulcra and ...
27
votes
1answer
1k views

Is there a typed SKI calculus?

Most of us know the correspondence between combinatory logic and lambda calculus. But I've never seen (maybe I haven't looked deep enough) the equivalent of "typed combinators", corresponding to the ...
10
votes
2answers
362 views

How do I classify my emulator input optimization problem, and with which algorithm should I approach it?

Due to the nature of the question, I have to include lots of background information (because my question is: how do I narrow this down?) That said, it can be summarized (to the best of my knowledge) ...
7
votes
1answer
257 views

What techniques exist for energy-efficient computing and networking?

I am currently reviewing the potentials of cloud computing regarding energy efficiency and green IT. In connection with this review I am having a look on techniques for increasing energy-efficiency in ...
3
votes
0answers
385 views

Cyclic coordinate method: how does it differ from Hook & Jeeves and Rosenbrock?

I have trouble understanding the cyclic coordinate method. How does it differ with the Hook and Jeeves method and the Rosenbrock method? From a past exam text: Describe the cyclic coordinate ...
20
votes
2answers
493 views

How to scale down parallel complexity results to constantly many cores?

I have had problems accepting the complexity theoretic view of "efficiently solved by parallel algorithm" which is given by the class NC: NC is the class of problems that can be solved by a ...
6
votes
1answer
351 views

Target-Value Search (& II)

[previously appearing in cstheory, it was closed there and introduced here instead] Given an edge-weighted graph $G=(V,E)$ the problem of finding the shortest path is known to be in P ---and indeed a ...
10
votes
2answers
2k views

What is the difference between classical crypto and post-quantum crypto?

Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be ...
46
votes
6answers
6k views

Dealing with intractability: NP-complete problems

Assume that I am a programmer and I have an NP-complete problem that I need to solve it. What methods are available to deal with NPC problems? Is there a survey or something similar on this topic?
8
votes
3answers
639 views

What is the name of this logistic variant of TSP?

I have a logistic problem that can be seen as a variant of $\text{TSP}$. It is so natural, I'm sure it has been studied in Operations research or something similar. Here's one way of looking at the ...
7
votes
1answer
342 views

What is a good reference to learn about state transition systems?

I am studying different approaches for the definition of computation with continuous dynamical systems. I have been trying to find a nice introduction to the theory of "State transition systems" but ...
3
votes
2answers
535 views

Survey of informed search algorithms?

I'm looking for a list of informed search algorithms, also known as heuristic search algorithms. I'm aware of: best-first search Greedy best-first search A* search Are there more best-first ...
1
vote
1answer
131 views

Where can I find good study material on Role Mining?

I need to cover these topics in Role Mining. If anyone knows good site which well summarizes the topics and concepts are well explained please help out. Basic role mining problem • Delta-approx RMP • ...
21
votes
1answer
2k views

Classification of intractable/tractable satisfiability problem variants

Recently I found in a paper [1] a special symmetric version of SAT called the 2/2/4-SAT. But there are many $\text{NP}$-complete variants out there, for example: MONOTONE NAE-3SAT, MONOTONE 1-IN-3-SAT,...
11
votes
4answers
372 views

Introductory books on nature sciences behind bioinformatics

My question goes to those who are concerned with computational biology algorithmics. I'm going to take a course on bioinformatics this fall; the problem, however, is that I have too little background ...
36
votes
2answers
2k views

Quantum lambda calculus

Classically, there are 3 popular ways to think about computation: Turing machine, circuits, and lambda-calculus (I use this as a catch all for most functional views). All 3 have been fruitful ways to ...
14
votes
1answer
380 views

Research on evaluating the performance of cache-obliviousness in practice

Cache-oblivious algorithms and data structures are a rather new thing, introduced by Frigo et al. in Cache-oblivious algorithms, 1999. Prokop's thesis from the same year introduces the early ideas as ...
13
votes
2answers
2k views

Decidable restrictions of the Post Correspondence Problem

The Post Correspondence Problem (PCP) is undecidable. The bounded version of the PCP is $\mathrm{NP}$-complete and the marked version of the PCP (the words of one of the two lists are required to ...
22
votes
7answers
1k views

Computer Science Book for Young Adults

What is a good beginner computer science book for a young adult, say, a 15 year old? I want to get started in CS, but have no idea where to start. I have limited experience in programming.