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

0
votes
0answers
10 views

Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $

Problem Construct PDA that accepts the language $ L = \{ w \in \{ a,b,c\}^*; |w|_c=|w|_a + |w|_b \} $ My first idea was this: There can be an "a","b" or a "c" at the beginning of a word Then we ...
0
votes
1answer
27 views

Find regular expression that defines a given language

I want to find a regular expression that defines a language L over the alphabet {0,1} with a following condition: every word contains exactly two 000 substrings. For example, a valid word would be ...
-1
votes
0answers
17 views

Computer Programs and Unsolvable lambda terms [on hold]

λ-calculus an ideal mathematical model in which to interpret programs. Under what condition, a program can be interpreted as a solvable lambda term, and what condition, as a unsolvable term? What role ...
0
votes
1answer
20 views

show how 42.25 would be stored as a floating point number with an 8-bit mantissa and a 4-bit exponent.

So I know that in binary: 42: 00101000 0.25: 01 I then put combine the numbers so it would be: 00101000.01 Once I get this point I'm not sure how to show the mantissa as an 8-bit and the exponent ...
1
vote
1answer
32 views

In formal languages, why is $L^0 = \{ \epsilon \}$? Why isn't it the empty set ∅?

It just doesn't make logical sense to me that a language to the power of $1$, is itself, but to the power of $0$ is only a tiny part of itself (since every language contains $\epsilon$) Wouldn't it ...
2
votes
0answers
35 views

What exactly is wrong with this argument (Lucas-Penrose fallacy)

Argument "For every computer system, there is a sentence which is undecidable for the computer, but the human sees that it is true, therefore proving the sentence via some non-algorithmic method." ...
0
votes
0answers
12 views

Size of remaining search space for Vehicle Routing Problem given a partial solution

The vehicle routing problem is a NP-hard problem that, in its most basic form, involves scheduling routes for v vehicles that have to make n deliveries in total. So a solution (schedule) has the form ...
-3
votes
0answers
33 views

R.E set and Recursive Set, A Confusing Axioms !?!? [on hold]

I want to check true or false of the following two axioms. who can help me or add some hint: I) $ A=\{x \mid \Phi_x\text{ is not one-to-one function} \}$ is an r.e set. II) if $A$ is an r.e ...
0
votes
2answers
37 views
0
votes
0answers
16 views

Rent's Rule and Modularity?

Rent's Rule http://en.wikipedia.org/wiki/Rent%27s_rule plays a very important role in the engineering of computer circuits, as well as in models of processing (be it of information, be it of brain ...
0
votes
1answer
11 views

Brauer Algorithm [duplicate]

