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

Python Read and write program [on hold]

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:” ...
-4
votes
0answers
25 views

Python Read A finle and returen capital letters program [on hold]

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
15 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
35 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
11 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
votes
1answer
99 views

Is there a term called 'GRAIL'?

I've been a talk with a PhD student about some graph issue and told me about GRAIL graph and have drawn it for me as you see in the picture, however, I try to generalize so-called "Grail graph" to ...
1
vote
0answers
10 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
640 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
38 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
487 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
841 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 ...
1
vote
0answers
26 views

Basic Maths for competitive programming [closed]

I really require some help!!!In Competitive programming i know that you need to know the basics of mathematics but i don't know on which fields to concentrate on.Since maths is a very large field i ...
0
votes
1answer
428 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
35 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
29 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
316 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
303 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
32 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
31 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
95 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
23 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?
0
votes
1answer
25 views

What is $h^{-1}(L)$, for $L$ a regular language and $h$ a homomorphism?

Let $L = L((00 + 1)^∗)$ and $h : \{a, b\}^* \to \{0, 1\}^*$ be defined by $h(a) = 01$ and $h(b) = 10$. What is $h^{−1}(L)$? In this context "$+$" means "$\cup$". So the language $L$ is all the ...
4
votes
2answers
2k views

Concrete FFT polynomial multiplication example

I have read a number of explanations of the steps involved in multiplying two polynomials using fast fourier transform and am not quite getting it in practice. I was wondering if I could get some help ...
-4
votes
1answer
56 views

Why is it that if one NP complete problem is solved, all NP problems are solved?

I get NP completeness, but I don't understand why it's said that by solving one NP complete problem, all of them are solved. Is it saying that solving one NP complete problem proves that all of them ...
5
votes
1answer
63 views

Counting the expected number of strings with a given contiguous substring.

Question: Let a random bit string $x$ of length $n$ be given. What is the expected number of bit strings $w$ of length $2n$ that contain $x$ as a contiguous substring? What I know: For any bit ...
6
votes
0answers
80 views

How to attack universal hash function based on finite-field arithmetic?

As per the Recursive n-gram hashing is pairwise independent, at best paper, I want to use the algorithm described in chapter 6 and 7 (page 7 - 10). The hash works as follows: Define a random ...
3
votes
2answers
37 views

Computational Complexity of Primality Checking

"PRIMES in P" proved that primality checking is in $P$. However, the CS 101 prime checking algorithm is to divide a number $n$ through all integers up to ${\sqrt n}$ , and if no results are whole ...
0
votes
1answer
42 views

Prove $K_4-Cover$ is NP-Complete

I'm studying for a computational theory exam, and as part of my studying I'm trying to solve previous years' exams. I have come across this problem and I'm having some difficulty with it: Let $ G ...
0
votes
0answers
9 views

Identify arbitrer policy of a network component

I would like to identify the formula of the service rate of a network component ARB based on input and output rates of flows crossing it. For instance, I have several flows which cross several ...
1
vote
1answer
54 views

Echo State Network learning Mackey-Glass function, but how?

I got this example of a minimal Echo State Network (ESN) which I analyse while trying to understand Echo State Networks. Unfortunately I have some problems understanding why this really works. It all ...
0
votes
2answers
44 views

Fast multipole method: help on tutorial

I have some hard time with the FMM (Fast multipole method). I try to understand the basics with: "http://www.umiacs.umd.edu/labs/cvl/pirl/vikas/publications/FMM_tutorial.pdf". So here are my ...
1
vote
1answer
56 views

What is the context-free grammar for $0^{n}1^{2n+1}0^{n}$

context free grammar for $0^{n}1^{2n+1}0^{n}$ I've tried several different methods to find it but I can't figure out how to make both sides opposite to each other...please help I've been working on ...
0
votes
2answers
2k views

problem simplifying boolean algebra expression using consensus theorem

Please simplify this logic expression for me with helping boolean algebra : A'C'D + A'BD + BCD + ABC + ACD' I know that must use consensus theorem . my solve : STEP 1 : Terms 1 & 3 ...
6
votes
1answer
109 views

FRACTRAN for natural numbers

Is there a simple analogue of FRACTRAN that maps a natural number to a natural number, instead of mapping a list of fractions to a natural number? One could use Gödel encoding to translate FRACTRAN ...