texts: How does time/space complexity work with lisp

texts:
I'm completely new to programming but I've had a course in computational complexity.  I'm trying to read the book "Structure and Interpretation of Computer Programs."  In the first few sections, the authors make some claims about the relative efficiency of tree recursive and iterative processes.  I find it a little frustrating that they don't formalize exactly what that mean by the run time of a program.  They do mention that the interpreter uses applicative order evaluation. The problem is that it's still not totally clear what counts as one "step" of the process. For instance if one uses applicative order to evaluate the the 5th element in the sequence of Fibonacci numbers using the tree recursive algorithm fib(n)=fib(n-2)+fib(n-1), one gets

(Fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0))) (+ (+ (fib 1) (fib 0)) 1))

(+ ( + (+ (+ (fib 1) (fib 0)) 1) (+ 1 1)) (+ ( + 1 1) 1))

(+ ( + ( + ( + 1 1) 1)  2) ( + 2 1))

(+ (+ (+ 2 1) 2) 3)

(+ (+ 3 2) 3)

(+  5 3)

8

So there are ten steps, and in general fib(n) will take 2n steps: n to get to the bottom of the tree, and n to come back up.  It's claimed, however, that the run time is asymptotic to fib(n). I can sort of see intuitively why this is true; the number of times in the process that two numbers are added together is clearly about fib(n), but I was hoping there is a more exact definition of run time.  Any help is appreciated.


texts: Maximum Weight Independent Set in Circular-Arc Graphs (Proof of A Lemma)

