texts: Pseudo code algorithm for beauty contestant question

texts:
Say beauty pageants are judged based on 3 criteria: 1) Appearance 2) Personality 3) Talent. A contestant $C$ will beat another contestant $C'$ if she gets higher scores in ALL THREE of the criteria.

There are $n$ girls competing. Contestant $C_i$ is "Model Material" if $C_i$ is not beat by any other contestant $C_j$. Pretend you're the announcer and you have a collection of tuples: $(A_i, P_i, T_i)$ for $i = 1, 2,...,n$

The $i$th tuple contains the appearance, personality, and talent rating for $C_i$ (higher scores are better). Return a list of the "Model Material" contestants in in $O(n\log{n})$ time.

Given a data structure w/ a set $E$ of ints that, given an int $a$, --- (1) tells if a is in $E$ (2) finds smallest value > $a$ or largest value < $a$ in $E$ (3) inserts or removes a from $E$ in $O(\log{|E|})$ time.

I am trying to write pseudo-code for this algorithm but am lost trying to think of a correct algorithm that also runs in $O(n\log{n})$ time. I thought about starting initially with the $A_1$, $P_1$, and $T_1$ values for the first contestant, and if another contestant has a higher score in each category, remove the current tuple and replace it with the higher tuple, then repeat this process starting with a different contestant each time, but that's obviously not $O(n\log{n})$, and probably doesn't even work.

(This question was from my algorithms professor, and I can't find it online or in our textbook)


texts: Tight upper bound for forming an $n$ element Red-Black Tree from scratch

texts:
I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order statistics can be done in $O(lg(n))$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $i$ th order statistic can be achieved in the $O(n)$ time in the worst case.[ where $n$ is the number of elements].
Now I felt like finding a tight upper bound for forming an $n$ element Red-Black Tree so that I could comment about which alternative is better : "maintain the set elements in an array and perform query in $O(n)$ time" or "maintaining the elements in a Red-Black Tree (formation of which takes $O(f(n))$ time say) and then perform query in $O(lg(n))$ time".

So a very rough analysis is as follows, inserting an element into an $n$ element Red-Black Tree takes $O(lg(n))$ time and there are $n$ elements to insert , so it takes $O(nlg(n))$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.
I tried to attempt a detailed analysis as follows (but failed however):
Let while trying to insert the $j=i+1$ th element the height of the tree is atmost  $2.lg(i+1)+1$. For an appropriate $c$, the total running time,
$$T(n)\leq \sum_{j=1}^{n}c.(2.lg(i+1)+1)$$
$$=c.\sum_{i=0}^{n-1}(2.lg(i+1)+1)$$
$$=c.\left[\sum_{i=0}^{n-1}2.lg(i+1)+\sum_{i=0}^{n-1}1\right]$$
$$=2c\sum_{i=0}^{n-1}lg(i+1)+cn\tag1$$
Now
$$\sum_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+...+lg(n)=lg(1.2.3....n)\tag2$$
Now $$\prod_{k=1}^{n}k\leq n^n, \text{which is a very loose upper bound}\tag 3$$
Using $(3)$ in $(2)$ and substituting the result in $(1)$ we have $T(n)=O(nlg(n))$ which is the same as the rough analysis...
Can I do anything better than $(3)$?

All the nodes referred to are the internal nodes in the Red-Black Tree.


texts:
The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence

$$T(n) = aT(n/b) + f(n),$$

where $a \ge 1$ and $b > 1$. But for selection sort, $b=1$. I am trying to apply the master theorem and stuck.


texts: Serving $k$ customers with bounded time window

texts:
A person provides a service and he/she can serve $k$ clients each minute.
Now, client number $i$ comes at the beginning of minute $a_{i}$ and waits $w_{i}$ minutes to receive the service and if they don't receive the service in the interval $[a_{i}, a_{i} + w_{i}]$, they leave.
If we have $n$ clients, can the person serve all them or not?
My question: Does the above problem have a formal name? I want to write a python code for that but I don't know which keywords should I search?


texts:
I am trying to solve this code cracking problem. The solution is either the code or all possible solutions if you can't narrow the possibilities.

We have a 5 character code that is consisting of digits {0,1, ..., 7}. We have 10 attempts and for each attempt we have the amount of correctly guessed digits on the right indexes, and the number of correctly guessed digits on an incorrect index.

What I did what to generate all 5 digit numbers consisting of digits {0,1, ..., 7}., however I failed to find any way to narrow the attempts down. Could you help me find the right algorithm? Thanks!


texts: Confusing example of a language which may be Context-free or not context-free

texts: Hi so consider the language $L= \{(0^i)(1^j)\mid i=k*j \text{ for some positive }k\}$ Could I not rewrite this as $\{((0^k)^j)(b^j)\mid k>1\}$. Seeing it in this form makes me think of a form $a^n b^n$ which we know is context free so therefore it should be context free. Is my logic wrong and if not what would be the best way to show it's context free.


texts: Interpreting Minimal STLC using a $\lambda 1$ Category

texts:
On page 139, example 2.4.5 of "Categorical Logic and Type Theory" by Bart Jacobs demonstrates the interpretation of the abstraction typing rule with respect to a $\lambda 1$ category. Specifically, the category in question is $(\mathcal C \ell 1 (\Sigma), T_1)$:
An object of $(\mathcal C \ell 1 (\Sigma), T_1)$ is a pair $(\Gamma,\tau)$ where
$\bullet$ $\Gamma$ is a typing context
$\bullet$ $\tau$ is a type, formed from the types of signature $\Sigma$ and the exponent type constructor.
An arrow from $(x_1:\tau_1 \ldots x_n:\tau_n,\tau)$ to $(y_1 : \sigma_1 \ldots y_m : \sigma_m,\sigma)$ is a pair $([M_1]\ldots[M_m], [M])$ where $M_i$ is an equivalence class w.r.t. $\beta$ and $\eta$ of the term-in-context $x_1 : \tau_1 \ldots x_n : \tau_n \vdash M_i : \sigma_i$, and $M$ is the equivalence class of the term in context $x_1 : \tau_1 \ldots x_n : \tau_n, x:\tau \vdash M : \sigma$.
The abstraction rule is interpreted using the right adjoint to the substitution functor induced by the base category's projection arrow $$\pi_{(x_1:\tau_1,\ldots,x_{n-1}),x_n:\tau_n} : (x_1:\tau_1,\ldots,x_{n}:\tau_{n}) \to (x_1:\tau_1,\ldots,x_{n-1}:\tau_{n-1})$$
This right adjoint brings us from the fibre over $(x_1:\tau_1,\ldots,x_{n}:\tau_n)$ to the fibre over $(x_1:\tau_1,\ldots,x_{n-1}:\tau_{n-1})$.
This works when there are at least two variables in context, but what I would like to know is this: how can we interpret the formation of an abstraction from a typing judgment with a single-variable context? If the base signature contains a nullary symbol, we could use that to silently insert a throw-away type into the "type" position and move the single variable into the "context" position. Is this why the CT structure is required to be non-trivial? That seems kind of awkward, and I'm wondering why it isn't explained in the text.


texts:
Given that,

$T(n) = \sum_{i=2}^{n} \log_i n$

I need to find the asymptotic boundary of $T(n)$.

Answer given is $\theta(n)$.
Please provide explanation.


texts:
This is a problem that involves matching students with various skills into groups so that there are as many groups as possible while ensuring that each group has certain skills present. I've reduced it to this:

Given a set of $N$ people with $S$ skills where $A_{n,s}$ is the quantity of skill $s$ that person $n$ has.
Group the $N$ people into as many groups as possible, such that there are no more than $G$ people in any group, and so that the sum of each skill in each group is at least $B_s$.

Constraints: $N, S, G < 100$ and $A_{n,s}, B_s < 10$

I haven't been able to come up with a better solution that a brute force so far. Would be very keep for some pointers as to what I should be searching for to find an algorithm for this class of problem.


texts:
Have been trying to understand the image below which shows status of spinlock using cache coherence. Reference is Computer Architecture A Quantitative Approach------------------
Could anybody explain why there is a cache miss in step no.5 when P2 tries to execute swap.


texts: Do we alter the input string when converting a multi-tape Turing Machine to a single-tape Turing Machine?

texts:
I'm having difficulty understanding the conversion from a multi-tape Turing Machine $M$ to a single-tape Turing Machine $S$. Suppose that $M$ has 3 tapes with input strings $w_1 = 0110$, $w_2 = aaba$, and $w_3 = XXXX$, and configurations

$\textbf{0}110$

$aa\textbf{b}a$

$X\textbf{X}XX$,

where the bold-faced symbols represent the current positions of the read/write heads. The single-tape Turing Machine will have an input string of

$w = \#\textbf{0}110\#aa\textbf{b}a\#X\textbf{X}XX\#$

I'm unclear as to whether we have to delineate $w_1, w_2,$ and $w_3$ manually (i.e. the input string $w = 0110aabaXXXX$) , or if we alter the input string $w$ to include those hash delimiters (i.e. $w=\#0110\#aaba\#XXXX\#$).


texts:
Is the speed of compiling software very dependent on the CPU? I know this question is a bit broad, but I'm to find an answer to the case described below.

If I download a software project that makes use of Node.js, TypeScript, and JavaScript and compile it running yarn it takes a certain duration on machine A and another duration on machine B. In my test case machine A is equipped with an Intel i5-4570 and machine B is equipped with an AMD Ryzen 5 1600x. Both have 16 GB RAM and both also have similar SSD drives in use.

Now, if I run the software compilation on both machines, machine A takes about 1:30min and machine B takes about 1:20min. Hence, machine B is not significantly faster, even though the CPUs are quite different in capability and get different scores according to CpuBenchmark:

Intel i5-4570: 7109 CPU Mark
AMD Ryzen 5 1600x 13232 CPU Mark

The single core rating of both CPUs is quite similar at around 2000 Points, but when I run compilation all cores move up to 100% according to system power statistics.

I also checked the network usage, but doesn't move over 10kB/s and is therefore negligible. The RAM use fluctuates within about 1GB in both systems between 9GB and 10GB.

Now, as the expected results differ quite intensly to the reality, I obviously am missing a point. So, an experienced input of some of you guys would very much help.

Is there anything else I could measure? Is there anything I missed or maybe don't know and therefore should further test? I basically want to find out, why the Ryzen is not significantly faster than the Intel mentioned above.


texts:
Given a tree with N vertices numbered from 1 to N.

The vertex 1 is the root of the tree. Each vertex is assigned with an integer weight. A remove operation can remove sub-tree rooted at an arbitrary vertex u. We must use at most K remove operations (possibly zero) so that the total weight of the remaining vertices is largest.

We need to tell the largest total weight of the remaining vertices.

Example : Let N=5 and K=2 and weights of all 5 nodes are : [1,1,-1,-1,-1].

Also Let N-1 edges are as follow :

1 2
2 3
4 1
4 5

Then here answer is 2.

Explanation : We use 2 remove operations: one for the sub-tree rooted at 3 and the other one for the sub-tree rooted at 4. There are only 2 remaining vertices which are 1 and 2. The total weight is 1+1=2.

My Approach : Keep weight of its sub tree at each Node of the tree and delete the one with minimum weight.But how to update the weight of remaining tree is one of the problem.Also what is efficient way to store the weight of sub tree at each Node.Any Help Please ?


texts: Non-asymptotic rate of convergence of iterative methods

texts:
I want to know what is the definition of rate of convergence (non-asymptotic) of iterative methods ?
For example is it true that if $\|x_n - x^*\| \leq \frac{K}{n}\|x_0 - x^*\|$ then the rate of convergence is $O(1/n)$.


texts: How will Big O be with quantum computers?

texts: I don't even know if this is the right place to ask this this...but how will Big O be with quantum computers? More specifically, will the worst case always be constant? If yes, how will this change our understanding of current algorithms? For example, will this mean that the difference between an algorithm running at Big O(2^n) and another running at Big O(n^2) in traditional computers be insignificant in a quantum computer? Would time complexity even be an issue with quantum computers? This might have a very obvious answer but I don't know the answer (and I'm really am curious).


texts: Proving a language is neither Recursively Enumerable nor co-Recursively Enumerable

texts:
$$L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| = 1\)} \}$$

