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

90 views

### Finding final value of sum from double summation code fragment.

sum = 0; inc = 0 for i from 1 to n for j from 1 to i sum = sum + inc inc = inc + 1 What does it mean when it is asking the "final value of sum" from above code ...
176 views

### Proof completion: if $Y$ is a closed term in strong nf, then $Yx$ weakly reduces to a strong nf $Z$

I am self-studying Hindley & Seldin's Lambda-Calculus and Combinators. I would appreciate some help with filling in a final detail for a proof for the following statement regarding combinatory ...
79 views

### Computable Set & Function

we know that i read this sentence are true? can anyone say an example for following sentence? there are a non computable set A such that
33 views

### Convex hulls for a finite amount of points

I'm trying to understand what a convex hull intuitively is, and say given for a set of points $(x,y)\in\mathbb{R}^2$ how is it generated from these points? I tried reading the wikipedia article and ...
104 views

### Turing & Computability & Computation

We know if we have: we can show (T=t= Turin Redu.) but i have no idea why this relation be correct? any idea?
306 views

### How to obtain $\operatorname{lcm}(a_1,a_2,a_3,\ldots,a_n)\%1000000007$ [closed]

The problem is that you have $n$ numbers whose value can be in range $[1,100000]$. The task is to find the LCM of all these numbers. Now the answer can be very large so it should be printed MODULO ...
207 views

36 views

### What kind of set system is defined to have this property?

Let $E$ be a set, and $F \in \mathcal P(E)$ has the following property: For every $x\in E$ and $Y,Z\in F$ with $x\notin Y\cup Z$, there exists $X\in F$ with $(Y\cap Z)\cup\{x\}\subseteq X$. I wonder ...
34 views

### Generating interesting random TMs

To get a more intuitive understanding of the halting problem I want to generate some random TMs and see how they behave, what some heuristics can tell about them, etc. The problem is that, if I ...
70 views

### another counting problem

There are $k$ warriors that participate in the Wars, which have happened for the past $n$ years. Each year there has been a victor. Further, a particular warrior $W$ has won the Wars an even number of ...
32 views

### A set system generated by a closure operator?

Given a ground set $E$, and a matroid closure operator $\tau$ on $\mathcal P(E)$, we can define a set system $(E,F)$ with $$F := \{X \in \mathcal P(E): \forall x \in X, x \notin \tau(X-\{x\}) \}$$ ...
53 views

### What does “modular” in “modular functions” mean?

From Wikipedia If $\Omega$ is a set, a submodular function is a set function $f:2^{\Omega}\rightarrow \mathbb{R}$, where $2^\Omega$ denotes the power set of $\Omega$, which satisfies one of the ...
60 views

### minmizing average problem

Given a set containing N numbers, minimize the average where you can take out any string of consecutive numbers in the set. |N|<=100000 Ex. {5, 1, 7, 8, 2} You can take out {1,7}, etc. but the ...
71 views

### Function Combination on Computer Science

I read some material on Computational Function, every one could describe the result of following combination? suppose $g_1(x)=3x$, $g_2(x)=4x$, $f(x,y)=x+y$, how we compute combination of $f$ with ...
275 views

### Compressing binary numbers

If I have a arbitrarily long random binary number with the condition that the probability that a given digit is 0 and 1 is 1/4 and 3/4, respectively. What is the best way to compress this into a ...
94 views

### Find coordinate $y$ of an elliptic curve point

If I have an elliptic curve over a finite filed $F_p$ ($p$ is prime) defined as $$y^2 \equiv x^3 + ax + b\pmod p,$$ such that $4a^2 + 27b^2 \neq 0$ and suppose I have only given the coordinate $x$, ...
54 views

### Understand the English paragraph on association rule.

I am currently studying Association Rule Pattern Mining. I am reading the explanation on wikipedia about it. Somehow, I feel like I have a problem in understanding the paragraph below. Can somebody ...
236 views

### How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a ...
2k views

### How is math used in computer graphics? [closed]

I'm doing a research paper on the mathematics of computer graphics and animation (3D) and I do not know where to start. What mathematical equations and concepts are used for computer graphics and ...
70 views

### Check if there's a cycle in an undirected graph

I'm trying to find an algorithms that checks if there's a cycle in a given undirected graph G=(V,E). But I didn't succeed. Can anyone give me such an algorithm?
407 views

### Shortest path between wikipedia articles

I'm trying to figure out whether it is possible (and if so how) to find the shortest path inside a network from one node to another. I know that there are different possible algorithms to do that the ...
21 views

### Finding the upper bound of the length of a closed walk

I am having trouble understanding a part of the proof of Lemma 2 (Page 184). It says the length of the tour is $$\leq \lceil n^{1/2} \rceil + \triangle(n + \lceil n^{1/2} \rceil) + \sqrt{2}$$ I ...
44 views

### Reduction between languages in P

I have a simple question about the class P: Is there exist a polynomial time reduction between every two languages A, B in P?
38 views

### Do sets require a general equivalence relation over all elements?

and does this mean there cant be sets of things I have not defined equivalency for? This is maybe a weird question and maybe not even a meaningful one, my understanding of sets and such is not ...
68 views

### Calculate the probability that at least k of his favourite students are awarded?

Our hero - Maga is going to make a new contest for making the best teams. He is really excited about it. There will be S students in the contest. First N students in the final standings will be ...
225 views

### Is there any algorithm (if possible, I need the codes) for Jordan normal form decomposition for large matrices in practice?

Although it is an ill-posed problem as B Kågström said in "An algorithm for numerical computation of the Jordan normal form of a complex matrix", I wonder what people do when they need to do Jordan ...
41 views

58 views

### Exact calulation of trigonometric functions

My question is a bit related to computer science and I am not quit sure if this place is a good one for it. Let me know if I should move it. So as you know values of functions like sin or cosine can ...
771 views

### Calculating time complexity of algorithms written in pseudocode.

Nowadays we are interested to find some algorithms with a prescribed running time. For example if for certain decisional problem $X$ there is an algorithm with running time $O(n^3)$ we try to break ...
76 views

### Myhill-Nerode theorem for the language: $L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$

I have to use the Myhill-Nerode theorem for the following language: $$L = \left\{ a^n b^n\mid n\ \geq\ 1 \right\}$$ An equivalence relation is the following: x \sim y\ \Leftrightarrow \forall\ \ ...