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
10 views

A question about Singular Value Decompositon(SVD)

Using this paper as a reference (Section IV.C, page 4318), We have the following objective function which we wish to minimize with respect to $D \in \mathbb R^{n \times K}$: $$\min_{D} ...
0
votes
0answers
11 views

The DNF complexity of a function and its complement

If $f:\{0,1\}^n \to \{0,1\}$ is a $DNF$ formula with $t$ terms of width $w$, what can we say about the $DNF$ complexity of $\neg f$ (i.e., what is the number of terms and width needed to represent ...
8
votes
3answers
854 views

Karatsuba vs. Schönhage-Strassen for multiplication of polynomials

I am wondering how to most effectively multiply two polynomials with several $100$'s of coefficients, each coefficient having $1000$-$2000$ decimal digits. I know Schönhage-Strassen begins to ...
0
votes
0answers
10 views

Duplicating characters using sed [migrated]

I am working on trying to duplicate characters on certain words, but the sed script I wrote is not quite doing what I want it to. For example, I am trying to duplicate each character in a words like ...
1
vote
1answer
34 views

Why does my induction proof of an algorithm's running time always seems tautological?

I'm having some trouble proving algorithm's running times. The problem is not so much that I can't define the recurrence in open form nor that I cannot come to the conclusion that I know to be true. ...
0
votes
0answers
14 views

Proof of optimal substructure for the “plus sign game”

First of all, I think there's no "plus sign game", I have just invented the name to describe the problem faster. Another thing: I thought to ask the question in these stack exchange's website because ...
1
vote
0answers
20 views

If $\lg(n!) = \Theta(n \lg n)$, does $\lg(n!) = \Theta(\lg(n^{n^n}))$ as well?

First consider that we have: $$ \begin{align} \lg(n!) &= \overbrace{\lg\Bigg(\sqrt{2\pi{n}}\Big(\frac{n}{e}\Big)^n\Big(1+\Theta(\frac{1}{n})\Big)\Bigg)}^{\text{Stirling's Equality}} = ...
-1
votes
2answers
25 views

What are good techniques for creating a DFA state diagram given a set of accepted/rejected strings?

I am in a Discrete Structures class and my teacher is pretty big on proving his intellect to the class and getting an average of about 60% for his test questions. Right now we are working with ...
0
votes
0answers
18 views

Which correct sentence to explain the function $g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$

I have a edge indicator function that has formula as $$g(\nabla I)=\frac{1}{1+\beta |\nabla(G_{\sigma}*I)|^2}$$ where $\nabla$ is gradient operator, $*$ is convolution operator, $G_{\sigma}$ is a ...
0
votes
1answer
40 views

Writing regular expressions

So here's the problem: Let $Σ =\{a, b, c\}$. Write a regular expression for the set of all strings in $Σ^∗$ such that the sum of the number of $a$’s and $b$’s in the string is at most two. Thus the ...
1
vote
0answers
12 views

Complexity of fast multipole method

I am trying to implement the Fast multipole Method on Matlab. But i have a question: if we call N the number of source point we need (in the FMM algorithm) to sort the data points. Such a procedure ...
0
votes
1answer
31 views

What exactly does this inequality do?

I this paper which is titled "KSVD: An Algorithm for Designing Overcomplete Dictionaries for Sparse Representation", in the section about "kmeans algorithm for vector quantization", there is the ...
0
votes
1answer
39 views

Give some examples of strings in, and not in, these sets, where Σ = {a,b}

Here's the set: {w : for some u ∈ Σ*, www = uu} From what I understand, it's saying "w (which is a string) such that for some u (which is another string) is an element of the possible combinations ...
1
vote
0answers
40 views

Rewriting regular expressions

For the following two regular expressions, how would I rewrite them as a simpler expression representing the same set? $b^* \cup a^* \cup (a \cup b)^*$ $\Big((a^*b^*)^*(b^* \cup a^*)^*\Big)^*$ I ...
0
votes
0answers
21 views

Big $O$ question for While and For loops [on hold]

I have to find the exact $O(N)$ for these instructions, not just the order of magnitude. I'm not getting any of the answers provided for me. I know the first loop is $O(3N+2)$. The declaration of ...
-5
votes
0answers
22 views

Python Read and write program [closed]

Write a program to prompt for a file name, and then read through the file and look for lines of the form: X-DSPAM-Confidence: 0.8475 When you encounter a line that starts with “X-DSPAM-Confidence:” ...
-7
votes
0answers
34 views

Python Read A finle and returen capital letters program [closed]

Exercise 1 Write a program to read through a file and print the contents of the file (line by line) all in upper case. Executing the program will look as follows:python shout.py Enter a file name: ...
-4
votes
1answer
27 views

Binary word addition; error pattern

If a word $a = a_1,a_2,...,a_n$ is sent is sent (this is in regards to coding/IT/etc.-I'm trying not to include any extraneous information) and a word $b= b_1,b_2,...,b_n$ is received (where the ...
2
votes
1answer
20 views

For a finite character set $\Sigma$, what would be a formal proof that $\Sigma^{+} = \Sigma^{*}\Sigma$?

Let there be a finite character set $\Sigma$, as in computer science convention. $\Sigma^{*}$ is defined as in Kleene star notation (https://en.wikipedia.org/wiki/Kleene_star) with $\Sigma^{+}$ ...
0
votes
0answers
36 views

P vs NP: Is there a “mathematical” way to state it?

If I wanted a statement of the Riemann Hypothesis, I could say the prime counting function pi(x) satisfies such and such an analytical approximation. If I wanted a statement of the P vs NP problem, ...
1
vote
1answer
15 views

Calculating some probability of buying different cards

This problem was recently featured in an ICPC contest. The problem stated, without taking the story into account and as well as I recall: Peter likes a fad card game. This game has various cards, and ...
9
votes
2answers
6k views

Reed Solomon Polynomial Generator

I am developing a sample program to generate a 2D Barcode. And i am using reed solomon error correction code. By Going through this article i am developing the program. But i couldn't understand how ...
1
vote
0answers
11 views

Is there a Little law for a network of two connected queues?

From Patterson et al' Computer Organization and Design: Throughput and Response Time Do the following changes to a computer system increase throughput, decrease response time, or both? ...
2
votes
1answer
641 views

Finite state machine

I am doing discrete math, and we are studying Finite State Machines. But i am a little confuse on how to do this. Here is a question, Write a regular expression for the language, and define a finite ...
0
votes
2answers
45 views

Diagonalization Principle

Diagonalization principle has been used to prove stuff like set of all real numbers in the interval [0,1] is uncountable. How is this principle used in different areas of maths and computer science ...
8
votes
6answers
8k views

Great Book on Probability and Statistics (for Computer Scientists)

I'm a Computer Science sophomore and we're studying Probability and Statistics (fundamentals and all). The teacher recommends a book which I don't like since it does not even try and explain ...
0
votes
1answer
497 views

Y-Axis units on FFT graph

A 50Hz sinusoid wave with a voltage range of +/-20V is sampled at 512Hz for 1 second. No bias or phase shift are present. The signal is run through an FFT. The result is one spike at 50Hz on the ...
1
vote
1answer
844 views

Using BFS or DFS to determine the connectivity in a non connected graph?

How can i design an algorithm using BFS or DFS algorithms in order to determine the connected components of a non connected graph, the algorithm must be able to denote the set of vertices of each ...
5
votes
2answers
331 views

'(Pseudo)-random functions' by seeding of PRNGs?

I have an application that wants controllable random functions from $\mathbb{Z}^2$ and $\mathbb{Z}^3$ to $2^{32}$ , where by controllable I basically mean seedable by some parameters (say, on the ...
0
votes
1answer
434 views

Calculating normals for a polygon mesh (3D computer graphics)

I want to write a program to generate arches, a common architectural form, and export them to a wavefront object format for sharing with various three dimensional graphics editors. To do this, I need ...
0
votes
1answer
36 views

Purpose of Loop invariant

I have some small fairly easy questions regarding following procedure. My teacher has post some answers which I fairly understand but also have questions about. Note: I have taken a screenshot of the ...
1
vote
2answers
30 views

expected value of final x using the following algorithm

It has a bit of pseudo code so i'll try to explain x = 0 for i from 1 to n: if random() > 1/4: x = x + 5 else: x = x - 1 the probability ...
17
votes
4answers
4k views

Number of ways to partition a rectangle into n sub-rectangles

How many ways can a rectangle be partitioned by either vertical or horizontal lines into n sub-rectangles? At first I thought it would be: ...
0
votes
4answers
326 views

How to find inverse of 2 modulo 7 by inspection?

This is from Discrete Mathematics and its Applications By inspection, find an inverse of 2 modulo 7 To do this, I first used Euclid's algorithm to make sure that the greatest common divisor ...
3
votes
2answers
60 views

Proving the rules of a complicated game are well defined

What strategy could one use to formally model a game and prove that the rules do not lead to any self contradiction? A major example that comes to mind is Magic the Gathering. The card ...
1
vote
0answers
24 views

Chaining integer division operations

In an assembler program I am writing, I need to (quickly) calculate $a\text{ mod }n$. Now, in the language I am using there is a division instruction that takes two numbers $x$ and $y$ and returns ...
0
votes
1answer
77 views

Better time complexity.

I am new to complexity theory and want to know, Which one is better time complexity(faster) for an algorithm ?? \begin{equation} n^{k+log_2(n)}/log_2(n)2^{n(n+1)/2} \end{equation} or ...
0
votes
1answer
324 views

How can I tell/compare the asymptotic complexity of a function?

For something, like a quadratic I just take the highest degree and see if it is theta or big O or Omega of n, correct? So like 2n^2+2n+1 could be theta(n^2). What are the general ...
0
votes
1answer
34 views

Find a recurrence to count paths in a directed graph

Suppose we have an unweighted directed graph with vertices numbered as $1...n$ From each vertex $i$ there are edges to $i+1$, $i+2$ and $i+7$. My task is to find a recurrence $f(i,j)$ to compute the ...
1
vote
1answer
35 views

Computably enumerable closed under inverse image

Let $f: \mathbb{N} \rightarrow \mathbb{N}$ be a computable function and let $A \subseteq \mathbb{N}$ be computably enumerable. I'm trying to find a reason why the inverse image $f^{-1}(A)$ is also ...
0
votes
1answer
96 views

Finding number of subarrays not including certain pairs

How many contiguous subarrays of an array exist such that they do not contain certain pairs of positions of the array? For eg. if array ={11,22,33,45} and if we do not want to include say position ...
0
votes
0answers
6 views

Example of weighted max cut taking exponential time iwth local search

In the Coursera algorithms course, the instructor mentions some graphs with weighted edges take exponential time to solve in the worst case with local search the max cut problem. The search algorithm ...
0
votes
1answer
43 views

Proof that there isn't a graph search algorithm that is complete with finite memory

Is there a proof that any graph-search algorithm capable of exploring any graph (where there is a upper bound on the degree of each node and there is an ordering of the edges at each node-i.e left to ...
0
votes
0answers
15 views

Why $H_{V^* \cup W^*} > H_{V \cup W}$ if $H_V$ denotes entropy of language

Let $W \subseteq X^*$ be an infinite language over a finite alphabet $X$, and define ($|w|$ denotes the length of $w \in W$) $$ H_W := \limsup_{n\to \infty} \frac{\log_{|X|} | \{ w \in w \in W, |w| = ...
4
votes
3answers
3k views

Finite automaton that recognizes the empty language $\emptyset$

Since the language $L = \emptyset$ is regular, there must be a finite automaton that recognizes it. However, I'm not exactly sure how one would be constructed. I feel like the answer is trivial. ...
0
votes
0answers
52 views

Standard notation for the transform that turns a function $A \rightarrow (B \rightarrow C)$ into a function $B \rightarrow (A \rightarrow C).$

Suppose we're given sets $A,B$ and $C$. Then to each function $f : A \rightarrow (B \rightarrow C)$, we can assign another function $F : B \rightarrow (A \rightarrow C)$ by defining: $$F(b)(a) = ...
2
votes
0answers
13 views

Is cubic graph decomposition into claws NP-complete?

I am aware that deciding the existence of decomposition of a cubic graph into edge-disjoint claws is polynomial time solvable. What is the complexity of deciding the existence of decomposition of ...
2
votes
1answer
66 views

How is this equation evaluated $\binom {n}2 = \frac{n^2}{2}$?

I would like to know how $\binom {n}2 = \dfrac{n^2}{2}$ works out while I'm reading a proof on this page. I have tried several ways, but I couldn't. i.e. we knew that combinatorics formula that ...
0
votes
0answers
24 views

Inequality for the set of factors of length $n$ of some regular language

If $W \subseteq X^*$ is some language denote by $$T(W) := \{ u \in X^* : \mbox{there exists }x, y \mbox{ such that } xuy \in W \}$$ the set of factors (infixes) of $W$. If $W$ is regular, then ...
2
votes
2answers
27 views

Set of all factors of regular language regular?

If $L$ is a regular language (i.e. acceptable by a finite automata), is the the set of its factors (infixes) also regular?