I have to prove that this is not R.E. and not co-R.E.

I know how to approach these kind of problems. For
$\check L = \{ \langle M \rangle \mid \text{\(M\) is a Turing Machine and \(|L(M)| \le 1\)} \}$,
Here a simple reduction from complement of HP would do the trick. (Make a TM $M'$ which on input $w$ runs $M$ on $x$ and accepts if $M$ accepts $x$. If $\langle M,x \rangle$ belongs to complement of HP then $x$ would not be accepted and hence $M'$ would reject everything thereby satisfying the $\le 1$ property. Also in case $\langle M,x \rangle$ doesn't belong to complement of HP, $M'$ would accept everything and hence would be $\gt 1$. Thus we know that the complement of HP is reducible to $\check L$. Hence $\check L$ is not RE.)

But in the main problem I don't have an inequality and I am stuck with how to approach such problems. I would face the same problem while proving $L'$ (complement of $L$) as not RE for proving $L$ as not co RE.


texts: About graphs whose edge set decomposes into perfect matchings

texts:
Is there a characterization of graphs whose edge set decomposes into a disjoint union of perfect matchings?

One trivial class of such graphs are $d$-regular $(n,n)$-bipartite graphs. Their edge set will decompose into $d$ disjoint perfect matchings.


texts:
I have begun reading Numerical Analysis by Walter Gautschi. On page $3$, the author introduces the floating point number system as follows: a floating point number is a number representible as
$$
\begin{equation}
\pm (.b_{-1}b_{-2}...b_{-t})_2 \cdot 2^{\pm(c_{s-1}c_{s-2}...c_0.)_2} \tag {1}
\end{equation}
$$
where $s, t$ are fixed. We denote this number system by $\mathbb{R}(t, s)$.

Then, Walter says that a number $x \in \mathbb{R}(t, s)$ is normalized if $b_{-1}=1$, and that we $"$assume all numbers in $\mathbb{R}(t, s)$ are normalized $"$.

My Question: Consider consider the number
$$x = +(.00100) \cdot 2^{-(111.)}$$
Is this number an element of $\mathbb{R}(5, 3)$? According to the definition, I want to say yes. But when the author says $"$we assume all numbers in $\mathbb{R}(t, s)$ are normalized,$"$ I don't know if he is implicitly redefining $\mathbb{R}(t, s)$ to be numbers of the form $(1)$ with the additional requirement that $b_{-1}=1$. If we try to impose this requirement on $x$, I believe $x$ would come out to
$$x=+(.10000) \cdot 2^{-1001}$$
which shouldn't be part of $\mathbb{R}(5, 3)$

Background
I am a math major taking my first numerical analysis. I do not have any prior experience with computer science or numerical mathematics.


texts: Number of combinations to put n items into 2 bags

texts:
I’m currently working on a finger exercise for mit6.00.2x, a MOOC in computaional thinking, and was having some issues.

First of all: don’t worry, I don’t need you to do my homework for me, I just want to clarify an aspect of the question.

So, the original question asked us to program the computer to find all subsets of a list of items to go into a bag. It said that "The number of possible combinations to put n items into one bag is $2^n$."

So far, so good.

However, the extension of the question is to program the computer to output the amount of combinations possible to put n items into 2 bags: an item must be in either bag or neither.

Now we arrive at my question: At this point it is said that there are $3^n$ possible combinations for this, as each item has three possibilities instead of two.

This makes sense, but I actually did the problem with two items and only found seven combinations:

[][1], 2 outside

[1][], 2 outside

[][], 1 and 2 outside

[][1,2]

[2][1]

[1,2][]

[1][2]

So, there are 2 items, there should be $3^2=9$ combinations, but there are only 7.

I'm sure I'm missing something....help!


texts: design cache system using queuing theory

texts: If we have data from a random population, a 3d histogram of throughput and current cache size of DRAM (intersection of a IOPS  & a cache size will have a count). How can one use queuing theory to estimate the best possible cache size ?


texts: How are prime implicates of HORN-Formulas defined?

texts:
I'm confused about the definition of prime implicates in Horn formulas.
For example in the paper of Kira 2012 on page 109 it is stated:

Now in the paper of Boros 2010 on page 82 the following definition is used:

My goal is to decide whether a Horn formula is prime or not in polynomial time. For that I want to assume the definition used in Kira 2012.
How can I prove that the two definitions above for prime implications of Horn formulas are equivalent?
Edit:
What I have so far is that if we assume Kiras definition and have for example a clause $C=\neg x_1 \vee \neg x_2 \vee x_3$ of formula $F$ and $C$ is prime then $F\rightarrow C$. If one neglects a literal in C we get $C_1=\neg x_1 \vee \neg x_2$ and obviously $C_1 \rightarrow C$. Therefore, since $C$ is prime then by Kiras definition no other proper sub-clause of $C$ is an implicant so $F \nrightarrow C_1$. Neglecting more literals in $C_1$ to get $C_2$ will give $C_2\rightarrow C_1 \rightarrow C$. Then by definition of $C$ it must be that $F\nrightarrow C_2 \rightarrow C_1$ and we get that all sub-clauses of $C_1$ are not prime if we check that $C_1$ is not prime. Therefore, to check if a Formula $F$ is prime we consider each clause $C$ and neglect all literals of $C$ once and check if the new clause is not prime. If One clause is prime it follows that F is not prime.
I think the equivalence for the other direction is similarly . Assume the definition of Boros. Then if we consider the clause $C$ and drop an arbitrary literal we get $C_1$ which is not an implicate if $C$ is prime so $F\nrightarrow C_1$. Again we have oviously $C_1 \rightarrow C$ and by dropping any more arbitrary literals in $C_1$ to get $C_2$ we note $F\nrightarrow C_2 \rightarrow C_1$(otherwise $F\rightarrow C_2 \rightarrow C_1$ which is wrong since $C_1$ is no implicate). Since by dropping literals we can produce arbitrary sub-clauses one can follow that also all proper sub-clauses of C cant be prime otherwise $F\rightarrow C_2 \rightarrow C_1$ which is a contradiction. And Kiras definition follows.
Is my reasoning correct?


texts: Can a Markov Algorithm Replace the Empty String?

texts:
Suppose I have a Markov Algorithm, and I have some rules, such that after execution of these rules, the remaining string is either "a", "b", or the empty string, "". Then I have three terminal rules to cover these cases:

"a" ->. "100"
"b" ->. "99"
"" ->. "0"

Is the last rule a valid terminal rule? Can a Markov Algorithm replace the empty string, or does it halt as soon as the string it is computing is empty?


texts: Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S) = \epsilon (\epsilon (S))$

texts:
Let M be an $\epsilon$-NFA and let $S\subseteq Q$. Prove $\epsilon (S)= \epsilon (\epsilon (S))$.

I would like to prove this by contradiction but I don't know if my idea is correct.

  Definition of $\epsilon -closure$:
  $\epsilon : 2^Q \rightarrow 2^Q $

  a) $S \subseteq \epsilon (S)$ Base case

  b) If $q \in \epsilon (S)$ then $\delta(q,\epsilon )\subseteq \epsilon (S)$ Recursive case

  c) and nothing else is in $\epsilon (S)$

Prove i) That $\epsilon (S) \subseteq \epsilon (\epsilon (S))$.

By contradiction, suppose $\exists x \in \epsilon (S)$ such that $x \notin \epsilon (\epsilon (S))$.

Using definitions of $\epsilon (S)$ , we know $S \in \epsilon (S)$. So $x \in S \in \epsilon (S)$, and $\delta(x,\epsilon ) \subseteq \epsilon (S)$.

Using definitions again, we know $S \in \epsilon (S)$, so $x \notin \epsilon (\epsilon (S))\notin \epsilon (S)$. Also $\delta (x, \epsilon) \nsubseteq \epsilon (\epsilon (S))$

We have a contradiction because $x \notin \epsilon (S)$ and we said $x \in \epsilon (S)$.

Therefore i) is true.


texts: Is log(n) equivalent to (log(n))^x for big-O analysis?

texts:
My professor noted that we could treat any logarithmic function with an exponent as equivalent to log(n) for the purposes of big-O analysis.

ie. $(n log(n) + 1)^2 + (log(n) + 1)(n^2 + 1)$

From the left I would get $(n^2)(log(n))^2$ and from the right I would get $(n^2)log(n)$. According to my professor I can just say this function is $O(n^2log(n))$. However, I don't see how these functions grow in the same order. Looking at their graphs it would seem they are quite different.


texts:
given two arrays of integers A and B of size m, with values in the
  range [-n,n]. I want an algorithm to count how many common values are
  in A and B , if a value is repeated we only count it once , for
  example :  $A=\{2,2,14,3\}$ and $B=\{1,2,14,14,5\}$ the algorithm
  should return 2 . Problem is I need to do this in $O(m)$ time.

My attempt was to create an array $C$, of size $2n$.
and increment all the values of $A$ and $B$ by $n$, and count the values of $A$ like:
$C[A[i]] = 1$
that would take me $O(m)$ time , and $O(1)$ time to create the array.
then going over $B$ and counting how many $1's$ I encounter in $C$.

So far it sounds good, however I have no idea what's in $C$ in the first place and it could be that there's a $1$ in there already and that would increment the counter falsely , and initializing $C$ would take $O(n)$ time.

Any ideas?
Thanks ahead.


texts: How memory remapping of physical address space that is above 4GB RAM works?

texts:
I have a query regarding the below information in http://duartes.org/gustavo/blog/post/motherboard-chipsets-memory-map/

"In 64-bit mode it is possible to use physical addresses above the total RAM in the system to access the RAM regions that correspond to physical addresses stolen by motherboard devices. This is called reclaiming memory and it’s done with help from the chipset."

