All mathematical questions about computer science, including theoretical computer science, formal methods, verification, and artificial intelligence. For questions about Turing computability, please use the (computability) tag instead. For numerical analysis, use the (numerical-methods) tag. For ...

learn more… | top users | synonyms

1
vote
1answer
311 views

Counting the number of asymmetric graphs on n nodes?

Asymmetric graph is a graph that has only trivial automorphism. Asymptotically, almost all finite graphs are asymmetric. I'm looking for upper bounds and lower bounds on the growth rate of the number ...
1
vote
1answer
293 views

Can a polynomial size CFG describe the finite language \{$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed\} over alphabet \{0,1\}?

Can a polynomial size Context free grammar describe the finite language {$w \pi(w)$ : $\pi(w)$ is fixed string permutation, $|w|=n$ is fixed} over alphabet of {0,1}? One case this is possible is when ...
0
votes
1answer
157 views

Problem k-subvector using dynamic programming

Given a vector V of n integers and an integer k, k <= n, you want a subvector (a sequence of consecutive elements of the vector ) of maximum length containing at most k distinct elements. The ...
2
votes
1answer
1k views

Solving a nonlinear system using Groebner basis computations

I have discovered that Groebner basis computations may help in a problem I am working on. However, I am having some very specific problems. First, the literature I have discovered on Groebner basis ...
3
votes
1answer
324 views

Best Practices for Learning Mathematics (especially in the classroom)

What study practices have led you to the best success in learning mathematics (or applied math, or theoretical CS) in the classroom (undergraduate/lower graduate level), especially in courses that ...
15
votes
6answers
2k views

What math should a computer scientist take in college?

I'm a computer science major and like many of us we have to take two additional sciences. These two additional science courses are in addition to three semesters of calculus,two semesters of physics, ...
9
votes
3answers
11k views

What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
3
votes
1answer
982 views

Pushdown Automata deriving context free language

I'm trying to understand how you derive a context free grammar (CFG) from a Pushdown Automata (PDA)? I have the following PDA. I believe the following context-free language can be derived.. ...
1
vote
1answer
1k views

Grammar to Chomskys Normal Form eliminating epsilon productions

I've got the following grammar I'm attempting to convert to CNF. S -> T01 | USV | epsilon U -> X V -> S1S | X | 1 X -> 0XS | 0 T -> TV | XT | UTU ...
0
votes
2answers
997 views

How to create a graycode of N bits with a code-agnostic iteration function

I'm posting this as more of a theory/mathematic how-to followup to a stackoverflow question. The non-iterative method for calculating graycode depends on Log2N bytes, to store position information ...
3
votes
1answer
189 views

Help needed on method to use for anomaly detection in Computer Science

I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some undesired event occurring in the system like a virus infection. I could get ...
0
votes
1answer
2k views

In this Cholesky Algorithm in matlab, what is the abs function doing

We have been told in our homework to implement the following program: function A = Cholesky(A) % Cholesky Decomposition of a Matrix A, so that the resulting matrix L gives A=L*L N = size(A,1); ...
3
votes
2answers
18k views

Implement a program in Matlab for LU decomposition with pivoting

I need to write a program to solve matrix equations Ax=b where A is an nxn matrix, and b is a vector with n entries using LU decomposition. Unfortunately I'm not allowed to use any prewritten codes in ...
0
votes
1answer
103 views

Minimum number of numbers to be inserted in a sequence to transform it into an A.P

Given a sequence of N numbers, how can we find the minimum number of numbers to be inserted to make this sequence to an Arithmetic progression.(we can insert at any position of this sequence) For ...
1
vote
1answer
259 views

Complexity of verifying proofs

My question can be read on many levels and so I welcome answers to any reading. The general question is: What is the computational complexity of verifying a proof? One way of looking at a ...
4
votes
2answers
827 views

Addition on big omega notation

It seems to my uneducated mind that if I have $\frac{n}{k}$ subproblems, each of size $\Omega (k \log k)$, that my overall problem must be at least of size $\Omega (n \log k)$, by the reasoning that ...
13
votes
4answers
13k views

