texts: Finding pairs $a \in A$, $b \in B$ where $a \ge 3b$ in linear time

texts:
There are two sorted arrays A and B containing distinct values. How to find all the pairs $(a,b)$ such that $a \ge 3b$ and a is in A and b is in B. This needs to be done in linear time.

I have tried solving it but it is taking me $n \log n$ time, not $n$. I simply use binary search to look for the value of $b$ corresponding to $a$. But in worst case it will come up as $n \log n$ only.

I have tried to read about it online but found nothing and kind of stuck for the past 2 days. I just want some hints to move in the right direction because I feel that maybe I am missing something very fundamental.


texts: How does the processing happen in a CPU when it uses Virtual Memory?

texts:
I am just trying to visualize how computers work with Virtual Memory/Address.

Assume there is a program on the disk that looks like this:

a b c d e f g h i j k l m n o p where the a .. p are instructions and their address is from 0 to 15.

What happens inside the CPU while executing this program? Assume that the operating system uses pages of 8 bytes.

To begin with, my understanding is that the operating system loads the program into physical memory in page-sized chunks and creates a mapping to the pages of the program numbered from 0..n which looks like:

# assume it is in reverse in the real memory (16-31)!

[i j k l m n o p] [a b c d e f g h]

# cpu's view of the program

  page1 (24-31)     page2 (16-31)
[a b c d e f g h] [i j k l m n o p]
 |
 PC

Depending on the program size, program-size/page-size page's
will be created. So here it would be 16B/8B = 2 pages numbered as
page1 and page2.
Now, the Program Counter (PC) would be set to the Virtual Address of
a which is 0 and the CPU will somehow resolve it and load the
corresponding instruction from the real physical address of a
which is 24 here.
But wait, how did CPU know that it has to look up into a certain
page map, page1 in this case? The operating system knows that but
how does the CPU know that? Is it something like the Virtual Address
of a program corresponds to one and only one page map and that can
be determined directly from the Virtual Address itself? For example,
0x00 automatically means to lookup in page1, 0x08 means to
lookup in page2. Divide by 8 and look into the page{quotient}
with the remainder indicating the offset to look into the real
memory?
Suppose there is an instruction d that refers to the memory
corresponding to o which is in page2, how will that be resolved?
Is it using the same principle? If you know the Virtual Address,
then you know the place to look up for the real address?
Now, when there are multiple programs how do we uniquely determine
what is page1? Could another program have a page1 as well? Is it
like page maps are unique (which I think is complex because I
thought it has to be sequential and starting from 1 so that given a
Virtual Address you can calculate the page map + offset) or is there
a per process Page Table managed by the Operating System?
Suppose we finished executing the instruction h, the PC would
automatically load the Virtual Address of i, which gets
automatically resolved to page2 using the same above principle?


texts: CFG to CNF, but stuck on the last few steps

texts:
I recently learned about the conversion, but I seem to be stuck.

I need to convert the following CFG to CNF:

$S → XY$

$X → abb|aXb|e$

$Y → c|cY$

There is no S on the right side, so I did not need to add another
I removed the null productions $X → e$

$S→XY|Y$

$X→abb|aXb|ab|$

$Y→c|cY|$

I removed unit production
$S→Y$ $Y→c$ with $S→c$
There are no production rules which have more than 2 variables
Here, I struggle. I am not allowed to have a terminal symbol and a variable together, but I am not sure how to get rid of these.

New grammar after step 4:

$S→XY|c$

$X→abb|aXb|ab$

$Y→ZY$

$Z→c$

I managed to replace the symbol c with Z, and added the new rule, so that seems fixed. However, I am unsure what do do with $aXb$.

Is this okay so far? if yes, what step should i take next?

Thank you in advance!


texts: Trying to figure out if a modern computer is capable of manipulating arbitrarily large pointers

texts:
I was just thinking about Turing-completeness and its relationship with modern computers.  I've always thought that a real computer is not technically Turing-complete.  It is equivalent to a linear-bounded automaton; a Turing machine has infinite memory, whereas a real computer has only finite memory.

However, you can add memory to a computer through expansion cards, external mass storage drives, etc.  The limiting factor then becomes the maximum size of pointers.  Obviously, a 64-bit CPU can store a 64-bit pointer in its general-purpose registers, and languages like C/C++ can easily be modified to support 64-bit pointers.  However, I'm not sure if they would be able to manipulate arbitrarily large pointers, and thus an arbitrarily large address space.

My thoughts are as follows: Most modern CPUs include instructions that allow for arithmetic involving arbitrarily large integers.  For example, the Intel architecture has the ADC and SBB instructions, where the carry flag from the last operation is added or subtracted from the result of the current operation.  This allows for addition and subtraction of arbitrarily large numbers in a piecewise fashion.

Theoretically, this could also be done with pointers.  Say you want to increment a 1024-bit pointer by some amount.  You simply add an immediately addressed value to the pointer using the ADC instruction in 16 successive operations.

The problem comes when you actually have to dereference the pointer.  Intel CPUs, and probably most other CPUs as well, are incapable of operating directly on variables in memory, while simultaneously being incapable of storing an entire arbitrarily large pointer in the registers all at once.  You can't dereference a pointer in a piecewise fashion; you have to dereference the entire thing.  So it all boils down to the question of whether a pointer can be dereferenced in this fashion.  It has occurred to me that I don't actually understand how pointer dereferencing is done at the machine level, and I would like someone to explain how this works.

Of course, this question is of no practical importance, because simply having 64-bit pointers allows for an address space that probably surpasses all the memory currently in existence.  I am simply interested in this question from a theoretical standpoint.


texts:
Is inverting a matrix in the Complexity class $\text{P}$ ?

From the runtime I would say yes $\mathcal{O}(n^3)$ but the inverted matrix can contain entries where the size is not polynomially bounded by the input?


texts:
The program below uses six temporary variables a, b, c, d, e, f.
a = 1
b = 10
c = 20
d = a+b
e = c+d
f = c+e
b = c+e
e = b+f
d = 5+e
return d+f

Assuming that all operations take their operands from registers, what is the minimum number of registers needed to execute this program without spilling?
(A) 2
(B) 3
(C) 4
(D) 6
My attempt :

But, people are using register R3 for variable C.
I've applied register re-usability without spilling, so answer is only 2.
My question is :

Whether, can we apply register re-usability or not !?


texts: How do I prove that a language is deletion closed?

texts:
For example, how could I prove that the following language is deletion closed:

{$a^k$$b^j$ : $j$, $k$ $\geqslant$ 0}

The reason seems obvious to me, I just can't see a way to prove it.


texts: Why does taking advantage of locality matter in multithreaded systems?

texts:
As we all know, when a given thread/process reaches a memory address it does not have cached, the execution will (for the most part) freeze up until said data is fetched from memory. What I don't understand, is why in multithreaded systems, we can't save ourselves the headache of data-oriented design. Why can't the processor/OS simply do work elsewhere on a different thread until the data is received?
I couldn't find a good post on this exact question, and this may just be obvious to others. I only know so much about the pipeline and such so there could be a very obvious reason for this, I simply don't know why.


texts: Articulation Vertex, significance and real world usage?

texts:
This question is not about any particular algorithm to look for articulation vertices (cut vertices) in a graph but rather seeking real world applications of algorithms involving such vertices.

I am going through Skienna's The Algorithm Design Manual and it gives an example of an articulation vertex in a telephone network as an approachable example.

Personally, I think there may be applications in networking where multipathing is implemented using more than one switches between the same set of connected hosts to provide tolerance against failure of one of the switches. But still, an algorithm to look for an articulation vertex is not directly applicable in this scenario.

Are there any real world examples of articulation vertices and how looking for them helps solving problems arising due to such vertices ?

EDIT:

Just adding a bit more food for thought. I think simulation based applications or maybe gaming could have some applications ?

For e.g. a game engine may generate some graph based entities on the fly, let's say a building which a player must go into in a FPS game. For testing the the on the fly part, it may be useful to look for parameters which may generate buildings(graphs) which are biconnected (or higher connected) for easy or easier settings where as graphs with articulation vertex can be considered to be hard settings.
(Easy or hard here are relative terms and the semantics may be even reversed depending on the outcome of players' entering the graph)


texts: Is there a computer science theory behind automatic source code generation

texts:
The OpenAPI specification aims at standardizing the representation of REST based systems in json and yaml formats. A short version of the petstore is below:

{
 "swagger": "2.0",
 "info": {},
 "host": "petstore.swagger.io",
 "basePath": "/v2",
  "tags": [],
  "schemes": [
 "http"
 ],
 "paths": {},
 "securityDefinitions": {},
 "definitions": {},
 "externalDocs": {
 "description": "Find out more about Swagger",
 "url": "http://swagger.io"
 }
}

Based on this document, client and server stubs can be generated in different programming languages/frameworks using the OpenAPI codegen project. Is there a computer science theory behind this ? To be more precise, I want to specifically know if there are theoretical concepts behind taking an input, (in this case a json/yaml document) and getting a source code representation in one or more programming languages that represents the initial input ?


texts:
I wonder why do we say $\log n$ is the best possible approximation factor for Set Cover Algorithm? We already know there exists a 2-approximation algorithm for vertex cover, which is obviously better than $\log n$. So we can use Vertex Cover algorithm to solve Set Cover problem and get a better approximation ratio. Can anyone explain this to me?
Thanks in advance


texts: Armstrong's axioms more precisely 'inference rules': what's the distinction?

texts:
"more precisely 'inference rules'" is what wikipedia says twice.

Other references I've looked at (the Alice book, Ullman lecture notes cited, Maier textbook) name them as Armstrong's Axioms, use them for inference. talk about axiomatisation and decidability, etc.

Wikipedia's links to axiom vs inference rule isn't helping me. "a rule of inference's action is purely syntactic, and does not need to preserve any semantic property:" Ok I can see that for (for example) modus ponens: it wants a premise like $p \supset q$ and a premise looking like $p$.

Hmm take the Armstrong Axiom of reflexivity

  If $X$ is a set of attributes and $Y$ is a subset of $X$, then $X$ holds $Y$.

    If $Y \subseteq X$ then $X \rightarrow Y$.

How to determine syntactically that $Y \subseteq X$?

So what is wikipedia trying to say? What distinguishes an axiom (which might be of the form $p \supset q$) vs an inference rule?


texts: It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates (that is, solutions to the equation) in linear time by plugging in our solution and evaluating. So the problem is in NP. Why does this not imply P $\neq$ NP?


texts: Uniform Binary Search explanation and lookup table

texts: Please can anyone explain me the worst ,average and best case running time for the Unifrom binary search .. Also how can the lookup table be explained?


texts: Hash functions producing uniform outputs

texts:
I've seen this question in a past exam paper, and I know that the answer given is (b), but I'm not sure why.

  Which one of the following hash functions on integers will distribute keys
  most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to
  2020?

  (a) h(i) = i2 mod 10

  (b) h(i) = i3 mod 10

  (c) h(i) = (11 i2) mod 10

  (d) h(i) = (12 i) mod 10

I understand the number of buckets relating to the modulus, but not how the factor or power of i affects the uniformity of the distribution.


texts: Priority queue with both decrease-key and increase-key operations

texts:
A Fibonnaci Heap supports the following operations:

insert(key, data) : adds a new element to the data structure
find-min() : returns a pointer to the element with minimum key
delete-min() : removes the element with minimum key
delete(node) : deletes the element pointed to by node
decrease-key(node) : decreases the key of the element pointed to by node

All non-delete operations are $O(1)$ (amortized) time, and the delete operations are $O(\log n)$ amortized time.

Are there any implementations of a priority queue which  also supportincrease-key(node) in $O(1)$ (amortized) time?


texts:
I was reading Tuple Relational Calculus from a textbook.
I came across this query:

For every project located in 'Stafford', list the project number, the controlling department number, and the department manager's last name, birth date and address.

The solution query is:

{p.Pnumber,p.Dnum,m.Lname,m.Bdate,m.Address |
    PROJECT(p)}  AND
    EMPLOYEE(m)  AND
    p.Plocation = 'Stafford' AND
    ((∃d)(DEPARTMENT(d) AND
          p.Dnum = d.Dnumber AND
          d.Mgr_ssn = m.Ssn
         )
    )
}

