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

3k views

### Are there dictionaries in math?

Consider the following dictionary in the programming language Python: D = {'A': 1, 'B': 2, 'C': 3} It is saying that the value of A is 1, the value of B is 2, ...
216 views

### is all math beyond arithmetic just advanced arithmetic? [on hold]

Is it true that at the bare-bones of all advanced math, its all just mostly arithmetic? In computer programming languages they are mostly constrained to arithmetic operators. I suppose this is ...
31 views

### Is there a method that determines an unknown permutation better than $\sum_{k=1}^n (k+1)/2$ steps on average?

Suppose I have a random permutation $s \in S_n$ that is unknown to me. However, suppose I can make a query where when I ask if $i$ is in the $j$th position in the permutation, I receive a yes or no ...
17 views

70 views

### Are Pandemic chain reactions confluent? (vertex spills weight to neighbors at threshold, once)

Are resolutions of chain reactions order-independent in the board game Pandemic? More formally: You're given an undirected graph $G = (V, E)$ and a vertex weight $w \colon V \to \{0, \ldots, 3\}$. ...
16 views

### Passing variables into function (MATLAB)

I am creating a function that perform multiple regression in MATLAB. The function is created as function [Beta] = george_linreg(y,x1,x2,x3,....,xN). I don't ...
24 views

### The relativised Church–Turing thesis

Barry Cooper states in his computability theory "The relativised Church–Turing thesis" on page 142 as follows: All formalisations of "$B$ computable from $A$" which are sufficiently reasonable ...
101 views

### Why does this pattern occur when using modular arithmetic against set of prime numbers?

I have been recently playing around with number theory and going through the project Euler problems. So I am very new to a lot of these things. I apologize for not knowing how to look up my answer. ...
73 views

### As a computer science major, should I take differential equations, linear algebra, or both? [closed]

I've taken three semesters of calculus (altho the way my school does it, Calc III excludes Green, Stokes, Divergence/Curl Theorems and puts them in a class called Calc IV), and I've met my math ...
23 views

### How to get increasing int number based on two values

I did ask this question on SO but it seems this will find more appropriate audience here. I have a Google map where I am dropping markers based on events, this happens periodically and after 8 hours ...
44 views

### Find a path from $s$ to $t$ with smallest “bottleneck”

Let an undirected graph, $G=(V,E)$ with weights defined by the function $w:E\to\mathbb{N}$ and for each edge: $1\le w(e) \le |V|$. You are given two vertices: $s,t\in V$. Find a path from $s$ to $t$ ...
22 views

### Finding an MST among all spanning trees with maximum of white edges

Let an undirected graph $G=(V,E)$ with the color property $c(e)$ for every edge (could be black or white) and a weight property $1 \le w(e) \le 100$. Find the MST from the set of all spanning trees ...
49 views

### Shortest path from $s$ to $t$ in a graph with $5$ negative edges and no negative cycles?

Let $G=(V,E)$ a directed and weighted ($w:E\to\mathbb{R}$) and let $s,t\in V$. It is given that there are exactly $5$ negative edges and no negative cycles. Find the shortest path from $s$ to $t$. ...
20 views

### Find a set of vertices $U\subseteq V$ included in some simple cycle

Let $G=(V,E)$, an un-directed graph. Find an efficient algorithm to return a $U\subseteq V$, where $u\in U$ is in some simple cycle of $G$. So basically we've learned in class about the $low$ ...
51 views

### Hyperplane Problem

Given $M$ points in $\mathbb{R}^{N}$, (where $M$ is larger than $N$) I was wondering if there is an approximation algorithm to find a hyperplane which goes through the origin and also intersects as ...
60 views

### finite state machine transition table problem

I have the following question which im not able to do. I have done things with DFA/NFA's before but this is the first time ive seen a question like this, I have been looking for similar questions in ...
44 views

### What are some properties that the regular languages are not closed under?

In a standard Theory of Computation class, one learns a variety of closure properties of regular languages, including but not limited to: homomorphism, inverse homomorphism, union, complement, ...
21 views

### For every $v\in V$, determine if it belongs to some negative cycle in $G$

Let $G=(V,E)$ a directed graph with a weight function $w:E\to\mathbb{R}$. For every $v\in V$, determine if $v$ belongs to some negative cycle. Obviously we need to utilize Bellman-Ford algorithm for ...
50 views

### Alphabet on homomorphism

So I am trying to learn for an exam, and I found an exercise but without solutions and I can't really get behind the topic: Let $G = (V,E)$ be a connected graph with $v \geq 2$ Vertices. $P(G)$ is ...
46 views

### How to evaluate this infinite series arising from a CS problem? [duplicate]

$$\sum_{i=1}^{\infty}i\cdot((1-\frac{1}{N!})^{i-1}\cdot\frac{1}{N!})$$ where N is an integer and $N \geq 2$? I obtained this series from the following problem: Given a sequence of $N > 2$ unique ...
29 views

### Growth function and one misunderstanding point?!

I have a question about Growth and Asymptotic notation topic. My question is as follows: $2^n$ > $n^{log_2{(n)}}$ is True. anyone could say how we can deduce that this fact is true?
24 views

### Big O notation for summation function

May be I am missing something very simple but I am finding it hard to understand why Big O for summation is O(n^2). I know that Big O for summation comes from fact that sum(1 to n) = n(n+1)/2. But if ...