Let's say if the RAM size is of 4GB. In 64-bit mode or with PAE enabled for 32-bit mode, if the address space above the total RAM 0x10000012C is assigned to some assorted device on the mother board, then how that assorted device can get hold of some memory region on RAM?


texts:
I recently came across a problem where I was charged $50 by a merchant with my bank card but there was a communication error, so the money was taken from my account but never arrived in the merchants account.  I have contacted both banks and neither know what happened to the money.

How could one would construct software to avoid this problem?


texts: Better Algorithm to determine the number of all TRUE rows in a logical matrix

texts:
I have a matrix of logicals (TRUE, FALSE) and I need to count the number of rows that contain only TRUE values.

My current algorithm:

For every row:

initialize counter
reduce each col by + (take the sum of all the values in that row)
if the result from 1. == the number of total columns, increment counter.

Is there a different (hopefully more efficient) routine I could apply?


texts: Binary Search Tree Traversal output validity and unique BST construction

texts:
I had two specific type of questions involving Binary Search Tree (not simple Binary Tree) traversals :

Given x-order traversal output of BST, can we state if it is valid or invalid output?
(For example, this: [3,2,1,4,6,7,8,5] can be valid postorder traversal output, but this: [4,1,3,2,6,7,8,5] cannot be.)

Given x-order traversal output of BST, can we draw unique BST?

Put Pre, Post, In and Level in x. So there are actually 8 questions.
I didnt find any place discussing these all. But after a bit of thinking I realized that,

for all x-order traversal outputs, we can state whether it is valid or not.
for all x-order traversal outputs except the inorder, we can draw unique BST.

This is really confusing me. Especially in case of inorder. Logically, it seems that if we can construct unique BST for given x-order traversal output, then we can say that for that x-order traversal output, we should be able to tell whether the output is valid or not. But this does not seems to be correct, since in case of inorder traversal, we can tell if the given output is valid or not but we cannot construct the corresponding unique BST.


texts:
I'm curious if the origin of any successful computer virus is known to NOT have an intentional, human originator.  To put it another way, do computer viruses ever "spontaneously" originate through the process of natural selection in the same way biological viruses originate; without an intentional "designer?"

