Use this tag if you ask for pointers to material for self-study.
3
votes
2answers
58 views
Where can a student learn image processing?
I am a student of computer science with interest in image processing. I have learned how to apply a few effects to images like making them grayscale, sketching them out of lines, etc.
I would like ...
1
vote
1answer
23 views
Multicommodity circulation formulation
On the circulation problem page on wikipedia, the multicommodity circulation formulation seems to be insufficient, since we can just set all but one flow to $0$, and reduce it to a circulation ...
0
votes
0answers
15 views
Simple explanation for Stacked Generalisation ensemble method
I cannot undertand how exactly the Stacked Generalisation works.
I have tried to read the original paper and also the survey by Robi Polikar. I understand that a meta-classifier is created and it is ...
4
votes
1answer
72 views
Largest reported speedup for a parallel computation?
A parallel implementation of a computation is usually compared to a sequential version of the same computation. The ratio of the time taken by the sequential version to the time taken by the parallel ...
2
votes
1answer
80 views
Quantum computing roadmap
I have to create a roadmap for the quantum computing technology. Looking around I found the timeline on wikipedia that is pretty wide but does not highlight the key events in quantum computing ...
2
votes
0answers
39 views
Is there a formal CS definition of VCS and file versions?
I don't know whether it was a joke, but once I read what was referred to as a formal definition of a file in a versioning system such as git, hg or svn and that was something like a mathmetaical ...
3
votes
1answer
33 views
Where can i find literature about the $\frac{4}{3}$-conjecture for approximation of the Metric TSP?
In Graph-Theory there are many ways for efficient approximation-algorithms to solve the Metric TSP. The best solution seems to be the Christofides Heuristic with a factor of 1.5 to the optimal ...
3
votes
1answer
49 views
Quasigroups, congruences and recognizable subsets
My question refers to the draft of Mathematical Foundations of Automata Theory, IV.2.1 (pages 89ff in the pdf). I will repeat everything necessary nevertheless:
Let $M,N$ be monoids and $\varphi: M ...
1
vote
0answers
20 views
machine learning applied to automatic assesment?
I am making a survey of Artificial Intelligence Techniques applied to educational fields. Actually I would like to find papers related to machine learning techniques applied to automatic scoring of ...
-1
votes
0answers
37 views
What are different ways of executing computational tasks? [closed]
The different ways of executing computations that am aware of are, broadly
Centralized (Client/Server Model, a client outsources computations to a powerful server)
Decentralized (distributed Model, ...
1
vote
0answers
16 views
Name and complexity of a problem concerning metrics
Do you know the name of the following problem and can you give a reference for its complexity (especially the relation to $\mathsf{GraphIsomorphism}$ and/or other isomorphism/homomorphism problems)?
...
5
votes
1answer
62 views
Paper with proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$ is not Deterministic Context Free?
These lecture slides sketch a proof that $L=\{ a^n b^n \mid n \geq 0 \} \cup \{ a^n b^{2n} \mid n \geq 0 \}$
cannot be accepted by any Deterministic Pushdown Automaton. Unfortunately, the slides give ...
0
votes
0answers
31 views
Computer Graphics reference request
I am self-studying computer graphics (both 2d and 3d) and was wondering if someone could provide me with some references like websites, literature, etc.
I am a complete beginner to computer ...
1
vote
1answer
79 views
Parallelization of an iterative function application
What I have
An iterative process based on the application of a very simple function to represent a rate, with total dependence among any iteration and its predecessor (one input parameter for (n)th ...
6
votes
1answer
88 views
Is the universe problem for one-counter automata with restricted alphabet size undecidable?
Consider the following universe problem.
The universe problem. Given a finite set $\Sigma$ for a class of languages, and an automaton accepting the language $L$, decide if $L=\Sigma^*$.
In [1], ...
11
votes
1answer
230 views
What does 'true concurrency' mean?
I often hear phrases like 'true concurrency semantics' and 'true concurrency equivalences' without any references. What does those terms mean and why are they important?
What are some examples of ...
2
votes
1answer
116 views
Amdahl's Law and Computer Science
I would like to learn more about Amdahl's Law and other similar topics. In what branch of computer science would one place Amdahl's law? Could someone point me to a textbook or further reading ...
1
vote
0answers
22 views
Code metric for code redundancy or code cloning
Is there a common code metric for "code redundancy" or "code cloning"?
I think I read somewhere a definition, where the LOC (lines of code) of
the redundant code was measured.
I also searched for ...
3
votes
2answers
78 views
Can we understand SVM without knowledge of Machine Learning [closed]
I was told by my adviser (future one) to look into libsvm library or any other and try to get familiar with it.. to work on a programming project (on Machine Learning) (will start in a month).
my ...
1
vote
2answers
77 views
Why don't we scale the cost of memory access when analyzing runtime of algorithms?
Runtime for many programming languages is typically analyzed either assuming each operation takes a constant amount of time, or assuming each operation takes a logarithmic amount of time in the size ...
2
votes
0answers
31 views
Light approximation for shortest path tree
I am looking for the paper : "B. Awerbuch, A. Baratz, and D. Peleg, Efficient broadcast and light-weight spanners, Manuscript, (1991)."
It claims that we can build $(\alpha ,1+\frac{4}{\alpha -1})-LAST$ ...
3
votes
1answer
30 views
Chazelle's discrepancy book: greedy method
In Bernard Chazelle's book The Discrepancy Method, which is available free as a PDF from the author's website, the very first statement requiring thought by the reader (on page 3, just before Theorem ...
3
votes
1answer
68 views
Asymptotic bounds on number of 3SAT formulas with unique solutions
A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if ...
1
vote
2answers
81 views
Introduction to complexity and computability
I'm looking for a good book that explains these subjects in a readable way.
Any suggestions ?
I currently pursuing my BSC in computer science, and I just failed to pass the course introduction to thr ...
16
votes
0answers
165 views
Asymptotics of the number of words in a regular language of given length
For a regular language $L$, let $c_n(L)$ be the number of words in $L$ of length $n$. Using Jordan canonical form (applied to the unannotated transition matrix of some DFA for $L$), one can show that ...
2
votes
0answers
31 views
Computing the inverse of Johnson-Lindenstrauss transform
It seems, from a quick (and incomprehensive) survey of the literature (e.g. N. Ailon, B. Chazelle, SIAM J. Comput. 39 (2009), 302-322.) that there are many fast algorithms (and constructions) for the ...
6
votes
0answers
37 views
Interval density of time bounded Kolmogorov complexity
The Kolmogorov complexity of a string $x$ is the size of the smallest Turing machine $M$ that started on empty tape produces $x$. To make it computable, we can add a bound on the time used by $M$ to ...
5
votes
2answers
73 views
Given a tree, find a vertex which maximizes the minimum distance to any leaf
If I am given a graph which forms a tree, I am interested in finding a vertex which maximizes the minimum distance to any leaf.
I am sure this problem has been studied before.
Does anybody know the ...
4
votes
1answer
33 views
Independent set where two vertices need to have distance >= c
An independent set (IS) in a graph is a set $V' \subseteq V(G)$ of pairwise non-adjacent vertices.
I am interested in the generalization $c$-IS where two nodes in $V' \subseteq V(G)$ need to have ...
6
votes
1answer
130 views
Are context-free languages in $a^*b^*$ closed under complement?
The context-free languages are not closed under complement, we know that.
As far as I understand, context-free languages that are a subset of $a^*b^*$ for some letters $a,b$ are closed under ...
2
votes
1answer
52 views
Comparing variations of A*
I am running some experiments with a maze, and trying different variations of A*. Based on my experiments, I have been able to form some opinion (that at least in those cases, graph checking is better ...
2
votes
0answers
31 views
Prolog programming references [closed]
I am new in Prolog, and have read the book "Programming in Prolog". I am looking for some online resources that can provide me with more challenging (or tricky!) programs, so I can enhance my skills.
...
6
votes
0answers
55 views
Given a chordal graph $G$, what is the complexity of computing the reduced clique graph $C_r(G)$?
A graph $G$ is chordal if it doesn't have induced cycles of length $4$ or more. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ ...
0
votes
4answers
113 views
A good introductory book on cryptography
Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the ...
0
votes
0answers
32 views
study materials on Artificial Neural Networks [closed]
I am searching for the study materials on Artificial Neural Networks, specifically, the ones that cover next topics:
Use of ANN for classification and non-linear regression (feedforward Neural ...
4
votes
0answers
49 views
Decomposition of graphs that uses centers
Do you know of any kind of decomposition of graphs that involves centers, especially in the context of parametrized complexity? If so, please provide some reference. If not, do you see any reason ...
2
votes
0answers
40 views
Fair division of two-dimensional cake
I am interested in procedures for fair division of land (i.e. envy-free division, or at least proportional division).
In contrast to the well-studied cake-division problem, land-division is ...
7
votes
2answers
130 views
Job scheduling with a bottleneck problem
Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete.
Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a ...
6
votes
1answer
116 views
Difference between the languages accepted by two DFAs with different initial state/accepting states?
Recently, I asked a question on Math SE. No response yet. This question is related to that question, but more technical details toward computer science.
Given two DFAs $A = (Q, \Sigma, \delta, q_1, ...
4
votes
2answers
91 views
Getting started with Program Analysis
I'm looking for resources on getting started with program analysis.
The only book I've found on the topic is the Nielson & Nielson book.
Other than that, it seems like there are only "compiler" ...
3
votes
1answer
58 views
Minimal-envy land division
There is a land divided to $D$ districts.
There are $C$ citizens.
We want to divide the land to the citizens, such that each citizen receives a single land-plot in a single district.
Each citizen ...
2
votes
0answers
21 views
Stereo images rectification and disparity: which algorithms?
I'm trying to figure out what are currently the two most efficent algorithms that permit, starting from a Left/Right pair of stereo images created using a traditional camera (so affected by some ...
5
votes
1answer
97 views
Problem Solving in MapReduce Framework
I am looking for good resources which have classified and solved typical large scale data processing in MapReduce framework (like graph algorithms, statistics, numerical algorithms ...). Any help is ...
0
votes
3answers
99 views
Top Turing machine simulators on the web? [closed]
There are many Turing machine simulators on the web of varying degrees of sophistication and can be highly useful for pedagogical purposes for students of widely varying ages, and they also have ...
1
vote
1answer
121 views
Studying advice
I don't know much when it comes to computers,
But If I wanted to learn how to programm algorithms that perform symbolic calculations and other techniques used to solve or aid mathematical problems, ...
4
votes
2answers
102 views
How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?
I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.
My ...
3
votes
4answers
172 views
Practical application of Finite State Machines
I am looking for practical applications of Finite State Machines like DFA, NFA, Moore, Mealy machines...
It would be helpful if someone point to examples from Linux Kernel. I know that DFA is used in ...
3
votes
1answer
69 views
Origin of theta-joins
I've taken an introductory database course where like many good database courses, they taught relational algebra, including $\theta$-joins. However, I've recently read E. F. Codd's 1970 paper, A ...
0
votes
1answer
53 views
Parsing: Tutorial? [closed]
Does anyone know of a good website/online resource that provides a tutorial on writing a parser? I've done a few google searches, and haven't had any worthwhile results returned. I was hoping to find ...
1
vote
2answers
93 views
Research papers in Computer Science [closed]
What are some research papers which are really fundamental and led to the birth of a new field of study or a novel idea in Computer-Science?