I'm working on a problem and I'm looking at an equation: $lg(n) + (1 + o(1))(lg(n))/(lg(lg(n))$ All I want to know is, what does o(1) mean? Thanks!
-2
votes
0answers
17 views

i have this gui calculator code. but i don't know how to make the arithmetic operation appear on textfield. can someone help me tnx . [on hold]

import java.awt.; import java.awt.event.; import javax.swing.; import javax.swing.event.; import java.awt.event.; import javax.swing.border.; class CalculatorFinal extends JFrame implements ...
11
votes
4answers
719 views

why is $2.2250738585072014\text{e}{-308}$ not a number? [on hold]

In programming the min value of a float is: $$2.2250738585072014\text{e}{-308}$$ but when I type this into a calculator, it says Not a Number. what I am wondering ...
2
votes
1answer
14 views

The reason for using normalized data as inputs of Neural Networks [closed]

Hello I would like to forecast time series and in many algorithms are used as inputs normalized data -1, 1. What is the reason for this normalization? My original data have scale from 1 to 2. Thank ...
1
vote
1answer
20 views

What is the total speedup?

This is a repost of a StackOverflow thread. I was told that people on this forum will be able to answer this question faster. So here it is: This is not homework. I'm taking a computer architecture ...
0
votes
1answer
26 views

What is the difference between finding the sum of a series and its closed-form solution?

In complexity theory, it is sometimes necessary to find the "closed-form solution" of a summation. This was put in our exam guide as "solving arithmetic and geometric series", which I initially ...
1
vote
2answers
21 views

Expected codelength for Huffman-algorithm with probabilities

I am unable to solve the following problem: Let $$n \geq 2$$ $$p_{1} \geq p_{2} \geq ... \geq p_{n}$$ $$p_{i} = 2^{-k_{i}}$$ with $k_{i} \in \mathbb{N}$ and $\sum_{i=1}^{n}p_{i} = 1$. $p_{i}$ is the ...
3
votes
1answer
60 views

Is it possible to show that a particular theorem or its negation is provable, without knowing which of the two is true?

I've been thinking about this for a while: as far as we know, is it possible that for a particular statement $\sigma$ of $\textsf{ZFC}$, we can prove that $(\textsf{ZFC} \vdash \sigma) \vee ...
-3
votes
0answers
39 views

SimRank Example? [closed]

By using Similarity in SimRank as shown by this formula $$ s(u,v)= \left(\frac{C}{|I(u)||I(v)|}\right). \sum_{x\in I(u) } \sum_{y\in I(v) }s(x,y) $$ How can we find SimRank between 5,4 ? or s(5,4), ...
2
votes
2answers
28 views

Tweaking formulas to increase scoring

I am building a model for SVM classification. However, the confidence score that i have would be from negative to positive. This is the formula i am using to normalize the confidence score ...
0
votes
1answer
20 views

Can we program a computer to check a proof in first-order arithmetic is valid, and can we find out whether such a statement is true?

Slightly confused by this. I wish I knew what more to add, but I know it's asking something about the halting problem, and something about Godel but I cannot seem to figure it out.
2
votes
1answer
28 views

How to show that the Restricted-3-color decision problem is in the polynomial class

I'm struggling to answer a past paper question, which asks to prove that the defined problem is in the polynomial complexity class(P). The question is mentioned below The only strategy I can come ...
0
votes
1answer
19 views

Languages in coNP

if a language $L \in$ coNP, i.e. it's complement is in NP, then does L have a deterministic turing machine that decides it? i think that this is false, but am unsure how to show it? my guess is using ...
0
votes
0answers
16 views

determining whether a turing machine

For $i\in \mathbb{N}$, define $L_i :=${$ ⟨M⟩ |$ On input $101$ M halts after at most i steps} For any fixed i the language $L_i$ is decidable as if there is no end state up to the i$^{th}$ position ...
0
votes
1answer
12 views

Proving from Myhill-Nerode that the minimum DFA is the smallest automaton recognizing $L$

From this paper, In the proof of (Myhill-Nerode theorem) it's stated that if $L$ is a regular language and the index of $\sim_L$ is $i_L \in \mathbb{N}$ then it's both necessary and sufficient for ...
0
votes
0answers
97 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a strongly $k $ regular graph G(srg($n,k,\lambda ,\mu$);$\lambda ,\mu >0;k>3$). The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ ...
0
votes
0answers
13 views

How to calculate effect of different variables/parameters on a quantity?

I am developing a game for iOS. In the game I have around eight different parameters that directly affect the score of the player. We can say that these eight variables decide the difficulty of the ...
0
votes
1answer
38 views

Context free grammar $\{a^n b^m c^k\; : \;k>m \; \; k>n\}$

Is this a CFL? $$\{a^n b^m c^k\; : \;k>m \; \; k>n\}$$ When on seeing $a$'s and $b$'s I push them onto stack and as I see $ c$ as input if $ TOS$ is $b$ ,I pop them ,again if $TOS$ is a,I pop ...
3
votes
1answer
93 views

A few questions about KSVD algorithm (dictionary learning) in a paper

To learn more about dictionary learning, I am currently trying to understand the concept in detail and to do so, I've found the following paper quite informative: KSVD: an algorithm for designing ...
1
vote
1answer
27 views

Construct a deterministic finite state automaton

Construct a deterministic finite-state automaton that recognizes the set of all bit strings that end with 10. This is what I drew. Not sure if its correct. State 2 is the final state. Am I missing ...
0
votes
1answer
16 views

Find the language recognized by the given deterministic finite state automaton

I got 01* U 1(01)01 as my answer. I'm not sure if its right.
1
vote
0answers
40 views

Permutation and Combination Problem-word arrangement

There are three pieces of paper.In the three papers ,a string (non-empty) has to be written such that none of the string on any paper is prefix of some other string.Also alphabet size of characters ...
0
votes
1answer
21 views

Regular Expressions that define given languages

A few of these here I just wanted to make sure I had right. For $\Sigma = \{0,1\}$ a. The language consisting of all strings of 0's and 1's that have even length and where 0's and 1's alternate I ...
3
votes
1answer
22 views

How to compute $\cos(x)$ within $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$

How does one compute $\cos(x)$ within desired $n$ digit accuracy when $x = \sqrt{y}$ with $y \in \mathbb{N}$ and $x$ is not rational? The reason I am asking this question is that calculators ...
2
votes
1answer
28 views

Is this the correct minimum number of coins needed to make change?

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used ...
0
votes
1answer
22 views

Use the Pumping Lemma to prove that $L=\{a^{m}b^{2^{n}} \}$ is not regular.

Normally pumping lemma proofs aren't too hard; you just experiment with different values of $i$ and sort of stumble on the solution. However, this problem is really bugging me and I am spending a lot ...
0
votes
1answer
19 views

How would you apply the Greedy technique in this situation/why wouldn't it work?

I am going over the Rod Cutting Problem The author states "Selling a rod of length $i$ units earns $P$[i] dollars." Here is the table $P$ for this problem I'am currently going over this question ...
1
vote
1answer
32 views

Where does 13 come from?

I am going over the Rod Cutting Problem Everything makes sense to me until For example, $L$ = {9} has the total cost Cost($L$) = $P$[9] = 13, whereas $L$' = {1,1,1,1,1,1,1,1,1} has the total cost ...
0
votes
0answers
20 views

What's the mathematical model of Consistent Hash?

What's the mathematical model of Consistent Hash? There are several implementations: Karger's implementation using a bucket cycle: Jump Consistent Hash [Highest Random Weight (HRW)][3] hashing: ...
1
vote
1answer
57 views

Undecidable definition of pure function

I am trying to come up with a formal definition for functional purity in a simple programming language (think JavaScript). What I've got so far is this: DEFINITION: A statement is impure if ...
1
vote
1answer
17 views

What does the notation $\{ \pm 1 \}^X$ in relation to functions and hypothesis classes means in the context of PAC learning over half spaces?

I was reading the following paper (on PAC learning over half-spaces) and encountered the following notation for a hypothesis class (on page 4): $$\mathcal{H} \subset \{ \pm 1 \}^X$$ However, it was ...
0
votes
0answers
31 views

About Katz centrality

I am studying Graph Theory and Network Analysis, I have this measurement formula which called Katz centrality: My question is: why $A^k$ will grow [infinitely] in $k$ for most cases. As I think ...
1
vote
1answer
64 views

Struggling with difference between greedy and naive but optimal algorithms? (Graph theory)

I've been thinking about the following problem for quite a while and tried multiple solutions, but I'm having difficulty telling the difference between a greedy algorithm and an inefficient naive ...
0
votes
0answers
7 views

Is my LL(1) parse table correct?

I have the following Grammar: ...
0
votes
2answers
184 views

Why are every finite language decidable?

I don't understand why every finite language is decidable. For example, if I have an infinite set of strings L over an alphabet E, why is there a Turing Machine M that decides L? I understand the ...
0
votes
1answer
47 views

A formula that, when plotted, yields its own display

I've just seen a video on Tupper's self-referential formula. When I heard that this formula was not at all self-referential but merely a simple way to generate every possible $17\times 107$ dot matrix ...
0
votes
2answers
29 views

Converting an NFA to DFA

I am atttempting to convert an NFA into an equivalent DFA. I did it, but i am not sure if it is correct. If anyone can please take a look at let me know if it is correct or if there is something wrong ...
0
votes
0answers
16 views

Computing Combinations

I toss a coin N times (with a big N) and write down the results, in order. I have also several arrays of H's (Heads), T's (Tails), and X's (Any), each with length N. How could you compute the ...
3
votes
3answers
64 views

Wouldn't each addition take time $O(n)$?

I am going over the asymptotic runtime of regular matrix multiplication. Here is a lecture slide I am referencing(too much to type out, shown below), from Algorithms Everything makes sense up ...
0
votes
0answers
29 views

data and signals [closed]

A periodic composite signal with a bandwidth of 1500Hz is composed of two sine waves.The first one has a frequency of 100Hz with a maximum amplitude of 20V; the second one has a frequency of 50Hz and ...