I dont understand what difference existential quantifier will make if I can write the  same query as follows without existential quantifier (and of course if it produces same result and hence correct, which also I dont know):

{p.Pnumber,p.Dnum,m.Lname,m.Bdate,m.Address |
    PROJECT(p)}  AND
    EMPLOYEE(m)  AND
    DEPARTMENT(d)
    p.Plocation = 'Stafford' AND
    p.Dnum = d.Dnumber AND
    d.Mgr_ssn = m.Ssn
}

Is it like: the solution query provided uses existential quantifier just because we dont actually project DEPARTMENT relation's attributes in the final output?


texts: What set of primitive operations are assumed to be constant time in complexity analyses?

texts:
Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only O(N*log(N)) if one assumes both integer comparison and random array indexing are O(1). While this might hold for bounded N, I believe complexity analysis is, theoretically, supposed to speculate about the asymptotic growth of a function, whereas it is obvious that you can't implement constant-time comparison or array indexing for arbitrarily large values. This makes me question the theoretical merits of such complexity analyses.

My question is: when there is a literature result such as X algorithm is found to be quasipolynomial, which set of primitive operations are assumed to be constant time?


texts:
So the definition of a compiler I got is that:

  A compiler takes a string as input and checks if that string is syntactically correct, then outputs "Yes" or "No".

So does that mean all compilers are Turing Machines?


texts: Show complement of language in same complexity class?

texts:
If $L$ is a binary language ($\Sigma = (0, 1)^*$) and $\overline{L}$ is the complement of $L$, the set of binary strings not in $L$.

How can I show that, if $L$ is in the complexity class $P$, then so is $\overline{L}$?


texts: Total bits required for a direct-mapped cache

texts:
I'm taking a course in computer architecture in which the main reference is the Computer Organization and Design by Patterson and Hennessy. I came across an example which I couldn't grasp its answer:

Example: how many total bits are required for a direct-mapped cache with 16 KiB of data and 4-word blocks, assuming a 32-bit address?

In the answer it says "We know that 16 KiB is 4096 (2^12) words. With a block size of 4 words (2^2),
there are 1024 (2^10) blocks".

But how do we know how many words would be 16 KiB?

And then it goes on and says the total bits are (number of blocks) * (data (32 * 4) + tag and validation bits). why don't we count index or offset bits in total bits?

And finally it says number of tag bits is (32 - 10 - 2 -2). we have 10 bits for the index part, 2 bits for offset, what's the second 2 bits we are subtracting from 32?

Honestly I think I have missed something when studying the textbook, or there are some assumptions I'm missing.

BTW the answer according to the textbook is 147 Kibibits (18.4 KiB).


texts: Efficient algorithm to check if a vector exists in the span of a subset of vectors

texts: I have a binary vector $v \in \mathbb{F}_2^m$ and a set of binary vectors $Q=\{q_1,q_2,\dots,q_n\}$ each belonging to $\mathbb{F}_2^m$ and I know that $v \in \text{span}\{Q\}$ but I want to know if there exists a subset $Q_k \subset Q$ of at most $k$ vectors ( i.e. $|Q_k| \le k < n$ ) such that $v \in \text{span}\{Q_k\}$. Is there a fast algorithm to do this other than the naive way of checking all the subsets of cardinality at most $k$? Assume that all of the operations are done in GF(2).


texts: Calculating Floating point Operations Per Second(FLOPS) and Integer Operations Per Second(IOPS)

texts:
I am trying to learn some basic benchmarking. I have a loop in my Java program like,

float a=6.5f;
int b=3;
for(long j=0; j<999999999; j++){
       var = a*b+(a/b);
    }//end of for

My processor takes around 0.431635 second to process this. How would I calculate processor speed in terms of Flops(Floating point Operations Per Second) and Iops(Integer Operations Per Second)? Can you provide explanations with some steps?

PS:I have already asked this question in StackExchange but did not get any answer.


texts: Confuse on using bucket number to replace hashing multiple times in hyperloglog explanation

texts:
In this blog the author states that the following

  So we now have a rather poor estimate of the number of values in the
  dataset based on bit patterns. How can we improve on it? One
  straightforward idea is to use multiple independent hash functions. If
  each hash produces its own set of random outputs, we can record the
  longest observed sequence of leading 0s from each; at the end we can
  average our values for a more accurate estimate.

can be replace with

  A better approach is one known as stochastic averaging. Instead of
  using multiple hash functions, we use just a single hash function, but
  use part of its output to split values into one of many buckets.
  Supposing we want 1024 values, we can take the first 10 bits of the
  hash function as a bucket number, and use the remainder of the hash to
  count leading 0s

I am confused on his description of replacement, can someone help me understand what does take the "first 10 bits of the hash function as a bucket number" mean? And how is it a direct replacement of the hashing multiple times and take the average.

Thanks

Edit:

The author claims that given a random hashed set of element, by counting the highest consecutive k prefix bit that is 0, you can estimate the cardinality of the distinct set to be 2^k.

But using 2^k once might not be a good idea, so he suggest using multiple hashing to determine the average of 2^k. For example given n distinct n hash function. 2^k_approximate = (2^k_1 + 2^k_2 + .....2^k_n)/n

However he claims that multiple hash can be be replace by using the first 10 bit of a single hash function as a bucket number. Which I don't quite understand why that would be similar to the original multi hash average technique.


texts: Bellman-Ford: Find all nodes that have minus infinite distance to source

texts:
Given a weighted, directed graph (V, E) may contains some negative cycles and a source node s, I would like to know for all node u, if there is a path from s to u but there is no shortest path from s to u (the distance from s to u is minus infinite). To do this I implemented a version of the Bellman-Ford algorithm:

Do V iterations of Bellman-Ford, save all nodes relaxed on Vth iteration to a queue `Q`
Do BFS with `Q` and find all nodes reachable from `Q`
All those nodes and only those can have infinite distance from `s`

Here is BFS:

visited(Q.first) = true
while Q not empty:
    u <- Q.deQueue()
    shortest[u] = 0 // there is no shortest path from `s` to `u`
    for all (u, v) in E:
        if not visited(v):
            visited(v) = true
            Q.push(v)

This algorithm is the best I can come up with and sadly it fails some test cases. I would be greatly appreciated if you guys can help, thanks.


texts: Is this "superset existence" problem NP-complete?

texts:
The "Superset Existence Problem":
Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y < |S|$, which is a superset of at least $z$ of those subsets?
To me, this feels like it should be NP-complete (in $|S|$), since it seems intuitively related to covering problems and minimum $k$-union. But I'm not sure where to start with the reduction.
So: is this problem NP-complete?


texts: Time complexity of an algorithm: Is it important to state the base of the logarithm?

texts: Since there is only a constant between bases of logarithms, isn't it just alright to write $f(n) = \Omega(\log{n})$, as opposed to $\Omega(\log_2{n})$, or whatever the base might be?


texts: Constant in Complexity of SQRT algorithm

texts:
this is my first question in CS so I apologize if this question is off-topic.