Representing IF … THEN … ELSE … in math notation

How do I correctly represent the following pseudocode in math notation? EDIT1: Formula expanded. EDIT2: Clarification. (a,b) represents a line segment on a 1D line. a <= b for each segment. The ...
2
votes
1answer
72 views
1
vote
3answers
439 views

Can we partition NP-complete problem into finite number of polynomially solvable problems?

I have asked this question on cstheory. Let $\Pi$ be NP-complete problem. Can we partition the set of instances of $\Pi$ into finite number of subsets (subproblems) each of which is polynomially ...
2
votes
2answers
177 views

NP-problem that needs superlinear certificates

In the definition of the complexity class NP, we allow the certificate to be polynomial in the input size. But do we ever need a certificate that is longer than the input? In all the NP problems I ...
4
votes
1answer
228 views

Can a polynomial size CFG over large alphabet describe any of these languages:

Can a polynomial size CFG over large alphabet describe any of these languages: Each terminal appears $0$ or $2$ times Word repetition $\{www^* \mid w \in \Sigma^*\}$ (word repetition of an arbitrary ...
3
votes
1answer
310 views

Big-oh for function of two variables

Is it true that $O(M^3 + NM^2) \, = \, O(M^3 + N)$, where $M$ and $N$ are variables of the function?
2
votes
1answer
276 views

Restricted read twice BDDs and context free grammars

Several papers give poly-time algorithms for constrained paths on labelled graphs, e.g. [1] Quote: Given an alphabet Σ, a (directed) graph G whose edges are weighted and Σ-labeled, and a formal ...
5
votes
5answers
717 views

Can a polynomial size CFG over large alphabet describe a language, where each terminal appears even number of times?

Can a CFG over large alphabet describe a language, where each terminal appears even number of times? If yes, would the Chomsky Normal Form be polynomial in |Σ| ? EDIT: What about a language where ...
1
vote
2answers
158 views

How to select the optimum combination of numbers from a random list that add to up to a certain total (or as close to)

I'm developing a computer program, and need an algorithm to solve the following problem: How to select the optimum combination of numbers from a random list that add to up to a certain total (or as ...
5
votes
0answers
347 views

Constructor And\Or-graph on function transition of the alternating automata

In a And\Or-graph induced by the transition function, each node of $G$ corresponds to a state $q$ belonging to a set $Q$ of the state of the Automaton, for $q$ with $\delta(q,a)=q_1*q_2$, the node is ...
2
votes
1answer
3k views

Quotient of a regular language

According to wikipedia the right quotient of a regular language with ANY other language is regular. I have not been able to find a proof of this fact. All the sources talk about quotient with another ...
3
votes
1answer
175 views

Reduce the number of operations on a simple expression

Lets say I take a computation that involves only addition and multiplication: (a+b)*(c+d) which can be done in many other ways, eg. ...
2
votes
1answer
2k views

Help understanding the proof that 2SAT is in P

I have read this paper and the wikipedia summary here and even this homework problem, but I do not understand how 2SAT is in P. Here is my concern: the idea is that we start by setting a random ...
2
votes
1answer
492 views

Right-moving Turing Machines

The idea of a read-only right-moving Turing Machine already exists [1]. Is there a relaxed version of this where an input-reading head only moves right to read inputs as needed? There may be other ...
5
votes
3answers
712 views

knapsack algorithm that looks too good to be true

I have an idea for solving the knapsack problem, but it looks too good to be true. I would like someone to explain potential problems with this approach. I'll give an example: I want to find a subset ...
9
votes
2answers
1k views

Can we reduce the number of states of a Turing Machine?

My friend claims that one could reduce the number of states of a given turning machine by somehow blowing up the tape alphabet. He does not have any algorithm though. He only has the intuition. But ...
3
votes
2answers
245 views

Rounding trouble in a calculator's square root function

I made the following observation following a suggestion from a friend. This question is about the Microsoft calculator program implemented on Windows. Since I don't have access to any other calculator ...
0
votes
1answer
438 views

Calculation of G force

I have a formula which is G-force = velocity*omega/9.8. Omega is the angular velocity. I've seen on the internet that G force is actually acceleration/9.8. I'm confused as to which formula is correct. ...
2
votes
5answers
8k views

Program for working with DFA/NFA/PDA?

I'm looking for a program or utility to help construct DFA/NFA/PDA etc. and the like. The main reason I'm interested in this, is because I want to be able to move the various states around without ...
0
votes
1answer
194 views

context free languages closure properties

This isn't homework. Prove or dis-prove the statement: If $R$ is a regular language and both $L$ \ $R$ and $L \cup R$ are context-free, then $L$ is context-free.
2
votes
3answers
422 views

Partitioning a graph (clustering of point sets in 2 dimensions)

I am given $n$ points in 2D.(Each of say approximately equal weight). I want to partition it into $m$ clusters ($m$ can be anything and it is input by the user) in such a way that the center of mass ...
3
votes
3answers
296 views

categorization of logic

(1). I was wondering about what are the relation and differences between formal and informal logic? What topics does each of them have? For example, topics such as Meaning and Definition, Syllogistic ...
1
vote
0answers
62 views

Who uses R with multicore, SNOW or CUDA package for resource intense computing?

who of you in this forum uses R (http://www.r-project.org/) with the multicore, SNOW or CUDA packages, so for advanced calculations that need more power than a workstation CPU? On which hardware do ...
2
votes
2answers
265 views

Does this proof for the undecidability of the halting problem violate the axiom of regularity?

One proof of the halting problem goes by contradiction like this : Assume there is a Turing machine $H$ that can decide the halting problem, then construct a Turing machine $Q$ that takes as input a ...
3
votes
2answers
508 views

shadow simulation from buildings

is it possible to calculate shadow areas of buildings or simulate shadows of buildings in a city, using the heights of these buildings and the sun angle and azimuth? the basic light tracing concept ...
4
votes
0answers
139 views

Hardness of perimeter minimization?

Given $xy=C$ where $x, y$ are integer variables and $C$ is integer constant. What is the most efficient algorithm that finds $x,y$ such that $x+y$ is minimum? Providing references is highly ...
8
votes
2answers
906 views

Looking for a bijective, discrete function that behaves as chaotically as possible

I need to write a coupon code system but I do not want to save each coupon code in the database. (For performance and design reasons.) Rather I would like to generate codes subsequent that are ...
0
votes
1answer
969 views

How to calculate daily user churn rate?

I have a table in my database that records, 48 times per day, the total users, total active users within 2 weeks, total users logged in within the past 24 hours , and total users that logged in within ...
3
votes
3answers
2k views

What are the prerequisites for combinatorics?

I'm looking to strengthen my understanding of the math that is directly useful to practical computer science, as opposed to unsolved computer science problems. In other words, the kind of math that ...
1
vote
1answer
105 views

Problem interpretation - Distance Formula?

If you've got multiple arrays like this: (24,36,28,28,16,27) (38,38,45,57,35,50) every array being 6 integers, each integer in range [0,60] I would like to find the distance between those 2 ...
6
votes
2answers
765 views

What requirements should a CRC polynomial satisfy?

What requirements should a CRC polynomial of a given degree satisfy to make the CRC catch a maximum of errors? edit I'm talking about GF(2) polynomials. As an example of the kind of requirements ...
6
votes
4answers
12k views

Reduction from Hamiltonian cycle to Hamiltonian path

I'm looking for an explanation on how reducing the Hamiltonian cycle problem to the Hamiltonian path's one (to proof that also the latter is NP-complete). I couldn't find any on the web, can someone ...
3
votes
3answers
770 views

Applications of Logic and Algebra in Computer Science

I have used logic for specification of security policies in a security model. One of my reviewers asked a question that "why did you use logic and not algebra for this purpose, and what is your ...
1
vote
1answer
181 views

Related Integer Combination

The title and tags are a little goofy since I'm not quite sure what to call this. This may be more of a computer science question, but I thought I'd ask here too. I have two integers $n$ and $m$ ...