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

2
votes
0answers
9 views

The reason for using normalized data as inputs of Neural Networks

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
19 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
0answers
13 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
12 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 ...
2
votes
1answer
49 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
26 views

SimRank Example? [on hold]

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
27 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
18 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
14 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
10 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
54 views

Combinatorial algorithm problem of a symmetric matrix.

Given a matrix A of a regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$. $ A_x$ is the symmetric matrix of the graph $(G-x)$, where $C$ is the ...
0
votes
0answers
12 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
30 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
0answers
32 views
+150

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
25 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
15 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
39 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
18 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
24 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
31 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
53 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
16 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
60 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
159 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
46 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
28 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
63 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
23 views

data and signals [on hold]

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 ...
1
vote
0answers
17 views

Learning Booth's Algorithm, I Can't Find the Issue on Final Result

I am practicing using Booth's Algorithm to multiply a positive number and a negative number (specifically the problem is $-12 \times 4$). I have included my attempt, but I can't find the issue. If ...
0
votes
1answer
16 views

How do I input this Boolean Expression into a K map?

Determine the minimum SOP, sum of products expression using K-Map F(A,B,C,D,E) = (A’ + B + C’ + D + E’)(A’ + C’ + D + E )(A’ + C’ + E )AC’ Do i have to actually simplify it first by multiplying ...
1
vote
3answers
42 views

How to apply Master theorem to this relation?

This is the definition of master theorem I am using(from Master Theorem) I am trying to use that master theorem to find the tight bound for this relation $T(n) = 9T(\frac{n}{3}) + n^3*log_2(n)$ ...
-3
votes
0answers
55 views

What areas of mathematics are not related to computer science?

I'm taking a Bachelor's in Computer Science, and I love Mathematics, so I want to know what I'm missing out on!
0
votes
0answers
13 views

Torelli Shanks Algorithm - Repeated Squarring Method

This algorithm is using when you want to find a square root of a number in a given moduli. I can't see the idea behind this algorithm, so can someone explain it in a simple way?
1
vote
3answers
43 views

How to find the solution of $T(n,m) = T((n-1),m) + T(n,(m-1))$ in terms of big $O$ notation?

I would like to solve the recurrence $T(n,m) = T((n-1),m) + T(n,(m-1))$. I think the solution is $$O(2^{n+m})$$ because in every step you can reduce either $n$ or $m$ by one or not, but I can not ...
2
votes
1answer
25 views

Proving a language $L$ is in $\mathrm{co\text{-}NP}$ if $| L \cap \{0,1\}^n | \in \operatorname{poly}(n)$ for all $n$

Let $L \in NP$ such that $|L \cap \{0,1\}^n|=\operatorname{poly}(n)$ for all $n$. Prove that $L \in \mathrm{co\text{-}NP}$. If I understand the problem correctly, in words this says that "for any ...
1
vote
1answer
26 views

How to simplify Boolean Expression $\bar B + \bar C (B + A)$

I trying to figure out how $ \bar B + \bar C (B + A)$ simplifies to $ \bar B + \bar C$.
3
votes
2answers
67 views

What is a good book for reviewing high school math, and preparing for university?

I'm signing up for University soon (Compsci program) as a mature student. It's been a long time since I've done any math, and I went as far as grade 11 in high school. So, I'm looking for a book that ...
1
vote
0answers
20 views

Can boosting be thought of as a genetic algorithm? [migrated]

Can boosting be classified as a genetic algorithm or as an instance of simulated annealing? Or, is it a completely different paradigm? Essentially, I'm trying to rectify discrete optimization ...
1
vote
0answers
15 views

Changed matrix dimensions - now formula doesnt work. Related to computer science

I'm writing a computer code to solve a problem, and I ran into some difficulties. This is not a coding question, my problem is purely mathematical, I will explain. We have a matrix $M\in Mat(\mathbb ...
1
vote
1answer
23 views

Entropy Calculation and derivation of logarithm

I have probabilities as $$p_1 = 0.4,\ p_2 = 0.3,\ p_3=0.2,\ p_4=0.1$$ hence entropy is given by: $$H(x) = -\big(0.4\cdot \log_2(0.4) + 0.3\cdot \log_2(0.3) + 0.2\cdot \log_2(0.2) + 0.1\cdot ...
0
votes
1answer
19 views

NDFSM Transition State Network

My coursework question asks me to "Draw a State Transition for the nondeterministic finite state machine (NDFSM)" from a state transition table. By following the examples in our lecture materials, ...