# Tagged Questions

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 ...

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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
11k views

### What makes a context free grammar ambiguous?

What makes a context free grammar ambiguous?
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.. ...
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 ...
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 ...
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 ...
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); ...
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 ...
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 ...
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 ...
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 ...
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 ...
72 views

### How to solve such system with given parts of it? (maple)

So I had a system ...
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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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. ...
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 ...
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.
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 ...
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 ...
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 ...
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 ...
508 views

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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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$ ...