If we use Newton`s Method for finding square root then complexity is $O(M(n))$ (using Wikipedia Notation: $M(n)$ is the algorithm to multiply two $n$-digit numbers).

I am interested to know whats the constant hidden in Landau notation in this case and/or how can I calculate it.


texts:
This is actually exercise 3.7 from "Computational Complexity: A Modern Approach".

I need to prove that the NP-Completeness of 3-sat does not relativize, i.e. I need to show that that exists some oracle $A$ such that there exists $L\in \mathrm{NP}^A$ s.t. $L\not\leq_p\mathrm{3SAT}$, where the reduction can query the oracle for $A$.
A lead of some kind would be most helpful (I know that using locality in the proof for Cook-Levin Theorem ruins the relativization, but it doesn't help me find an example).

Another question popped on the way (I hope it's ok): why is $\mathrm{EXP}$ not low on itself, i.e. why
$\mathrm{EXP^{EXP}}\neq \mathrm{EXP}$? Cant I simply simulate the machine $M_L$ deciding some $\mathrm{EXP}$-Complete oracle $L$, for exponential number of steps and replace querying the oracle for input x with the output $M_L(x)$. Suppose $M\in \mathrm{EXP^L}$ runs in $2^{n^c}$ time, and $M_L$ runs in $2^{n^d}$, the machine replacing the oracle queries runs in at most
$2^{n^c}\cdot2^{n^d}$ and is therefore in $\mathrm{EXP}$.

Thanks!


texts: Number of cycles that arithmetic instruction takes for 25% improvement in performance?

texts:
The program has the following proportion of instructions:
Arithmetic: 70%
Load/Store: 10%
Branch: 20%

The question is to find the number of cycles on average that an arithmetic instruction take for a 25% improvement in performance if load/store and branch instructions are not improved at all?

How to proceed with such type of questions?


texts: Probabilities of duplicate mail detection by comparing notes among servers

texts:
I have the following problem:

We want to implement a filtering strategy in e-mail servers to reduce the number of spam messages. Each server will have a buffer, and before sending an e-mail, it checks whether there is a duplicate of the same message in its own buffer and contacts k distinct neighboring servers at random to check whether the duplicate is in another buffer. In case any duplicate message is detected, it will be deleted as spam, otherwise it will be sent after all negative replies are received.
Let us assume that there are N mail servers, and that a spammer sends M copies of each spam mail. We assume that all copies are sent simultaneously and that each mail is routed to a mail server randomly.

Given M, N and k I need to find out the probabilities that no spam message is deleted (i.e. no server detects spam), all spam messages are deleted (all servers detect spam) and spam messages are deleted from at at least one server.
So far, I have used combinations without repetition to find out the cases that need to be taken into account for an M and N. Now I need to find out the probability that one server receives at least two copies of a message, but I am at complete loss. Could you please provide some insight into the problem?


texts: What does it mean to prove that a set of binary integers is regular?

texts:
I'm not exactly sure what this question is asking me to do:

  Show that the set of binary integers (given as strings over $\{0, 1\}$) that are divisible by $3$ is regular, by giving a DFA that recognizes it. Leading 0s are allowed. The empty string should be accepted. Briefly explain your answer.

Is this asking me to construct a DFA where the set of binary integers add up to be divisible or the number of elements is divisible?

I understand that by constructing the DFA I prove that it is regular.


texts: Length of the certificate in complexity classes

texts:
A nondeterministic machine trying to decide membership in a language
  is presented with a hint (called a "witness" or "certificate") which
  proves membership (no such witness is provided for elements outside
  the language; the definition is asymmetric).

So, if a non-deterministic algorithm can solve a problem in O(f(n)) time, does this mean the length of the certificate is f(n) [Since it could try all the possible combinations and the length of the shortest one will be f(n)]? And the input size is n?

Also, if a deterministic algorithm A exists that can verify a certificate in O(f(n)) time, how does this imply the existence of a non-deterministic algorithm that can solve the problem in O(f(n)) time?


texts:
So I have a question:

Give a CFG for $\{a^i b^j : 2 i<j\}$

And this is my approach:

$S\to AB$

$A\to aAb\mid \varepsilon$

$B\to b \mid bB$

A confirmation, or correction, along with how you tested(and tips for testing future of my problems) will be greatly appreciated thanks.


texts: To show that a graph-problem is in $L$ or $NL$

texts:
Consider the following problem:

$$A=\left\{ (G(V,E),s,t)\mid\text{conditions 1, 2, 3 and 4 hold} \right\}$$

$G$ is a directed graph.
$s,t\in V$.
There is a simple path from $s$ to $t$ (a simple path is a path that visits every vertex not more than once).
$\forall v\in V: \deg^+(v)\leq 2$ (in words: every vertex in $V$ has outdegree at most 2).

Out of the following classes: $\mathsf{L,NL,P,NP,co-NP,EXP}$, I need to determine what is the smallest class (with respect to inclusion) that has $A$ in it.

My idea is: since every vertex has outdegree at most 2, I can write a function $F$, s.t for every $v\in V$ I'll recursively call $F$ with the two adjacent vertices of $v$.

The termination condition will be either if $\deg^+(v)=0$ (we've reached a leaf node) or $v$ has alredy been visited (this will make sure the path is simple) or $v=t$ (we've found a path to $t$), thus concluding that $A\in P$ (the complexity of the described algorithm is $n\log n$).

I'm just not sure if that is the best that can be done. Can it be shown that $A$ is in $\mathsf{L}$ or $\mathsf{NL}$?


texts: Is the languague L={, M accepts a finite amount of words} decdidable?

texts:
Is $L=\{<M> | L(M) \ is \ finite\} $ decidable ? M is a TM.
I think its relative simple to proof with the theorem of rice. But I am interested in a solution which does not use the Rice theorem.
This my try  :
Let f(<m,w>) be a function which works in the following way :

Run w on M
If M accepts Construct a TM Mwhich accepts only the word w and return M
If M rejects Construct a TM Mwhich accepts everything. Return M

So if m is in $A_{TM}= \{<M,w>|M \ accepts \ w\}$ we know that f(<m,w>) is in L. If m is not in A then we know that f(<m,w>) does accept every word and therefore infinity words. So f(<m,w>) not in L.
Is this a correct mapping reduction ?


texts: Dynamic programming for counting knapsack solutions

texts: Suppose the usual dynamic programming algorithm for the knapsack problem. If we swap the max    with an addition, does the modified algorithm compute all the solutions with benefit $\leq W$? I described the problem very briefly but I think anyone familiar with these notion wouldn't find any difficulty understanding what I ask. I think the complexity stays $nW$. Is it right?


texts: If NP is a subset of DTIME[n^O(log n)] then what happens?

texts: If $\mathsf{NP}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$ then what happens? Does it imply $\mathsf{NP}\neq \mathsf{EXP}$? Is there any other consequences such as $\mathsf{BPP}\neq \mathsf{EXP}$? Does it also give $\mathsf{PSPACE}\subseteq \mathsf{DTIME}[n^{O(\log n)}]$?


texts:
Let $~G~$ be unweighted unordered tree. I have some number of pairs of this tree's vertices $~(u_1, v_1), \dots, (u_n, v_n)$. I need to construct a smallest subgraph of original tree such that for each pair $~(u_i, v_i)~$ there is path connecting this pair of vertices. "Smallest" in the sense that the number of edges being used is the least possible.

Does this problem have some special name? Can anyone offer efficient algorithm to deal with it?


texts: Is it possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$

texts:
I am wondering if it is possible to simplify $O(A \times B \times C + A^B)$ into $O(A^B)$, i.e. omit the left part. $A$, $B$, and $C$ are all independent from each other.

Personally, I think that the simplification is possible. $O(A \times B \times C)$ is a polynomial growth, and (I think) it can be rewritten as $O(A^3)$, $O(B^3)$, or $O(C^3)$. On the other hand, $A^B$ is a exponential growth. As a result, it is possible to omit the left part from the Big O notation.

In other to test my hypothesis, I develop a simple simulation to compare $A \times B \times C$ with $O(A^B)$, the value of $A$, $B$ and $C$ range from 1 to 1000. According to my simulation, there are only $3\%$ chance that $A \times B \times C \geq A^B$. It is enough to omit $A \times B \times C$ from $O(A \times B \times C + A^B)$?


texts: How is this sorting algorithm Θ(n³) and not Θ(n²), worst-case?

texts:
I just starting taking a course on Data Structures and Algorithms and my teaching assistant gave us the following pseudo-code for sorting an array of integers:

void F3() {
    for (int i = 1; i < n; i++) {
        if (A[i-1] > A[i]) {
            swap(i-1, i)
            i = 0
        }
    }
}

It may not be clear, but here $n$ is the size of the array A that we are trying to sort.

In any case, the teaching assistant explained to the class that this algorithm is in $\Theta(n^3)$ time (worst-case, I believe), but no matter how many times I go through it with a reversely-sorted array, it seems to me that it should be $\Theta(n^2)$ and not $\Theta(n^3)$.

Would someone be able to explain to me why this is $Θ(n^3)$ and not $Θ(n^2)$?


texts: Why is adding log probabilities considered "numerically stable"?

texts:
Every once in a while, I come across the term numerical stability, which I don't really understand. In particular, I have seen a description of the practice of "adding logs rather than multiplying numbers" as "numerically stable." I would like to know why this is considered numerically stable.

By "adding logs rather than multiplying numbers" I mean that if you have several numbers, for example 0.01, 0.001, 0.0001, and you want to get their product, you can instead add the logs of each term. In this case assuming log base 10, the result would be -2 -3 -4 = -9. This doesn't give you the same output as multiplying, but it's a good way to get something like the product so that you don't experience numerical underflow.

My question is that I'm a bit confused because the definitions of numerical stability I've found on the Internet don't seem to apply to this case. The definitions of "numerical stability" I've found are that it occurs when a "malformed input" doesn't affect the performance of an algorithm, see for example here. In this case I don't really see how we would consider the numbers 0.01 etc "malformed," they are what they are. It would be more accurate to say that the algorithm (of multiplying them) is bad in this context since the computer can't handle it, so we choose a better algorithm. So why do people say this is "numerically stable"?


texts: Space(n) not closed under Karp reductions - what about NTime(n)?

texts:
In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't.

To show that $Space(n)$ isn't closed under Karp reductions, the suggested technique (both in the solutions given at my place of study as well as those given at many other universities) is to assume we have a TM that decides language $L$ in $Space(n^2)$. Now take an encoding $enc(x)$ of some $x$ in $L$ with $|enc(x)| = n$ and blow it up (in quadratic, thus polynomial time) to an encoding $enc'(x)$ of $x$ with $|enc'(x)| = n^2$ by padding the smaller encoding with $n^2-n$ padding symbols. Now we take the same TM, and it can decide $L$ in space linear in $enc'(x)$ by ignoring the padding stuff and just operating on $enc(x)$. This implies that $Space(n^2) \subseteq Space(n)$, which contradicts the space hierarchy theorem, so $Space(n)$ can't be closed under Karp reductions.

My problem here is that while I realize that we can easily show that $NP$ is closed under Karp reductions, it somewhat confuses me regarding what this says about $NTime(s(n))$. It seems to me that this approach will also work to show that $NTime(s(n))$ isn't closed under Karp reductions for any time-constructible function s(n) using the time hierarchy theorem, or am I mistaken here?


texts: Time complexity of a recursive function which generates all combinations of an array

texts:
The following function getCombinations, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would appreciate the workings or simply an idea about how to approach this. Thanks in advance
function getCombinations(chars) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}


texts:
We are given N sets, each of which has a finite number of pairs $(x_i,y_i)$.

$M_1=\{(0,0), (x_{1,1},y_{1,1}), ...\}$

...

$M_N=\{(0,0), (x_{1,N},y_{1,N}), ...\}$

The problem is to select one and only one item from each set such that

$Min \{\displaystyle\sum_{j=1...N}(x_{i,j})\}$

s.t. $\displaystyle\sum_{j=1..N}(y_{i,j}) > R$

where $R$ is a given constant.

Is there any classic problem similar to this? or what is known about this class of problems?


texts: What is the difference between these terms?

texts:
Between my textbook and various online sources (namely wikipedia), I'm very confused... can somebody clear up which words are synonymous and which mean different things?

Many-to-one reduction
Mapping reduction
Turing reduction
Cook reduction
Karp reduction
Polynomial-time many-to-one reduction
Polynomial time turing reduction

I've also seen others, but I can't recall them currently.


texts: How probable is a deadlock in the dining philosophers problem

texts:
I created this simulation of the dining philosophers problem, but did not manage to initialize it with four philosophers without running into a deadlock:

*Philosophers are represented by black beads. They think when running in small circles and eat when running in bigger circles. Forks are represented by yellow beads. The number of meals are counted.

Might it be the case that for $N=4$ participating philosophers a deadlock must inevitably be reached? Or can a situation be described in which four philosophers can eat for ever and ever?

I am looking for a quantitative model and analysis of the dining philosophers problem.

Let $N$ be the number of philosophers. Let the problem be implemented as an algorithm that takes as inputs the set $T_k$ of partial functions $t: [N] \rightarrow [k]$ with $t(i)$ being the point in time when philosopher $i$ starts trying to pick the fork to his left (maybe never). The algorithm stops when it detects a deadlock or an oscillating state in which a philosopher starves.

I wonder especially about the probability $p_{stop}^{(k,n)}$ that the algorithm will stop, depending on the number $n$ of philosophers that join the diner, $n \leq N$.

$$p_{stop}^{(k,n)} = \frac{|\text{functions $t \in T_k^n$ for which the algorithm stops}|}{|T_k|}$$

with $T_k^n$ the functions $t\in T_k$ with $|\text{dom}(t)| = n$.


texts:
This problem is related to ”Normal coloring of cubic graphs (part 1)  - a previous post.  We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, rather than the more general normal edge $k$ colorability).

  Definition A normal edge 5 coloring (or normal 5 coloring) of a cubic graph $G$ is a proper coloring of the edges with 5 colors, so that for any edge $e\in E(G)$, the four edges adjacent to $e$ are colored with two colors, or with four colors.

Thus, an edge $e$ and its four adjacent edges might utilize three colors, or five colors.

  If three colors are used, $e$ is called poor, and if five colors are used, $e$ is called rich.

...

  Question I would like to know how to transform an instance of this problem to a CNF formula.  That is, given a graph $G$, produce a CNF formula, such that a satisfying assignment can be translated back to a normal 5 coloring of the graph.

Note that working with the line graph of the cubic graph, as one would in dealing with a typical edge coloring problem, is a bit tricky (and that is all I dare to say).

Please advise if this question would be better off if posted in the theoretical computer science pages. Thanks in advance.


texts: Find $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$

texts:
Let $L_\epsilon$ be the language of all $2$-CNF formulas $\varphi$, such that at least $(\frac{1}{2}+\epsilon)$ of $\varphi$'s clauses can be satisfied.

I need to prove that there exists $\epsilon'$ s.t $L_\epsilon$ is $\mathsf{NP}$-hard for any $\epsilon<\epsilon'$.

We know that $\text{Max}2\text{Sat}$ can be approximate to $\frac{55}{56}$ precent of the clauses from a $\text{Max}3\text{Sat}$ reduction. How should I solve this one?


texts: Why can't we generate the output of a cellular automata at time step t without first generating all the preceding states

texts: Why can't we generate the output of cellular automata at time step t without first generating all the preceding states? Why can we do this for some functions? What features of a function does it relate to? Is it about whether it can be graphed as a line or a curve? Why can't we come up with a function that takes in a cellular automata ruleset and a timestep t and gives us the output in constant time with respect to t?


texts:
In Motwani and Raghavan's textbook, p38-39, they states:

A sequence $C_1, C_2, C_3, \dots$ of circuits is a circuit family for function $f_n\colon {0,1}^n \rightarrow \{0,1\}$ if $C_n$ has $n$ inputs and computes $f_n(x_1, x_2, \dots, x_n)$ at its output for all n-bit inputs $(x_1, x_2, \dots, x_n)$. The family $C$ is said to be polynomial-sized circuits if the size of $C_n$ is bounded above by $p(n)$ for every $n$, where $p(\cdot)$ is polynomial.

It is clear that this is the definition of P/poly. And the next paragraph is the definition of RP/poly.

A randomized circuit family for $f$ is a circuit family for $f$ that, in addition to the $n$ inputs $x_1, x_2, \dots, x_n$, takes $m$ random bits $r_1, r_2, \dots, r_m$, each of which is equiprobably 0 or 1. In addition, for every $n$, the circuit $C_n$ must satisfy two properties:

If $f_n(x_1, x_2, ..., x_n)=0$, then the output of the circuit is 0 regardless of the values of random inputs $r_1, r_2, \dots, r_m$.
If $f_n(x_1, x_2, ..., x_n)=1$, the the output of the circuit is 1 with probability at least $\frac12$. In other words, at least one half of the $2^m$ choices of the bits $r_1, \dots, r_m$ will result in the circuit evaluating to 1. We will refer to such $m$-tuples $r_1, r_2, \dots, r_m$ as witnesses for $(x_1, x_2, \dots, x_n)$, in that they testify to the correct value of $f_n(x_1, x_2, \dots, x_n)$ when it is 1.

Question: I don't understand what is relationship between $n$ and $m$ or $r_1, \dots, r_m$ and $f_n(x_1, x_2, \dots, x_n)$? For example, we have n inputs, i.e. $x_1, x_2, \dots, x_n$. But, in second property, they states that at least one half of the $2^m$ choices of the bits $r_1, \dots, r_m$ will result in the circuit evaluating to 1. Now, how did we bring $r_1, \dots, r_m$ to $f_n(x_1, x_2, \dots, x_n)$?


texts: Difficulties proving when a language is in P or is NP-complete

texts:
I have some difficulties in understanding how to prove when a language is in P or is NP-Complete. Specifically, consider the following decision problems w.r.t undirected graphs $G = (V, E)$:

$L_1 = \{ \langle G = (V, E), k\rangle \mid \text{$G$ consists of connected} \\ \text{components of size at most $\log|V|$ each, and has a vertex cover of size $k$}\}$

$L_2 = \{\langle G = (V, E), k \rangle \mid \text{$G$ consists of two connected} \\ \text{ components  of size  $\frac{|V|}{2}$ each, and has a vertex cover of size $k$} \}$

I think that $L_1$ is in $\text{P}$, and $L_2$ is in $\text{NP-complete}$. Am I right? How can I prove that?


texts: Is a graph of zero nodes/vertices connected?

texts:
Suppose there is a graph G of zero nodes, there is an even number of nodes. By definition of connectivity, the graph G is connected when there is a path between every pair of nodes. But there are no pair of nodes since there are zero nodes.

Does this mean G is connected because there is a path for every pair of nodes (in this case zero) or would this mean G is not connected because there are no paths?


texts: Maximizing product of list of integers whose sum equals n

texts:
Given a positive integer n, find the list of positive integers whose product is the largest among all the list whose sum is n. For example, if n is 4 the desired list is 2, 2 because 2x2 = 4 is larger than 1x1x1x1 = 1, 2x1x1 = 2 and 3x1 = 3, if n is 5, the desired list is 2, 3.
What is the desired list if n = 2001?
Actually, what is an algorithm to generate this list? After tried lots of examples, I discern (hope am right) for n > 5 it's a list of 3's, and a remainder n % 3.
So, for n = 2001, I got a list of 667 3's.
Question
If Correct, what property of 3 makes it the ideal integer in that it composes (mostly) this list?.


texts: Minimal number of states for an NFA of all different words

texts:
Given $\Sigma =\{0,1,@\}$, I am looking at a language $L=\{u@v | u,v\in \{0,1\}^k\wedge u\neq v\}$. So $u,v$ have only $0,1$s, same length $k$, yet are different.
Also, for me $k$ is a known constant. So the language ìs regular (at most $(2^k)\cdot (2^k-1)$ words).
I want to build the most efficient NFA for $L$. So far, I have been able to cone up with an NFA of $O(k^2)$ states, but I want to find one with $O(k)$ states. Of course one could argue that as $k$ is constant, its the same as $O(1)$, but assuming $k$ is a constant parameter - that is, given a value of $k$, I construct $L$ and an NFA for $L$ with $O(k)$ states.
My idea to use $k^2$ states:

A path for each index, as $u$ and $v$ of size $k$... they differ means there is at least one $1\leq i \leq k$ where they differ at that character.
Read '0' in $i$th character and '1' in $i+k+1$th character (due to '@'). Or other way.
In between make sure that $u$s length and $v$s length is $k$. Which characters you read in between? I don't care.

But this will give me around $2k$ states (I can do a bit less, but still $O(k)$) for each index. Total $O(k^2)$, as there are $k$ indices.
I would ask for a way to improve my idea, to use $O(k)$ states. Or maybe a totally different approach.


texts: Local search (Hill Climbing) scope and definition

texts:
I'm taking an artificial intelligence class and in one of the recent lectures the topic was local search algorithms, more specifically Hill Climbing. At one point the professor showed the classic 8-queens puzzle to illustrate the algorithm working, he stated that in it a queen can only move one row up or down, so for example in a column with the following configuration:

In the first iteration the queen can only move to either rows 4 or 6 (8 rows, 0-based index), then in the next iteration it would be stuck in a local maxima because neither row 3 nor 7 have values lower than 14, so the algorithm would then proceed to the next column or terminate. He argued that even tough a queen can legally move directly through all the rows of its column doing so would make the algorithm fall of the concept of "Local search", because a local search move is limited to only one of its closest neighboors per time/iteration.

I found this weird because it appears to me that such a limitation greatly reduces the usefulness of hill climbing (in the  8-queen problem it makes the success rate abysmal). So I would like to know what's the correct/formal definition of local search and hill climbing, should it always be constrained to the closest neighboor? what constitute a closest neighboor? I would especially appreciate some book references.


texts: Sample Complexity for Real-Valued PAC-Learnable Functions

texts:
Can anyone shed some light on how the VC Dimension affects the sample complexity bounds of infinite hypothesis classes with real-valued outputs in PAC learning, or how to calculate the sample complexity bounds of said classes with some other measure of the class's 'complexity'?

I'm studying machine learning theory, particularly the PAC model, and been having trouble finding some definitive upper and lower bounds on the sample complexity for real-valued hypothesis classes, like those given for binary classification classes with the 0-1 Loss. I know the PAC model and VC Dimension have been generalised to real-valued functions, but at this stage the actual work of Vapnik is a bit impenetrable to me. Still, the VC Dimension still seems like a very intuitive measure to use when determining number of samples you're likely to need to learn a given class; too few samples given the complexity and your learner can't have a clear enough picture of the underlying distribution, and too many and those extra samples aren't really going to improve the learner's capability to learn.

The literature that's out there seems very disjointed, I understand the field is constantly in motion so I'm trying to catch up, without necessarily knowing where 'up' is.


texts: What are open-loop and closed-loop modes of neural networks?

texts:
I came across the following line in the book ‘Deep Learning (Ian Goodfellow) 10.2.1, pg 374;

The disadvantage of strict teacher forcing arises if the network is going to be later used in an open-loop mode, with the network outputs fed back as input.

Please explain the difference between these modes.


texts: Average branching factor of an undirected graph

texts:
I'm trying to determine, given an unweighted undirected graph, the maximum number of leaves of any travelling of the graph, which means, the maximum number of leaves among all traversals of every spanning tree of the graph.

I know that, given a tree of $n$ nodes, an average branching factor $b_f$ and $n_l$ leaf nodes, these three variables are related as follow:

$$b_f = \frac{e}{n-n_l} \Rightarrow n_l = n - \frac{e}{b_f}$$

where $e = n - 1$ (the number of edges).

However, if instead of an undirected tree you have an undirected graph of $n$ nodes and $e = n - 1 + k$ edges (or with $k$ fundamental cycles), different traversals of the graph would give you different spanning trees, depending on which one of those $k$ edges are the one being ignored from the graph.

Is there any known property of graph's spanning trees that can offer an upper bound on the number of resulting leaves nodes of any traversal?

My best approximation so far is that, the maximum number of leaves must be bounded by $$n_l <= |\{n_{e^1}\}| + 2k$$ where $|\{n_{e^1}\}|$ is the number of nodes of the graph with degree 1, and $k = e - n + 1$.

That's a worst case scenario where there exists $k$ edges in the graph connecting nodes with degree 2 each, whose removal doesn't create new connected componentes, because removing them will give $2k$ nodes with degree 1 each, and thus $+ 2k$ leaves. If $k$ is very low that can be an acceptable good approximation, but the biggest the connectivity of the graph, the worst the significance of the approximation.

If someone could give a better approximation based on the average degree of the graph or something similar that can be calculated on a first traversal would be appreciated.


texts: Proof sketch that NP total search problems cannot be NP-complete

texts:
From a blog post, about proving that NP total search problems cannot be NP-complete unless NP=co-NP.

It's possible to write a convincing proof sketch as follows. Consider what would it would mean if an NP total search problem (like FACTORING) was NP-complete. There should then be a poly-time reduction from (say) SAT to FACTORING. That is, an algorithm $A$ that can solve SAT efficiently, provided that it has access to an efficient solver for FACTORING.
Now consider what happens when pass a non-satisfiable formula $\Phi$ to $A$. What you end up concluding is that any run of $A$ must constitute a (short) certificate that $\Phi$ is not satisfiable, implying NP=co-NP. $A$ will process $\Phi$, from time to time constructing instances of FACTORING that it can solve “for free”. Since every such instance of FACTORING must have a solution, A cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance, so must run its course. If it ends without finding a satisfying assignment, there isn’t one.

I don't understand the second paragraph. So we pass a non-satisfiable formula $\Phi$ to the algorithm $A$, which processes $\Phi$ and possibly constructing instances of FACTORING to solve for free. These instances always have a solution. I can understand up to here.
So $A$ cannot fail for reasons of presenting the FACTORING oracle with an unsolvable instance. (This seems like an obvious statement -- how is it useful?) From here, why must it be the case that NP=co-NP?


texts: Efficient ways to avoid cycles in a graph

texts:
I am trying to implement an algorithm called the 'rapidly exploring random belief tree'. The aim of this algorithm is to come up with a path for a robot, which, instead of connecting start and goal with a least distance metric or something similar, drives the robot into areas where it can get high accuracy measurements, and only then moves to the goal.

In the implementation of the algorithm, I start off by building a graph through random sampling of a given space. Every time a new point is sampled, a new edge is added to the graph. Initially, the error in the position of the robot will be high, as it won't be getting good measurements, but once the tree I am exploring through reaches the 'good' area, the robot's error suddenly drops, and with this knowledge of where the 'good' area is, I traverse backwards through the graph, pruning previously connected edges and connecting those vertices towards the good area. Given enough samples, in an optimal scenario, the graph would be propagating outward from the good area, hence connecting any two vertices would guarantee that you would pass through these points.

Here's where I have a problem. Once I start the traversal to prune and update my edges, the algorithm shouldn't prune the edges that connect the good area to the starting point, which would result in an infinite loop. An example is shown in this picture:

The algorithm finds vertices 1, 2, 3 and 4. The connections are 1 -> 2, 2 -> 3, 2 -> 4.
Now we find #5, which is a 'good' area for the robot. Visiting this vertex will magically enhance its accuracy in the future. I find neighboring vertices from 5: I find #3. I update the parent of #3 to #5 instead of #2. Now if there were more vertices surrounding #3, I would traverse those too, and update their parents to #3 etc., thus creating a path from #5 to all of those. (For more information, the traversal essentially computes the covariance of the robot if it were to move from #5 to #3 and whether that's more desirable than moving from #2 to #3).
But in no circumstances should I update the parent of #2 to #3: because the only way the robot got to #5 in the first place was through #2.

To avoid this, a simple (but highly inefficient?) thing I did was to compute the shortest path to the vertex from where I began my traversal, and if any vertex I come across during traversal is part of this path, I don't update its parent. This works reasonably well, at the expense of a lot of computational cost because I need to do this every time I have to traverse backwards with an update, so I was wondering if there was a better, efficient way of doing this.


texts:
Taken from Wikipedeia:

A simple voting game, taken from Game Theory and Strategy by Phillip D. Straffin:
[6; 4, 3, 2, 1]
The numbers in the brackets mean a measure requires 6 votes to pass, and voter A can cast four votes, B three votes, C two, and D one. The winning groups, with bolded swing voters, are as follows:
AB, AC, ABC, ABD, ACD, BCD, ABCD

Using a non-trivial structure, we know that ABCD will always be a member of the set of winning groups. Also, we know that if AB is a winning group, then ABC and ABD are also winning groups. In other words, the set of winning groups AB, ABCD is invalid. Thus, any member of the set, besides ABCD, can be constructed by removing a single element from another set in the group. (Edit: While this is true, it gives the wrong impression.)
In the beginning, the goal was to generate the set of possible winning groups for a given number of players. Using three players as an example, the set of winning groups is:
{1, 2, 3}

{1, 2, 3}, {1, 2}
{1, 2, 3}, {1, 2}, {1}
{1, 2, 3}, {1, 2}, {2}
{1, 2, 3}, {1, 2}, {1}, {2}

{1, 2, 3}, {1, 3}
{1, 2, 3}, {1, 3}, {1}
{1, 2, 3}, {1, 3}, {3}
{1, 2, 3}, {1, 3}, {1}, {3}

{1, 2, 3}, {2, 3}
{1, 2, 3}, {2, 3}, {2}
{1, 2, 3}, {2, 3}, {3}
{1, 2, 3}, {2, 3}, {2}, {3}

{1, 2, 3}, {1, 2}, {1, 3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}
{1, 2, 3}, {1, 2}, {1, 3}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {2}, {3}
{1, 2, 3}, {1, 2}, {1, 3}, {1}, {2}, {3}

# and so on...

This is doable through a relatively simple algorithm as thankfully offered here.
(Edit: That algorithm does what was requested, but, per my oversight, generates false positives, e.g. {{1, 2}, {1, 3}, {1, 2, 3}, {1, 2, 3, 4}}.)
However, I want to only generate one set per "isomorphic group." For example, the sets {1, 2, 3}, {1, 2} and {1, 2, 3}, {1, 3} are the same if we swap the labels of 2 and 3. This is the primary goal.
The secondary goal is to only generate the sets of winning groups that could be realized through a voting structure. Using a four player system and a maximum of 20 votes per person, I found sets of winning groups that satisfied the above criteria, but could not be realized. (Edit: See previously mentioned false positives and the answer below.)


texts:
An array $A[1...n]$ is said to be k-ordered if
$$A[i - k] \leq A[i] \leq A[i + k]$$
for all $i$ such that $k < i \leq n - k$.
For example, the array $A = [1, 4, 2, 6, 3, 7, 5, 8]$ is 2 ordered.
Q1. In a 2-ordered array of 2n elements, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

Q2. In an array of 2n elements, which is both 2-ordered and 3-ordered, what is the maximum number of positions that an element can be from it's position if the array were 1-ordered?

a) 2n-1                b) 2
c) n/2                 d) 1                 e) n

I can understand how the example array is two ordered, but I am having trouble understanding what the questions 1 and 2 are trying to say.
Can someone please explain to me the meaning of the questions in simple terms?
Thanks!
P.S. First time questioner here. Sorry if I missed anything.


texts: Assume we have a big 2d array. All its elements are either zeros or natural numbers. A local minimum is an element that is less than all its 8 neighbors. Is there an effective algorithm to find all local minima in the array?


texts: Differences between linear/nonlinear vs. deterministic/nondeterministic neural nets

texts:
When speaking of neural networks, I don't get the difference between nonlinear and non-deterministic. Basically, both say that the output of something is not directly correlated to the input?

Hope someone can illuminate me.


texts:
Our problem is: Given an undirected graph, does it have a vertex cover consisting of $k$ vertices?

A vertex included in this vertex cover variant will cover every edge incident to it and every edge incident to some edge incident to it. Hence, we call this variant a vertex cover with covering radius 2.

What is the computational complexity of this problem?


texts: Conservation Law in Finite difference Scheme

texts:
I am using a Finite Difference scheme to solve a simple PDE in conserved form:

$$\partial_t u = \partial_x (\partial_x u +au\partial_x u) = (1+a)\partial_x^2u +a(\partial_x u)^2 $$

$$\frac{u_n+1,j - u_n,j}{dt} = (1+a) \frac{u_n+1,j+1 - 2 u_n+1,j + u_n+1,j-1}{dx^2} + a \bigg(\frac{u_n,j+1-u_n,j-1}{2 dx}\bigg)^2$$

As you see, I use a fully implicit scheme for the diffusive part, and an explicit scheme for the first derivative bits (squared). It can easily be seen that the PDE states the conservation of the integral of $u(x,t)$, because:

$$\partial_t \int_0^L u(x,t)dx=\int_0^L\partial_x(\partial_x u +au\partial_x u)dx=[\partial_x u +au\partial_x u]_0^L$$

So if I impose Neumann boundary conditions, $$\partial_xu\bigg|_{0,L}=0$$ the integral of $u(x,t)$ must be conserved. I implement the Neumann BC saying that:

which is second order (notice that I use three points to derive this, it is equivalent to approximating the function $u(x,t)$ at the boundary with a parabola)

Now, when I solve and plot, I hardly see any conservation of the integral of $u(x,t)$. Is there something I am missing?

The profile of u(x,t) (different colors different times):

The integral of $u$ and its maximum over [0,L]:

The quantity inside the $\partial_x(...)$ (different curves different times):


texts:
What is the definition of an "orthogonal greedy algorithm"?

What is the definition of a "relaxed greedy algorithms"?

Can you give an example to illustrate how these notions differ from ordinary greedy algorithms?

Wikipedia's article on greedy algorithms says:

  There are a few variations to the greedy algorithm:

  Pure greedy algorithms
  Orthogonal greedy algorithms
  Relaxed greedy algorithms

Wikipedia does not explain further or provide any examples, so it's not clear what the Wikipedia article is referring to.


texts: If recursive Fibonacci is $O(2^N)$ then why do I get 15 calls for N=5?

texts:
I learned that recursive Fibonacci is $O(2^N)$.

However, when I implement it and print out the recursive calls that were made, I only get 15 calls for N=5. What I am missing? Should it not be 32 or near abouts? It's like less then half!

$COUNT = 0

def fibonacci( n )
   $COUNT +=1
   return  n  if ( 0..1 ).include? n   # Base Case returns 0 or 1
   fibonacci( n - 1 ) + fibonacci( n - 2 ) # Recursive case
end


texts: how to prove original intervals and canonical form of intervals have the same interval graph

texts:
According to this paper,a family of intervals is said to be canonical if the coordinates of the endpoints of the intervals are distinct integers between 1 and 2n where n is the number of intervals.

Here is the example
Original intervals = {[2,5], [3,11], [6,9], [7,13], [8,18], [12,16], [15,19]}

Canonical form of intervals = {[1,3], [2,8], [4,7], [5,10], [6,13], [9,12], [11,14]}

These original intervals and canonical form of the original intervals give the same interval graph, but how can I prove that it is always the case mathematically ?

Edit: This is the method I use to create canonical intervals:
I sort the intervals according to their starting points in ascending order
Then, I assign the first interval's [2,5] starting point as 1. Then, I compare it with the following intervals to see the overlappings. Then, I arrange the intervals accordingly.

I repeat this process for all intervals.

Examples:

[2,5] contains only the starting point of interval 2, so

[2,5] becomes [1, (start of interval 2), 3] = [1,3]

[3,11] contains, start of interval 3, start of interval 4, end of interval 3, and start of interval 5, so

[3,11] becomes [2, 3, (start of interval 3), (start of interval 4), (end of interval 3),(start of interval 5),8] = [2,8]

note: interval 2 can not start here because at point 3 because it is where interval 1 ends. All start and end points should be distinct.


texts:
Take a graph $G=(V,E)$ .

As we know both DFS and BFS are graph search algorithms .

But why the algorithm for BFS is designed in such a way that it does not cares about the vertices that are not connected to the source vertex  $s$  but DFS takes care about all vertices in $V$.

I mean if $G$ has $l$ connected components and a vertex $s$ is in one of the connected component among $l$ , then if $s$ is the source vertex for BFS , then BFS performs only traversal on the only one connected component (which contains $s$).

If $G$ is input for BFS , it constructs one BFS tree (for component which contains $s$).

But in case of DFS , it constructs a DFS forest with $l$   DFS trees.

Why no BFS forest and it is restricted to a specifc component (containing $s$)?  Any reason involved ?

For Bfs algorithm page # 595 and for Dfs algorithm page # 604 from here


texts:
I'm trying to figure out of if there's a way to generate all unique sets of integers of length K, where each member has an upper bound of N, and a lower bound of M, without tracking which sets have already been generated, where the order doesn't matter.
To be clear: I'm not looking for ways to filter duplicates from a pre-computed set of sets.
I'm asking if there is an algorithmic approach to generate the unique combinations of values, without producing duplicate combinations/repetitions along the way that must be tested for and removed.
For example, I wrote this counter, which will generate all sets of length K with members bounded at N, but with duplicates.
JavaScript:
function count(k, n, m = 0) {
    // Create counting columns
    let cols = Array(k).fill(m);
    let rows = [];

    while (true) {
        rows.push(cols.slice(0));

        for (let j = 0; j < k; ++j) {
            ++cols[j];

            if (cols[j] <= n) {
                break;
            } else if (j === k - 1) {
                return rows;
            }

            // If no overflow, reset column and increment the next on next loop
            cols[j] = m;
        }
    }
}

Output:
> let k=3, n=5, m=1

> count(k, n, m).join('\n');

"1,1,1
2,1,1
3,1,1
1,2,1
2,2,1
3,2,1
1,3,1
2,3,1
3,3,1
1,1,2
2,1,2
3,1,2
1,2,2
2,2,2
3,2,2
1,3,2
2,3,2
3,3,2
1,1,3
2,1,3
3,1,3
1,2,3
2,2,3
3,2,3
1,3,3
2,3,3
3,3,3"

But, as you can see, that produces 1,2,3 as well as 3,2,1.
An example case: if I'm searching for sums of cubes that equal a cube, I don't need to test 2^3 + 16^3 + 12^3 = 18^3 if I've already checked that 2^3 + 12^3 + 16^3 = 18^3.
So I wouldn't want to generate an equivalent set again after having already tested an alternate order of the same terms.
Many thanks.


texts:
I found a proof that shows CFL is closed under inverse homomorphism.

First of all the Definition of an homomorphism and its inverse:

$h: \Sigma^{*} \rightarrow \Delta^{*} \ \ \ h(L) = \{h(w) |w \in L\}$

$h^{-1}: \Delta^{*} \rightarrow \Sigma^{*} \ \ \ h^{-1}(L) = \{w | h(w) \in L\}$

The proof I found works as follows:

Let $L = L(A)$ for some PDA $A$.
Construct PDA $A’$ to accept $h^{-1}(L)$.
$A’$ simulates $A$, but keeps, as one
component of a two-component state a
buffer that holds the result of applying
$h$ to one input symbol.

I really can't get my head around that intuition.
My approach was to create an example:

Let $L=\{a^{n}b^{n} | n \in \mathbb N\}$ and $h: \{a,b\}^{*} \rightarrow \{0,1\}^{*} | \ \ h(a) = 01, h(b) = 1$

$\Rightarrow h(L)= \{(01)^{n}1^{n} | n \in \mathbb N\}$

I would then create an PDA $A$ that accepts my $h(L)$ and PDA $A'$ (because I already know how my inverse image looks like) that accepts $L$.

And that is the point I got stuck. I know that I need a different PDA for $A'$ with some sort of buffer but I don't know how to realise that.

My Question: Can someone explain the proof a little bit more detailed. And what it means that $A'$ simulates $A$?


texts: Finding the equivalence classes of a language

texts:
I'm doing a problem where I need to find the $≡_A$ equivalence classes of the language
$$A = \{ 0^{n}x \mid n \in \mathbb Z^+, x \in \{0, 1\}^*, \text{ and } \#_0(x) ≥ n \}. $$

The best way I've learned to find the equivalence classes from a formal language is to create an automation and minimize it. Is there a conventional way of finding the equivalence classes of a language more quickly and intuitively? Because I do not know the DFA for this problem. Thanks for the help!


texts:
I'm not sure if this is the correct place to ask this kind of a question, but here goes:

I'm doing my own reading of the Principles of Program Analysis book, and i'm having trouble understanding some priciples from Chapter 5 - Type and Effect Systems.

In the book (page 286) there is an example:

I can not understand, why do they start with the expression funF f x => ...
Is this maybe guessing the values of the types of the bound variables f and x, we just assume that f is of type function that takes a function and returns a function, and that x is of type function (because it seems about right)?

After that we have to determine the type of the function body, so we move to f (fnY y => y). From the assumed types, we infer the type f (the top bottom rule in the image), and then we move to: fnY y => y, and it is streightforward that the type of that expression is t -> t (a function that returns the same type that it was given).

Now that we know this, we can determine the type of the function application  f (fnY y => y) as t -> t.

Then again we move up to determine the type of funF ... which accoring to the rules for recursive functions is streight-forward (the same type as for f in the assumed typed enviroment)..

Then we move to the in body: g (fnZ => z). g's type has already been determined immediatly above, so we move to fnZ => z which is the same as for fnY. And in the end we get that the whole expression has the type: t -> t.

What i'm asking is: is this the correct trail of thought? Or i'm i missing the point somewhere?

I'm not sure about the guessing part, why did we start where we did, why not more simply with variable y or somewhere else? The rest of the chapter heavily depends on the proper understanding of these concepts, and i would like to understand this.

In general, I would be grateful if somebody could point me out to a book or something that, in more details explains type systems.

Thank you!


texts: How to prove that a minimum edge cover is a forest?

texts: How can it be proved that any minimum edge cover is a forest? As far as I understand an edge cover could be one connected component therefore a spanning tree). If it's the case then it wouldn't be a forest.


texts: Why do we use persistent data structures in functional programming?

texts: Functional programming employs persistent data structures and immutable objects. My question is why is it crucial to have such data structures here? I want to understand at a low level what would happen if the data structure is not persistent? Would the program crash more often?


texts: How to collect all states of a behavior in TLA+?

texts:
Description of the problem:

I am modeling checking a distributed protocol against a global property with TLA+ developed by Leslie Lamport. The global property is defined on all states of a behavior (more details can be found below). However, by the nature of exhaustive enumeration of model checking, the state transition graph explored consists of all states of all behaviors. How should I collect all states of each behavior against which the global property can be checked?

More on the global property:

Consider an implementation of a replicated list object. The property requires that for any two list states, e.g., $l_1$ and $l_2$, across the whole system, if they contain two common elements such as $a$ and $b$, then $a$ precedes $b$ in $l_1$ if and only if $a$ precedes $b$ in $l_2$.

My solution is to check this property against each behavior. This requires to collect all states of a behavior. Is this feasible? Are there better solutions?

Note: This is a re-post.


texts: Difference between hypervisor and exokernel

texts:
An hypervisor (1st type) is a software that creates and run virtual machines, managing guest's operative systems's requests to the hardware.
An exokernel is an operative system kernel, that let's programs access directly to the hardware or, with the support of specific libraries that implements abstactions, run different types of executables for that architecture.

Both the two are an abstraction layer between hardware and application software.
Both the two let you run on the same machine different executables/software/operative systems/whatever

So what's the difference between the two?


texts: Do we need to check for mantissa overflow in floating point multiplication?

texts:
We do check for the mantisas overflow in floating point addition

e.g.

If we are adding $8.02 \times 10^3 + 9.01 \times 10^3 =17.03 \times 10^3$ i.e we get an overflow, so we shift the number right and increase the value of exponent.

But does it occurs during floating point multiplication?

According to my logic, it should occur. because $9.99\times9.99=99.80$ which is a mantissa overflow, but that's not the case.

I have referred to Morris Mano's books and William Wtallings Computer Organization and Architecture book but none of those books mentioned about floating-point multiplication mantissa overflow.

So I feel like I am wrong.

Please tell me where I am wrong?


texts: Problems of cyclic executive approach for scheduling of real time systems

texts:
I have a doubt on the cyclic executive approach for scheduling on real time systems. From Alan Burns's book Real-time Systems and Programming Languages.

  This final property represents one of the major drawbacks of the
  cyclic executive approach; others include (Locke,1992) [...] the
  difficulty of incorporating processes with long periods; the major
  cycle time is the maximum period that can be accommodated without
  secondary schedules [...]

Why is it a difficulty to incorporate processes with long periods?

Also I'm reading some notes that claim:

  If the periods are of different sizes the number of minor cycles
  becomes too big.

Can anybody give me an example of this case?


texts: Response time of scheduling a DAG where each vertex is a task

texts:
Suppose I have a directed acyclic graph where each vertex $v$ represents a task with a certain execution time and the edges represent precendence constraints between the tasks. I.e. task $v_i$ has to execute before task $v_j$ if there exists an edge $(v_i,v_j)$ between those two tasks. I have $x$ threads that can execute those tasks.

Is there a (simple) formula to determine the response time (or at least an upper bound) for the given setup using any work-conserving scheduler?


texts: How connected are information theory and algorithmic information theory?

texts:
In the book by Cover and Thomas on information theory, there is a chapter on algorithmic information theory (kolmogorov complexity and so forth).

As far as I understand, algorithmic information theory was developed separately from information theory, and Kolmogorov didnt formalize AIT in terms of shannon entropy and so forth (am I wrong?)

How connected are the two fields? Are they really about quite separate things? Are there only some marginal connections? Or are they deeply connected?


texts: Algorithm to solve $L_1$ optimization of $\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

texts:
Is there is an efficient algorithm to solve the following optimization:

$\mathbf{x}^* = \arg\min_\mathbf{x}\sum_i ||\mathbf{A_i x} - \mathbf{b_i}||_1$

for given $\mathbf{b_i}, \mathbf{A_i}\ \forall i$, where $|| \mathbf{y} ||_1$ is the $L_1$ norm (i.e. $\sum_j |y_j|$) and $\mathbf{A_i}$ are big matrices which we don't have their explicit representations, only access to operations $\mathbf{A_i y}$ and $\mathbf{A_i^T z}$?

I can solve the problem for small matrices $\mathbf{A_i}$ using linear programming using the same trick from here, but if the matrices are large, there is no obvious way (at least for me) to solve it using linear programming.

Any ideas and suggestions are welcome.


texts:
The problem I have in hand is like drawing Google Maps by myself, in particular, roads. When my map scale is huge, I face no problem, but when I zoom out there are too many things to draw -- sure, I can rank the elements, and for example draw only important roads (like highways), but at given scale there will be always some case, when the road has so many intersections and turns, and instead of nice drawing I will get ugly blob.
So I would like to simplify it, yet not in misleading way. I would like to avoid drawing dense map (part of it).

is there official name of this problem/algorithm for it?
if there is special case for maps?

And if there is nothing anything "official" -- how to tackle this problem?


texts:
Given an undirected tree (with no specific root), how to find the longest path, i.e. 2 vertices that are the farthest apart from each other? There are no lengths associated with the edges (each edge has length 1 by default).
Obviously one idea is to check the path lengths between all pairs of vertices (e.g. by doing a DFS from each vertex), but there should be a more efficient solution. Please include a short proof in your answer.


texts: What is minimization (μ-function) in layman tems?

texts:
In Computer Science μ-function is used to extend set of primitively recursive functions to generally recursive functions, and I can't understand what this function does.
There is a lot of formulae, but I can't understand what is is. Let's say I'm writing in Python (or any other general purpose language). What are examples of μ-function IRL?


texts: How to implement insertion sort on linked list with best case performance O(n)?

texts: I have an almost sorted linked list containing N distinct elements with only 1 element not in it's place. Every implementation I have seen start insertion from the beginning (unlike insertion sort on arrays) therefore the complexity will be $O(N^2)$.


texts: Numerical example of theoretical diff file size using Kullback Leibler?

texts:
I understand that the theoretical size of a diff patch between two similar files can be calculated using Kullback Leibler (KL) as described @ Wikipedia.  Can anyone point me to a numerical example of this calculation?  I can only find general theory and formulae. I'd like to check my work.  So this is what I have so far...

This is a graph of the individual divergences for each byte probability between two files, say P and Q.  They are calculated according to the standard log formula for divergence.  The byte values (0-255) are along the bottom.  You can see that the divergences are both positive and negative.

I am unsure as to what the units of the y axis are, but following on from Shannon entropy, they must be bits per byte.  And they're small values.  The sum of all the divergences, keeping sign, is 0.019 bits /byte.  Both file sizes are approximately 20KByte, so can I say that the theoretical patch size going from P to Q is 20,000 * 0.019 = 380 bits or 48 bytes?

This feels wrong.  If the graph represents the patch size somehow, then I cannot see how the information contained in this complex shaped graph can be encoded in just 48 bytes.  There are no examples anywhere on the Interweb that I can find.

One further thing.  The above is for two similar files.  If P or Q should be totally random (from a random number generator), the KL divergence calculation = approx. 0.5.  This at least makes some semblance of sense if you think about all of the bits from P to Q being on average 50% different due to the randomness.  Perhaps 48 bytes is correct.  Err, um...


texts: How to enumerate minimal covers of a set

texts:
I have a set $S$ and a set $P = \{P_{1},...,P_{n}\}$ with $\bigcup P_{i} = S$. I want to find all the inclusion-minimal subsets of $P$ that are covers of $S$.

What is the best algorithm for enumerating all the inclusion-minimal covers of $S$ contained in a set $P$ and what is its running time?

Additional information : The algorithm must work in the general case. $|S|$ and $n$ can be anything.
I need to enumerate the exact set of all the inclusion-minimal covers of $S$ contained in $P$. Obviously, it is possible to find the first one in polynomial time by just removing elements of $P$. The second one could be found easily by using the same method starting with the different $P\setminus \{P_{i}\}$ with $P_{i}$ an element of the first cover.

I don't really hope for a polynomial delay algorithm but I would be really happy with an incremental polynomial delay, if such a thing exists.


texts: Complexity of transposing matrices represented as list of row or column vectors

texts:
Given [[1,4,7],[2,5,8],[3,6,9]] which is a list of the column vectors of matrix

|1, 2, 3|
|4, 5, 6|
|7, 8, 9|

is $ \Omega(n^2) $ a lower bound for transposing? Assume the matrix is not always square. I have to touch each element at least once, because going from 2 x 5 to 5 x 2 matrix for example, will mean going from a list of 5 lists to a list of 2 lists, so I can't really do any tricks with the array indices, right?

Is there a faster way to transpose matrices?


texts:
The are cuisenaire rods with N differnt lengthes $x_1,x_2,...,x_n$ (each length is a natural number), the number of the Cuisenaire rods is unlimited. Given a natural number B. you should tell if you can pick a bunch of Cuisenaire rods with exactly the length of B.

  for example: if the cuisenaire rods are $3,11,19$ and $B=20$ so you should return true because $3+3+3+11=20$. but for $B=19$ return false.

I made a $(N+1)\times(B+1)$ table named "opt", checked for all $0\leqslant i\leqslant n$ and for all $0\leqslant b\leqslant B$ if i can get a length using the lengthes $x_1,x_2,...,x_i$ and weights $0\leqslant b\leqslant B$

For the given example he output should be (this is my output also)

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 0 1
0 0 0 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 1 1 1

My idea:

fill in with zeros the first line and the first column, i.e opt[0][b]=0 for all b and opt[n][0]=0 for all n

Here  cuisenaire={0,3,11,19} is array with the cuisenaire lengths

 for n=1 to N+1
        for b=1 to B
            opt[n][b]=opt[n-1][w];//copy the previos row
            if w modulu cuisenaire[k]=0
                opt[n][w]=1;

            if w >=cuisenaire[n] and n>1 and (w+cuisenaire[n]-1)module (cuisenaire[n-1])=0)
                opt[n][w]=1;

my Idea works only for small B's $\implies $ wrong idea but maybe close, e.g for $B=100$ and cuisenaire={0,13,19,29} my idea doesn't work
can't think on recursive idea


texts: What is the solve of F(n,n) = F(n-1,n) + F(n, n-1) + 1 Where F(0,a) = 1 and F(a, 0) = 1 for every a

texts:
I'm given the following python function:
def recurser(i, j):
    x = 0
    if j == 0:
        return 1
    if i == 0:
        return 1
    x += recurser(i, j - 1)
    x += recurser(i - 1, j)
    x += 1
    return x

And I'm Asked to find x for any i = j = n where n can be any positive integer. however the recursion can do the job but the question says no recursion is allowed so that I have to solve the following recursive function:

F(n,n) = F(n-1,n) + F(n, n-1) + 1
F(0,a) = 1 for every positive a
F(a, 0) = 1 for every positive a

Is there any solution for it?


texts: Language is regular via regular expression

texts:
I was wondering if this language is regular L={$a^{2m+k}b^{3n+l}c^{m+n}$ & $
 k>2 $ & $ l \le 3$ & $m,n \in \mathbb{N}$} .I think the regular expression is :

$(aa)^*aaa(a)^*(bbb)^* \cdot ({e} \cup {b}  \cup {bb}  \cup {bbb} ) \cdot (c)^* $ .Am I correct?


texts: Want to do 3D reconstruction via simple matching

texts:
I have 2 images, called left and right images. I have some matched points $[c_l,r_l]$ and $[c_r,r_r]$ in both of them (these points are in pixel coordinates).

For a 3D point in the real world, they are related by:

$\lambda_l*[c_l , r_l,1]^t = W_l*[X,Y,Z]^t$

$\lambda_r*[c_r ,r_r,1]^t = W_r*[R|T]*[X,Y,Z,1]^t$

Here $W_l$ and $W_r$ are the intrinsic parameters of the left and right cameras and $T and R$ are the relative / overall translation and rotation between the cameras.

I attempted to solve this as:

$Q*[M,1]^T = 0$

where Q is

$$
        \begin{matrix}
        (k_1 +k_2-k_3*c_r-k_3*r_r) & (tw_x + tw_y -r_r*tw_z - c_r*tw_z) \\
        (w_1 + w_2 - w_3*c_l -w_3*r_l) & 0 \\
        \end{matrix}
$$

and M is $[X,Y,Z]$

Here:

$k1,k2, k3$ are the rows of the matrix K given by $K = R_r*R$
$tw$ is the vector formed by $tw = W_r*T$, its elements are
$[tw_x,tw_y,tw_z]$
$w1, w2, w3$ are the rows of the matrix $W_l$

I'm solving this as:

$Q*[M,1]^t = 0$

I look for a solution in the null space of $Q$.

$[M,1]^t$ would be hence be the null vector of Q.

That is,

$svd(Q) = [U,S,V]$ and $[M,1]^t$ would be the last column of V.

The result I get would be of form $[mx,my,mz,mk]$ so I simply divide all elements by $mk$ to get something of the form

$[mx/mk,my/mk,mz/mk,1]$. I consider this to be the value of X,Y,Z

Is there a better way to solve this? Correct me if I'm wrong here but I'm feel this could have been done in a simpler (more accurate) fashion.


texts:
my question is about how to compute a database with initial moves for Connect Four, where each board constellation is classified as leading to a win, draw or lose.

John Tromp already has done this for the standard 7x6 sized board (https://tromp.github.io/c4/c4.html) and all board configurations with 8 tiles.  Since I'm going to try to make up an AI for a larger board, these are not usable at all.  Moreover I'd like to know more about the theory behind:
How is it possible to determine the outcome of an initial position with e.g. 8 placed tiles, while not searching the whole game tree (which shouldn't be feasible i guess)?


texts: Is there a formal difference between $f:X \to X$ and $f\in X \to X$?

texts:
We can denote by $X\to X$ the set of all functions from $X$ to $X$.
Therefore, we can use the following statement to say that $f$ is a function from $X$ to $X$:
$$f\in X\to X$$

But we usually state instead

$$f:X \to X$$

In fact, we could say that $X\to X$ is defined as $\{f| f:X\to X\}$. If I'm not mistaken, $:$ is a notation that belongs to type theory, rather than set theory as $\in$ does.

So is there a fundamental difference between these two notations? Does it make sense to say that one of the two is more "fundamental" than the other?


texts:
Im studying for OS-finals and I cant figure out the difference.

A page is a chunk of addresses e.g 0-4095. This maps to 4kB of memory.
This page is 4kB big. But according to the litterature the Page table entry is around 4 Bytes big. I thought Page Table Entry are the same as a page.


texts: how to proof ${ NPC \bigcap CO-NPC \ne \varnothing then NP = P ? }$

texts:
how proof ${\ \ NPC \ \ \bigcap \ \  CO-NPC   \ne   \varnothing }$  then
${NP = P ?   }$


texts: Time complexity of 8-queen, by placeing one by one without attack

texts:
I am new to artificial intelligence. I have been trying to analyse the time complexity of 8-queen, by placing one by one without attack.

One approach to achieve goal state is to "add a queen to any square in the leftmost empty column such that it is not attacked by any other queen". And this approach will have a state space of 2057 (also wondering: How to compute this?)

What is the time complexity if I am using Depth First search algorithm (which I think is the most suitable one)? How about the space complexity?

I am puzzled because the brunching of the search tree is reducing greatly when goes deep. $O(8^8)$ looks too much for time complexity, even for worst case.


texts: How can we find number of triangles in a given undirected graph?

texts:
If we assume we have n triangles in a given graph. How can we find the n triangles in O(n) time?

And we also have to add and remove edges in O(log k) when k=|v|


texts: Hypothetical question on floating point normalization

texts:
I've seen a few questions posted regarding the upsides/downsides of floating point formats that have explicit integrals vs. formats that have implicit integrals, but have not seen an answer that really handles my question about it. By integral, I mean the single digit to the left of the radix point.

Let's assume that the hypothetical formats in question both have adequate precision for every possible use they will be put to (so that we can avoid the obvious point that the implicit integral adds more precision in most circumstances).

In one format we have an implicit integral and the requirement that all operation results must be normalized. In the other format we have an explicit integral and do not have the requirement that operation results be normalized. What are the upsides/downsides to this second format in comparison to the first format?

My first observations are that:
1) The format with the explicit integral will have multiple valid representations for a large subset of representable numbers. The format with the implicit integral will have only one valid representation for any given representable number. I don't immediately see a reason why this would be a downside, but I feel like it could be.

2) The format with the explicit integral seems like it would have a marginally simpler hardware or software implementation. This doesn't look like much of an upside unless you are going for really intense performance optimizations, but it ought to be mentioned.

3) The big upside for the explicit integral is that it makes a special arrangement for subnormal numbers unnecessary. Every number that would have fallen into the not-quite-zero gap would just be another representable result with the same gap as between any other pair of results for a given exponent. It seems like this would also slightly simplify design implementations, but I don't take that as a certainty.

Is there anything obvious I'm missing? Anything non-obvious? I'm just trying to really understand this concept better from a purely theoretical CS perspective.


texts:
I need to detect whether a binary pattern P of length m occurs in a binary text T of length n where m

I want to state an algorithm that runs in time O(n) where we assume that arithmetic operations on O(log2n) bit numbers can be executed in constant time. The algorithm should accept with probability 1 whenever P is a substring of T and reject with probability of at least 1−1n otherwise.

I think fingerprinting could help here. But I can't get it.


texts: Why does universe level restriction behave differently between inductive family and parameterized inductive type without axiom K in agda

texts:
An observation when defining List in agda with --without-K enabled:
The following parameterized inductive definition is accepted:
data List (A : Set) : Set where
    [] : List A
    _::_ : A → List A → List A

but not the equivalent inductive family definition:
data List' : Set → Set where
    []'  : {A : Set} → List' A
    _::'_ : {A : Set} → A → List' A → List' A

The error message is Set₁ is not less or equal than Set, so I have to change the type from List' : Set → Set to List' : Set → Set₁ in order for it to type-check. If I disable --without-K, then agda also correctly type-checks.
I tried to look up why this is the case, e.g., on the page https://agda.readthedocs.io/en/latest/language/without-k.html it says "When --without-K is enabled, some indexed datatypes must be defined in a higher universe level. In particular, the types of all indices should fit in the sort of the datatype." But it doesn't say the reason for such difference between inductive family (indexed datatypes) definition and the parameterized inductive definition. I guess it has something to do with the homotopy model interpretation of the underlying type theory. However I want to know what sort of "bad" thing will happen if the inductive family lives in a smaller universe (syntax and semantics). And how would parameterized inductive definition avoids such issue?


texts: Why doesn't the Floyd-Warshall algorithm work if I put k in the innermost loop

texts:
The Floyd-Warshall algorithm is defined as follows:

   for k from 1 to |V|
      for i from 1 to |V|
         for j from 1 to |V|
            if dist[i][k] + dist[k][j] < dist[i][j] then
               dist[i][j] ← dist[i][k] + dist[k][j]

Why doesn't it work if I simply use

for i from 1 to |V|
  for j from 1 to |V|
     for k from 1 to |V|
        if dist[i][k] + dist[k][j] < dist[i][j] then
           dist[i][j] ← dist[i][k] + dist[k][j]

In this case, the intermediate node k is iterated in the innermost loop. I expect it will make the same comparisons, but maybe different order. Why is the result different and incorrect?


texts: Network Reconstruction from Flow Function

texts:
Suppose that $T$ is a set of vertices in an unknown network.
We have oracle $F(X,Y)$ that returns maximum flow value between $X, Y \subseteq T$ in the unknown network.

Can we reconstruct the unknown network by calling this oracle polynomially-many times?
More precisely, can we construct a network whose flow function is consistent with the given oracle?

Example:
$T = \{a,b,c\}$,
$F(a,bc) = F(b,ac) = F(c,ab) = 1$.
Then both "triangle $K_3$ whose edge weights are $1/2$" and "3-star $S_3$ whose edge weights are $1$" are solutions.


texts: Dynamic programming approach for finding perfect square subsequence

texts:
Given an array of numbers $a_i$ with length $n$, such that $0<a_i<30$, how can we find the number of subsequences that the product of numbers is perfect square.

I have tried to find a dynamic programming approach but had no success so far.


texts: What formal representation is commonly used to describe compiler optimizations?

texts:
I have devised a compiler optimization that works on any structured language that has arrays assignments array[index] = value and counted loops (for i = n; i < N; i++) {doTHIS} (*).

Now I want to represent this optimization using some formal semantics. Since I want to publish my results in a Programming Languages venue, I would like to know:

What formal(s) representation(s) is (are) most commonly used to describe compiler optimizations?

I have already described my optimization using operational semantics, but I'm currently reviewing this choice. Hence, I came to the community for advice.

(*) Please forgive this C-like representation in a question asking for formal semantics.


texts: Transition from Delaunay triangulation to Voronoi diagram

texts:
In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P).
A Voronoi diagram is a kind of tesselation that divided the medium into polygons in 2D and polyhedrons in 3D.
I have Delaunay triangulation of a three-dimensional space. For the transition from Delaunay to Voronoi, firstly center of circumsphere of  Delaunay tetrahedron is found (vertice) then edges linked to this center are determined. Founded edges are formed polyhedron faces.
I want to know: is there any algorithm that finds polyhedron faces from edges?
I will appreciate any comments that give me a little help and forgive me for writing shortcomings.


texts: (AVL Trees) What is the maximum possible difference between the number of nodes in the root node's subtrees?

texts:
Question: If an AVL tree has height h (assume h ≥ 2), what is the maximum possible diﬀerence between the number of nodes in its two subtrees? Prove your answer. Your answer should not use big-Oh or big-Theta.

I drew six trees and drew the max number of nodes I could on one tree and the min number of nodes on the other subtree while keeping it an AVL tree.
Here  is table with the information for number of minimum nodes in left subtree, max number of nodes in right subtree and difference between the number of nodes between the two trees:

But I simply cannot figure out a pattern for the maximum possible difference between the number of nodes in the two subtrees. My current guess is that the max possible difference between the two number of nodes is 2h-1 - (h-2).

Here is a picture  of the diagrams I drew to come up with the numbers in the table above:

I drew as little nodes as possible on the left subtree and drew as many nodes as I could on the right subtree.


texts:
As part of my homework I need to prove (or disprove) that changing the contrast and, then, changing the brightness is (or isn't) the same as changing the brightness and, then, changing the contrast.

Let's assume that we are using gray-scale.

Brightness: the mean of the gray levels.
Changing brightness: adding or decreasing a constant value from every pixel.
Contrast: max - min of the gray-scale levels.
Changing the contrast: stretching the gray levels around the mean.

I understand that you need to disprove it, but I don't know how to do it in a formal way.


texts:
I am looking for some puzzles like Sokoban or 15-puzzle but more difficult to solve and satisfy the following requirements:

The number of possible moves at each step should be limited, let's say < 10.
Easy to generate a lot of levels (unique instances of puzzle). Let's say > 10**8.
One player.
Ideally has a terminate state at each level (game over).
Has a lightweight implementation (or can be implemented easily).
Difficult to be solved with tree search.

For example Sokoban satisfies all items except 2. Any suggestions would be greatly appreciated. Thanks!


texts:
The naive prime test goes something like this:

is_prime(n):
  for(i=2; i<=sqrt(n); ++i):
     if n mod i == 0 :
       return false
  return true

If $n$ is prime the loop runs for $\sqrt(n)$ iterations. I was wondering what the "average" runtime is. It is of course troublesome to define this properly, because there is no uniform distribution on the natural numbers, so I don't know whether this question actually makes sense or not. My intuition is that "most" numbers have relatively small divisor and prime numbers are relatively rare.

Maybe the following definition works: Let $f(n)$ be the number of loop iterations necessary for testing the first $n$ numbers using the above function. What is a good upper bound for $f(n)/n$?


texts: Is the set of programs that compute some function other than $h$ recursively enumerable?

texts:
Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$
  recursively enumerable?

Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated as a more general case.

By Rice's Theorem, it is not recursive. Intuitively,

$S$ is not r.e. as if it was, it would mean that we would know that
$f_x(y)$ halts for some input $y$ in order to check if it has a different image of $h(y)$.
$\overline{S}$ is not r.e. as if it was, we would be able to check if $f_x(y)
   = h(y)$ for every input $y$ (we would check equality for infinite inputs).

How would you solve this problem?

Note: I tried something, but I'll post it as an answer. Some thoughts would be great and really helpful. Any approach to this problem using reduction or diagonalization methods would be useful.


texts: Creating a Deterministic Push Down Automata

texts:
I saw this old post on stack overflow of a PDA that accepts a language where there are exactly twice as many a's as there are b's. The image they used is below and so is the link to the post itself.

PDA for language that accepts twice as many a's as b's.

It was commented that the PDA was not deterministic. So I'm wondering what exactly makes a PDA deterministic, for example, would you remove the epsilon transitions here to make it deterministic or what?

If somebody could convert this into a deterministic PDA and explain the steps to do so, I would appreciate it, I'm pretty lost when it comes to push down automata.


texts: Can a transcript change dependent random variables into independent variables?

texts: Let's say $X, Y$ are dependent random variables. Can I find an example such that for a transcript $t$ conditioned on a communication protocol $\Pi=t$, the variables become independent?


texts: Count numbers less than $x$ co-prime to $p$

texts:
We have given two numbers $x$ and $p$. We want to count how many numbers are less than $x$ and are co-prime with $p$.

I know that we can solve the problem in $O(x\log x)$ with iterating over all numbers less than $x$ and check if their greatest common divisor is $1$.

Is there any way to solve this faster, because I think that we can reduce this somehow. Please give some hints on where to start working.


texts:
I'm new to CHR and I was wondering if it makes sense to have have functions as arguments for constraint heads in a rule. I know that in the body of the rule this is possible.

E.g. Is C(X-Y) legal here?

C(X), C(X-Y), C(Y) => C(X * Y)