I imagine (though I'm not sure) that it's possible for sufficiently knowledgable software engineer to make use of software engineering tools like neural networks, genetic algorithms, adversarial networks, etc to write a virus according to his/her specifications, but that's not what I want to know.  I want to know if computer viruses ever begin on their own, and if they don't, why not?

The three core tenets of evolution by natural selection are descent with modification, variable fitness, and resource limitation. Some scientists say that wherever these conditions are in place, evolution occurs necessarily.  Importantly, being alive is not a prerequisite, which is why biological viruses continue to evolve even though they are not technically alive.  Richard Dawkins says that thoughts and ideas survive and proliferate through the same mechanism.  So, does computer code ever evolve organically without human intervention to form a successfully self-replicating entity?  If not, why not?


texts: How is a JIT compiler different from an ordinary compiler?

texts: There's been a lot of hype about JIT compilers for languages like Java, Ruby, and Python. How are JIT compilers different from C/C++ compilers, and why are the compilers written for Java, Ruby or Python called JIT compilers, while C/C++ compilers are just called compilers?


texts: Algorithm for meshing parametric manifolds with dimension higher than 3?

texts:
I'm looking for an algorithm for meshing parametric manifolds in a given range. To be specific, in n-dimensional space, the manifolds are given as $$x=e^{At}x_0$$ where $x_0$ are the solutions of a linear equation $$Fx=g$$

$x_0$ is an (n-2)-dimensional linear set. For example, in 4-dimenional space, $x_0$ is a 2d plane, and the manifold is 3d.

I did some searching, and the algorithms I can are usually used to mesh manifolds given as explicit funstions.

Any clue such as an algorithm name would be helpful, thank you.


texts: Why is the distribution of the clustering coefficient of a random network independent of degree?

texts:
I was reading about clustering coefficient distribution, and it seems that it is independent of node degree for the case of random networks, or even scale-free networks. I'm wondering why this is the case conceptually.

I do understand that the degree distribution in the case of a random network shows a Poisson behavior, but don't understand why the clustering coefficient shows no change with degree.

Edit: my claim about clustering coefficient distribution with respect to random graphs comes from box 2 in this article:


texts: Recognizing interval graphs--"equivalent intervals"

texts:
I was reading a paper for recognizing interval graphs. Here is an excerpt from the paper:

  Each interval graph has a corresponding interval model in which two intervals overlap if
      and only if their corresponding vertices are adjacent. Such a representation is usually far
      from unique. To eliminate uninteresting variations of the endpoint orderings, we shall
      consider the following block structure of endpoints: Denote the right (resp. left) endpoint of
      an interval $u$ by $R(u)$ (resp. $L(u)$). In an interval model, define a maximal contiguous set of
      right (resp. left) endpoints as an R-block (resp. L-block). Thus, the endpoints can be grouped
      as a left-right block sequence. Since an endpoint block is a set, the endpoint orderings within
      a block are ignored. It is easy to see that the overlapping relationship does not change if one
      permute the endpoint order within each block. Define two interval models for $G$ to be
      equivalent if either their left-right block sequences are identical or one is the reversal of the
      other.

I am unable to understand the notion of equivalent intervals. Can someone help me?


texts: Need help implementing an algorithm to solve roots of a transcendental equation

texts:
I'm trying to implement this algorithm but I'm having problems reproducing the exemple that it gives a solution to.

The general method that I tried is:

Make a grid $\theta \in [0,2\pi)$, with say N=256 points in it
Create a complex vector $G(\theta) = \frac{1}{F(e^{i\theta})}$, where $F(z) = z\tan(z) - 1$ is the complex extension of the transcendental equation in question.
Solve $G_{k} = \int\limits_{0}^{2\pi} G(\theta)e^{ik\theta}d\theta$ for as many $k$ as I need.

  If I understood correctly, there'll be a $nroot\times nroot$ symmetric matrix with $2\times nroot$ independent elements. E.g for $nroot = 3$ I will have to solve for $G_{1},G_{2},G_{3},G_{4},G_{5},G_{6}$. Eventually $G_{6}$ will go to the right side of the equation as when we fix the value of $c_{3}$.

Solve the system $A\cdot X = -B$

The problem that I'm getting is the following:

The eventual values of $c_{k}$ are complex, and in the system that the author gets to in (18) there are just real numbers. The author mentions the use of the routine cfft which I'm unaware of, I solved the integral explicitly and with ordinary FFT and in neither I get real numbers. Even the real part of the $c_{k}$'s I'm getting, even though are of the same order of the solution it is far from it.

My solution is just wrong, I get the wrong system therefore the wrong $c_{k}$'s and I'm unable to get to the solution.


texts: Calculate all pairs of outer products between columns in matrix

texts:
Imagine you have a matrix m of dimension MxN
What I'm trying to do is get a set of elements (of length N*(N-1)/2) of the diagonal elements (each of whose individual length would be M) of the outer product which is formed by every possible pair of columns within the matrix m
For instance, I would take outer product of  columns 1 and column 2 and extract that diagonal, then do the same with columns 1 and 3, columns 2 and 3,... etc)
Is there a quick way to do this without looping over every pair of columns (ie complexity O(N^2)
Currently how I have written it in R is:
for i in 1:ncols:
    for j in i:ncols:
        diag(outer(m[,i],m[,j]))

But obviously, this is painfully slow. Any suggestions?


texts: What is the formal, rigorous definition of a programming language?

texts: In programming language theory, people study the theory behind programming languages. But I have never heard any formal definition of programming languages themselves. What is the formal definition, not of a particular programming language like Python or C++, but of programming languages themselves?


texts: Runtime analysis of bit sorting algorithm with input size and integer size

texts:
I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I can find solve recursion based on n solely. The algorithm is:

def sortB(seq,bitnum):
    # length of seq
    n = len(seq)
    lists = []
    for j in range(0,256):
        lists.append([]);
    for i in range(0,n):
        bits = (seq[i] >> bitnum) & 255;
        #print("bitnum :", bitnum)
        #print("seq[i] :", seq[i] >> bitnum)
        lists[bits].append(seq[i]);
        #print("bits ",bits)
    i = 0;
    for j in range(0,256):
        seqj = [0]*len(lists[j])
        k = 0
        for m in lists[j]:
            seqj[k] = m
            k = k + 1

        if (bitnum > 0):
            bitnum = bitnum - 8
            seqj = sortB(seqj, bitnum)

        for m in seqj:
            seq[i] = m
            i = i + 1

    return seq

I tried to think about this and basically I get this far:

Because the recursion happens based on the number of times bitnum is decremented by 8
   $b = bitnum$

$T(n,b-8)$

I solve the recursion of $T(b) = 256T(b-8)$

and I get T$(b) = 256^{(b/8)}$  which simplifies to $2^{(b)}$

Therefore, the whole algorithm gets multiplied by a factor of $2^{b}$: I get a runtime of $O(2^{b} n)$ which is in $O(n)$? But I feel this is wrong since the upper bound on the running time isn't taking this new factor (b) into account.


texts: How to solve for p in Akra-Bazzi method for analyzing time complexity?

texts:
Every single online resource I've looked up on Akra-Bazzi method appears to skip over the same step: They say you have to solve for $p$ without explaining how. If you look up the various PDFs and webpages online, they all basically say "Here's the equation. Solve for $p$. It equals (whatever). Moving on now to the integral..." without explaining how they solved the equation.

If I had to figure it out I could use a binary search but I imagine there is a more mathematical way to get an exact answer.

It is not at all obvious to me how you're supposed to solve for p.

That is:

$$ a_1 b_1^p + a_2 b_2^p + a_3 b_3^p + \dots + a_k b_k^p = 1, $$

Where all $a_i$ terms are positive and all $b_i$ terms are fractional ($0 < b_i < 1$).

How can you solve for $p$ by hand?


texts: PSpace-completeness under PSpace reductions

texts:
A language $L$ is PSpace-complete, if it meets two conditions:

It is in PSpace.
Every other PSpace-complete language reduces to it in polynomial time.

Question: suppose we change the second condition to polynomial space (instead of time)?
Why is it so that then SAT would be PSpace-complete?


texts:
Here are a couple of questions I struggle with.  (We use $A'$ to denote the complement of the problem $A$.)

A problem $A$ is NP-complete if and only if $A'$ is in NP?
A class problem $A$ is NP-Complete iff $A'$ is in NP?  (Is there any difference between these two?)

I got this claim to be true that

  If there is an NP-complete language $L$ whose complement is in NP, then the complement of any language in NP is in NP.

And this claim also to be true:

  $A$ is NP-hard iff $A'$ is coNP−hard

Then is the upper claim also true?


texts: Modeling a set of probabilistic concurrent processes

texts:
I'm looking into discrete-time Markov chains (DTMCs) for use in analyzing a probabilistic consensus protocol. One basic thing I haven't been able to figure out is how to model a set of independent processes: consider $N$ processes. These processes will concurrently execute a series of identical instructions labeled $0, 1, 2, 3,$ etc. and all are starting in instruction $0$. When probability is not involved, modeling this is simple: it's a state machine which branches nondeterministically off the start state to $N$ different states, where in each of those $N$ states a different process was the first to execute instruction $0$. What do we do when probability is involved? Do we do the same thing with $N$ states branching from the start state, where the probability of transitioning to each state is $\frac{1}{N}$? As in, it's uniformly random which process was the first one to execute instruction $0$?

Is this like taking the product of the state machines of each process?

I'm using a DTMC here, would I gain anything by moving to a CTMC if I don't care about anything beyond the global order of execution?

Bonus question: assigning probabilities to whichever action is taken first seems like a generalization of the non-probabilistic notion of fairness; if it is, what is the formal definition of this generalized notion of probabilistic fairness?


texts: Relationship between dynamic programming and reinforcement learning

texts:
I wasn't sure whether to post this here or in the ai stack exchange - please let me know if i need to move my post elsewhere)
I have been learning about how dynamic programming can be used as a tool to solve the bellman optimality equations: (only show state value function)
$$ v_{*}(s) = \max\limits_{a\in A(s)}\sum\limits_{s',r} p(s',r|s,a)[r+\gamma v_{*}(s')]$$
I understand how backward induction can be used on the above equation to find the optimal policy and value function.
What I dont understand is how policy iteration and value iteration can be describe as "dynamic programming algorithms" i.e exploiting optimal overlapping substructure. I have provided my attempt at trying to answer this question below
Attempt at trying to answer

In policy iteration do we consider ($v$,$\pi$) to be the "states" of the DP and we go back until we eventually converge on the optimal solution ($v_*$,$\pi_*$) as follows
$$ (v_{t+1},\pi_{t+1}) \rightarrow  (v_{t},\pi_{t+1}) \rightarrow (v_{t},\pi_{t}) $$

For value iteration

in the case of episodic tasks (finite duration) we use the bellman optimality equations directly, initialising the value function for each state to some value (typically 0) at the terminating $t=T$ and backward inducting until we get to $t=0$ so that we can the find the optimal value functions and policy to use from $t=T$ through to $t=0$

For continuing tasks we apply the same approach as episodic task but we keep backward inducting until we forget the initial conditions and reach an equilibrium hence the expected returns for each time-step are time invariant

$$ v_{*}(S_{t+1}=s) = v_{*}(S_t=s)$$
Any insight into this would be great, thanks in advance!


texts: Decidable restrictions of the Post Correspondence Problem

texts:
The Post Correspondence Problem (PCP) is undecidable.

The bounded version of the PCP is $\mathrm{NP}$-complete and the marked version of the PCP (the words of one of the two lists are required to differ in the first letter) is in $\mathrm{PSPACE}$ [1].

Are these restricted versions used to prove some complexity results of other problems (through reduction)?
Are there other restricted versions of the PCP that make it decidable (and in particular $\mathrm{PSPACE}$-complete)?

[1] "Marked PCP is decidable" by V. Halava, M. Hirvensalo, R. De Wolf (1999)


texts: What is the time complexity of the following algorithm on graphs

texts:
Consider undirected graph with $O(n)$ nodes and $O(m)$ edges. We store the edges in adjacent list, so for each node we keep list of the nodes such there exist edge between those nodes.

Our search goes as follows: For each node in the graph (let it be i) we iterate over all pairs of nodes(let it be $n_1 \text{ and } n_2$) such that there is edge between $i \text{ and } n_1 \text{ and between } i \text{ and } n_2$.Let's just analyze the complexity of those iterations.

Here is the pseudo code to make sure everything is understood well

for each node i in graph G:
    for each node n1 in adjacent list of i:
        for each node n2 in adjacent list of i:
            O(1) work here

From first look it looks like $O(n^3)$ since there are three nested loops, however I don't think that this is correct. What is the correct way to analyze the time complexity here?


texts: Bellman Ford facts and specific question

texts:
The Bellman-Ford algorithm checks all edges in each step, and if for each edge the following:
$d(v)>d(u)+w(u,v)$
holds, then $d(v)$ will be updated. $w(u,v)$ is the weight of edge $(u, v)$ and $d(u)$ is the length of best path was found for vertex $u$.
If in any step there is no update for all vertexes, the algorithms terminate.
If Bellman-Ford will be used for finding all shortest paths from vertex $s$ in graph $G$ with $n$ vertex, terminate after $k < n$ iteration then following is True:
number of edges in all shortest paths from $s$ is at most $k-1$

I think some times this is true and sometimes is false (when we check all edges simultaneously... maybe this is wrong), but I need a clear definition for the above sentence or a small example about logic.  I need verification of the above fact. is it always true? why?
New Updates:
The above statement is dependent on the implementation of your algorithm (at least I think).
Which implementation makes it true and under which condition it becomes false...
I see 4 version of Belman Ford on This Jeff Erricson Algorithm Book on Page 295.


texts: Primitive Recursive Function for Division and Hailstone function

texts:
Are division and Hailstone primitive recursion function?

$$\text{Div}(x,y) = \begin{cases}
x/y,  & \text{if $y$ divides $x$ } \\
0, & \text{otherwise}
\end{cases}$$

$$\text{Hailstone}(n) =\begin{cases}
3n + 1,  & \text{if $n$ is odd } \\
n/2, & \text{if $n$ is even}
\end{cases}$$

I tried to solve division in this way
$$\text{Div}(0,y) = 0 $$
$$\text{Div}(x+y,y) = \text{Div}(x,y) + 1$$

I do not know how to proceed from here. Can anyone help me?


texts:
I'm learning data structures from "Fundamentals of Data structures in C" by Sahni . In the topic, Circular Queue using Dynamic Array, the author has mentioned below point,

  Let capacity be the initial capacity of the circular  queue,We must first
  increase the size of the array using realloc,this will copy maximum of capacity elements on to the new array. To get a proper circular queue configuration, we must slide elements in the right segment(i.e, elements A and B) to the right end of the array(refer diagram 3.7.d). The array doubling and the slide to the right together copy at most 2 * capacity -2 elements.

I understand array doubling copies at most capacity elements. But how does array doubling and slide to right copy at most 2 * capacity -2 elements??


texts:
Let $A$ be an adjacency matrix of a directed graph. What's the meaning of the $(i,j)-$entry of the matrix $((A^T)^{7} \cdot (A^{7}))$ ?

My initial interpretation is that $(i,j)$ of this matrix is zero whenever nodes $i$ and $j$ have no 7-length in-coming paths from a common source. Is that right? Any attention is appreciated!


texts: Fastest way to solve a system of linear equations

texts:
I have to solve a system of up to 10000 equations with 10000 unknowns as fast as possible (preferably within a few seconds). I know that Gaussian elimination is too slow for that, so what algorithm is suitable for this task?

All coefficients and constants are non-negative integers modulo p (where p is a prime). There is guaranteed to be only 1 solution.  I need the solution modulo p.


texts:
Given a binary tree, construct the set of nodes whose sum is maximum subject to the restriction: if a node is included, its parent and children must be excluded, but grandchildren, etc. may be included.

My intuition tells me dynamic programming (and possibly two-coloring) should be involved, but not sure where to start. Could you please offer me a hint?


texts:
I'm interested in the Lovinger and Zhang paper Enhanced Simplified Memory-bounded A Star (SMA*+).   Are there any further papers on this algorithm or publicly-visible code (in any language) implementing it?
I have some things I'd like to understand better about the algorithm (apologies, they're quite basic).

What is the precise relationship between a state and a node in Algorithm 1?   They are clearly not synonyms otherwise $s(n)$ would not exist.
How does one efficiently determine the parent of $w$ in Algorithm 2?   Is it the case that $\forall n \vert n \in O$, $parent(n) \in O$?  If yes, is this simply because we only cull leaves?
Some problems (including the one I'm interested in) exhibit cycles.   If I encounter two identical  states $n$, $m$ at different depths $g(n) > g(m)$ I can always discount $n$.  As far as I can see though, nothing would seem to stop SMA*+ exploring some cycle $m \rightarrow x \rightarrow  y \rightarrow  z \rightarrow  n \rightarrow  m$ releatedly at ever-greater depth.   If this idea is wrong, what prunes these cycles?  If this idea is right, is there a simple way of avoiding this?    Do I have to simply prune $m$ from the successors of $n$ when computing $N$?


texts:
I would like to construct a Minimum Distance Spanning Tree (Dijkstra) for the graph below:

MDST: {(a,c), (c,h), (c,f), (a,d), (h,g), (a,b), (d,e), (h,j), (h,i), (j,k), (e,m), (i,l)}

Is my understanding correct? The total cost would be 49 (sum of the distance from the root for each node).


texts: "higher intensity" and "high signal intensity" in images

texts:
I'm newbie in Computer Vision and image processing.

I'm reading the article "Automated White Matter Hyperintensity Detection in Multiple Sclerosis Using 3D T2 FLAIR" and it said:

  2.2.4. WMH Segmentation with High Spatial Frequency Suppression

  White matter lesions have higher intensity and generally clear
  boundaries relative to the surrounding WM. Unfortunately, in the 3D T2
  FLAIR images, the GM can also present with high signal intensity,
  especially in elderly people.

What does it means "higher intensity" and "high signal intensity"?

I think it means that white matter lesions are very white but I'm not sure because I don't understand why the use the words "intensity" and "signal" when they are talking about images.


texts: Prove that Acyclic Subgraph is NP-Hard by showing Independent Set can be reduced to Acyclic Subgraph

texts:
I am trying to prove that the Acyclic Subgraph Problem (AS) is NP-hard by showing that the Independent Set Problem (IS) is polynomially reducible to AS.

AS is as follows: Given a directed graph G = (V, E) and an integer k, does G contain a subset V' of
k vertices such that the induced subgraph on V'is acyclic?

IS is as follows: Given an undirected graph G = (V, E) and an integer k, does G contain a subset V' of k vertices such that no two vertices in V'are adjacent to one another?

I have developed the following:
Given an undirected graph, G = (V,E), we can construct a directed graph, D =(V, E'). We do this by addd the edges (u,v) and (v,u) for every edge in E. If G has an independent set of size k, then the corresponding vertices in D are an acyclic subgraph. Similarly, if D has an acyclic subgraph of size k, then those k vertices must form an independent set in D as if there is an edge between two vertices in D. Then, there is a directed cycle between them, thus those k vertices form an independent set in G.

Can anyone help me further with this proof? I am not sure if what I have is going in the right direction or not.

Any help is appreciated, thanks!


texts: Perform Dijkstra on graph with negative edges by adding a big enough constant to every edges

texts: I know that this doesn't work because shortest path with a lot of edges may have bigger weight than a longer path with less edges. But what if, you keep track of the edges that our current weight path on each node and when we compare we subtract the number of edges on this path * the constant so that we get the original weight. I understand there is also the negative cycles problem, but is there an efficient algorithm that tell if a graph contains a negative cycle ?


texts: Finding same-cost assignments for 3-SAT formulas

texts:
Suppose I have a 3-SAT formula in CNF with $ m $ clauses on $ n $ variables,
$$ F = C_1 \wedge \dotsb \wedge C_m, $$
with each clause $ C_i = l_{i_1} \vee l_{i_2} \vee l_{i_3} $ and each literal $ l_k \in \{x_1, \bar{x}_1, \dotsc, x_n, \bar{x}_n\} $.

Define the cost $ E $ of each assignment $ \mathbf{l} = (l_1 \dotsb l_n) $ as the number of clauses not satisfied by it, so that
$$ E(\mathbf{l}) \in \{0, 1, \dotsc, m\} $$
(zero cost corresponding to satisfying assignments).

Finally, suppose the clause density $ m/n $ is sufficiently high so that most (or even all) assignments have nonzero cost (one can show that for large enough $ n, m $, clauses can be deemed independent and the cost distribution becomes a binomial distribution with mean $ m/8 $).

I'm trying to answer the following question: given an assignment $ \mathbf{l} $ with cost $ E(\mathbf{l}) > 0 $, what is the quickest way of finding another assignment $ \mathbf{l}^\prime $ such that $ E(\mathbf{l}^\prime) = E(\mathbf{l}) $?

I haven't been able to find this problem in the literature, and right now I can't do better than random search. Thank you for any insight or even just referrals to some article I might have missed.


texts: Does the Halting Problem have practical relevance? I can calculate all outputs for a finite number of states and inputs

texts:
Coming from a digital functional hardware verification background, I don’t really understand the Halting Problem. I can represent the program as a state machine and show whether all inputs in all states generate a valid output or lead to an infinite loop.

The only requirement is that the inputs and states are finite. E.g. an infinite counter would lead to an infinite number of states.

Since infinite counters or infinite inputs are impossible in reality, does the Halting Problem really have a practical relevance?


texts: How does youtube do video quality change/video compression?

texts:
After uploading a high definition video in youtube, youtube automatically makes a low definition(standard definition) version of the video.
I would like to know what algorithm they use to reduce the quality of video. Is it lossless or lossy?

If not youtube, I would like to know what algorithms are there in the literature that does this?


texts: Understanding Expected Running Time of Randomized Algorithms

texts:
I want to understand the expected running time and the worse-case expected running time.

I got confused when I saw this figure (source),

where $I$ is the input and $S$ is the sequence of random numbers.

What I don't understand from the above equation is why the expected running time is given for one particular input $I$?

I always thought that for a problem $\pi$,  $E(\pi) = \sum_{input \in Inputs}(Pr(input)*T(input))$ , isn't this correct?

So, let's assume Pr(x) is the uniform distribution, and we are to find the expected running time of the problem of searching an element in a $n$ element array using linear search.

Isn't the expected running time for linear search,

$$E(LinearSearch) = \frac{1}{n}\sum_1^ni $$

And what about the worst case expected running time, isn't it the time complexity of having the worst behavior? Like the figure below,

I would highly appreciate if someone can help me understand the two figures above.

Thank you in advance.


texts: Official Name for the “First” Programming Language Developed by Turing?

texts:
As is widely known, Alan Turing discovered/invented the Turing Machine in his classic 1936 paper. Here he also gave how these machines are specified in terms of their machine states and instructions on how they operate. Is there any official or widely accepted name for this "first" mathematically defined programming language$^*$ $L$ that consists of a specification of a Turing Machine together with its transition function?  Clearly by definition this language is Turing complete and hence can simulate any other algorithmic programming language. For instance here would be how program of $L$:

//Some specification of the machine $M$'s states, initial state, final state, allowable tape symbols, blank tape symbol, etc.

<0, 0, 1, R, 2>   // If $M$ is in state 0 and sees a 0, then write 1, move right, and enter state 2

<2, 0, 0, R, 3>  // If $M$ is in state 2, sees a 0, then write 0, move right, and enter state 3

<2, 1, 0, L, 3>  // etc

*By first mathematically defined programming language, I'm ignoring for the moment innovations like automated loom printing or natural programming languages like DNA/RNA which are definitely algorithmic, and instead focusing on a particular strand of algorithmic specification that most closely matches what is commonly thought of as a programming language today. There are also other mathematically defined systems that were shown to be Turing equivalent around the same time as Turing, but none of these really caught on in terms of influence as Turing machines and their programming language did.


texts: Finding big O notation of function with two parameters

texts:
I'm looking to work out the big-O notation for the following:

$$\frac{n^{s + 1} - 1}{n - 1} - 1$$

I have a feeling the result is $O\left( n^s \right)$ but I'm not sure how to prove it.

Any help greatly appreciated! :)


texts: Standard ILP Formulation of Travelling salesman problem: Purpose of subtour elimination constraints?

texts:
Consider the Traveling Salesman Problem:
Input: $n$ cities, distances $c_{ij}$ for each ordered pair $(i,j)$ of them.

Output: Find a shortest round tour visiting every city exactly once.

I came across the following ILP formulation, where we introduce a variable $x_{ij} \in \{0,1\}$ for each pair of cities $i,j$ where $x_{ij} = 1$ means arc $i,j$ is part of the tour. Then we have:

Minimize
 $$\sum_{1 \leq i,j \leq n} c_{ij} x_{ij}$$

Subject to
$$\forall k = 1, \dots, n: \sum_{1 \leq i \leq n} x_{ik} = 1$$
$$\forall k= 1, \dots, n: \sum_{1 \leq j \leq n} x_{kj} = 1$$
$$\forall \subsetneq S \subsetneq \{1, \dots, n\}: \sum_{i,j \in S} x_{ij} \leq |S| -1 $$

While I understand the purpose of the first two constraints to make sure there is only one incoming and one outgoing edge per city, I do not understand the purpose of the third constraint. From what I read, this constraint is to make sure that solutions consisting of several disconnected tours are not possible - But how is this enforced by the third constraint and why are disconnected subtours not prevented by the first two constraints already? If we have two disconnected subtours, then at least one vertex must have an incoming edge but no outgoing edge, no?


texts: After stereo image rectification, why does the relation between disparity and depth still apply?

texts:
The relation between disparity and depth is derived based on the assumption that the two cameras are parallel.

Image rectification does not make this assumption valid.

But I see in many university computer vision lectures, with two rectified images, the depth map is directly calculated.
I cannot figure out why.


texts: Is there a name for this graph search strategy?

texts:
The standard implementation of breadth-first search looks like

queue = [root]
while queue:
    node = queue.pop()
    visit(node)
    for_each child in node.children:
        queue.push(child)

Just by switching the queue to a stack:

stack = [root]
while stack:
    node = stack.pop()
    visit(node)
    for_each child in node.children:
        stack.push(child)

we get depth-first search.

There is another way to write breadth-first search:

visit(root)
queue = [root]
while queue:
    node = queue.pop()
    for_each child in node.children:
        visit(child)
        queue.push(child)

But when you switch this one from a queue to a stack:

visit(root)
stack = [root]
while stack:
    node = stack.pop()
    for_each child in node.children:
        visit(child)
        stack.push(child)

You do not get a traditional depth-first search.  Instead, you get a variant where all a node's immediate children are visited first, then its other ancestors in a depth-first way.  For example, on this tree:

     F
   /   \
  B     G
 / \     \
A   D     I
   / \   /
  C   E H

Depth-first search gives the order

  [F, G, I, H, B, D, E, C, A]

The last algorithm gives the order

  [F, B, G, I, H, A, D, C, E]

which is not exactly depth-first because B and G are both visited before I.  Does this algorithm have a name?


texts: Lower-bounding the Membership Problem in the Bitprobe Model

texts:
I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound.

In particular, they are trying to show that $s_A(2, m, 2) \in \Omega(m^{4/7})$. That is, the goal is to store a set $S$ of $2$ elements from a universe $U$ of size $m$ such that a query of the form "is $x \in S$" can be answered using only $2$ bit probes. The $s_A(2, m, 2)$ indicates the minimum number of bits required to answer such queries, and in particular, the scheme is allowed to be adaptive (the second probe can depend on the first one).

They begin by saying that such a scheme can be defined by three functions $a, b, c\colon [m] \to [s]$, where the query "is $x \in S$" is answered by first probing location $a(x)$ then probing locations $b(x)$ or $c(x)$ depending on the outcome of the first probe. They then go on to explain that this can be viewed as a bipartite multigraph where $G = (B = [s], C = [s], E = \{\langle b(x), c(x)\rangle : x \in [m]\})$. Lastly, they state that $E$ is naturally partitioned into sets $E_1, E_2, \ldots E_s$, where $$E_i = \{\langle b(x), c(x)\rangle : x \in [m], a(x) = i \}$$.

Now, my questions are as follows. First they make the assumption that "Each $E_i$ is a matching $\ldots$ Details Omitted". Why can this assumption be made? I can't for the life of me figure out why this needs to be the case.

My second (and more important question) is this. They provide the following example:
They state that edges with the same type of label (i.e $x$ and $x'$) belong to the same matching. In their caption, they state that if such a scheme were to exist, then there are some pairs that cannot be stored (such as $x$ and $y$ on the left). This is what I don't understand. They do not provide an explanation beyond the "If it were to exist in our graph, then the underlying scheme cannot store all sets of size two. In particular, it is easy to verify that if this configuration exists, there is no way to store the set $\{x, y\}$".

I am just getting myself familiar in this area, so some of the "obvious" things may not be so obvious to me right away.


texts: Algorithm Question: Stacking bricks of different colours?

texts:
I have a bunch of coloured bricks. There are X different colours, and a random number of each colour. How do I stack them up into Y columns so that a) no row has two bricks of the same colour and b) the height of the largest column is minimised?

There is an obvious lower bound of highest number of bricks of a single colour but beyond that I don't know where to go. This is equivalent to an optimisation problem I'm trying to solve and I'd be grateful if someone recognised the problem!


texts: Proving NP-Complete problem by reduction of subset-sum

texts:
My assignment question as "given a multiset of symbols (letters) L from an alphabet Σ (thus, the same letter may appear in L multiple times), and a set of words W ⊆ Σ' , UseAllLetters asks if it is possible to use all letters from L to make words belonging to W. You may form the same word multiple times. Prove that UseAllLetters is NP-complete."

I'm new learning NP problems and still having trouble to understand the intuition behind this. But I'll try my best and sharing my idea here to verify that I'm on the right track.

My suggestion as following:

To prove this question is NP-complete, we can do reduction to subset-sum problem, but we also have to show few things.

1.This problem is in NP. (I'm stuck on this)

2.Any NP-complete problem Y can be reduced to X.

So we choose subset-sum problem, as it defined as:Given a set X of integers and a target number t, find a subset Y ⊆ X such that the member of Y add up to exactly t. Which is similar to our problem, we can find a subset of letters $l$ in our L that make words belonging to W if we are able to find a subset Y ⊆ X such that the member of Y add up to t.

The reduction works in polynomial time.
UseAllLetters problem has solution iff subset-sum has solution. I'm also stuck on this, it seems like I have to argue the correctness of my reduction, and I'm not sure my reduction is the right way to do it, I just do like one-to-one mapping to subset-sum problem.

Any feedback?


texts: Reducing optimization problem to decision problem

texts:
I'm trying to reduce an optimization problem to a decision problem, more specifically, consider the Max-Cut problem in its decision version:
Given $(G=(V,E),k)$ as input, where $G$ is an undirected weighted graph (all weights are positive integers, formally: $w: E\rightarrow \mathbb{N}$ is the weight function) and $k\in\mathbb{N}$, one should decide whether there exist a cut $(V_1,V_2)$, s.t its weight is at least $k$, meaning $k\leq \sum _{u\in V_1, v\in V_2}w(u,v)$.
The optimization version is simply finding the maximum weighted cut.
What I'm trying to achieve is, given an algorithm $A$ that can solve the decision problem, I want to describe an algorithm that can find the maximum cut in $G$.
So, first of all, this is what I had in mind:

Find the weight of the maximum cut in $G$ (this can be done with a simple for loop that starts with 1 and stops at $m$, where $m=\sum _{e\in E}w(e)$ while in each iteration the algorithm queries $A$), define $k$ to be the weight of the maximum cut.
Initialize new set $S\leftarrow \phi$
For $e\in E$ do:

Omit edge $e=(u,v)$ from $G$, to create new graph $G_e$.
If  $A(G_e,k)=0$ (both ends of $e$ are at the same set), $S\leftarrow S\cup \left \{ u,v \right \}$
else if $A(G_e,k)=1$ then...(?)
This is where I'm stuck, I'm not sure how can I tell which end of $e$ should be in $S$...
In fact, I'm not even sure if this is the right way to do it.

Any help and thoughts will be appreciated.


texts:
Please take this question with a grain of salt. I'm trying to write a very simple layout engine and wanted to formally create a grammar to parse the input. I stayed up all night researching LL(k) parsers - mostly from papers from different colleges. They tend to use the same examples and I've never been a fan of abstracting through notation, so I'm almost positive I have the syntax incorrect.

The input is very trivial:

header>rows>h-row>a|b

main>rows>m-row>qs|d
qs>qs-row>qa|qu

footer>rows>f-row>a|b

And this is the grammar definition:

S -> aBC
B -> op
C -> a

First:

S: [a]
B: [>, |, /]
C: [a]

Follow:

S: $
C: $
B: C | S


texts: Find all shortest paths in a graph where path has even number of edges and greater than 6

texts:
Let $G=(V,E)$, a directed with non-negative weights ($w:E\to\mathbb{R}^+$). Describe an algorithm, finds all shortest paths in the graph from a source vertex, $s\in V$, such that, each paths has an even number of edges and the number of edges is greater-equal to $6$.

So I know I need to use Dijkstra algorithm on a modified graph. Somehow I need to "count" the number of edges. I think I need to add some vertices for each vertex which will make the "count" but I can't figure it out completely.

I'd be glad for help.

Thanks.


texts: Blank tape halting problem vs. Emptiness problem ($H_0$ vs. $E_{TM}$)

texts:
I have difficulties to differentiate the $H_0$ from the $E_{TM}$ problem.

What exactly means $L(M)= \emptyset $? Is it dffierent from $input~ \varepsilon$ or is $L(M)= \emptyset \leftrightarrow input~ \varepsilon$

Emptiness problem:
$E_{TM} = \{\langle M \rangle | ~M~ is~ a~ Turing~ machine~ and~ L(M)= \emptyset \}$
$E_{TM}$ is undecidable
$E_{TM}$ is recognizable but not co-turing-recognizable
$E_{TM}$ is not recognizable but co-turing-recognizable

Blank tape halting problem:
$H_0 = \{\langle M \rangle ~ |~ M~ is~ a~ Turing~ Machine~ that~ halts~ on~ input~ \varepsilon  ~\}$
$H_0$ is undecidable
$H_0$ is recognizable but not co-turing-recognizable

any help is greatly appreciated


texts: Do Predecessors Ever Get Updated in Depth-First Search?

texts:
Is it true to say that in a Depth-First Search that uses a dictionary of predecessors to find the path to its destination, once a node has been pushed onto the stack and been added to the predecessors dictionary, there will never be a need to update the predecessor for that particular node? If so, why is that?
The reason I'm not clear is that in my understating the algorithm can backtrack to a previous node and start searching from there. When it does this, can we assume that the node that the algorithm "gave up on" will never be part of the solution path?
That is to say, is it the case that, once visited, a cell is either part of the solution path or never will be?
Below is my implementation in Python. It seems correct, but I'm niggled by the fact that predecessors are never updated. Are there any situations where this would prevent the algorithm giving a correct path to a reachable goal?
offsets = {
    "right": (0, 1),
    "left": (0, -1),
    "up": (-1, 0),
    "down": (1, 0)
}

def is_legal_pos(maze, pos):
    i, j = pos
    num_rows = len(maze)
    num_cols = len(maze[0])
    return 0 <= i < num_rows and 0 <= j < num_cols and maze[i][j] == 0

def get_path(predecessors, start, goal):
    current = goal
    path = []
    while current != start:
        path.append(current)
        current = predecessors[current]
    path.append(start)
    path.reverse()
    return path

def dfs(maze, start, goal):
    stack = [start]
    predecessors = {start: None}

    while stack:
        current_cell = stack.pop()
        if current_cell == goal:
            return get_path(predecessors, start, goal)
        for direction in ["up", "right", "down", "left"]:
            row_offset, col_offset = offsets[direction]
            neighbour = (current_cell[0] + row_offset, current_cell[1] + col_offset)
            if is_legal_pos(maze, neighbour) and neighbour not in predecessors.keys():
                stack.append(neighbour)
                predecessors[neighbour] = current_cell

    return None

maze = [[0] * 3 for row in range(3)]
maze[1][0] = 1 # obstacle
start_pos = (0, 0)
goal_pos = (2, 2)
result = dfs(maze, start_pos, goal_pos)
print(result)


texts: Single source shortest paths with even path

texts:
Given directed graph with non negative weights and vertex s.
I need an algorithm that finds shortest paths from s to all vertices and the paths have to be even.


texts: Is there a relationship between graph entropy and node entropy?

texts:
Eagle, et al [1] discuss the notion of node entropy and this is captured in igraph via the diversity metric. I was wondering if there was any relationship between these node entropies and the idea of the entropy for the entire graph.

A related question: Does the concept of edge entropy make sense? The probability would be the ratio of the weight of the edge in question and the sum of the weights of all edges connected to the nodes incident to the edge in question.

[1]: N. Eagle, M. Macy, and R. Claxton, “Network Diversity and Economic Development,” Science, vol. 328, no. 5981, pp. 1029–1031, May 2010.


texts: Fibonacci Sequence recursion algorithm and the time complexity

texts:
I am reading a free book on algorithms

http://www.cse.iitd.ernet.in/~Naveen/courses/CSL630/all.pdf

and on page 13 it says

"Compare this to the recurrence relation for Fn: we immediately see that T(n) ≥ Fn"

I do not understand how they know that T(n) ≥ Fn

if someone could explain it to me it would be much appreciated.
here is a picture of the information needed


texts: How to extend Bellman-Ford to solve the $k$ shortest path routing?

texts:
Browsing the wikipedia I got to this page where it is said:

  Finding k shortest paths is possible by extending Dijkstra algorithm or Bellman-Ford algorithm and extend them to find more than one path.

The same statement is somewhat repeated in the hall of fame of algorithms:

  To find the shortest path one can use shortest path algorithms such as Dijkstra’s algorithm or Bellman Ford algorithm and extend them to find more than one path

Then, the Wikipedia (i.e., the first link, not the second) goes into proving how it is possible to extend Dijkstra's algorithm to solve the loopy variant (i.e., where non-simple paths are allowed). The extension is absolutely simple as it simply consists of allowing each node to be expanded up to $k$ times, with $k$ the number of paths to find to the goal state. This idea, indeed, was generalized by Rina Dechter to consider heuristics as well:

Rina Decther, Natalia Flerova and Radu Marinescu. Search algorithms for $m$ best solutions for Graphical Models. AAAI 20, pp. 1895--1901
Natalia Flerova, Radu Marinescu and Rina Dechter. Search algorithms for the $m$ best solutions in Graphical Models. Journal of Artificial Intelligence Research (55) 2016, pp. 889--952.

However, I never heard of any extension of Bellman-Ford for solving neither the loopy nor the loopless variants of the $k$ shortest path routing problem. Moreover, I'm not aware of any algorithm that can solve this problem in the presence of negative edge costs.

The only variant I can think of for extending Bellman-Ford is observing that upon termination the cost of the optimal path of one designated vertex to all the other vertices $v\in V$, $d_v$, is known so that one could run sort of a Recursive Best-First Search to enumerate all paths. Maybe is this what the authors of those pages mean?

Thus, my questions are:

What is the way to extend Bellman-Ford to solve the $k$ shortest path routing problem?
Are there any algorithms out there for solving the $k$ shortest path routing problem with negative edge costs (provided there are no negative cycles)? Note that neither Eppstein's nor Yen's algorithm can deal with negative edge costs.

This is all I know about the subject and please note that my questions are a result of my ignorance so that I would be very grateful if any answer is provided or any link I could follow.

Cheers,


texts: How to Implement a reversible OR operator with a Fredkin gate (controlled swap)?

texts: How to implement a reversible OR operator with a Fredkin gate ?


texts:
Currently I'm trying to understand the CTL* model checking algorithm from this book. The basic idea is clear to that we can use the LTL algorithm to whenever we have a subformular $E\phi$ or $A\phi$ but I have still a question I can't figure out:

Why is there no case for $\phi_1 U \phi_2$ in this algorithm? Of course we can write the until modality as a release modality but this case isn't here either. So is this algorithm incomplete or have I missed something?


texts:
I am new to backtracking and recursion. I have seen numerous explanations on how on to find the minimum number of coins needed to make a particular amount. This involves a top down dynamic approach with mermoization and a bottom up using dynamic programming. Even the brute force apporach always starts using a top down approach breaking the problem down into smaller sub problems and then caching.

However, I have written the following algorithm that is not optimized to do the same but cannot figure out how to apply memoization. Is it even possible?

My basic algorithm is I start from sum = 0 and keep count of how many coins I have used by adding coin values and then returning the minimum count.

//function is called with sum = 0, coins = 0 and minCoins = Integer.MAX_VALUE
//coins[] contains the different coin denominations and target is the desired amount
// count is the number of coins that have been used

public static int makeChangeBacktracking(int sum, int[] coins, int target, int count, int minCoins) {

        if(sum == target) {
            return count;
        }

        for(int coin : coins) {
            //choose
            sum+= coin;
            //explore
            if(sum <= target) { //if it is greater than the target then why recurse???
                int c = makeChangeBacktracking(sum, coins, target, count + 1, minCoins);
                if(minCoins > c) {
                    minCoins = c;
                }
                //undo
                sum-= coin;
            }
        }
        return minCoins;
    }

I would like to apply any technique to improve the run time of the above algorithm. A clear explanation of whether or not memoization or other optimization techniques can be applied to this to speed up would be helpful.


texts: Creating an O(n log n) time and O(n) space algorithm for counting pairs in an array

texts:
Given an integer array $a$, create a function, $\text{int} \; \text{pairs}( \text{int} \;a[\;])$ that returns the number of equal element pairs in the array. For example, given the array $a=[2,5,1,2,5,1,1,6]$ the pairs are $(2,2), (1,1), (1,1), (1,1)$ and $(5,5)$, so the function should return $5$. The solution needs to run in $O(n \log n)$ time and $O(n)$ space.

My algorithm first sorts the array using  quick sort in $O(n \log n)$ time, then go through the sorted array and for each chunk of equal elements, keep track of the size of the group(which resets to $1$ when a distinct element is next), runs in $O(n)$ time.

If the next element equal the previous element, then increase the group size variable.

Otherwise, if the group size variable is bigger than $1$, add $n \choose 2$, where $n$ is the group size, to the overall sum of pairs variable(initially $0$), then reset the group size variable to $1$.

The problem I have is that, although the algorithm is correct, the algorithm runs in $O(n^2)$, which I think is because of the $n \choose k$ method.

The pseudo-code for my $n \choose k$ method is:

int binomial(n,k)
    if(k>(n-k)) k=n-k

    int b=1
    for(int i=0, m=n; i<=k; i++, m--)
        b=b*m/i

    return b

If the method does run in $O(n^2)$, then can I modify it to make it $O(n \log n)$. If its not possible to make a binomial coefficient method to run faster than $O(n^2)$, then does anyone have another algorithm for achieving the number of pairs from the array.


texts:
I have a question, does non-polynomial reduction exists for all problems?
the issue is only regarding polynomial reductions?


texts: How to mathematically determine row, column, and sub-square of cell in nxn array where n is a perfect square?

texts:
Given an one dimensional array of size nxn, where n is a perfect square

How can one mathematically determine the row, column, and/or sub-square the cell resides in? Additionally, is there a mathematical way to traverse the subsquare?


texts: Construct a pushdown automaton for $\{a^{2n}b^{3n}|n\ge0\}$

texts:
My idea is to (not formal) push an 'a' when we see an a, nondeterministically guess when n a's were seen from the input word, go to the next state. From there, when we see an a, push 2 'a's into the stack and again guess when n a's were seen (now there should be 3n 'a's in the stack) and go to the final state, where if we see a b, we pop from the stack. So the stack will be empty in the last state iff we saw 3n b's.
The problem that with this line of thought we can construct an automaton for$\{a^{n}b^{n}c^n|n\ge0\}$. So where am i wrong in this thinking?


texts: Problem with proving the undecidability of REGULAR$_{TM}$

texts:
Sipser in his book provided the following proof for undecidability of  REGULAR$_{TM}$:

  S = “On input $<M,w>$, where $M$ is a TM and w is a string:

  Construct the following TM $M_2$.

  $M_2$= “On input $x$:

  If $x$ has the form $0^n1^n$, accept .
  If $x $ does not have this form, run $M$ on input $w$ and
  accept if $M$ accepts $w$.”

  Run $R$ on input $<M_2>$.
  If $R$ accepts, accept; if $R$ rejects, reject .”

and it also states:

  Note that the TM $M_2$ is not constructed for the purposes of actually running it on some input. We construct $M_2$ only for the purpose of
  feeding its description into the decider for REGULAR$_{TM}$ that we have assumed to exist.

So it means we don't run the $M$ on $w$ at all. I would like to know why when the $M_2$ accepts regular languages we conclude that the $M$ accepts $w$ while we never run $M$ on $w$? The reduction must have a meaningful relationship between the problems. I can't understand this relation in this problem.

thanks


texts: How to calculate runtime complexity of the nested loops with variable length

texts:
Suppose I have a task to write an algorithm that runs through an array of strings and checks if each value in the array contains s character. The algorithm will have two nested loops, here is the pseudo code:

for (let i=0; i < a.length; i++)
  for (let j=0; j < a[i].length; j++)
      if (a[i][j] === 'c')
         do something

Now, the task is to identify the runtime complexity of the algorithm. Here is my reasoning:

let the number of elements in the array be n, while the maximum length of string values m. So the general formula for complexity is

n x m

Now the possible cases.

If the maximum length of string values is equal to the number of elements, I get the complexity:

n^2

If the maximum length of elements is less than the number of elements by some number a, the complexity is

n x (n - a) = n^2 - na

If the maximum length of elements is more than the number of elements by some number a, the complexity is

n x (n - a) = n^2 + na

Since we discard lower growth functions, it seems that the complexity of the algorithm is n^2. Is my reasoning correct?


texts:
I am confused about what does a VC dimension of a set of hypothesis means.

I have two hypothesis, say $H_1$ with VC dimension of $x$, and $H_2$ of VC dimension of $y$. Does this automatically mean that the VC dimension of this set is $max(x,y)$?

Or does this mean that I can use the combination of these two somehow to get a VC dimension which is possibly higher than $max(x,y)$? like if $H_1$ can't classify a specific ${(+,-)}$ combination of points but $H_2$ can classify it and vice versa, then that larger set is the new dimension of the set of hypothesis?


texts: Are there problems that are polynomial-time equivalent to factoring composites?

texts:
It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = \mathsf{NP}$ for quantum computing.

Are there interesting, non-obvious examples of problems with polynomial-time verifiability for solutions, which have been shown to be polynomial-time equivalent to factoring a composite number into primes, under the classical non-quantum computational model?


texts: Algorithm to find if there are N 1's in a matrix where no two 1's are in same row or column

texts: I am trying to find an algorithm to determine whether a $N\times N$ matrix of ones and zeroes could have a sublist of ones,  such that in that sublist we have only one $1$ from each row or column.


texts: How to calculate the total error from an arbitrary hidden layer in a neural network back propogation?

texts: I'm following the tutorial over at https://mattmazur.com/2015/03/17/a-step-by-step-backpropagation-example/ and so far everything makes sense to me. I am now trying to reason about how these formulas extend to any number of hidden layers. Specifically, how to proceed when you have the partial derivative of total error with respect to a weight. In the above post, $\frac{\partial Etotal}{\partial w1}$ is just the sum of the partials for $Eo1$ and $Eo2$ with respect to $w1$. Let's say that there is an extra layer between the $h$ nodes and the $o$ nodes, with nodes $j1$ and $j2$. Is $\frac{\partial Etotal}{\partial w1} = \frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}$ or is it more complicated? Something like: $\frac{\partial Etotal}{\partial w1} = \frac{\partial Eo1}{\partial w1} + \frac{\partial Eo2}{\partial w1} = (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1}) + (\frac{\partial Ej1}{\partial w1} + \frac{\partial Ej2}{\partial w1})$


texts: Is there a Dijkstra like pathfinding with condition satisfication algorithm?

texts:
Say we have a place-transition digraph system. A transition can fire if all input places have marks. A transition fires by consuming items from input places and placing one into each output place. A number near the transition is a transition price. So, for example, we can get an image like this:

We want to find the cheapest path from From to To. So it is quite simple to see how one can modify Dijkstra to find a path in algorithm terms, yet in terms of formal theory in generalised case it does not look so simple and there can appear loops and loop step related conditions. So Is there a Dijkstra like pathfinding with condition satisfaction algorithm?


texts: Efficiently comparing total values of two unsorted arrays

texts:
The general form of my question would be, what is the most efficient way to compare the total values of two different arrays to see which one is greater?

Would be as simple as prefix sum ($O(n)$) for both arrays? Or is there a more efficient method?

The specific question I'm staring at is:

  Let $A$ and $B$ be two unsorted arrays that each contains $n$ positive integers. Assume that all $2n$ integers are distinct. We say that $A$ is totally greater than $B$ if it is possible to re-order both arrays in a way that $A[i] \gt B[i]$ for every index $1 \le i \le n$. Describe an efficient algoirthm that for given arrays $A$ and $B$ determines if $A$ is totally greater than $B$.

If Prefix sum (adding $A[0]+A[1]$, then adding that sum to $A[3]$) is $O(n)$ and you have to run it twice for $O(2n)$, I don't see how you could improve on that efficiency.

All comparison sorts are $O(n(log(n))$ and Bucket Sort is $O(n)$...but this prompt would suggest there's some other efficient way to sort and compare two arrays.


texts: Should you post basic computer science homework to your github?

texts:
I am currently taking computer science coursework as part of a computer science related degree at my University. I was wondering if I should upload the solutions I make for various trivial homework assignments (ie. not more than 20-30 or so lines of code, on basic/fundamental topics) to my GitHub account, or if I should only upload larger course/personal projects to it.
I have only been regularly coding for about a year, and a large portion of the code I have written was for a company where I was under an NDA, so I was wondering if this would be an appropriate way to add more breadth to future job applications.


texts: (Symbolic) Equivalence of deterministic infinite word transducers with restriction

texts:
Given a deterministic infinite word transducer (also called deterministic generalized sequential machine) with the following restriction:

There is exactly one initial state
All states are final
The transducer is real-time, i.e. reads excactly one input character on each transition
The transducer produces zero or more output characters on each transition
The deterministic input automaton (obtained by eliminating the output on each transition) recognizes $\Sigma^\omega$, i.e. each state has $|\Sigma|$ transitions, one for each input character
There are no output $\epsilon$-loops, i.e. any infinite path yields an infinite word output

Are there special algorithms to decide equivalence for this type of automaton? I am particularly interested in those algorithms that admit a symbolic solution, e.g. using an SMT solver.

Note that one way to decide equivalence of two such transducers is to decide if the union of both automata is single-valued. However, I am not aware of a symbolic algorithm to decide single-valuedness if both states and transitions are given symbolically (e.g. by bit-vector constraints).


texts:
I have a small problem with the first order logic, in particular, predicate logic

Let us take this sentence as an example:

Each teacher has given a form to each student.

From this sentence, can we have different reading?

This is my try to solve such problem, I did not know if this is the answer for such question:

Every Teacher has given a form to each Student.

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Student then he has received a form from a teacher

Student(x)→(∃y)  Teacher(y)^(∃z)Form(z)^Give(x,y,z)

If X is a Teacher then he has gave a from for all his students

Teacher(x)→(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

If X is a form then a teacher gave it to all student.

Form(x)→(∀y)  Employer(y)^(∃z)Teacher(z)^Give(x,y,z)

EDIT

To clarify my needs !

I think that the form is in logical dependency, either of student, either of teacher, or both, so we can find three other readings; so What are those reading? (Look at the begining to find what I did)

And How can I transform this sentence in predicate logic?

Each teacher has given a form to each student.

because it seems that

(∀x)Teacher(x)^(∀y)  Student(y)^(∃z)Form(z)^Give(x,y,z)

is wrong.


texts: What algorithm is most suitable for large text compression?

texts:
Currently, I am looking for an lossless compression algorithm that is suitable for a large amount of text, that will be further encrypt by AES and use as the payload in steganography.

Based on A Comparative Study Of Text Compression Algorithms, it seems that Arithmetic coding is preferable in Statistical compression techniques, while LZB is recommended for Dictionary compression techniques.

So now I am wondering whether Statistical compression or Dictionary compression is more suitable for large English text compression in terms of compression ratio and ease-to-implement.

I have search through but still barely have an idea of the suitable algorithm. Thank you very much for your time in answering. Have a nice day. :)


texts: How can I calculate tree sizes to "stretch up" a finger tree?

texts: I've been working on implementing an efficient Cartesian product operation (actually the <*> operation, but it amounts to about the same thing) for sequences based on Hinze and Paterson's "Finger trees: a simple general-purpose data structure". It seems that a natural way to calculate $xs \times ys$ when $xs$ and $ys$ each has at least two elements is to (conceptually) replace each leaf $x$ in $xs$ with a 2-3 tree representing $\{(x,y)\mid y \in ys\}$, and then "stretch" the first and last element of the resulting tree upwards/outwards to bring the tree to the proper depth. But for efficiency and other reasons, this actually needs to be done in the opposite direction—I'd need to pull off the first and last element of $xs$, and then work my way down, calculating at each level how much of $ys$ to leave behind there, and also to check whether it's possible to represent $ys$ by a 2-3 tree of the appropriate size for that level. I'm not really sure how to get a grip on the necessary math.


texts: Two way deterministic pushdown automaton accepting word consisting of two equal words

texts:
I have a homework where I have to construct two way deterministic pushdown automaton that accepts this language:

{ww | w ∈ {a, b}*}

Does anyone have any idea? Thanks a lot


texts: Clarification for binary search in solving optimal TSP when a polynomial algorithm with a budge exists

texts:
Below is Question 8.1 in Algorithms by Dasgupta et al.

There's a solution to this problem that uses binary search from here. Pasting the answer for posterity.

My questions are:

When they say input size, are they just referring to edges or both
edges and vertices?
Is it correct to say that we make at most $log( |E| log K)$ calls?
Does this work if the edge weights aren't integers, like 10.4 etc?
Why is this NP-Hard as the solution mentions? I thought that Traveling Salesperson Problem was NP-Complete

This question on stackoverflow asks for clarification of binary search use but doesn't answer the above question.


texts: Example of Soundness & Completeness of Inference

texts:
Is the following example correct about whether an inference algorithm is sound and complete?

Suppose we have needles a, b, c in a haystack, and have also an inference algorithm that is designed to find needles.

sound - Only needles a, b and c are obtained.
complete - Needles a, b and c are obtained. Other hay may also be obtained.


texts: Approximation algorithm for TSP variant, fixed start and end anywhere but starting point + multiple visits at each vertex ALLOWED

texts:
NOTE: Due to the fact that the trip does not end at the same place it started and also the fact that every point can be visited more than once as long as I still visit all of them, this is not really a TSP variant, but I put it due to lack of a better definition of the problem.

This problem was originally posted on StackOverflow, but I was told that this would be a better place. I got one pointer, which converted the problem from non-metric to a metric one.

So..

Suppose I am going on a hiking trip with n points of interest. These points are all connected by hiking trails. I have a map showing all trails with their distances, giving me a directed graph.

My problem is how to approximate a tour that starts at a point A and visits all n points of interest, while ending the tour anywhere but the point where I started and I want the tour to be as short as possible.

Due to the nature of hiking, I figured this would sadly not be a symmetric problem (or can I convert my asymmetric graph to a symmetric one?), since going from high to low altitude is obviously easier than the other way around.

Since there are no restrictions regarding how many times I visit each point, as long as I visit all of them, it does not matter if the shortest path from a to d goes through b and c. Is this enough to say that triangle inequality holds and thus I have a metric problem?

I believe my problem is easier than TSP, so those algorithms do not fit this problem. I thought about using a minimum spanning tree, but I have a hard time applying it to this problem, which under the circumstances, should be a metric asymmetric directed graph?

What I really want are some pointers as to how I can come up with an approximation algorithm that will find a near optimal tour through all n points


texts: Mistake in Karp's paper on NP-Complete problems?

texts:
I read on a blog that there are mistakes in Karp's paper where he proved that 0-1 programming is NP-Complete, but I couldn't find it, can anyone explain? And I doubt that there are also mistakes where he proved Steiner Tree Problem is NP-Compelete but not sure.

The blog post a little old and I thought asking the writer of the blog may not receive answer quickly enough. I didn't find any referrence in other places so I thought this question may worth asking.


texts:
http://cs.jhu.edu/~misha/Spring14/Preparata77.pdf

This is a divide and conquer algorithm for computing the convex hull in 3 dimensions.

I am having trouble understanding the merge step, which is titled Merge in 3 Dimensions, outlined in the paper.

I am specifically having trouble understanding how the number of comparisons made is done in O(n) time for the whole hull.

On page 92 in the last paragraph on the left column, it says that the number of comparisons made is bounded by the number of edges which is linear for each hull. But what if each vertex had p edges (so you are checking duplicates), then that would add up to quadratic running time. Or, if the number of edges each time was monotonically increasing from 1 to p-1, that still adds up to quadratic running time for the comparisons. For instance, a tetrahedron has 4 vertices and each vertex has a degree of 3, so the number of comparisons made would be 12.


texts: Why do we need "potential” for amortized analysis?

texts:
In the current version as of the Wikipedia article “Potential method”, the amortized cost of each operation is defined as the following
$$
T_{\mathrm{amortized}}(o) = T_{\mathrm{actual}}(o) + C \cdot (\Phi(S_{\mathrm{after}}) - \Phi(S_{\mathrm{before}})),
$$

and the total amortized cost is
$$ \begin{align*}
T_{\mathrm{amortized}}(O) &= \sum_i (T_{\mathrm{actual}}(o_i) + C \cdot (\Phi(S_{i+1}) - \Phi(S_{i}))) \\ &= T_{\mathrm{actual}}(O) + C \cdot (\Phi(S_{\mathrm{final}}) - \Phi(S_{\mathrm{initial}})).
\end{align*} $$

I understand the formulas and understand $T_{\mathrm{amortized}}$ is an upper bound on $T_{\mathrm{actual}}$ if the initial potential is zero. And I think I understand the basic examples like "binary counter", "two stack FIFO", etc. However, I am puzzled this:

  The actual cost is part of the formula.

I might be wrong but it looks like the actual cost is a known quantity. If we already know the actual cost, why do we need to add the "potential" to get an upper bound? It looks useless to me. Can anyone help give an example in which such "potential analysis" is useful?


texts:
I am Implementing a Queue using circular arrays in C language .The Implementation uses one empty position to indicate that the queue is full.That is if the rear is two position behind front. The condition is we cant use a variable to count the entries in the queue as we insert or delete . I have created this function to find the size of queue with Time Complexity Big-Oh(n) because it starts with front and goes upto rear in a loop .

int QueueSize(Queue *q)
{
    if(QueueEmpty(q))
    {
        return 0;
    }
    else{
        int count=0;
    for(int i=q->front;;i=(i+1)%MAXQUEUE)
    {
        count++;
        if(i==q->rear) break;
    }
        return count;
}
}

Is there a way to find the size of queue in constant time ?
Elements are inserted from rear and deleted from front !
My Queue starts from 0 and assume maximum queue size is 6 in below example

10 Appended at position 0
20 Appended at position 1
30 Appended at position 2
40 Appended at position 3
50 Appended at position 4
10 Removed from position 0
20 Removed from position 1
60 Appended at position 5
70 Appended at position 0
30 Removed from position 2
40 Removed from position 3
80 Appended at position 1
90 Appended at position 2
Queue Size:5
Position:4  Element:50 (front)
Position:5  Element:60
Position:0  Element:70
Position:1  Element:80
Position:2  Element:90 (rear)


texts: Are all integers kept in 2's complement form in all microprocessors?

texts: Are all integers kept in 2's complement form in all microprocessors or do microprocessors use 1's complement form and unsigned integer form too?


texts: Hash function - uniformity / strong universality

texts:
I am currently learning how randomised Hashing works.
So, you have a class (aka family) $H$ of hash functions, each of which maps the universe $U$ to the hash table $N$.

That class is called "strongly universal" or "pairwise independent" if $\forall x,y \in U, x \neq y: \forall z_1,z_2 \in N: \Pr\limits_{h \in H}[h(x) = z_1 \land h(y) = z_2] \leq \frac{1}{|N|^2}$. In words: pick any two elements from the universe and two from the hash table. If you pick a hash function from the hash class at random, the probability that these two elements are mapped to each other by $h$ is less or equal than $\frac{1}{|N|^2}$.

Now, what is confusing me is that, since $x$, $y$, $z_1$ and $z_2$ are all completely independent, it looks to me like you could just "remove" one pair from the equation and still get the same result. That would be $\forall x \in U: \forall z \in N: \Pr\limits_{h \in H}[h(x) = z] \leq \frac{1}{|N|}$. This, however, is called "uniformity" of a hash class.

Could someone explain to me why these two attributes are different from one anoter?


texts: Why are there no complete problems for NP ∩ coNP?

texts:
The fact that PPAD is a subclass of TFNP seems to be taken as evidence that PPAD cannot be shown complete (or hard) for classes of independent interest like NP ∩ coNP. Slightly confusing, it even seems to excuse that it has not yet been shown complete for PPA, in which it is contained and which has complete problems.

A hint why this is expected is given at the end of Megiddo and Papadimitriou. A Note on Total Functions, Existence Theorems and Computational Complexity (1989):

  Finally can we hope to have TFNP complete problems? As with other classes  (such as NP ∩ coNP, R, BPP etc.) whose machine based definition is semantic instead of syntactic (i.e., depends on a property that the machine exhibits when computing on any input), we do not expect such problems to exist.

I had a similar experience with R (or rather RP) that I started to settle for completeness of smaller classes, until I suddenly realized that the lower end (first the compressed word problem for monoids, then the compressed word problem for free groups) was actually P-complete, i.e. I had wrongly believed that those would be hard problems.

How valid are such excuses really for failing to show completeness (or hardness) of "believed to be difficult" problems with respect to complexity classes of independent interest?


texts: Why does introsort use heapsort rather than mergesort?

texts:
As part of a homework assignment covering implementation of introsort I'm asked why heapsort is used rather than mergesort (or other $O(n\log(n))$ algorithms for that matter).

  Introsort is a hybrid sorting algorithm that provides both fast average performance and (asymptotically) optimal worst-case performance. It begins with quicksort and switches to heapsort when the recursion depth exceeds a level based on (the logarithm of) the number of elements being sorted. (Wikipedia, retrieved 2014-May-06.)

The only reason I can think of is that heapsort is "in place" ... But tbh I don't really understand why this would matter here though.