texts:
I am reading the paper: "Maximum Weight Independent Set Of Circular-Arc Graphs and It's Applications" (http://link.springer.com/article/10.1007%2FBF02832044). And I had a question regarding the proof of Lemma 3 in the paper. It is stated as follows.

If $X$ is the maximum weight independent set of the circular-arc graph $A$, then for any clique $Z$ of $A$, we have that $\| X \cap Z\| = 1$.

The paper then proves this by contradiction in two cases, the first when $\| X \cap Z\| \geq 2$ and the second when $\| X \cap Z\| = 0$. I buy the argument for the first case, but I am concerned about the argument they make for the case equal to 0. Their argument goes as follows: If $\| X \cap Z\| = 0$, then including any vertex in $Z$ into $X$ will remain independent and the weight will be greater than the previous set, contradicting the fact that $X$ was a maximum weight independent set. To me, this statement does not seem true.

If we pick vertices 8, 6, and 3 to have weight 1000, and all other vertices to have weight 1, then clearly {8, 6, 3} is a maximum weight independent set. However, their exists cliques of size two (edges) that have an empty intersection with {8, 6, 3}... such as the edge {1, 2}. You can also extend this to cliques of size 3 by adding an arc that intersects with arcs {8, 2, 1} then the clique formed by this new arc and arcs 1 and 2 will have an empty intersection as well.

So where have I gone wrong in my understanding? I feel like I must be missing something really obvious. Clarifications would be greatly appreciated!


texts: Logistic model and Linear regression model

texts:
I am reading the book "An introduction to statistical learning with applications in R". I am reading Logistic Regression and I don't understand why when it's compared to linear regression model, the author said that "the problem with this approach: for balances close to zero we predict a negative probability of default; if we were to predict for very large balances, we would get values bigger than 1." as in the highlight. Could anyone please explain me how the probability can be smaller than 0 or larger than 1?

Your help is really appreciated!

Thank you


texts: I want to know whether the 2-DNF problem is NP-complete or not? If it is NP-complete, can anyone provide a proof?


texts:
I was given the following grammar

$S \rightarrow S (  S  ) S\mid \epsilon$

First I was asked to eliminate left recursion, yielding me the following :

$S \rightarrow S' $

$S' \rightarrow (S)SS' \mid \epsilon$

I was then asked If the grammar is LL(1). So I computed the FIRST and FOLLOW sets shown below:

$\mathrm{FIRST}(S) = \mathrm{FIRST}(S') = \{ ( , \epsilon \}$,

$\mathrm{FOLLOW}(S) = \mathrm{FOLLOW}(S') = \{ \$, ( , ) \}$.

I now tried building the LL(1) parsing table $M$ as follow:

Since we have production $S \rightarrow S' $ and $\mathrm{FIRST}(S') = \{ ( , \epsilon \}$, the table's entry  $M [ S , ( ] = S \rightarrow S'$.

But since $\epsilon$ belongs in $\mathrm{FIRST}(S')$ then for each element $b$ in $\mathrm{FOLLOW}(S)$,

$M [ S , b ] = S \rightarrow S' $.

This would entail that $M [ S , ( ] = S \rightarrow S' $.

Since the entry was already populated, is this a conflict? If yes, what kind?

Or since the 2 productions are the same we can just ignore it?

Also if the second case is the right one, is the grammar LL(1)?


texts: Collection of real world non computable programming tasks

texts: I'm quite new to computability theory and would be interested in some examples of realistic programming tasks you could encounter when working as a C++ programmer that are not computable.


texts:
How can a operating system run on more than one CPU architecture?

Does the OS detect what type of architecture it is currently running on?
If so, does it simply use a different set of code for that architecture?

How does the CPU detect the type of architecture?


texts: Fibonacci Heap / Binomial Heap - Decrease Key

texts:
I've been implementing a Fibonacci Heap in C this past week and today I just hit a mental roadblock that I can't figure out.

Decrease Key is a function that almost all min heaps have (vice versa with increase key with max heaps). However all of the decrease key functions declarations look like this:

// Big Theta 1 performance.
void decrease_key(Node n);

That's great, but what about Node find_node(Object data);?

Before you can decrease the key of the node, you have to locate it first. So the call of

decrease_key(52,17) first needs to search for 52, then update it to 17, and then restructure the tree (unless structure is lazy, such as fib tree). Doesn't that absolutely murder the complexity of that call? Locating an element in the tree cannot be fast. You'd approach n very quickly, only skipping Node roots that are greater than the element you are looking for (since their children are even larger).

None of the documents online which feature Fibonacci heaps or binomial heaps talk AT ALL about locating a node inside the tree. I assume that I just loop over each node, and perform the following logic?

for every node n in the list
   int c = compare(n, data)
   if (c > 0)
      call logic recursively on his child
   if (c == 0)
      decrease_key(n, data)
   otherwise
      error cannot compare greater

Furthermore, why is there a decrease_key but not a increase_key, or frankly a set? I suppose increase_key is a much harder problem to solve?

Thanks


texts: Understanding the Space Hierarchy Theorem and its proof

texts:
This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake.

The intuition behind the Space Hierarchy Theorem is that

"there are Turing Machines using s1 space that can perform computations not posible using s2 < s1 space"

s2 < s1 means that s1 uses O(f(n)) space and s2 uses O(g(n)) space and g = o(f) (the magnitude of g is less than the magnitude of f)

Following the sketch of the proof in wikipedia (claimed to be bogus):

Define language L

L = { T | T(T) = "reject" using O( f|T| ) space and less than $2^s$ steps }

// Note: f(n) is space constructible, $s = f(|T|)$
Define the following Turing Machine M1 that computes L

M1( T ) =

compute s = f( |T| ) the limit of usable space (this calculation can be done, by assumption, also in O( s ) space )
simulate T(T) watching that no more of s space and $2^s$ steps are used
If 2. is violated: return "reject T" (and stop).
return the opposite of T(T) (and stop).

By construction language(M1) = L.
M1( M1 ) = "reject" because  M1 emulates its input in step 2. and M1(M1) will result in an
infinite recursive call that eventually will consume space s.
Since M1( M1 ) = "reject", then M1 $\not\in$ L since language(M1) = L    (1)
Does M1 uses only O( f(|M1|) ) space? No, or otherwise M1 $\in$ L because it would satisfy L conditions (M1(M1)="reject" and M1 uses O((f(|M1|)) space). This would contradict (1).
// Caution: wikipedia says "L is in SPACE( f(n) )"

Thus M1 or any other TM recognizing L  uses MORE than O(f(|M1|) space. MORE is k(n) where f(n) = o(k(n)).
In sum, M1 is a TM able to compute a language, using O(k(n)) space, that no machine can compute in f(n) = o(k(n)).
References
Wikipedia SHT
Question about SHT
Question' about SHT


texts: A connected acyclic graph has $n-1$ edges

texts:
Let $G$ be an undirected graph with $n$ nodes. Prove that any two of the following implies the third:

$G$ is connected
$G$ is acyclic
$G$ has $n-1$ edges

Proving $1, 2 \implies 3$
A connected, acyclic graph is a tree. Each node(vertex), except the root, in the tree has exactly one edge going upwards(towards the root), hence it has $n-1$ edges.
The Problem
I'm not able to write a formal proof for the other two. The problem is that here I used the fact that connected, acyclic graph is a tree and then it was easy to prove using properties of a tree, for the other I tried using contradiction but couldn't prove them.
Any hint on how to approach this problem and how to prove $1, 2 \implies 3$ without using the fact that connected acyclic graph is a tree?
Reference
This problem is from Chapter 3 of Algorithm Design by Jon Kleinberg and Éva Tardos. Addison-Wesley


texts:
I see that Σ* is claimed to be decidable in many documents, but I have never seen an example or easy demostration that it is decidable.

What is the proof that Σ* is decidable?


texts: Are the following Big Oh Notations equivalent?

texts:
In the context of Upper bounds computaion and Big Oh Notation, I was wondering if the following could be proved... if they are equivalent.
$\mathcal{O}((log(n))^{-1}) = (\mathcal{O}(log(n)))^{-1}$

$\mathcal{O}((log(n))^{-1})$ can be rewritten as
  $\mathcal{O}(1/(log(n)))$  which is
$\mathcal{O}(1)/ \mathcal{O}(log(n))$ . This can be simplified to
$1/ \mathcal{O}(log(n))$
which is the same as the RHS. Would this be a possible solution? Any mistakes that are pointed are welcome.


texts: Can a deterministic finite automaton ever go into an infinite loop?

texts: As the title suggests, is this possible? Or does it halt execution when it hits the trap state? Thanks to anyone who can clear this up.


texts: Why is there a 2n+1 comparison for a linear search algorithm?

texts:
Suppose an algorithm goes through a list of n integers and for every iteration of the loop it is needs to check if the current evaluated element of the list is even. If it is even, return the index of the integer that is evaluated as even.

How come the algorithm would have 2n+1 comparison?

I thought linear search would have n comparision because it is going through n elements. +1 comparison for the if statement. So that would make the algorithm O(n+1) comparison, no?. Where did the extra n come from?

Pseudo-code:

procedure last_even_loc(a1,a2,...,an:integers);
location = 0;
for i = 1 to n

    if (a_i = 0) (mod 2) then location = i

return location;


texts: Resource Allocation Graph: Two processes want the same resource

texts: In the example below, is this guaranteed to be safe? I see two processes that require the same resource. It's not a direct cycle but it seems to be a possible deadlock where P0 could get held up.


texts: Semidecidability/Decidability for strings seperated by a non alphabet symbol

texts:
I am trying to prove the following:

Let $\Sigma $ be an alphabet not containing the symbol "$;$", and suppose that
$L \subseteq \Sigma^*$; $\Sigma^*$ is recursively enumerable. If this is the case language $L' = \{x \in \Sigma^*: x; y \in L \ for \  some \ y \in \Sigma^*\}$ is recursively enumerable.

which left me a little bit confused. Since $";"$ is not in the alphabet $\Sigma$ should I seperate $x$ and $y$ and show that check for $x \in \Sigma^*$ and $y \in \Sigma^*$ is recursively enumerable?

Also, will this statement be the case if we checked for being recursive instead, that is if $L$ was recursive, is $L'$ necessarily recursive as well? And is the proof of this the same with the recursively enumerable case?

Any help will be appreciated.


texts: Union of halting-like problem and non-halting-like problem

texts:
I came across the following problem:

Define languages $L_0$ and $L_1$ as follows :
$L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$
$L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$
Here $⟨M,w,i⟩$ is a triplet, whose first component $M$ is an encoding of a Turing Machine, second component $w$ is a string, and third component $i$ is a bit.
Let $L=L_0∪L_1$. Which of the following is true?
A. $L$ is recursively enumerable, but $\overline{L}$ is not
B. $\overline{L}$ is recursively enumerable, but $L$ is not
C. Both $L$ and $\overline{L}$ are recursive
D. Neither $L$ nor $\overline{L}$ is recursively enumerable

I first felt that despite the bit as a third member of triple, $L_0$ is still equivalent to halting problem and $L_1$ is non halting problem. Union of halting and non halting problem is recursive as can be seen here. So, same will apply to the languages in the problem and their union will also be recursive, that is option C. But the answer given was D. So am guessing if its correct or not. I was not able to guess how that extra bit in the triple makes it different from halting problem.


texts:
Consider the following naïve argument that any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario.

Let $f(x_1,x_2,\dots,x_n)$ be a Boolean function in conjunctive normal form (CNF). The problem SAT is to determine whether there exists a $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ such that $f(x_1,x_2,\dots,x_n)=1$. Nothing is known a priori about the function $f$, so in general, in order to determine this information, it is necessary to plug in each $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ into $f(x_1,x_2,\dots,x_n)$ to test whether $f(x_1,x_2,\dots,x_n)=1$, until one is found to satisfy $f$ or all are found not to satisfy $f$. There are $2^n$ possible $(x_1,x_2,\dots,x_n) \in \{0,1\}^n$ to plug into $f(x_1,x_2,\dots,x_n)$ to test. Therefore, any algorithm solving SAT must take $\Omega(2^n)$ time in the worst-case scenario. So $P \neq NP$. QED

What exactly is wrong with this argument? More importantly, are there any known counterexamples (algorithms that take $o(2^n)$ in the worst case scenario for SAT)?

Caveat: Note that there are known counterexamples if one restricts $f$ to being in 3CNF, but this is only because 3CNF has a special structure that plain CNF does not have. Plain CNF has no special structure at all, since any Boolean function can be placed in CNF.


texts: About a universal (functionally complete) function producing a constant

texts:
I read in a note the following:

Suppose we have a boolean function $f(x,y,z,w)$, if $f(a,a,a,a)=1$ then $f$ can't be functionally complete.

Why is that? how does it imply that $f$ can't produce nand or nor?


texts: generate possible inputs valid for automata

texts:
I find lots of solution where you have an Automata and a input string , you can validate whether input string is accepted by automata or not.

Can we do the reverse ?

I am looking for solution which generates few possible inputs (not all) accepted by automata(NFA/DFA).

One of the Brute-force approach can be to randomly select inputs and validate with automata if passes then consider those as desired .

But really don't want that . What really am i looking for here, can we use automata itself for produce possible inputs which are accepted by automata.

Any approach also would be helpful.


texts: What is the name of this code transformation that uses associativity of addition?

texts:
I am learning about compiler optimization technique and there is a technique that use associativity of addition to transform code.

For example, consider the following expression:

(a + b) + ((c + d) + e)

It can be transformed into:

a + (b + (c + (d + e)))

Does anybody know the name of this transformation?


texts:
I am reading about P and NP and looking at the reduction of a Rudrata/Hamiltonian path to a Rudrata cycle. I think adding an extra node and 2 edges connecting the start, s and the target, t is O(1) time as this doesn't depend on the size of the graph. Algorithms by Dasgupta et al. says that the pre and post processing steps take polynomial time.

One last detail, crucial but typically easy to check, is that the pre- and postprocessing functions take time polynomial in the size of the instance
(G, s, t).

This makes me think that O(1) is polynomial time. Is this incorrect?


texts: Determining whether the language of a DFA is closed under reversal

texts:
The question and its answer is given below:

Let $S = \{ \langle M \rangle \mid \text{$M$ is a $\textsf{DFA}$ that accepts $w^{\mathcal{R}}$ whenever it accepts $w$}\}$. Show that $S$ is decidable.
Answer:
For any language $A$, let $A^{\mathcal{R}} = \{w^{\mathcal{R}} \mid w \in A\}$. If $\langle M \rangle \in S$, then $L(M) = L(M)^{\mathcal{R}}$. The following $\textsf{TM}$ $T$ decides $S$.
$T = $ “On input $\langle M \rangle$, where $M$ is a $\textsf{DFA}$:

Construct $\textsf{DFA}$ $N$ that recognizes $L(M)^{\mathcal{R}}$.
Run $\textsf{TM}$ $F$ from Theorem 4.5 on $\langle M,N \rangle$, where $F$ is the Turing machine deciding $EQ_{\textsf{DFA}}$.
If $F$ accepts, accept. If $F$ rejects, reject.”

But I do not understand in the first line of the answer, in the second statement why does it say that $L(M) = L(M)^{\mathcal{R}}$, could anyone explain this for me please?


texts: Prove or disprove: L^2 context free implies L is context free

texts: Clearly we have to disprove this. But I am finding it hard to prove it. I was trying in following way: Considering any non context free language L. I was trying to prove that L^2 is context free which will contradict given statement. But I don't know to how to prove it. Because by pumping lemma we can show only that language is not CFL but converse is not true. Can you please help me. Or is there any other way to prove it. Thanks


texts:
Why is $\log_{2}n = O(n^{0.00001})$ true?

This is obvious to me when the exponent is $> 1$ but i'm having trouble understanding the cases where the exponent is very close to $0$. I would have to find some constants $c$ and $n_0$ where $\log_{2}n \le cn^{0.00001}$ for all $n \gt n_0$.

Where I'm stumped is that $n^{0.00001} \approx 1$ and $\log_{2}n$ approaches infinity as $n$ gets larger. It feels like regardless of whatever $c$ and $n_0$ I choose, if $n$ was large enough, I could show that $\log_{2}n \ge c$.


texts:
Here is a simple turing machine, that accepts only $0$.

For this, it read $0$, write it with $x$, then move to right and checks end, if it is end it accepts.

With that logic, I can also add this 1->x,R, then it accepts all strings of length 1, {'0','1'}.

What I want to do is, instead of writing to logic I want to write one, $anything$ -> $another_thing$,R.

Can I do it?


texts: Why is it necessary to use binary numbers in logspace?

texts: I have noticed that a lot of problems that are in L and NL use binary numbers. I don't understand why this is the case. Does a TM use less space by storing a binary number, than a "normal" one. In my head, it uses less space to store the number 0, than the binary ecquivalent number 0000. Hope someone can help me understand :)


texts: Minor Mistake in Computability, Complexity, and Languages?

texts:
In the book Computability, Complexity, and Languages (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions):

  A partial function on a set $S$ is simply a function whose domain is a subset of $S$. An example of a partial function on $\mathbb{N}$ is given by $g(n) = \sqrt n$, where the domain of $g$ is the set of perfect squares.

So far so simple. But he goes ahead and writes a couple lines later at the end of the section:

  We will sometimes refer to the idea of closure. If $S$ is a set and $f$ is a partial function on $S$, then $S$ is closed under $f$ if the range of $f$ is a subset of $S$. For example, $\mathbb{N}$ is closed under $f(n) = n^2$, but is not closed under $h(n) = \sqrt n$ (where $h$ is a total function on $\mathbb{N}$).

So in the first quote $\sqrt n$ on $\mathbb{N}$ is an example for a partial function, whereas in the second quote the same function is an example for a total function.

Both examples seem to contradict each other. Or am I missing something in regard to closures here?


texts: Is there a prefered name for the “effective access time” formula?

texts:
Any CS class about caches will at some point address this classical formula (or a variant of it)

Effective_access_time = hit_time + miss_penalty * miss_rate

My question is simple: does this formula have a "name" ? (i.e. unambiguous, and ideally, well-accepted too). I found plenty of references to many variants of that concept. I'd like to know whether there exists one name to denote them all. By the way, the question makes sense : there are plenty of variants of the following sentence...

  In any square triangle, the square of the length of the hypotenuse is equal
  to the sum of the squares of the lengths of the two shorter sides.

...but we prefer to refer to them all by the name "Pythagoras' theorem".


texts: What kind of pattern recognition algorithm would Facebook use to detect suicidal users?

texts:
Facebook announced that it would employ a machine learning "reporting process using pattern recognition in posts previously reported for suicide" (https://newsroom.fb.com/news/2017/03/building-a-safer-community-with-new-suicide-prevention-tools/).

Could anyone explain in more detail how this pattern recognition algorithm might work in their reporting system? Is it possible to say what kind of classification algorithm are they most likely using? Something similar to a spam filtering algorithm?

Here's the section I quoted from:

"Based on feedback from experts, we are testing a streamlined reporting process using pattern recognition in posts previously reported for suicide. This artificial intelligence approach will make the option to report a post about 'suicide or self injury' more prominent for potentially concerning posts like these. We’re also testing pattern recognition to identify posts as very likely to include thoughts of suicide. Our Community Operations team will review these posts and, if appropriate, provide resources to the person who posted the content, even if someone on Facebook has not reported it yet"


texts: why it said the "The left recursion has been removed at the cost of an extra non-terminal symbol(E1) and a little extra complexity"?

texts:
When I read the book "A Practical approach to compiler construction" the chapter 4 "approaches to syntax analysis" and the section 4.2.3.3 Left Recursion, it says:

  "The left recursion has been removed at the cost of an extra non-terminal symbol"

I have no idea why say that, since $A_1$ still contain recursion?


texts: Minimal Deterministic Buchi Automata Product

texts:
Problem:

Let $\varphi = \varphi_1 \land \varphi_2$ be Deterministic Buchi Automata (DBA) expressible LTL formulas.

Let $A$, $A_1$ and $A_2$ be translated DBAs such that ${\cal{L}}(A) = {\cal{L}}(A_1) \cap {\cal{L}}(A_2)$.

What can be said about the relation between the number of states in $A$ and that in the synchronous product $A_1 \otimes A_2$?

Some background:

I found two definitions of the Buchi product, the one given by Vardi in An Automata-Theoretic Approach to Linear Temporal Logic that uses $S = S_1 \times S_2 \times \{1, 2\}$ while the one demonstrated in this presentation uses $S = S_1 \times S_2 \times \{1, 2, 3\}$.

Also, Ehlers has proposed an approach to minimize the DBA in this paper.

However, I have been unsuccessful in finding any rigorous mathematical relation between the sizes of translated DBA $A$ and the minimal synchronous product of $A_1 \otimes A_2$.

My question:

I would like to know about

Any work regarding the size of Minimal DBA Product
Any work about the relation between the number of states.
How to construct the minimal DBA Product, given $A_1$ and $A_2$.


texts: Variant of nim game with particular rules

texts:
Let's say we have the following rule for that particular Nim game: You have multiple heaps, and you have to remove 1,2 or 3 sticks (not more) from a SINGLE choosen heap. The player who pick up the last stick LOSES. (misere game). Is there an algorithm which solves this variant of Nim game ?

Thanks in advance!


texts: Construct a grammar over {$a,b$} whose language is {${a^mb^ia^n | i = m+n}$}

texts:
I am a little confused on how to approach this problem. I am unsure how to construct both parts of the grammar using a context-free grammar.

This is as far as I got, but this will end up producing a's inside of the group of b's and a's. I'm not sure how to add the second group of a's to the right of the b's.

$S \rightarrow aSb \ | \ A$

$A \rightarrow bAa \ | \ λ$

This language should produce strings like

$abba, aabbba, aaaabbbbbbaa$


texts: An algorithm that find the max X/Y in a polygon in O(log n)

texts:
I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$.

The polygon is represented by an array of its vertices where each vertex is represented by its coordinates $(X,Y)$.
We also know that the first vertex in the array has the smallest $X$ coordinate and after that, all the other coordinates are set in the array clockwise and also that all of them are different (all the $X$'s and all the $Y$'s are different)

I have the general idea.. using binary search but I'm not sure how to fully apply it.

How should move in the array while checking coordinates and yet keeping it in $O(\log n)$ complexity?


texts:
In the general Steiner tree problem (Steiner tree in graphs), we are given an edge-weighted graph G = (V, E, w) and a subset S ⊆ V of required vertices. A Steiner tree is a tree in G that spans all vertices of S. There are two versions of the problem: in the optimization problem associated with Steiner trees, the task is to find a minimum-weight Steiner tree.

This is an online compendium on approximability of the Steiner Tree and related optimization problems: http://theory.cs.uni-bonn.de/info5/steinerkompendium/

I am currently studying different Steiner tree variants on Graphs and i had already read Compendium but i haven't found the following cases.

INSTANCE: Graph  $G=(V,E)$ , unweighted edges ,given a set of terminals $S\subset V$.
SOLUTION: A tree T=(${V_t},E_t$) in G such that $V_t$ number is minimum, $S\subset V_t\subset V, E_t\subset E$.

This problem looks like set cover problem or Vertex Cover for a specified subset of V. Also asked here:
Minimal Steiner Tree in unweighted directed graph
https://cstheory.stackexchange.com/questions/19477/steiner-tree-problem-for-unweighted-graphs for complexity only.
also here: https://stackoverflow.com/questions/3975763/minimum-connected-subgraph-containing-a-given-set-of-nodes/
and here: https://stackoverflow.com/questions/10056212/minimum-spanning-tree-between-a-start-location-and-a-set-of-required-nodes

INSTANCE: Graph  $G=(V,E)$ , edge weight->$\mathbb{R^+}$ , given a set of terminals $S\subset V$, node weight->R+. SOLUTION: A tree T=(${V_t},E_t$) in G such that T Prize(node and edge weights) is maximum and number of edges is minimum (Ratio:NodesWeights/NumberEdges) , $S\subset V_t\subset V, E_t\subset E$. (maximum path with minimum hopes-jumbs-edges).

This problem looks like Prize-Collecting Steiner Tree Problem.

INSTANCE: Graph  $G=(V,E)$ , edge weight->$\mathbb{R^+}$ , given a number for terminals $S\subset V$, where each S is adjacent to at least one other S, node weight->R+.
SOLUTION: A tree T=(${V_t},E_t$) in G such that T Prize(node and edge weights) is maximum ,$S\subset V_t\subset V, E_t\subset E$.

I want to know if any of these cases can be transformed into already known cases or if they are already exists. Are all of them Np ?


texts: Minimum number of swaps required to have an alternating array

texts:
We are given an array with only $0$s and $1$s. The number of $0$s is greater or equal to the number of $1$s. The goal is to ensure that there is not a pair of $1$s adjacent to each other. We can only read the value of an element or to swap 2 elements. What is an algorithm for the fewest swaps possible?
I tried swapping central elements in any $0011$s and $1100$s first, then finding $000$s, saving their positions in an auxillary array, then putting them wherever we could not do $0011$ or $1100$ swap, but to both orders of these operations there were counterexamples.
The exercise is a preparatory one for a test, but it was marked as harder and no one in my class was able to solve it.


texts: How to define the Atomic Propositions in Model Checking

texts:
The atomic propositions in Symbolic Model Checking form the state in the state-transition graph (the model $\mathcal{M}$ in Model Checking). The other part of Model Checking is the specification, which is usually some sort of temporal logic formula over the atomic propositions in the model.

My question is about the atomic propositions themselves. I have only seen a few rudimentary examples of them, such as $x = 20$ or $printer is busy$. These atomic propositions (I think) are stating a fact about the state of the program at that point in the system. You then use a temporal logic formula to see if the model holds under it. I am confused by how the atomic propositions are both defined and used.

First, how they are defined. I haven't seen anywhere a description on how you define these atomic propositions. That is my first question. I don't understand how stating $x > 100$ in a state in the model $\mathcal{M}$ means anything. I didn't have to prove it or anything. It was just stated as fact. Then the temporal logic formula comes along and is checked against it, but there's some disconnect there for me. The value was never proven correct in the first place. It's as if, in my program, I make an HTTP request and during the waiting period before a response, my atomic proposition is that $\mathtt{the\ sky\ is\ blue}$. Wondering why was it put there, how do I know that it is true. A better atomic proposition would be $\mathtt{the\ request\ was\ sent}$. But again, I don't see how the program/model/checker "knows" this. I don't see what is doing the verification that that statement is true.

So my question is basically, how you define atomic propositions in Symbolic Model Checking. What goes into them. How you are allowed to make such statements that seemingly aren't verified. I don't see how I can say anything about the state of the program without something else "checking" that yes $\mathtt{the\ request\ was\ actually\ sent}$. I understand that after we define this model, we have our specification formulas and check them against the model. But we never checked the model itself for accuracy, is what I'm trying to get at.

I feel like, after writing down, in a specific state, an atomic proposition, I would then need to write a unit test to verify that it was true for some input. Not sure what I'm missing.


texts:
I am reading the proof of PCP theorem in Proof Verication and Hardness of Approximation Problems. The following paragraph appears in section 3 (page 4), "Outline of the Proof of the Main Theorem".

  The results of these sections show that $NP \subset OPT (poly(n), 1)$ (Theorem 5) and $NP \subset OPT (\log n, poly \log n)$ (Theorem 8). Theorems 9 and 10 show that the recursion idea applies to these proof systems, and in particular shows the following:

  $OPT (f (n), g(n)) \subset OPT (f (n) + O(\log g(n)), (\log g(n))^{O(1)} )$ and
  $OPT (f (n), g(n)) \subset OPT (f (n) + (g(n))^{O(1)} , 1)$.

  This allows us to conclude that $NP \subset OPT (\log n, poly \log \log n)$ (by composing two $OPT (\log n, poly \log n)$ proof systems) and then by composing this system with the $OPT (poly(n), 1)$ proof system we obtain $OPT (\log n, 1)$ proof system for $NP$.

Edit. Composition of verifiers is defined in Probabilistic Checking of Proofs: A New Characterization of NP  section 3 (page 13) "Normal Form Verifiers and Their Use in Composition".

  Let $r, q, s, t$ be any functions defined on the natural integers. Suppose there is a normal-form verifier $V_2$ that is $(r(n), s(n), q(n), t(n))$-constrained. Then, for all functions $R, Q, S, T$, $$RPCP(R(n), S(n), Q(n), T(n)) \subseteq \\RPCP(R(n) + r(\tau), s(\tau), Q(n) + q(\tau), Q(n)t(\tau))$$ where $\tau$ is a shorthand for $O((T(n))^2)$.

Where $RPCP(r, s, q, t)$ is a $PCP(r, s \cdot q)$ which takes $t$ time to accept of reject after reading the $s \cdot q$ bits.

I still don't see how this composition works. Is $OPT(r, q) = RPCP(r, q, 1, q)$ and a normal form verifier? In that case it seems to work, but then just composing $OPT(poly(n), 1)$ with $OPT(\log n, poly \log n)$ is enough, so why bother with $OPT(\log n, poly \log \log n)$ or relations $1.$ and $2.$?


texts:
I am creating an event notification system.

Each event has a user and a subject, such that, 'user did event to the subject'. Now while presenting these the events need to be grouped.

All the events in the same group must either refer to the same user or the same subject and each event must be in exactly one group.  Subject to those constraints, a group can contain any number of events, including just one. I want to calculate the grouping that uses the least possible number of groups.

Note that forming one group for each user, or forming one group for each subject does not, in general, give the smallest possible number of groups. Also, the events cannot, in general, all be placed in the same group, as that usually gives a group containing multiple users and multiple subjects, which is forbidden.

If I start from the first event and start putting it in the group with most possible events (acting all greedy), I will end up with a sub-optimal solution.

I could check all possible groupings but that will blow up exponentially ($2^n$ possible groupings for just n events).

How can I go about optimally grouping these events such that most of the events get grouped one way or the other, minimising the total number of groups?

Sample data -

event1    user1    subject1
event2    user2    subject1
event3    user3    subject1
event4    user2    subject2
event5    user3    subject2
event6    user1    subject3
event7    user2    subject4
event8    user2    subject5
event9    user3    subject5
event10   user1    subject5
event11   user4    subject1
event12   user4    subject2
...


texts: How to understand quantifier without predication " ∀(λφ. (φ x m→ φ y))"?

texts:
I am reading about embedding/automation of modal logics in classical higher order logic (http://page.mi.fu-berlin.de/cbenzmueller/papers/C46.pdf) and Goedels proof of God's existence is prominent example here https://www.isa-afp.org/entries/GoedelGod.html (as encoded for Isabelle/HOL).
This embedding has embedding for Leibniz equality for individuals:
abbreviation mLeibeq :: "μ ⇒ μ ⇒ σ" (infixr "mL=" 90) where "x mL= y ≡ ∀(λφ. (φ x m→ φ y))"

and this type of euqality is used for the first axiom already:
A1a: "[∀(λΦ. P (λx. m¬ (Φ x)) m→ m¬ (P Φ))]"

which can be written without lambdas as:
A1a: ∀φ[P(¬φ)↔¬P(φ)]

My question is - how to understand the expression ∀(λφ. (φ x m→ φ y)), because usually we have ∀x.P(x)? I.e. universal quantifier expects the argument (x) and the predicate (P(x)), but this expression contains noone know what? is entire (λφ. (φ x m→ φ y)) and argument x or Predicate P(x)? What can be omitted here, what is the convention used here?


texts:
I want to determine which parts of an audio file contain speech respectively music.

I hope someone has a made something like this or can tell me where to start. Can you please suggest some method or tutorial for doing the same?


texts: Serializable schedules but not view serializable

texts: I know that to check if a given schedule is serializable we can test for either view serializability or conflict serializability. But do serializable schedules exist which are not view serializable?


texts: Looping and branching with Algorithmic Differentiation

texts:
Algorithmic (aka Automatic) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary operation in a computer program, but I am not sure to get how this applies to every computer program.

To quote from this wikipedia page:

  every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations

.. which I totally agree with. However, it sounds then that the number $m$ of variables newly produced from any $n$ initial input is fixed and can be determined from static code analysis. But this is not straightforward to me since constructs like:

if x_1 > x_2:                         # branching
    perform 4 elementary operations
else:
    perform 84 elementary operations
endif

and:

while x_1 < x_2:                      # looping
    perform 2 elementary operations
endwhile

do exist in so-called « complicated » computer programs. This make the number (and the type) of elementary operations not straightforward to compute in advance. And I even suspect it is impossible to gess that in general, right?

Does AD support such branching and looping programs?
Are there extensions of AD adapted to programs that are not just intricate closed-form expressions?
How does AD deal with Turing-completeness?


texts: Understanding definitions of Deterministic Context Free Grammar and Deterministic Pushdown Automaata

texts:
I read following here:

  Unambiguous grammars do not always generate a DCFL.
  Example:
  For example, the language of even-length palindromes on the alphabet of 0 and 1 has the unambiguous context-free grammar S → 0S0 | 1S1 | ε. An arbitrary string of this language cannot be parsed without reading all its letters first, which means that a pushdown automaton has to try alternative state transitions to accommodate for the different possible lengths of a semi-parsed string.

Now I am confused about definition of Deterministic Context Free Language or Deterministic Context Free Grammar.

According to wikipedia, DCFG are those that can be derived from Deterministic Pushdown Automata and they generate DCFL.

I read

  A CFG is deterministic iff there are no two productions with the same terminal prefix on the right side of them.

I find that this condition applies on above example grammar. But still the grammar is said to not generate DCFL. Thus, it seems that this definition wrong, because the condition "no two productions with the same terminal prefix on the right side of them" holds on above grammar and above grammar does not seem to generate DCFL. Q1. So is it indeed wrong?

  DPDA is defined as pushdown automata that never has a choice in its move (for any given next input character and stack top).

It seems that above definition of DCFG is wrong because it puts all importance on input string, whereas definition of DPDA puts condition on both input character and stack top.

Q2. However then how exactly these conditions in the definition of DPDA failed for above example CFG?


texts: Partition a bipartite graph to a complete matching and an independent set

texts:
I am looking for a reference for the following theorem:

Let $G$ be a bipartite graph with partitions $X$ and $Y$, each with the same number of vertices ($n$).

There is a nonempty subset $Y_1 \subseteq Y$, and a partition of $X$ to disjoint subsets $X_1$ and $X_2$, such that:

There is a complete matching between $X_1$ and a subset of $Y_1$;
There are no edges between $X_2$ and $Y_1$.

Intuitively, $X$ can be seen as a set of men and $Y$ can be seen as a set of women. An edge between $x \in X$ and $y \in Y$ means that "$x$ and $y$ like each other" ("like" is considered a symmetric relation).

The goal is to find a subset of the women ($Y_1$) and a subset of the men ($X_1$), such that each man can marry a woman he likes without upsetting any of the other men ($X_2$), because no unmarried man likes any married woman.

This sounds similar to Hall's marriage theorem, but the premise is simpler. And, I am mainly looking for a reference that I can cite.

Some special cases:

If the graph is full (i.e. any man likes any woman), then we can take $Y_1=Y$, $X_1=X$, $X_2=\phi$.
If the graph is empty (i.e. no man likes no woman), then we can take $Y_1=Y$, $X_1=\phi$, $X_2=X$.
If there is $y \in Y$ with no neighbours (i.e. a woman that doesn't like any man), then we can take $Y_1={y}$, $X_1=\phi$, $X_2=X$.
If there is $y \in Y$ with a single neighbour $x \in X$  (i.e. a woman that likes a single man), then we can take $Y_1={y}$, $X_1={x}$, $X_2=X-{x}$.

The question becomes more problematic when all $y \in Y$ have at least two neighbours.


texts: How can I restructure matrices to have non-zero elements close to the diagonal?

texts:
I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members of class $j$.

The order of elements does not matter, but $c_{ii}$ has to be the correct predction of class $i$. So for any given matrix $C$ you can swap columns if you swap the same rows.

How can I order the classes $1, \dots, n$ so that the biggest elements are close to the diagonal?

I thought one might pose this as an optimization problem, e.g. minimize
$$\sum_{i = 1}^n \sum_{j=1}^n C_{ij} \cdot {|i-j|}$$

How could I minimize this?

Code and example

I've already visualized a $369 \times 369$ matrix without any optimization. The confuscation matrix as JSON file and the code are here.

Without modification, you get a score of 303535 for:

This looks as if there could be some improvement. A quick first thought was to just randomly swap rows. Letting this run for $10^4$ steps (~5 minutes) leads to a score of 82552 and a visualization which looks a bit cleaner:

Doing this, I realized that my score might also need some improvement. I instead of moving elements to the diagonal, it would be nice if big blocks within the matrix would only contain zeros.

The total number of possibilities to arrange the items in $C$ is equal to the number of permutations of a list of length $n$ and hence it is $n!$. Hence for $369$ classes it is already $369! \approx 10^{788}$ - too much to brute force.

See also

My similar question on datascience.SE


texts: How could a formal system ever be non-obviously unsound?

texts:
When reading discussions of Gödel's theorems one is always heeded that just because formal system $F$ proves a theorem $T$ that doesn't necessarily mean that when one applies the intended interpretation the theorem is actually true. After all, even if one assumes that $F$ is consistent, it might still be unsound.

But this puzzles me. When setting up $F$ one always makes sure that all the axioms are true under the intended interpretation. Presumably, one would also make sure that all the rules of inference are valid. That is, if all the theorems proven so far are true, then the rules of inference only produce further true theorems. Is that too much to ask?
However, this straightforward construction immediately implies that I can't prove falsehoods under the intended interpretation. Further, I'd be hesitant to even call something for which the rules of inference aren't truth preserving an "interpretation".
But then it seems that unsound formal systems couldn't even exist. So where's the problem with this view?


texts: Dynamic distance from source in a directed graph (only incremental or only decremental)

texts:
At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding some edge between two vertices $u$ and $v$. A query is asking, for some vertex $v$, what is $\mathrm{dist}(\mathrm{source},v)$ – the algorithm should also consider the possibility of being there no path at all, and return $-1$. The number $q$ of all operations (altogether, updates and queries) doesn't exceed $2\times 10^5$.

What I ask for is an algorithm that does the above with complexity significantly faster than the trivial $O((n+m)q)$.

It seems to me that in this problem we should either have a really quick time per operation (update and query), or there is some amortization to happen. If we stored distances from source to all other vertices explicitly, then answering a query would be a single lookup. When updating the graph, some of the distances may decrease, and others stay unchanged. Although one edge insertion can change almost all of the distances, every one of them is going to be some integer from $\{1,\dots,n\}$, so it follows that after any number of edge insertions changing one of the distances could happen at most $O(n^2)$ times, which is acceptable. For that to happen, we would need to somehow detect which distances from source to update, instead of just running BFS again, resulting in $O((n+m)q)$ complexity (the trivial approach mentioned earlier). Also note, that we don't need to answer queries instantly, so the version of this problem with edge deletions instead of edge insertions is exactly the same – all we have to do is "reverse time". In the case of edge deletions, I think it may be possible to somehow maintain the shortest paths DAG, and repair it when erasing an edge from it, but have no idea how.


texts: Since it's called a trap I consider it caused by software, so why it's called a hardware trap? And how does it work?


texts: (Generally) How to specify asynchronous action with side effects using logic equations

texts:
Say you have this function call sequence:

function all() {
  fn1()
  fn2()
  fn3()
}

And say that fn2 was asynchronous and caused all kinds of side effects:

var globalPacketCounter = 0

function fn2() {
  var httpRequest = ...
  httpRequest.on('data', function(){
    globalPacketCounter++
  })
  drawGraphicsToDisplay()
  ...
}

Something complicated and with unknown implementation, though you can probe it to determine the types of behavior it has, and read docs, etc.

I'm wondering, generally speaking, what you can do to incorporate this into a model checking or symbolic evaluation system, or other verification system like Hoare logic or something. I would like to do this:

all() =
  /\ fn1() in state 1
  /\ fn2() in state 2
  /\ fn3() in state 3
  /\ complete = true in state 4

Some sort of logical statement. The question is (partially) if this is a valid approach; that is, treating the fn2() as a single step in a logic equation. The main part of the question though is how to generally do this. I would like to basically treat everything as logic functions but am not sure how to apply it to the "async with side effects" case.


texts:
I am trying to find an algorithm that generates all directed multigraphs with a given number of vertices and arcs up to isomorphism (no two generated graphs should be isomorphic). I also want to allow self-edges.

I have done some research on this, and I found the tool "nauty" which can generate graphs up to isomorphism, but it can't generate directed multigraphs and it can't generate directed graphs with self-loops. Perhaps the nauty library could be used to solve this problem. It can efficiently calculate generators for the automorphism group of a graph. Is there a way that those could be used to generate directed multigraphs?

I can think of a way to generate undirected multigraphs, but it might not help with this problem.

This problem could be solved by solving graph isomorphism an exponential number of times, but that's not feasible. I am looking for an algorithm for which the main growth factor is due to the number of graphs generated. I have not found an algorithm that can count the number of these graphs.


texts: Why is a program with only atomics in SC-DRF but not in HRF-direct?

texts:
In the paper "Heterogeneous-Race-Free Memory Models" [1], the authors state that a program consisting only of atomic is race free in SC-DRF but it is not in HRF-direct. I am not able to understand why this is. Can anyone explain how this can happen?

[1] Derek R. Hower et al., "Heterogeneous-Race-Free Memory Models". In Proceedings of ASPLOS '14, ACM, 2014. (PDF)


texts: Scheduling Algorithm for aperiodic multiprocessor tasks

texts:
I've got a System, which is defined as follows:

A limited number of stations is given (n), which can offer different services (for now there are two services). A station can either offer one of the services or both (maybe it will be extended one day, then it should work with x different services and a station can offer 1..x of these services).
The throughput for a service can differ from station to station.
Each service in the system can have a fixed priority assigned by the developer. If multiple services have to be scheduled and the scheduler isn't able to assign each service at once to a single station, it can split up the services and chose the service with the highest priority to run first and run the other service/s later on. (also see next point)
If a task requests multiple services, it is okay to split them up.  For example, there are two services requested (a and b): requested service a is running on station c for 10 minutes, afterwords it is moving to station d to receive service b.  However, you could also think of this as two separate tasks, each of which requests a single service, if you prefer.
A task can arrive at any time, for example the incoming of a new request.
Each task has an arrival time, an execution time (computed by the requested amount of the service and the amount a station can offer. in other words: this is the time, a particular station will need to complete a task) and a deadline
Different tasks have different execution times.
Arrival time: there are "reservations", then the arrival time is known before the task arrives. but there are other cases, in which the arrival time is not known, so the arrival time equals "now".
A station can serve one task at a time, but a task can request multiple services at once (there are stations which offer these services at the same time, the different services doesn't influence each other).
Tasks can be preempted and moved between stations during execution, meaning that if one task is running on a station the task can be assigned to a different station which offers the same service (this station-change can cause costs, based on the distance between different stations). This could be caused by another task which needs the station the first task was running on until now.
The algorithm has to work in real time.

The System is given and works already with one service, I have to adapt it to work with multiple services. For this, I have to look for and implement a new scheduling algorithm, but I have no idea for what I have to look for. Another possibility is to design my own algorithm, but due to the lack of knowledge in this sector I think it would be a bad idea.

Any hints for what kind of scheduling algorithms I have to look for?


texts:
Suppose I have two stacks $<a_1,a_2,...a_m>$ and $<b_1, b_2,...b_n>$ and a third stack of size $m+n$.
I want to have the third stack in the following manner, $$<a_1,b_1,a_2,b_2,...a_n,b_n...a_m-1,a_m>$$ for $$m>n$$
This was easy to do if the two initial stacks were not size constrained. But if the two stacks are size constrained, I am in a fix.

Is it even possible to interleave the elements of the two stacks into a third stack in constant space? Also what would be the minimum number of moves to do this? I know using recursion this can be reduced to Tower of Hanoi variant, but what about a non-recursive algorithm?


texts:
$3^n = 2^{O(n)}$ is apparently true. I thought that it was false though because $3^n$ grows faster than any exponential function with a base of 2.

How is $3^n = 2^{O(n)}$ true?


texts: How to determine seed collision probability in a PRNG?

texts:
I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds are unique.

Do PRNGs encounter 'collisions', where two different seeds produce the exact same sequence of random numbers?

For example, if one initializes a PRNG with all possible 32-bit, 64-bit or 128-bit numbers, one would expect zero collisions since all seeds would be different.

When considering a Linear congruential generator, the seed gets divided into a multiplier. Since a Lehmer LCG uses a multiplier of 231-1, supplying a random 32-bit hash would cause collisions, since it is dividing all possible 32-bit numbers into 231-1 numbers. Thus, a seed of 1, 232-1 and 231 are equivalent and produce the same sequence of numbers. This is a problem since I am expecting the collision resistance of 64 or 128-bit hashes in the PRNG.

For more complicated algorithms, it's not as simple to determine these cases. My language of choice is JavaScript, which has no built-in seeded PRNG. There are of course many options to remedy this in the sense of libraries or standalone functions.

The best/fastest available PRNG for JavaScript seems to be Alea. It has a JS and C implementation and is based on Marsaglia's MWC algorithm. The JS implementation takes a variable string seed, so it is not clear how many unique seeds are possible. Alea is described as having a period length of 2116, which if I understand correctly, would mean it utilizes up to 116 bits of a supplied seed (e.g. a 128-bit hash).

Basically what I am asking is, how would I determine if seeds collide in a PRNG? Is it based on the described period length?

A good illustration of the issue is to compare Jenkin's small PRNG (2007) with xoshiro128+ (2018). They are quite similar. They both use 32-bit arithmetic, store the state in a 128-bit array composed of four uint32's and return one uint32 as the result. The main difference is that Jenkins only uses a 32-bit seed that is repeated in b,c,d. While in xoshiro128+ the entire initial state is the seed. Thus I can supply a 128-bit hash to the latter as the seed and still benefit from the quality of the generator (without modifying the algorithm). That is essentially what I mean - being able to provide a very large seed.

As a workaround to this potential issue, I thought about simply using the hash function itself, and running further iterations of the mixing function to obtain new pseudo-random bits (in the same way as obtaining a new number in a PRNG). It is deterministic and appears random enough, but it seems unlikely that hash function outputs pass "statistical randomness tests" such as Diehard or BigCrush since it was not designed as a PRNG.

Also, there are no cryptographic requirements here. The hash function I would use would be MurmurHash3 or similar--anything good enough to pass SMHasher suite of tests and produces 64-bit or 128-bit hashes.


texts: Is computation expression the same as monad?

texts:
I'm still learning functional programming (with f#) and I recently started reading about computation expressions. I still don't fully understand the concept and one thing that keeps me unsure when reading all the articles regarding monads (most of them are written basing on Haskell) is the relation between computation expressions and monads.

Having written all that, here's my question (two questions actually):

Is every F# computation expression a monad? Can every monad be expressed with F# computation expression?

I've read this post of Tomas Petricek and if I understand it well, it states that computation expressions are more than monads, but I'm not sure if I interpret this correctly.


texts: Compute single-source shortest paths in O(n+m) time?

texts:
I found the following problem in my textbook and I'm having trouble with coming up with a solution. I'm thinking maybe there's a way to improve Dijkstra's algorithm by using a data structure other than a priority queue, since that's what causes the log(n) time complexity, but I'm a bit lost. Here's the question:

Suppose you are given a connected weighted undirected graph, G, with n vertices and m edges, such that the weight of each edge in G is an integer in the interval [1, c], for a fixed constant c > 0. Show how to solve the single-source shortest-paths problem, for any given vertex v, in G, in time O(n + m).
Hint: Think about how to exploit the fact that the distance from v to any other vertex in G can be at most O(cn) = O(n).
The "single-source shortest-paths" problem, is a problem in which we are given one vertex along with several nodes in a graph, and we are required to find the shortest path to any other node, given the edge length between each node.

I really appreciate any help in advance!


texts: Detect all distinct k-th powers in a string for all k ≥ 3

texts:
In string theory, the $k$-th power of a string $w$ is named as $w^k$, where $w^0$ is the empty string $\epsilon$ and $w^n$ is the concatenation of $w$ and $w^{n - 1}$ $(n \in \mathbb{N}^{+})$.

The power in a string that mentioned below means some power which is one substring of the string. In addition, two strings are distinct if they don't look the same.

In Maxime Crochemore, et al. Number of Occurrences of powers in Strings, theorem 3 claims that "The number of distinct $k$-th powers, for a fixed integer $k \geq 3$, in a string of length $n$ is at most $\frac{n}{k-2}$".

If it is true, we may conclude the number of all distinct $k$-th powers for all integers $k \geq 3$ in a string of length $n$ is $\mathcal{O}(n \log n)$.

Is it possible to detect all these powers through some method in time complexity $\mathcal{O}(n \log n)$? For example, count the number of them and list one occurrence (start index and end index) for each of them.

I failed to seek results in recent research...

I asked the same question at here.


texts: How to identify a binary tree uniquely if its Inorder, Preorder and Postorder traversal is given?

texts:
Possible Duplicate:
  Which combinations of pre-, post- and in-order sequentialisation are unique?

I have three different tree traversal of a binary tree Inorder, Preorder and Postorder. I want to identify the tree back from these traversal. I found that a single traversal cant not identify the tree.
 So if I'll take in pair then can I identiy the tree?


texts: Absolute orientation alignment with vectors

texts:
I have two trajectories of a moving object. Each trajectory is composed of poses at discrete time. Each pose is a translation vector and a rotation matrix.

Each trajectory defines the same path (with noise) but expressed in some arbitrary frame of reference. I need to find the relative transformation that aligns both trajectories.

This is the absolute orientation problem that can be solved with Horn's method for a collection of points in the 3D space. So, I can solve this by taking into account just the translation vectors of the poses. However, I'd like to include the rotations as well.

Does this new problem have a name? Is there any known technique to solve it?


texts: Optimal improper vertex-coloring of graph with weighted edges

texts:
I have an undirected graph with weighted edges. I want to color the vertices with a given $k$ colors. Let's assume there is no proper coloring with $k$ colors such that adjacent nodes will always have different colors. I want to find the improper color assignments that would minimize the sum of weights of edges between nodes of the same color.

I have looked through many papers looking at improper coloring algorithms but cannot find this particular variant. This paper looks at something similar, but instead minimizes $k$ given a threshold on the sum of weights. Instead, I want to fix $k$ and minimize the sum of weights. Does anybody know the best approach for this?

Full citation to the paper:

J. Araujo, J.-C. Bermond, F. Giroire, F. Havet, D. Mazauric, R. Modrzejewski, Weighted improper coloring, Research report 7590, INRIA, Sophia Antipolis, 2011.


texts: Cost of solving linear equation using FFT algorithm

texts:
I have a linear equation $Cx=b$ where $C$ is $n \times n$ circulant matrix. By applying circular convolution process, vector $x$ can be solved using Fast Fourier Transform (FFT) to transform the circular convolution into component-wise multiplication. Therefore, vector $x$ can be written such that:
$x = F_n^{-1}\bigg[\bigg( \frac{(F_n(\textbf{b})))}{(F_n(\textbf{c}))}\bigg)\bigg]^T$ .
where vector $c$ is taken from the first column of matrix $C$ while vector $b$ is a solution of a linear equation.
My problem is I do not know how to count the total cost of vector $x$ using the FFT algorithm. From my understanding, the cost for FFT is $O(n log n)$, but from the equation above, I have to do transformation of $F_n(b)$ and $F_n(c)$ and inverse transformation. So, what is the total cost should be? I am very grateful if someone can help me for this. Thank you.


texts: How to interpret plot of cost function in gradient descend algorithm?

texts:
I have a data set to which I want to apply logistic regression. I set my cost function to be

$J(\theta) = -\frac{1}{m} [\sum\limits_{i=1}^{m} y^{(i)} log{(h_\theta \cdot x^{(i)})} + (1-y^{(i)}) log(1-h_\theta(x^{(i)}))$

and I am running gradient descend algorithm.

When I plot the cost function as a function of the number of iterations, I am getting a plot like this

Which I think is a good sign.

However, when I zoom in on the initial portion of the curve, I get this plot

I don't know what to make out of the rising and falling in the cost in the beginning. Is that something that we can expect? If so, why? Shouldn't the gradient descend algorithm decrease the cost after every step? How is it that after some iterations there is an increase in the cost? I know that it is possible for gradient decent not to converge if the learning rate is big enough but the algorithm does seem to converge eventually. So why is it that there are some instances where gradient descend tends to increase the cost?


texts: The Wikipedia article https://en.m.wikipedia.org/wiki/Lambda_cube is difficult to assimilate. I think examples (code snippets) that demonstrate each refinement might help clarify. For instance, a generic List in C# would demonstrate types based on types (I think). What are examples of the other axes? Are there meaningful yet succinct examples of combinations of multiple refinements, say the whole "calculus of constructions" in one snippet?


texts: Is it possible to add "memory" to a neural network?

texts:
Suppose I have a NN with one hidden layer, 10 inputs and 5 outputs, intended to be used as a (for example) game-bot AI. Would it make any sense to add, say, 5 (insert any number here) more inputs and outputs, and directly link these outputs from a previous step to these additional inputs of the next?

I imagine it could work as a RAM of sorts, making it possible to "save" some data that the network finds useful and use it later, therefore enabling the network to make decision not only on the current situation, but also on whatever it may "remember".

But maybe it's better to just hard-code these variables as actual variables and write only what the programmer decided to, such as "enemies killed", without the network being able to save whatever it finds useful?


texts: What is an efficient algorithm to solve the following combinatorial optimization problem?

texts:
I have a combinatorial puzzle to solve. The puzzle has 10 interconnected spots for polyhedral blocks to fill in. The blocks have these attributes:

weight,
shape (denoted by number of faces, $n_{\rm block} \in [4, 14]$, $n_{\rm block}=4$ is a tetrahedron, $n_{\rm block}=5$ is a pentahedron etc.),
a rank number printed on the blocks,
color, and
material.

None of these attributes are unique, there might be more than one blocks with the same attributes.

The slots are marked with a number $n_{\rm slot}$. Any block can be put in any slot, one slot can hold only one block. A solution must have all the slots filled in. There is a goodness score of a solution. If a block is put into a slot it receives a score $10 - |n_{\rm block} - n_{\rm slot}|$. After all the slots are filled, extra score is added to each block depending on the neighboring blocks. For each neighboring blocks matching both color and material, a block gets +3 score; for each neighboring blocks with either matching color or material, a block gets +1.5 score; for a non-matching neighbor no point is added. The total goodness score of the solution is the sum of all the blocks' scores. Now a solution has to satisfy the two following constraints.

a minimum goodness score
a minimum average rank number (average of the rank numbers of all the blocks)

The inputs of the problem are:

The map of the connected slots showing which slots are inter-connected,
A list of available blocks with all of their attributes (5000~15000 blocks)
Minimum goodness score necessary
Minimum average rank necessary

The output of the problem is:

A solution with the lowest total weight of all the blocks.

If finding the lowest-weight-solution is not feasible within 10-15 minutes in Python, a good enough solution with total weight lower than a specified budget can be a plan B.


texts: Why do we need to run the bellman-ford algorithm for n-1 times?

texts:
I'm a little confused about the concept of the Bellman-Ford(BF) algorithm to compute the shortest path in a general graph with negative weights knowing that there are no negative cycles present. I understand why Dikjstra doesn't work for a graph with negative weights. So in the Bellman-Ford algorithm we decide to update all nodes and their neighbors even though they might be visited before. My confusion can be summarized in a couple of questions:

Why running the BF algorithm once won't make sure that all nodes' distances have the minimum distance from the source?
Why do we have to run BF for N-1 (N: number of nodes) times to make sure all the nodes have the minimum distance from the source? Is it sort of because there are negative weights? How negative weights complicate things?


texts: Are Kernel Codes (which are written in C) compiled during boot time?

texts:
I have a confusion regarding how the Kernel is loaded during the boot time. The intuition I have is like following:

During installation of an OS, the compiled Code of the Kernel (depending on the architecture of the system) is written to the part of the Primary Memory that is restricted to the OS. When the PC is turned on, during boot time, initial some of the Assembly Instructions are executed to start-up (like creating the process init and starting other services).

But how the other processes, services are created ? Are all codes are compiled to Assembly codes during installation or Kernel codes (written in C) are compiled during boot time? If the latter happens, then is GCC pre-installed to the OS address space?


texts: How to find number of occurences of specific distances in binary (search) trees?

texts:
I want to calculate the amount of tree structures that have a given maximal distance between two nodes given an amount n of nodes (or keys).

E.g. with n = 3 there are 5 tree structures, each forced to have a maximal distance of two.
With n = 4 I can build 14 structures, only 2 of which have a maximal distance of two. The other 12 have a maximal distance of 3.

Now, generalizing the question:

Is there a way to calculate the amount of tree structures with a maximal distance d given n nodes?
And what's the total probability that when given a (uniformly distributed) random permutation of keys to be inserted in the empty tree leads to one of the structures with maximal distance d?


texts: How to prove the optimality of the "patience sort" algorithm?

texts:
I was trying to understand how we can solve the Longest Increasing Subsequence (LIS) problem in O(N log N) time. I came across a sorting algorithm called the patience sort algorithm. To learn it I was going through this document:
https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequence.pdf
I couldn't understand how the optimality was proved - i.e. why this algorithm leads to a minimum number of piles and correspondingly why it leads to the maximum length increasing subsequence.
In the above document from the weak duality principle (see pg. 5) we can understand that the number of piles ≥ length of any increasing subsequence.
Weak duality principle:

How can we use the above principle to prove the strong duality principle (see pg. 6)? If we can prove this, we will have proved the optimality.
Strong duality principle:

Thanks for the help.


texts:
(1) We know that $EXP ⊄ P/poly ⇒ BPP$ is in $SUBEXP$. Does $SUBEXP ⊄ P/poly$ mean $P=BPP$ or anything close?

(2) We know that if $NP$ is in $P/poly$ then $PH$ collapses to second level. What is the consequence if $\oplus P$ is in $P/poly$?


texts: Palstar algorithm Dynamic Programming getting the result

texts:
I recently started to read abour dynamic programming, and I am doing an exercise on it.
The problem to solve:
Given a String, find the least amount of palindromes it can be split into, and
print out the solution.
I found this article on here:
Is there an algorithm for checking if a string is a catenation of palindromes?

It helps me, but I dont quite get the last step of the answer: Quote:

  Now, you can compute s[1,…,j+1], by checking for each $1\le i\le j−1$ whether s[1,…,i] can be decomposed, and if s[i+1,…,j+1] is a palindrome (using the above 2D table). Giving a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

What do I do here? I am confused.


texts: insert(graph,x,y) in an undirected graph(adjacency list) already containing (y,x)

texts:
Good day.

In an undirected graph, if edge(x,y) is in the graph, (y,x) is also there.

Considering that I use adjacency lists to implement my graph, should insert(graph,x,y) do nothing if graph already contains (y,x)?

Thank you.


texts:
There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be

enumeration of prime numbers in ascending order
enumeration of grid points by increasing distance

For these there exist two fundamentally different techniques:

With one class of approaches you have to state the scope of your question up front. You'd state the upper bound for the primes you want, the maximal distance, or similar. The Sieve of Eratosthenes would fall into this category, as would an algorithm enumerating all points in a rectangle and then sorting them by distance.
With another class of approaches, you don't have to state the extent of the required output up front. You can see the enumeration as a lazily evaluated infinite sequence, and feed it to some other part of your code that should eventually terminate the generation once a generated output satisfies your requirements. Testing each odd number against a list of already found primes would be an example from this class.

Now I'm looking for a term to distinguish these two forms. Somehow the latter approach feels closely related to online algorithms, which is why I added that tag. But every deifnition I could find specifies an online algorithm as processing its input incrementally. There is almost no input here, unless you count the one-bit decision between “give me the next item” and “that's it, stop now” as an incremental input. Would calling this an online algorithm be appropriate, or is there a better term?


texts:
I am curious about something pretty simple, though I have never heard, read and more sadly seen any example of it.
Take any image, represent it as a matrix, invert the matrix (assuming the inverse exists) and represent it as an image again.
This in some sense visualizes the process of inverting a matrix. It would be pretty easy to code this, but before doing that I just wanted to ask if anybody has examples at hand or can say anything about this. Thanks!


texts:
I would like to find the height of a d-ary heap. Assuming you have an Array that starts indexing at $1$ we have the following:

The parent of a node $i$ is given by: $\left\lfloor\frac{i+1}{d}\right\rfloor$

The $d$ children of a parent at node $i$ are given by: $di-d+1, di-d+2,\ldots di+1$

The height of a heap (which is slightly different than the height of a binary search tree) is a longest path from the root to a leaf. A longest path will always be from the last node in the heap to the root, but how do I calculate this longest path?

My first Idea is to setup a recurrence relation for the height of the tree:

\begin{equation}
h(1) = 0\\
h(i) = h\left(\left\lfloor\frac{i+1}{d}\right\rfloor\right)+1
\end{equation}

This seems overly-complicated and I feel like the answer is much more simple. Is there a better way to find the height of a $d-$ary heap?


texts:
Suppose I have $k$ sets with $n$ elements in each. Define a selection as one element taken from each set.

A selection is unique if there's one and only one way it can happen—that is, one and only one mapping from the elements in the selection back onto the original sets. For example, if my sets are $\{1,2,3\}$ and $\{1,2,4\}$, then $(1,2)$ and $(1,3)$ are both valid selections, but only the second one is unique.

I'd like to find the number of unique selections, given a list of sets. But my first attempt is $O(n^k)$, which is pretty bad. (Generate all $n^k$ possible selections, then discard all duplicates, and count how many are left.)

Is it possible to do better than this? If so, how?

(If it simplifies things, you can assume the order of elements in a selection either does or does not matter. To switch from one "version" to the other, just multiply or divide by $k!$ at the end; no unique selection can contain two identical elements, after all.)


texts: Proving that a language does not belong to a language class by using more specific instances of that language

texts:
You have a description of a language that you have to prove is regular, context free, or other. In order to prove that it does not belong to a certain class of languages, you might think that it will be more convenient to prove it by using a subset of that language. The problem is that a subset of a language does not necessarily belong to the same language class as the superset language. For example: with $\Sigma = \{0,1\}$, $\Sigma^*$ is a regular language, while $ A = \{ 0^n1^n \mid n \geq 0\} \subseteq \Sigma^* $ is a context free language.
(I have fallen in the trap of trying to use subsets of languages in order to try to prove that they belong to a certain class of languages.)
An example:

Let $\Sigma = \{0,1\} $ and $L = \{ w \in \Sigma^* \mid \text{w contains less 1's than 0's} \}$
Is $L$ regular, context free, or neither?

My intuition says that it is not regular, since finite state machines can't count. I think it is context free.
The strategy I'm thinking of is to show that this language is context free:

$ L_2 = \{ 0^n1^m \mid n \gt m\}$

This language is clearly a proper subset of $L$. But, like we've seen, that may not be a very useful fact if we want to prove things about the proper superset (to my understanding). It seems that $L_2$ is easier to generate than $L$: it seems easier to count how many consecutive 0's there are rather than counting the number of 0's in a string. (Especially if you consider using a PDA to count it, since then it just boils down to pushing consecutive 0's and then popping when you start seeing 1's, accepting the language if there are 0's left on the stack when you have consumed the word.) Consequently, if this intuition of hardness is correct, then $L$ is at least not regular. But then another problem reveals itself; maybe $L$ is not context free? So then you have at least shown it to not be regular, but you still have to show that it is context free or not.
This is not the only problem for which I want to use this strategy. For example:

$L_p = \{ w \in \Sigma^* \mid \text{the number of 0's in w is prime}\}$

Here I think it might be more convenient to use something like the Pumping Lemma on this language:

$L_{p2} = \{ 0^n \mid \text{n is prime}\}$

Is this kind of strategy valid?


texts: Is there a standard (common) notation for the following operation on binary strings?

texts:
Typically, we use the notation $S = \{0, 1\}^n$ to denote the set of all $n$-bit strings. Suppose that I wanted to extract a subset of the strings where certain bits have some fixed values. For example, I could try defining $S' = \{s= s_n\ldots s_1 \in S : s_2 = 1, s_4=0, s_n = 1 \}$ to denote the set of $n$-bit strings where $s_2$, $s_4$ and $s_n$ have the specified values.

Given that I am going to need to define many such subsets, it would be useful to have some better notation.... say $S_{\{s_2 = 1, s_4 = 0, s_n = 1\}}$, though this doesn't look very appealing. For those perhaps more familiar with the literature than I am, is there a set of notation that is typically used to denote such subsets? If not, what might be a compact and appealing way to denote such a subset?


texts: What computational complexity classification does autonomous/self-driving cars belong to?

texts:
Self-driving car technology continues to attract popular attention and interest in today's media, but how would a computer scientist explain the theoretical nature of the problem? For example, we are frequently told that Sudoku and Go are examples of NP-completeness and PSPACE-completeness, and a range of practical progress has been made in dealing with these two categories. So similarly with autonomous vehicles, I think laypeople people (like myself) intuitively accept that learning to drive properly is a "problem", but then, what is the underlying problem that such machine learning algorithms are trying to tackle?
I did some Googling around and found different articles and papers alluding to some parts or formal abstractions of the driving problem and/or maybe robotics being PSPACE-complete. So is that the answer basically? Or is it that the question is too vague to be answerable? Or even that there hasn't been a clear understanding yet, because the area is fairly new? I'm just really curious, but didn't find anything explaining this at a high level. But when I took CS in college, the professors would emphasize to programmers that understanding the nature of the problem can be very important, e.g. understanding if your specific problem is in P or is NP-complete, and so forth.


texts: What mathematical guarantees gives alpha-beta pruning?

texts:
In the alpha-beta pruning version of the minimax algorithm, when one evaluates a state p with $\alpha$ and $\beta$ cutoff and gets a v value, i.e.,
v = alphabeta(p, $\alpha$, $\beta$)
are these properties true?

alphabeta(p, -$\infty$, $\beta$) = v when $\alpha$ < v
alphabeta(p, $\alpha$, $\infty$) = v when v < $\beta$
alphabeta(p, $\alpha$', $\beta$') = v when $\alpha$ $\le$ $\alpha$' $\le$ $\beta$' $\le$ $\beta$
if v > $\beta$, then alphabeta(p, $\beta$, $\infty$) = alphabeta(p, $\alpha$, $\infty$)
if v < $\alpha$, then alphabeta(p, -$\infty$, $\alpha$) = alphabeta(p, -$\infty$, $\beta$)

I've reached to this results studying the algorithm itself after reading a couple of papers. After applying it to a real case I've got an improvement of ~30% (in number of states visited, and this gives about a 30% of time execution improvement also), but I want to know if there is a mathematical background that supports these changes to the algorithm.


texts: Convert conjunctive normal form to equivalent boolean formula with only NOR gates

texts: Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with fan-in 2, without introducing any new dummy boolean variables. I'm wondering how much this will increase the size of the formula. If $\varphi$ has size $n$, how large does the resulting formula need to be? Can I convert $\varphi$ to an equivalent formula with only NOR gates that has size $O(n)$?  If $O(n)$ isn't achievable, what's the best that is?


texts: Show $L = $ { w $\in (a,b) ^* $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$ is regular

texts:
I try to show that this language is regular:
$L = $ { w $\in \ (a,b) ^ * $| for every u substring of w, $-5\le|u|_a−|u|_b\le5\}$
If I build a NFA and run on it every substring of w (skip other letters every time) - and only if they are all accepted (follows the condition) then accept w.
Is it possible in NFA? Is there other way to show the regularity of the language?


texts:
I am working on the following problem:

Prove that, for all $k\in\mathbb N$, there exists $n\in\mathbb N$ so that every binary string $x\in\{0,1\}^{kn}$ with Kolmogorov complexity $K(x)$ at least $kn$ satisfies the following property:
By interpreting $x$ as $x_1\cdots x_n$, with $|x_i|=k$, for any $z\in\{0,1\}^k$ there is an index $i$ for which $x_i=z$.

To show this, I want to suppose that if there exists a string $x$ of length $kn$ so that, after writing $x=x_1\cdots x_n$, not all $k$-bit binary strings appear in $x_1\cdots x_n$. Then ideally I want to show that $x$ can be described in less than $kn$ bits, which means $x$ have Kolmogorov complexity less than $kn$, which establishes the contradiction I want.
Any hints on how to do this?
For completeness, the Kolmogorov complexity of a string $x$ is defined as the length of the shortest description of $x$. And by the description of a string $x$, I refer to a pair $(M,w)$, where $M$ is a Turing Machine and $w$ is some string, so that $M$ halts on $w$ as input, leaving behind $x$ on the tape. I encode the pair $(M,w)$ as $0^{|M|}1Mw$. Then, for any string $x$, if $M$ is a Turing Machine that halts immediately upon execution, then $(M,x)$ is a description for $x$, of length $2|M|+|x|+1$. Hence the Kolmogorov complexity of $x$ does not exceed $2|M|+|x|+1$.


texts: Construct skolemform of: $\forall X.((\forall Y.\exists Z. R(X,Y,Z)) \land \forall S. \exists T. R(X, S,T))$

texts:
This question is not asking for a solution, but rather as a check / validation of my thought process.

Given the form: $W = \forall X.((\forall Y.\exists Z. R(X,Y,Z)) \land  \forall S. \exists T. R(X, S,T))$

The algorithm I learnt states, that I have to 1th bring $W$ into prenex form. Doing so I bring all quantors to the beginning, if necessary resolve all variable dependencies by defining fresh variables. The exact sequence of the operators has to be maintained in the process!

2th I look for something of the form: $ \forall x_1. \forall x_2. \forall x_3 \dots \exists y_1 \exists y_2 (R(y_1, y_2))$ and replace it by something like $ \forall x_1. \forall x_2. \forall x_3  (R(g(x_1, x_2, x_3, \dots), f(x_1, x_2, x_3, \dots))) $

In the above example $W$, following strictly the rules stated previously, I would expect the result:

Prenexform: $\forall X.\forall Y. \exists Z. \forall S. \exists T. (R(X,Y,Z)) \land R(X, S,T)) $

Skolemform: $ \forall X.\forall Y. \forall S. (R(X,Y,g(X,Y)) \land R(X, S,f(X,Y,S)) $, which might be correct, but kinda dumb looking.

Thus the question arises, if the rules above are absolut, if there were not a way to soften them and for example allow to switch the order of $\forall$ and $\exists$ operators.

Any constructive comments/answers to my question are appreciated.


texts: When is the big-O relation preserved under exponentiation?

texts:
Suppose that $f, g$ are functions from the positive integers to the positive reals. Under what circumstances will $\log f(n)=O(\log g(n))$ imply $f(n)=O(g(n))$?

It's easy to see that this isn't always true: If $f(n)=3^n$ and $g(n)=2^n$ then we know that $3^n\notin O(2^n)$, but taking logs gives $\log3^n = n\log 3$ and $\log 2^n=n\log 2$ and it's obvious that $n\log 3=O(n\log 2)$.

The reason is also clear: If there exists a $c>0$ such that $\log f(n)\le c\,\log g(n)$ then all we can say is that $f(n)\le (g(n))^c$, which won't necessarily allow one to conclude $f(n)=O(g(n))$. When, though, can we correctly make the inference?


texts: Categorisation of type systems (strong/weak, dynamic/static)

texts:
In short: how are type systems categorised in academic contexts; particularly, where can I find reputable sources that make the distinctions between different sorts of type system clear?

In a sense the difficulty with this question is not that I can't find an answer, but rather that I can find too many, and none stand out as correct. The background is I am attempting to improve an article on the Haskell wiki about typing, which currently claims the following distinctions:

No typing: The language has no notion of types, or from a typed perspective: There is exactly one type in the language. Assembly language has only the type 'bit pattern', Rexx and Tk have only the type 'text', core MatLab has only the type 'complex-valued matrix'.
Weak typing: There are only few distinguished types and maybe type synonyms for several types. E.g. C uses integer numbers for booleans, integers, characters, bit sets and enumerations.
Strong typing: Fine grained set of types like in Ada, Wirthian languages (Pascal, Modula-2), Eiffel

This is entirely contrary to my personal perception, which was more along the lines of:

Weak typing: Objects have types, but are implicitly converted to other types when the context demands it. For example, Perl, PHP and JavaScript are all languages in which "1" can be used in more or less any context that 1 can.
Strong typing: Objects have types, and there are no implicit conversions (although overloading may be used to simulate them), so using an object in the wrong context is an error. In Python, indexing an array with a string or float throws a TypeError exception; in Haskell it will fail at compile time.

I asked for opinions on this from other people more experienced in the field than I am, and one gave this characterisation:

Weak typing: Performing invalid operations on data is not controlled or rejected, but merely produces invalid/arbitrary results.
Strong typing: Operations on data are only permitted if the data is compatible with the operation.

As I understand it, the first and last characterisations would call C weakly-typed, the second would call it strongly-typed. The first and second would call Perl and PHP weakly-typed, the third would call them strongly-typed. All three would describe Python as strongly-typed.

I think most people would tell me "well, there is no consensus, there is no accepted meaning of the terms". If those people are wrong, I'd be happy to hear about it, but if they are right, then how do CS researchers describe and compare type systems? What terminology can I use that is less problematic?

As a related question, I feel the dynamic/static distinction is often given in terms of "compile time" and "run time", which I find unsatisfactory given that whether or not a language is compiled is not so much a property of that language as its implementations. I feel there should be a purely-semantic description of dynamic versus static typing; something along the lines of "a static language is one in which every subexpression can be typed". I would appreciate any thoughts, particularly references, that bring clarity to this notion.


texts:
Savitch's theorem "test[s] the existence of a path from a vertex s to another vertex t that uses at most k edges"

Could this be used to find the largest path in a graph?

We know there's a walk of length a from b to c.
We can keep lowering a by 1 to find a d where there's no walk from b to c. Now we know there's a path of length d+1 between b and c. We can try other b and c to maximize d+1. Does this find the largest path in the graph?

What is my mistake?


texts:
According to nLab, M-types are the dual of W-types. What are the introduction and elimination rules for M-types?

Edit: For example, the formation/introduction/elimination rules for W-types are:

$$\frac{A:Type\quad x:A⊦B:Type}{(W x:A)B(x):Type}-\text{W-Formation}$$

$$\frac{a:A\quad t:B(a)\rightarrow W}{sup(a,t):W}-\text{W-Introduction}$$

$$\frac{w:W⊦C(w):Type\\ x:A,u:B(x)\rightarrow W, v:(\Pi y:B(x))C(u(y))⊦c(x,u,v)C(sup(x,u))}{w:W⊦wrec(w,c):C(w)}-\text{W-Elimination}$$

I'm wondering what the corresponding rules for M-types are.


texts: Polynomial Multiplication and Modulo Operation complexity

texts:
Given two polynomials of degree $n$ and $m$ over $\Bbb F_q[x]$ it takes about $O((n+m)\log ((n+m)))$ operations ring operations over $\Bbb F_q[x]$ to multiply them.

What is the corresponding bit operations?

What is the corresponding ring and bit operation count for remainder operations in $\Bbb F_q[x]$.


texts:
What would be the best introduction to Per Martin-Löfs ideas about type theory? I've looked at some lectures from the Oregon PL summer school, but I'm still sort of puzzled by the following question:

What is a type?

I know what a set is, since you can define them by the usual ZF axioms and they have a very intuitive concrete model; just think of a basket filled with stuff. However, I've yet to see a reasonable definition of a type and I was wondering if there is some source that would distill this idea for dummy.


texts:
Question

Is Infinite Union of Recursive language is Recursive?

I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct.
My Approach/Doubt
$\text{let}\,\,L_1=abcd \,\,\,L_2=a^2b^2c^2d^2=aabbccdd,L_3=a^3b^3c^3d^3=aaabbbcccddd$
here $L_{1},L_{2},L_{3}\,....\text{are finite hence regular hence recursive}$
let $L_{Iu}=L_1 \,\cup\,L_2\,\cup\,L_3\,\cup........$
but $L_{Iu}=a^{n}b^{n}c^{n} \text{which is recursive }$ .
so can i say that Infinite Union of Recursive language is Recursive
Please help me out


texts: Why aren't recognizable languages and co-recognizable languages not reducible to each other?

texts:
While learning to prove undecidability of problems, I came across a statement that you can't reduce a recognizable language to a co-recognizable language and vice-versa to prove undecidability. Why is it so?

Eg: Halting problem of TMs can't be reduced to Emptiness problem of TM

$\qquad$ $H_{TM}$ = {$\langle M,x \rangle$|$M$ is a TM and $M$ halts on input $x$}

$\qquad$ $E_{TM}$ = {$\langle M \rangle$|$M$ is a TM and $L(M)= \emptyset$}


texts: To prove Turing-completeness, is it enough to prove capability of producing arbitrary output?

texts:
Turing completness is being typically proved via reduction to already proved Turing-complete machine.

Can the same be obtained by showing, that the machine in question is capable of generating arbitrary output – if proper input is given?


texts:
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression.  In my case, $k$ may be greater than $n$ and they grow independently.

Specifically, I'd expect some explicit exponential expression.
The best I could find so far is that based on Stirling's approximation $O(n!) \approx O((n/2)^n)$, so I can use that, but I wondered if I could get anything nicer.

$$O\left({{n+k-1}\choose{k}}\right) = O(?)$$


texts:
You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list?

First thought. We have a O(N log N) bound, but we also have additional information about the quantities in the array, so I think we could do better.

Second thought: should we use hash tables, do we care about duplicates? Cant see how to use hash tables.

Third thought: does this have something to do with radix sorting? no idea.

Fourth thought: Could we sort this list by creating another list, and then pass through the original counting frequencies of elements occured. But would we need another pass to create a larger sorted list, which would be O(N^2). ie too large.

Is this a very easy question or a very hard question?


texts: Shortest Path using DFS on weighted graphs

texts:
I read that shortest path using DFS is not possible on a weighted graph. I pretty much understood the reason of why we can't apply on DFS for shortest path using this example:-

Here if we follow greedy approach then DFS can take path A-B-C and we will not get shortest path from A-C with traditional DFS algorithm.

I think that we can modify DFS slightly in this way to get shortest path.In this example, after the DFS goes through A-B-C and comes back again to A, we can check all adjacent nodes and if the distance from A to any of the adjacent node is less than the distance which was assigned previously(i.e 2<4) then we visit the node again even if the node is visited again before and continue the DFS from this node (like visiting C again).
If we do this way, ofcourse the complexity will be bad but I don't think that its impossible to get shortest path using DFS. Is this the right approach?

Initially we have cost array initialized to infinity except for source vertex which is initialized to 0. dist(u,v) denotes edge weight from vertex u to vertex v.

function spath(vertex u)
{
  for each(vertex v adjacent to u)
   {
      if(cost[u] + dist(u,v) < cost[v])
       {
          cost[v]=cost[u]+dist(u,v);
          parent[v]=u;
          spath(v);
       }
   }
  return;
}


texts: Research Papers about Production Systems for Solving Algebraic Equations

texts:
I'm interested in coding up a small project that solves uni-variate algebraic equations (up to cubic) by simulating the actions of a human expert in solving the equation. To do this, I've drafted a set of production rules (if/then rules applied to an equation when certain conditions hold). However, I'd like to compare my rule set to perhaps other production systems in the same domain. I've been told that algebra problems are often used as the problem domain in research papers on intelligent tutors. So far I've found this paper, which is a bit dated, and only includes production rules for linear equations (on page 4). I know that more recently (in the 90s) Koedinger at CMU did some work on an intelligent tutoring system called PAT which seems related to what I'm doing; however, I haven't been able to find anything about the specific rule set used by PAT.

So the question is, does anyone know of any research papers that include a list of production rules to solve algebraic equations?


texts: Why process algebras à la chemical abstract machine are not common?

texts:
I recently read the Berry and Boudol's chemical abstract machine [1, 2]. I found the way they describe the semantic really nice and quite intuitive for a process calculus.
The aspect that really appealed me is that, in the chemical abstract machine (ChAM hereafter), configurations are multiset of processes (and processes are similar to those of CCS, but it does not really matter), e.g.  {{ a.b.0, /a.0, /b.0 }}, and the semantics is define on the multiset, with rules similar to a.P, /a.Q <-> P, Q, which means "if you find a a.P and a /a.Q in the multiset, you can replace them with P and Q.
Since the rules are on elements of the multiset, there is no need for a structural congruence like the one we usually have in e.g. the $\pi$-calculus. Also, from a moral point of view, such an approach seem more pleasant to me, since we explicitly have no structure, like concurrent processes (opposed to structured term to which we have to add a congruence to get rid of the structure).
Yet, as far as I know, the semantics of almost all process calculus are defined with SOS rules.
Hence my question : why is an approach à la chemical abstract machine not more popular/common?

I ignore two aspects of the ChAM in my question:

Processes of the ChAM include a construct for parallel processes, which semantics is  a | b <-> a, b, which syntactically allow composition à la CCS. Yet this does not affect the semantics, since such processes have to get separated before reducing.
Rules are often written with two ways arrows (<-> in the question), expressing that the rule can apply in two ways. One could argue that this is a drawback for the ChAM, since the calculus possibly loops forever (by doing and undoing a rule). I think this argument is not convincing since we could get rid of the two way semantics, and force forward progress. In fact, the same argument could apply to reversible process calculi ($\rho\pi$, RCCS, etc.), where reversibility is intended

[1] http://www.sciencedirect.com/science/article/pii/030439759290185I
[2] https://doi.org/10.1145/96709.96717


texts: Theoretical justification of "halting problem avoidance"

texts:
The wikipedia page for the Halting problem mentioned practical solutions to avoiding the halting problem such as avoiding infinite loops. And there is a mention that "by restricting the capabilities of general-purpose (Turing-complete) programming language, it is possible to guarantee the completion of all sub-routines (written under the restriction)".

What seems unclear to me is the underlying computation model of such restricted programming languages.

Say, if we remove -- from a general-purpose (Turing-complete) programming language -- the capability to conduct infinite loops (i.e. making the loop variable to always enumerate a finite list of elements, avoiding circular function recursions, etc), what would be the expressiveness of the resulting programming language or (the capabilities of) the corresponding computation model.

Possibly related questions

Is there an always-halting, limited model of computation accepting $R$ but not $RE$?