texts: A polynomial reduction from any NP-complete problem to bounded PCP

texts:
Text books everywhere assume that the Bounded Post Correspondence Problem is NP-complete (no more than $N$ indexes allowed with repetitions). However, nowhere is one shown a simple (as in, something that an undergrad can understand) polynomial time reduction from another NP-complete problem.

However every reduction I can think of is exponential (by $N$ or by the size of the series) in run-time. Perhaps it can be shown that it is reducible to SAT?


texts:
I'm doing a course on randomized algorithms and
I've encountered a question that I'm struggling to solve.

Given a system of $m$ linear equations with $n$ variables over finite field $\mathbb{F_2}$ where every equation is of form $a_1x_1+...+a_nx_n=b \mod 2$ and $x_i,a_i,b\in\{0,1\}$ and multiplication and sum are $\mod 2$.

First part of the question is to find an efficient randomized algorithm that finds an assignment to the variables over $\{0,1\}$ so that expected value of satisfied equations is $\frac{m}{2}$.  This part is relatively easy, choosing a random assingment over $\{0,1\}$ gives us the desired result. Each equation is satisfied with probability $\frac{1}{2}$ and expected value over $m$ equations will give us $\frac{m}{2}$ satisfied equations.

The second part is the one I struggle with, it is asked to prove that there exist $O(logm)$ assignments to the variables such that every equation is satisfied by at least one assignment. And it is asked to propose a randomized efficient algorithm that finds those $O(logm)$ assignments with probability at least $\frac{1}{2}$. There is also a hint: let $E_i$ be an event that random assignment satisfies equation $i$, then events $E_i(1<=i<=m)$  are $2-wise$ independent.

I really don't know how to approach this. Any help would be appreciated.


texts: Curious about an old algorithm which calculates modular inverse

texts:
I am not sure if I should ask this question here or somewhere else. In fact, I initially asked my question here at mathoverflow.net but it was marked as off-topic

Background: I was searching through random mathematics paper that are related to cryptography and I came across this paper (page 3). I just read the abstract and algorithm itself, I don't understand Chinese. It offers new method to find a Modular inverses. It has some interesting properties that I observed:

during each step iteration of the loop: $x_{11} * x_{22} + x_{12} * x_{21} = m$ which is good to validate the result during each iteration
algorithm terminates in even number of steps for some unknown reason

In abstract section, author says this method was invented by this mathematicians.

My question is, why does this algorithm always terminate in aeven number of steps (or number of iterations of the loop is always even)?

Algorithm to calculate: $a^{-1} (\bmod m)$:

  $\text{xgcd}(a, m):$

  $\quad x_{11} \leftarrow 1, x_{21} \leftarrow 0, x_{12} \leftarrow a, x_{22} \leftarrow m$

  $\quad \text{While }(x_{12} > 1) \text{ do}$

  $\quad \quad \text{If }(x_{22} > x_{12}) \text{ then}$

  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{22} - 1}{x_{12}}\Big\rfloor$

  $\quad\quad\quad\quad r \leftarrow x_{22} - q ~x_{12}$

  $\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}x_{11} & x_{12}\\q~x_{11} + x_{21} & r\end{pmatrix} $

  $\quad\quad \text{If }(x_{12} > x_{22}) \text{ then}$

  $\quad\quad\quad\quad q \leftarrow \Big\lfloor\frac{x_{12} - 1}{x_{22}}\Big\rfloor$

  $\quad\quad\quad\quad r \leftarrow x_{12} - q~x_{22}$

  $\quad\quad\quad\quad \begin{pmatrix}x_{11} & x_{12}\\x_{21} & x_{22}\end{pmatrix} \leftarrow \begin{pmatrix}q~x_{21} + x_{11} & r\\x_{21} & x_{22}\end{pmatrix}$

  $\quad \text{Return } x_{11}$

Screenshot of the algorithm
Python and SageMath implementations


texts:
I have a question regarding the Condensed Nearest Neighbor algorithm from “Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174:
! [“Nonparametric Methods.” Introduction to Machine Learning (OIP), by Ethem Alpaydin, Mit Press, 2004, pp. 174–174.]1

Ultimately, I am supposed to return the subset Z to be a local minimal subset to use for training set in KNN. Why am I returning Z, which, if I understand correctly, is the array of all of the misclassified points? Wouldn't I want to return the points that were classified correctly? What benefit does this give me in returning all the points I got wrong?


texts:
I see that most definitions of what it is to be Turing-complete are tautological to a degree. For example if you Google "what does being Turing complete mean", you get:

  A computer is Turing complete if it can solve any problem that a Turing machine can...

While it is very well defined whether different systems are Turing complete or not, I haven't seen an explanation of what the implications/consequences of being Turing complete are.

What can a Turing machine do that where no non-Turing machine exists that can also perform the same task? For example a computer can perform simple calculations like (1+5)/3=?, but an ordinary calculator can also do them, which is non-Turing complete if I am correct.

Is there a way to define the capabilities of Turing Machine without just saying "being able to simulate another Turing Machine"?


texts: Problems with decidability open (for a long time) proven decidable

texts:
It seems to me that problems whose dedicability remains open for a long time, if resolved, tend to end up being undecidable. A prominent example would be (e.g.) Hilbert's tenth problem, whose decidability was open 21+ years (†) until proven decidable. Is there a similiar example of a problem whose decidability was open for a long time (receiving considerable attention) but was proven, in the end, to be decidable?

(†) Hard to put an exact figure on how long it was open. Originally stated in 1900 and proven in 1970, but the original statement was before the modern notion of undecidability.


texts: Differences between Church and Scott encoding

texts:
I'm kind of new to lambda calculus and I found this Wikipedia article
https://en.wikipedia.org/wiki/Mogensen%E2%80%93Scott_encoding

The section Comparison to the Church encoding presents a short comparison between Church and Scott encoding

Church

λx1...xAi.λc1...cN.ci (x1c1...cN)...(xAic1...cN)

Scott

λx1...xAi.λc1...cN.ci  x1...xAi

Do you agree with the Church generic encoding description? The page specified that citation is needed for that description.


texts:
I'm working with a very large undirected graph (a social network from a telecomunication company).

I'm applying a clustering algorithm on this graph to find it’s most relevant communities. The problem is that the algorithm is very slow and I need to test it with a smaller graph to tune some parameters.

Recently, I came with the idea of getting a sample from this large graph. This sample has to be representative of the original graph.

Is there someone who knows the best algorithm to get that sample? And what should be the minimum size of the sample (is it 15%?)?

I already read some articles about sampling on large directed graphs (Estimating and Sampling Graphs with Multidimensional Random Walks, and Sampling from Large Graphs), and there doesn't seem to be any article about undirected graphs.

If you need any more information, please tell me.

Thank you very much,

DC


texts: Given a partition $[0,1]$，there are 5000 partition subsets $P_i=[a_{i1},a_{i2}]\in[0,1], 0≤a_{i1}\leq a_{i2} \leq 1, i \in \{1,2,...,5000\}$. I want to analyze these subsets and find 10 subsets to contain sixty or seventy percent of the subsets. These 10 subsets could be disjoint, or even overlapping.


texts: Name and complexity of a problem concerning metrics

texts:
Do you know the name of the following problem and can you give a reference for its complexity (especially the relation to $\mathsf{GraphIsomorphism}$ and/or other isomorphism/homomorphism problems)?

  Given two metrics $d_1$ and $d_2: V^2 \to \mathbb{N}$. Does there exist a  permutation $\pi$ on $V$ such that $d': V^2\to \mathbb{N}$ with
  $$d'(u,v)=\min \{d_1(u,v),d_2(\pi(u),\pi(v))\}$$
  is a metric?

Motivation: Think of two fishing nets. If you try to fasten every knot of one net to every knot of the other net, the maximal distance between two knots is determined by the length of the shorter thread in the two nets.


texts: A graph in descriptive complexity - is $x$ already a vertex?

texts: So suppose that there is an undirected graph with edge connections known. Now in first-order logic there is quantifier $\forall x$. Then does this automatically refer to vertexes, or can we use relation like $v(x)$ to say that $x$ is a vertex?


texts: Heuristic for searching for solutions on an 8-puzzle variant with non-unique tiles

texts:
I'm trying to perform an A* search on a particular N-puzzle variant in which some tiles are identical. More specifically, assuming an $m \times m$ grid, there are m colors with m tiles of each. The puzzle is considered solved when tiles form vertical lines of matching color. For example, with $m=3$

RG       GR     GR      RGB
RGB     BGR     GRB     RG      etc.
RGB     BGR     GRB     RGB

would all be valid solutions.

I am having difficulty coming up with a good heuristic for this, as any one tile could potentially occupy any one of the m*m locations when solved. Could anyone offer any suggestions or advice? Perhaps another type of search algorithm would be better?


texts:
One possible motivation for studying computational complexity classes is to understand the power of different kinds of computational resources (randomness, non-determinism, quantum effects, etc.).  If we look at it from this perspective, then it seems like we can obtain one plausible axiom for any attempt at characterizing which computations are feasible in some model:

Any feasible computation can always invoke another feasible computation as a subroutine.  In other words, suppose the programs $P,Q$ are considered feasible to execute.  Then if we construct a new program by hooking $P$ and $Q$ up, so that $P$ makes subroutine calls to $Q$, then this new program is also feasible.

Translated into the language of complexity classes, this axiom amounts to the following requirement:

If $C$ is a complexity class intended to capture which computations are feasible in some model, then we must have $C^C = C$.

(Here $C^C$ represents computations in $C$ that can invoke an oracle from $C$; that's an oracle complexity class.)  So, let's call a complexity class $C$ plausible if it satisfies $C^C=C$.

My question: What complexity classes do we know of, that are plausible (by this definition of plausible)?

For instance, $P$ is plausible, since $P^P=P$.  Do we have $BPP^{BPP} = BPP$?  What about $BQP^{BQP} = BQP$?  What are some other complexity classes that meet this criterion?

I suspect that $NP^{NP} \ne NP$ (or at least, that would be our best guess, even if we cannot prove it).  Is there a complexity class that captures non-deterministic computation and that is plausible, under this definition?  If we let $C$ denote the smallest complexity class such that $NP \subseteq C$ and $C^C \subseteq C$, is there any clean characterization of this $C$?


texts: Which process states exist a multi-processor machine?

texts:
In a single-processor architecture, A process might be New, Ready, Running, Blocked and Terminated.

Are there any additional states in a multi-processor architecture?


texts: Should I normalize values not bigger than 1

texts:
I have a question regarding a normalization of values especially in the case of image processing features classification. What if have a series of values that will never be bigger than 1.

A = 0.004 0.032 0.017

Do I still need to normalize it into [0,1] range? The thing is that the A variable will may also contain 0 at some point of the values construction and will never have 1 as its maximum value.

I have another variable like

B = 123.4 5.52 3.44

The B will be normalized.


texts:
Suppose we have a set of $n$ dimensional rectangles $R = \{(x_{i,1}, \ldots, x_{i,n}), i \in 1 \ldots k\}$. We want to create the highest stack in say the first dimension such that each side of the rectangles form a monotonically increasing sequence. More formally from the $l$-tuples satisfying this

$$
\max_{l: (j_{1}, \ldots, j_{l}), j_{i} \in 1 \ldots k, j_{q} = j_{p} \iff q = p}{\forall q \in 1 \ldots l - 1, \forall p \in 1 \ldots n:  x_{j_{q}, p} < x_{j_{q + 1}, p}}
$$

take the one with the maximal $\sum_{i = 1}^{l}{x_{j_{i}, 1}}$ or just simply calculate this maximal value.

What's the algorithmic complexity of this? For $n = 1$ we can think of this as a weighted LIS. Is there a better approach than just sorting it on the first dimension and trying to find the longest increasing sub sequence for all dimensions?


texts: Counting the nodes in a network in a distributed way

texts:
There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters).

One of the nodes, say $s$, wants to know $n$. How can it do this?

Each node has $O(\log n)$ memory bits, so it can hold a counter, but not a list of all nodes.

If the network is a tree, I think the following (inefficient) protocol should work:

$s$ sends a "Count" message to itself.
When a node $v$ receives a "Count" message from node $u$, it acts in the following way:

Send every neighbour except $u$ a "Count" message and wait for the result.
Send $u$ a "Result" message containing the sum of all results (0 if there are no neighbours).

The problem with general graphs is that we may not remember which nodes we already counted, so we might count the same node twice. What to do?


texts: Finding all edges on any shortest path between two nodes using dijkstra

texts:
Given a directed weighted graph, we need to mark all edges (represented by an ordered triple of (source,destination,weight) ) which lie on some shortest path from source to destination (there could be more than one shortest path);

I know that it can be done by running Dijkstra two times, first from source and another from destination with edges inverted. But i am not very clear about this algo so that i could implemment it,all i need a little description or explanation....
Thank You


texts: Subspace clustering with random transformation

texts: One approach for clustering a high dimensional dataset is to use linear transformation, and the most common approaches are PCA and random projection (where random projection arises from the Johnson-Lindenstrauss Lemma). I was wondering why we can't use other random transformation  s like when our transformation matrix $R$ was drawn from a uniform distribution?


texts: Runtime bounds on algorithms of NP complete problems assuming P≠NP

texts:
Assume $P\neq NP$.

What can we say about the runtime bounds of all NP-complete problems?

i.e. what are the tightest functions $L,U:\mathbb{N}\to\mathbb{N}$ for which we can guarantee that an optimal algorithm for any NP-complete problem runs in time of at least $\omega(L(n))$ and at most $o(U(n))$ on a input of length $n$?

Obviously, $\forall c:L(n)=\Omega(n^c)$.
Also, $U(n) = O(2^{n^{\omega(1)}})$.

Without assuming $QP\neq NP$, $ETH$, or any other assumption which is not implied by $P\neq NP$, can we give any better bounds on $L,U$?

EDIT:

Note that at least one of $L,U$ has to be far from the bounds I gave here, since being NPC problems, these problems has poly time reduction between each other, meaning that if some NPC problem has an optimal algorithm of time $f(n)$, then all problems has an algorithm (optimal or not) of runtime $O(f(n^{O(1)}))$.


texts: How does Lucene build its inverted index so rapidly

texts:
I am writing a small Ruby on Rails engine that does simple full-text search. When someone imports text from a given model (eg. Articles, Posts, etc) an inverted index is built that looks like the following:

Term        Doc. info               Doc. frequency  Spelling suggestions
appear      {:title=>[1], :body=>[1, 2, 3]}     4   ["appears"]
success     {:title=>[1], :body=>[1]}           2   ["successful", "success"]
year        {:body=>[1, 2, 3, 4]}               4   ["yearly", "year"]
synonym     {:body=>[1]}                        1   ["synonymous"]
fashion     {:body=>[1]}                        1   ["fashion"]
tv          {:body=>[1, 2]}                     2   ["tv"]
drama       {:body=>[1]}                        1   ["dramas"]
aesthet     {:body=>[1]}                        1   ["aesthetics"]

where the term is the stemmed version of the imported word, the doc info are the document ids and fields where the term appears, the frequency is the sum of occurrences and the spelling suggestions are the original (unstemmed word) which I will later be using for spelling suggestions (using Levenshtein Distance).

This import process can take ~20 seconds for several thousand words.

My question is, how is it possible that Lucene can rapidly tokenize and build an inverted index for several thousand documents within a fraction of the time that it's taking me? Am I doing something fundamentally wrong?


texts: How to determine the number of active linearly independent constraints in a basic feasible solution for linear programming?

texts:
I am trying to determine if a given solution is a basic feasible solution. I am working with an $n-$dimension polyhedron $P$ defined by a set of $M$ inequalities $Ax \leq B$. I am running into an issue where I am not sure how to determine if a solution is basic feasible or degenerate. Working off of the following definitions, from harvard.edu/lecture_notes:

A solution in $P = {x : Ax \leq B}$ is called basic feasible if it has $n$ linearly independent active constraints.
A solution in $P = {x : Ax \leq B}$ is called degenerate if it it has more than $n$ linearly independent active constraints.

If you were to define a new matrix $A'$ that consists of only the active constraints, how do you find the number of linearly independent constraints within $A'$? In the case of a pyramid, the pinnacle of the pyramid is a basic feasible solution that is represented with four constraints, of which three are independent. So, in this example, $A'$ would consist of four constraints, of which, we would want to be able to find that three of the four constraints are linearly independent.
Is there an efficient way to calculate the number of linearly independent constraints from a set of active constraints?


texts:
When you first learn more about computation you can imagine it in terms of boolean circuits. That is you get a boolean vector $v \in \lbrace 0,1\rbrace ^n$ which you can then apply a circuit $C$ to which then produces an output boolean vector, and $C$ must be constructed from some basic gates (and or not).
It's fascinating that if we assume our input vector is not a boolean vector $v \in \lbrace 0,1\rbrace ^n$ but rather an exponentially large complex vector $v \in \mathbb{C}^{2^n}$, BUT we also now restrict our circuits to strictly be complex unitary matrices, we end up with a stronger model of computation, BQP, which can solve problems that we currently don't know to be solvable in P.
Subjectively what happened here, was we made the state of our program much larger. After all $\mathbb{C}^{2^n}$ is for most n way bigger state than $\lbrace 0,1 \rbrace^n$, but then we made our circuit much weaker, that is we can't do arbitrary circuits anymore we can ONLY multiply with complex unitary matrices. Between making the state bigger (obviously strengthening your computational power power), and the circuit choice smaller (which would weaken your computational power), we all said and done end up with a slight net gain in computational power (factoring is now polytime, but NP has not yet obviously become accessible!).
So now this leads to the natural question, can the process: "expand state size", "reduce choice of operators" yield other interesting complexity classes that are stronger than BQP but don't collapse NP to their P?
An example of what I would look for could be the following: what if the state vector is $\mathbb{C}^{2^{2^n}}$ but the gates that we get to use are a much more restricted class than unitary matrices (ex: only unitary matrices with determinant 1). Does this model computation allow us to solve problems in polynomial time that are known to be intractable to a quantum computer?
Perhaps the example I give may not clearly give an answer so feel free to swap out the underlying field $\mathbb{C}$ with some other ring of your choice, and then restrict the operators as you see fit.


texts: Why can't we say that a Neural Network is a NP problem solver?

texts:
From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The example he draws on is just seeking the next yes till you find some final output. For those reasons, I had assumed that even SGD is NP complex, and by extension Neural Networks. And my logic was that, through readings it seems like a Back Prop algorithm is always looking for a way to reach towards the global minima by taking the most negative step.
However, from my reading, it seems like Neural Networks have a computational Complexity of P. And as a result of the fact that most people believe $P\neq NP$ then a NN can only take a guess/approximation at a solution.
From what I follow, the belief is that since a Neural Network can't promise an ideal result, it isn't an NP solver. But that confuses me since from what I have seen, a Neural Network just never gives that ideal solution. Does that mean all these problems are just more complex than P and so they can only make a different guess every time? While an NP solution is supposed to consistently give back the correct answer.
From linear Algebra, we know that a solution needs to be a repeatable, deterministic mapping from $X\to Y$ Or else it is a mere approximation function and $X$ is not in the domain of the transformation.
To me that means either my understanding of what a Neural Network does in its backpropagation is wrong. Or that my understanding of NP complexity is wrong.


texts:
Here is the question:

  Consider a computer system that has cache memory, main memory (RAM) and disk, and the operating system uses virtual memory. It takes 2 nsec to access a word from the cache, 10 nsec to access a word from the RAM, and 10 ms to access a word from the disk. If the cache hit rate is 95% and main memory hit rate (after a cache miss) is 99%, what is the average time to access a word?

Here is how I solved it.
   consider 100 references
   95 cache hits(due to 0.95 cache hit ratio)
   95*2nsec = 190 nsec

this would leave 5 references which were passed to memory
   5*0.99=4.95=5 successfully found in memory

this would count for

5*10nsec=50nsec

average access time=total time/total accesses
   =(50+190)/100 nsec
   =240/100 nsec
   =2.4 nsec

Is this correct?

Here is another solution

memory access time
   =cache hit ratio * cache access time + (1 - hit ratio) * miss penalty(or memory access time)
   =0.95*2+(1-0.95)10
   2.4 nsec

which one is the perfect solution to this problem?

In question memory hit ratio is also given but is not used in the formula I used in second solution.Was it unnecessarily given in the question?
If there is a problem where cache hit rate is 85% and memory hit rate is 5% and disk hit rate is 10%, then what would be the miss penalty in that case?


texts: longest palindromic subsequence / substring and dynamic programming

texts:
The longest palindromic subsequence problem can be solved using dynamic programming because it is recursive and has overlapping subproblems, as described in https://www.geeksforgeeks.org/longest-palindromic-subsequence-dp-12/ .

On the other hand, AFAIK there is no dynamic programming solution to the longest palindromic substring problem. In the DP solution presented at https://www.geeksforgeeks.org/longest-palindrome-substring-set-1/ , the overall solution is equal to the naive one: to compare the length of all palindromic substrings. The only difference is that DP is used to speed up the process of finding if each substring is palindromic, which reduces the time complexity from O(n^3) (naive solution) to O(n^2).

Why is there a DP solution for the LP subsequence problem, but not for the substring problem? Is it because the former can be expressed by a recursion and the latter not?


texts: The definition of a graph's transitive reduction

texts:
I want to determine the transitive reduction of this graph:

as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is what I did:
 (a,b)
 (a,c)
 (a,d)
 (a,e)
 (b,d)
 (c,d)
 (c,e)
 (d,e)

I'm not sure that this is the correct transitive closure of the graph, and I don't know how to move forward in determining its transitive reduction.


texts: I want to create multi-tape Turing machine that recognize language {ww,  $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from language. I have an idea to create x-tapes to solve this problem, but can be the number of tapes not known before reading from input(read-only) tape, and for n-length there will be n-tapes, is that possible ?


texts: How is n-gram different from k-mer? Both seem to be (n or k) length substrings of a larger string. Are these just terms common with different practitioners? viz. Computer Scientists and Bioinformaticians?


texts: Converting indirect recursion to direct one

texts:
I want to remove left recursion in grammar:

$G = ({S, A,B,C,D}, {a,b,c},P,S)$

$S → A$

$A → Aa | Bc$

$B → B a |CD$

$C →C b | ε$

$D → Bb | a$

We see that this grammar contains direct recursion ( $A → Aa$ ) and indirect recursion ( $B → CD → D → Bb$ ). We need to remove indirect recursion and convert it into direct recursion.

The problem in this grammar is $C →  ε$ rule , so we remove epsilon rules , after that we are left with

$B → B a |CD |D$ which is another indirect recursion so we remove simple rules.

Then we can remove left recursion step by step by alghoritm.

My question is , having large grammar , finding indirect recursion may be difficult. Is there any universal way how to convert indirect recursion to direct recursion? Thanks for answers


texts: A reference for pseudocode for Monge-Elkan algorithm?

texts:
Does anyone have a good reference to pseudocode for Monge-Elkan string comparison algorithm?

I have access to the two  original papers, but they do not show the pseudocode of the actual algorithm. Also, I have seen some implementations in Java (preference), but they are part of the larger package and with a complex inheritance and composition hierarchies.

I was wondering if someone can point me to a pseudocode for the algorithm, so that I could implement it myself.


texts: Sampling Multiple Times From a Markov Chain

texts:
In probability theory, the mixing time of a Markov chain is the time until the Markov chain is "close" to its steady state distribution. Lets fix some $\varepsilon\in (0,1]$ as our closeness parameter.

Now suppose that we have a Markov Chain M with mixing time T, and suppose that
we want to draw 10 independent samples from the stationary distribution of M. What is the correct way to do that?

Do we have to apply the Markov chain for $10\cdot T$ steps, and pick the
resulting states at time $T, 2T, ...,10T$ as my samples, or...
is it enough to apply the Markov chain for T+10 steps, and pick the    resulting states at time $T+1,T+2,...,T+10$ as my samples?

The justification for the first alternative is that once we have drawn a sample state $s$ at time $T$, then the immediate samples following $s$ will be correlated with $s$ according to the transition matrix of the chain.

On the other hand, maybe it is possible to use some property about Markov chains to show that alternative 2 is enough? For instance, by arguing that the distribution at time T+i is close to uniform with respect to the initial state anyways. This leads to question 3 below...

3) Is there some class of Markov chains for which alternative 2 is enough?


texts: Karp reduction between FACTORING and a variant of it

texts:
Consider the following variant of the FACTORING problem (given N,M decide whether N has a prime factor less than M):

MULTIPLE-FACTORING: Given three integers $1 \leq K \leq M \leq N$ decide if there are at least $K$ prime factors of $N$ less than $M$

FACTORING $\leq_m$ MULTIPLE-FACTORING (just pick $K=1$) and

MULTIPLE-FACTORING $\leq_T$ FACTORING (find all factors of $N$ using FACTORING, and count if their number is $\geq K$)

But is MULTIPLE-FACTORING many one reducible to FACTORING?
(MULTIPLE-FACTORING $\leq_m^?$ FACTORING)


texts:
How can I deal with recursive terminals in CFG when converting it to CNF? For example,

S -> MN

M -> AM | A

N -> BN | B

A -> a

B -> b

How can I reduce terminals M and N?


texts: Solution to the recurrence T(n) = 2T(n − 3)

texts:
We were asked the following question in our exam:

Solve or bound the recurrence T(n) = 2T(n − 3) for n>3 provided T(1) = T(2) = T(3) = 1.

How do I go about solving this type of recurrence?  For a normal recurrence of the form T(n) = 2T(n - 3) + cn, I would have considered cn to be the root and then solved the remainder of the tree.  However, since the constant term is missing here, it means that the work done in each recursive call is 0.  So, what would be the time complexity?  Is my understanding incorrect?

Thanks for you help!

P.S.: This is not this, because this one has the constant term missing.


texts: Variant of the knapsack problem and box stacking

texts:
I'm facing a problem described as follows:

You are given a set of $n$ types of rectangular 3-D boxes, where the i-th box has height $h_i$, width $w_i$, depth $d_i$ and value $v_i$. You want to create a stack of boxes with a height limit $H$ and maximize the sum of the values, but you can only stack a box on top of another box if the dimensions of the 2-D base of the lower box are each larger or equal than those of the 2-D base of the higher box. Of course, you can rotate a box so that any side functions as its base. You are also allowed to use multiple instances of the same type of boxes.

I realized that it is a combination of the knapsack problem and the box stacking problem with small variations. I tried to solve it using the knapsack algorithm adding the box stacking restrictions, but I'm not getting the right results. Does anyone know a similar problem or could indicate me an algorithm? I have to implement it using dynamic programming.


texts: Maintaining data structure with two operations

texts:
I was trying to implement data structure over set of rectangles that can perform two types of operations.

Update operation, add new rectangle with sides parallel to x and y axis and positive coordinates to the set.
Query operation, for some rectangle check if there is some rectangle intersecting with this rectangle.

I don't have big knowledge of data structures so I was thinking if you could give me some hints how to start approach this problem.

Thanks in advance.


texts: Understanding when to count key comparisons

texts:
I understand that for something like Linear search, this would be the key comparison:

 if(itemToFind == a[i])
    return i;

If I put this method into another method, say a Sorting method, do I still count the linear key comparison plus the sorting key comparison? Or do I only care about the sorting key comparison?

Example:

 public class SortAndSearch{

 void QuickSortAndSearch(A, p, r){
      if(p<r)
         q = Partition(A,p,r)

      if(itemToFind == a[i])
    return i;
 }


texts: Quicksort: Probability of an element being compared to fewer than $k$ pivot elements

texts:
Assume we want to use quicksort on some array $s$ with length $n$ consisting of only $n$ distinct elements.
Let $S_{(1)},S_{(2)},\dots,S_{(n)}$ be the sorted order of the elements in $S$.
Furthermore, let $d(i)$ be the number of elements that $S_{(i)}$ is compared to.
Finally, the pivot element is chosen uniformly at random.
How do I then compute the probability that $d(i) < k$ for some $k \in \mathbb{N}$?


texts: Trouble finding average case of a find max algorithm

texts:
I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.
findMax(list):
    maxNum = -oo  # negative infinity
    for k = 0 to len(list)-1:
        if list[k] > maxNum:
            maxNum= list[k]
    return maxNum

The distribution I have considered is uniformly random.

At the back of the textbook I am currently using, the solution is said to be $O(logn)$, however, using the approach that I have came up with (which I'm not quite sure why is incorrect), I got $O(n)$ instead.
In my approach: I have used the following formula $$E[t_n] = \sum^{n}_{t=1}t \cdot Pr(t_n=t)$$
And, I considered how many times maxNum was updated to calculate the expected value. First, I noticed that if the max would have been the first element, maxNum would have only been updated once. If the max was the second element, then it would have been updated twice, and so forth. Using this reasoning, I deduced that the probability of maxNum appearing in the nth position is $\frac{1}{n}$. Then, I got
$$E[t_n] = 1 \cdot Pr(t_n = 1) + 2 \cdot Pr(t_n = 2) + ... + n \cdot Pr(t_n = n)$$
$$=\frac{n+1}{2}$$
$$\Rightarrow O(n)$$.
I am a bit lost and am unsure where my mistake took place exactly.


texts: Show that a circuit of size $s$ can be converted to a DeMorgan circuit computing the same function of size at most $2s$

texts:
I am trying to prove the above statement. A DeMorgan circuit is a circuit that has only $\{ \wedge, \vee, \neg \}$ gates and the negation is applied only to input variables.
So, assuming we have a circuit of size $s$ that computes a function $f: \{0,1\}^n \rightarrow \{0,1\}$. The basis for this circuit is $\{\wedge, \vee, \neg\}$ with fan-in 2 for the OR and AND gates. I am trying to prove we can convert this circuit to a DeMorgan circuit of size at most $2s$.
Intuitively and in small examples this claim makes sense to me but I would like to prove that more formally. I have searched in several papers but this claim is mostly mentioned but not proved. Can someone give me an intuition about the proof?
The above statement was mentioned in the following paper https://eccc.weizmann.ac.il/report/2018/154/ in the second paragraph of the 1st page and continuing on 2nd page.


texts: Reduce Nondeterminism in Pushdown Automata

texts:
I know there might be some situations where we want transitions to be only taken when the stack is empty, and transitions to be taken only when the input stream is empty.

We can create an additional start state, and push a special key like "#" on the stack to start. We can also append the input stream with a "$" so we can use that as a transition symbol.

However, I'm trying to visualize this. I would want to change an existing PDA and make it less nondeterministic. I can't come up with a machine that would show this benefit.


texts:
I have a question about the Euclid's Algorithm for finding greatest common divisors.

gcd(p,q) where p > q and q is a n-bit integer.

I'm trying to follow a time complexity analysis on the algorithm (input is n-bits as above)

gcd(p,q)
    if (p == q)
       return q
    if (p < q)
       gcd(q,p)
    while (q != 0)
       temp = p % q
       p = q
       q = temp
    return p

I already understand that the sum of the two numbers, u + v where u and v stand for initial values of p and q , reduces by a factor of at least 1/2.

Now let m be the number of iterations for this algorithm.
We want to find the smallest integer m such that (1/2)^m(u + v) <= 1

Here is my question.
I get that sum of the two numbers at each iteration is upper-bounded by (1/2)^m(p + q). But I don't really see why the max m is reached when this quantity is <= 1.

The answer is O(n) for n-bits q, but this is where I'm getting stuck.

Please help!!


texts: Error bound for minimum-degree spanning tree

texts: I am reading The Design of Approximation Algorithms (Williamson and Schmoys; page 50 of this PDF) about solving the minimum-degree spanning tree problem of maximum degree 2 in polynomial time. The text states that we are going to find a tree $T$ with maximum degree at most $2\mathrm{OPT} +\lceil\log_{2} n\rceil$ in polynomial-time. $n$ is the number of the vertices in the graph.  Could someone clarify why $\log_{2} n$ is placed there? The text gives no explanation what it is.


texts: How do we pick and switch hash functions from a universal family?

texts:
When we have a universal family of hash functions, it gives us a few useful mathematical guarantees. But, if we pick a specific function from the family and use it all the time it's effectively like the family doesn't exists and we only have this one function.
Therefore, the only logical thing seems to be switching a hash function every once in a while (picking a new function from our family). If indeed this is what we should do, how often should we switch functions? How should this time period be selected and is there an optimal time period for different tasks?
Also, suppose we have two hash functions $h_1, h_2$, and then store values in an array according to $h_1$. After a while, we switch our has function to be $h_2$. Do we have to re-hash all of our values according to $h_2$? This seems rather wasteful


texts: Find the sum of numbers from an array closest to a number, where repetition of the numbers are allowed

texts:
I would like to find the sum of values from a given number array, where the repetition of numbers are allowed, closest to a target but the sum cannot exceed the target. If there are more solution, I'd prefer the one with the minimum element count.

Examples:

1)

Given values: [500, 1000, 2000, 5000]

Target: 7000

Result: [2000,5000]

2)

Given values: [500, 1000, 2000, 5000]

Target: 7990

Result: [500, 2000, 5000]

3)

Given values: [222,333]

Target: 444

Result: [222,222]

4)

Given values: [222,333]

Target: 777

Result: [222,222,333]

Later on I would like to implement this algorithm in JavaScript, and make it run in a browser. I have tried:

-Knapsack algorithm

-Generating all combination of the numbers and find one with the minimum difference

but both are very slow when implemented, and used with big numbers.


texts: Importance of Frequency vs CAS Latency in memory performance

texts:
I was looking at the Wikipedia page for CAS Latency: https://en.wikipedia.org/wiki/CAS_latency

And I noticed the obvious trend - at higher frequency, despite CAS latency degrading (growing), the delay to get the 1st, 4th and 8th word overall improved regardless.

I've heard in the past that frequency/CAS was perhaps the best metric for memory performance as a consumer, but this chart seems to disagree:

So my main question(s) are:

Is getting the 1st, 4th and 8th word an accurate representation of real-world performance of memory? If not, why not, and what would be?
If there some other factor to memory performance that would be a third "hidden variable" that I'm not accounting for, that's not constant between all these? The IMC's performance at high frequency? The motherboard's? Signal noise?

Thanks for any thoughts!


texts: How do we determine whether a heuristic is better than another in A* search Algorithm?

texts:
I am trying to solve a Maze puzzle using the A* algorithm. I am trying to analyze the algorithm based on different applicable heuristics.

Currently, I explored Manhattan and Euclidean distances. Which other heuristics are available? How do we compare them? How do we know whether a heuristic is better than another?


texts: How does storing encrypted password provide secure authentication?

texts:
It's universally accepted that storing an unencrypted password for automated authentication is a very bad idea, for the saved password can be used by malware, etc.

There is a number of systems that store encrypted passwords for the purpose of automated authentication elsewhere. For example, one can configure git to automate authentication during git push. My question is: how do such system manage to authenticate securely?

Specifically, here are two possibilities:

1) The local system stores the encrypted password, and when needed, sends it to the remote system. The remote system accept the encrypted password for authentication.

However, in this case the encrypted password leads to exactly the same vulnerability as unencrypted password: malware can use the unencrypted password to authenticate itself. For example, if your password was "brown fox" and it was stored as a hash 14921776, and the remote system would accept 14921776 as a valid authentication certificate, then malware can just look up 14921776 in the encrypted password file in the local system and use it as is.

2) Suppose now that the remote system does not accept the encrypted password for authentication. In the above example "brown fox" needs to be communicated between local and remote system; the hash 14921776 won't do.

How does the local system would provide automated authentication in that case? All the local system knows that the hash of the password is 14921776, but it cannot unhash it into "brown fox", and therefore cannot send the valid password to the remote.


texts: Finding the longest common subsequence algorithm using hash table Slow

texts:
I've designed an algorithm to find the longest common subsequence. these are steps:

Starts with i = 0

Picks the first letter from the first string start from ith letter.
Go to the second string looking for that picked letter.
If not found return to the first string and picks the next letter and repeat 1 to 3 until it finds a letter that is in the second string.
Now that found a common letter in the second string, adds that to $common_subsequence.
Store its position in $index.
Picks next letter from the first string and do step 2 but this time starts from $index.
Repeat 3 to 6 until reached end of string 1 or string 2.
If length $common_subsequence is greater than length of common subsequence so far add that  change lcs to the $common_subsequence.
Add 1 to the i and repeat 1 to 9 while i is less that length of the first string.

This is an example:

X=A, B, C, B, D, A, B
Y=B, D, C, A, B, A

First pick A.
Look for A in Y.
Now that found A add that to the $common_subsequence.
Then pick B from X.
Look for B in Y but this time start searching from A.
Now pick C. It isn't there in string 2, so pick the next letter in X that is B.
...
...
...

The complexity of this algorithm is theta(n*m).

I implemented it on the two methods. The second one uses a hash table, but after implementing I found that it's much slower compared to the first algorithm. I cant undrestand why.

Here is my implementation:

First algorithm:

import time
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if string is empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        start = 0 # start position in ystr
        for item in xstr[i:]:
            index = ystr.find(item, start) # position at the common letter
            if index != -1: # if common letter has found
                cs += item # add common letter to the cs
                start = index + 1
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed

Second one using hash table:

import time
from collections import defaultdict
def lcs(xstr, ystr):
    if not (xstr and ystr): return # if strings are empty
    lcs = [''] #  longest common subsequence
    lcslen = 0 # length of longest common subsequence so far
    location = defaultdict(list) # keeps track of items in the ystr
    i = 0
    for k in ystr:
        location[k].append(i)
        i += 1
    for i in xrange(len(xstr)):
        cs = '' # common subsequence
        index = -1
        reached_index = defaultdict(int)
        for item in xstr[i:]:
            for new_index in location[item][reached_index[item]:]:
                reached_index[item] += 1
                if index < new_index:
                    cs += item # add item to the cs
                    index = new_index
                    break
            if index == len(ystr) - 1: break # if reached end of the ystr
        # update lcs and lcslen if found better cs
        if len(cs) > lcslen: lcs, lcslen = [cs], len(cs)
        elif len(cs) == lcslen: lcs.append(cs)
    return lcs

file1 = open('/home/saji/file1')
file2 = open('/home/saji/file2')
xstr = file1.read()
ystr = file2.read()

start = time.time()
lcss = lcs(xstr, ystr)
elapsed = (time.time() - start)
print elapsed


texts: Generate all combinations of values that are less than array's elements and have a sum = target

texts:
I want to find a way to generate sets that contain elements that sum to a certain target. Initially, I have an array that contains elements representing the maximum value that can be stored in that index.

For example, the input is [8,6,1] and the target is 10. The algorithm should produce all sets that have elements [ (<=8), (<=6), (<=1) ] such that their sum is equal to 10. Examples include: [8,1,1], [8,2,0], [7,3,0], ...

A major consideration for this algorithm is that it should work on any input length (the above example has a length of 3).

I think the solution is close to the subset sum problem, but I wasn't able to figure it out. Any help is appreciated.

Side note: python code is preferred, but Pseudo-code should be fine.

Thanks


texts:
Operating System - CPU scheduling Decisions

The question above talks about why CPU scheduling does not take place when ready to running.
But I wonder why CPU scheduling does not take place when new to ready. I think it is similar to the process of waiting to ready. They both add processes to ready without changing processes that are running.


texts: Analysis of time complexity of travelling salesman problem

texts:
Recursive definition for travelling salesman problem can be written like this :-

T(i,S)=min((i,j)+T(j,S-{j})) for all j belonging to S, when S is not equal to NULL

T(i,S)=(i,S) when S is equal to NULL

Here, T(i,S) denotes the tour starting from i covering all vertices in Subset S and then travel back to i.

I built the recursive tree and calculated the subproblems at each level. For k elements, number of subproblems comes out to be :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+(n-1)(n-2)(n-3)......(n-k).

For k=4, number of subproblems at level 1,2 and 3 are 3,6 and 6 respectively.

I tried to solve it but couldn't find the actual solution but it can be seen clearly that the time complexity is factorial. Now, in the recursion tree there are repeated function calls at the last level which we use to improve our time complexity using dynamic programming. Now, half of the function calls at last level are repeated that would reduce the number of subproblems to :-

(n-1)+(n-1)(n-2)+(n-1)(n-2)(n-3)+.......+((n-1)(n-2)(n-3)......(n-k))/2.

But, I think the time complexity is still factorial. I read on various resources that time complexity of travelling salesman problem using dynamic programming is $O(n^2*2^n)$ which is exponential.

Is there something wrong in my analysis? Can anyone prove how the time complexity comes out to be $O(n^2*2^n)$ ?


texts: Union-Find with link-by-rank to represent a binary field with simple operations

texts:
I have a field $X$ of given length $n$ which is filled with zeroes in the beginning.

I only need these 3 simple operations:

GET_VALUE$(i)$: returns the value of $i$-th cell ($X[i]$)

SET_TO_1$(i)$:basically $X[i] \leftarrow 1$ for $i < n - 1$, otherwise nothing (the last cell of $X$ is always zero ($X[n-1] = 0$))

FIND$(i)$: find the least index $j \geq i$ s.t. $X[j] = 0$ (note that this operation will always succeed since the last cell is always zero)

I need the time complexity of operation GET_VALUE to be constant.
And both SET_TO_1 and FIND to be in $O(\log n)$.

My thinking so far:

I am almost sure the perfect data structure for this would be Union-Find, because sets elegantly represent all such $i$ that for which FIND returns the same value. The root of the sets would be the index that is returned by the FIND operation - the only index $i$ in the set s.t. $X[i] = 0$.

The implementation of GET_VALUE operation would be also pretty straightforward. If $i$ is a root (points to itself) return $0$ and $1$ otherwise.

However this doesn't work nicely for the SET_TO_1 operation. I would want it in case it sets a cell $X[i]$ from $0$ to $1$ to join the set represented by the root $i$ to the next one (which contains the element of index $i+1$). But if I want GET_VALUE to be in $O(\log n)$ I need to use link by rank and thus I cannot choose which root of the two unified trees is preserved - but in order for this to work it must be the second one (from the $i+1$ set).

How can I fix this?


texts: Is Acceptance by Empty stack and Final state possible in the same PDA?

texts:
$L$ is the language accepted by the above PDA :
$L = \{a^n\mid n\geq 0\}\cup\{a^n b^n\mid n\geq 0\}$ and is deterministic context-free is the language accepted by the PDA how can we accept $a^n$? As it doesn't contain an epsilon transition at the end right ? Is acceptance by both the final state and empty stack possible in the same PDA?


texts:
Let's use Traveling Salesman as the example, unless you think there's a simpler, more understable example.

My understanding of P=NP question is that, given the optimal solution of a difficult problem, it's easy to check the answer, but very difficult to find the solution.

With the Traveling Salesman, given the shortest route, it's just as hard to determine it's the shortest route, because you have to calculate every route to ensure that solution is optimal.

That doesn't make sense. So what am I missing? I imagine lots of other people encounter a similar error in their understanding as they learn about this.


texts: Find long connected similar subsequences in two given sequences

texts:
I'm looking for pointers to algorithms which will find long connected similar subsequences which two given sequences have in common. For example, in case of two strings:

abcaabbaabUVWXYZ
UVWXeYZababababab

I'm interested in:

**********UVWXYZ
UVWXYeZ**********

Not in:

ab*aabba*b*****
******aba*ab*bab

(which would be one possible longest common subsequence for the given strings).

For the example above, e represents a (small) difference in the otherwise identical strings UVWXYZ and UVWXeYZ. This is where the similarity comes in. e is not necessarily an addition of a single character. It may be a change as well. When thinking on longer strings, multiple characters (even in direct succession) may be different.

The algorithm should probably be driven by a rating function for the length and the similarity of subsequences.

I'm aware that this problem is rather vague, so any pointers to possibly related problem domains and corresponding algorithms are appreciated as well.

Update:
Removed exclusion criterion "LCS", because it actually seems to be what I'm looking for.


texts: How to prove the correctness of the binary tree inversion algorithm?

texts:
Define the inversion of a binary tree as the tree whose left sub-tree is a mirror reflection of the original tree's right sub-tree around the center and right sub-tree a mirror reflection of the original tree's left sub-tree.
Examples:

   Inversion 1           Inversion 2

   C    |    C           C    |    C
  / \   |   / \           \   |   /
 A   B  |  B   A           B  |  B
                          /   |   \
                         A    |    A

Consider the following binary tree inversion algorithm (source: LeetCode):
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public TreeNode invertTree(TreeNode root) {
    if (root == null) return null;
    TreeNode tmp = root.left;
    root.left = invertTree(root.right);
    root.right = invertTree(tmp);
    return root;
}

I sought to prove it inductively on the depth of tree but am stuck at the inductive step. How can I show that the mirror reflection of the left subtree (or right) around the center of the root tree is a combination of moving the subtree from root.right to root.left and inverting the subtree around the center of the subtree itself?


texts: What kinds of programming pitfalls modern languages are able to find?

texts:
I often see claims that modern functional strictly-typed languages are 'safer' than others. These statement mostly linked with type systems and their ability to explicitly express the following pitfalls:

Alternatives in function result. Maybe and Either datatypes vs. exceptions and null-pointers in C++-like languages.
Access to mutable state (possibly inconsistent behavior over time). State datatype in Haskell vs. variables in C++-like languages.
Performing IO. IO datatype in Haskell vs. just doing things in C++-like languages.

Haskell allows to express constraints required for safe handling of these situations. And compiler is able to warn programmer when he doesn't follow them.
Although pitfalls above are definitely the most common ones I can think of much more, for example:

Unexpected resource consumption. Memory, CPU, disk, bandwidth.
Inconsistent access to shared resources. Like read and write interference, broken lock ordering.
System-level failure. Like crashing process or pulled plugs.
Unexpected execution time for IO, timing violation.

Is there languages, libraries or at least models which allow to express constraints from the second set and yield a warning when they are not met?


texts: Computing the error bound of floating-point expression

texts:
How should I compute the maximum absolute and relative error of the following IEEE-754 floating-point expression?

a.y + (x - a.x) * ((b.y - a.y) / (b.x - a.x))

Also, we assume, that

the optimizer leaves the expression in the specified form
the default rounding mode (round to nearest even)


texts: How are these two definitions of the Third Normal Form (3NF) equivalent?

texts:
According to the textbook by Silberschatz,

A relation schema R is in third normal form with respect to a set $F$ of functional dependencies if, for all functional dependencies in $F^+$ of the form $\alpha$ → $\beta$, where $\alpha$ ⊆ R and $\beta$ ⊆ R, at least one of the following holds:

  $\bullet$ $\alpha$ → $\beta$ is a trivial functional dependency.

  $\bullet$ $\alpha$ is a superkey for R.

  $\bullet$ Each attribute A in $\beta - \alpha$ is contained in a candidate key for R.

Another definition from an online video lecture series by a reputed college that I am following states,

A relation is in third normal form if:

  $\bullet$ It is in second normal form,

  i.e., every non-prime attribute of R is fully functionally dependent on each candidate key of R

  (or in other words, no non-prime attribute of R is dependent on any proper subset of any candidate key of R).

  AND

  $\bullet$ No non-prime attribute of R is functionally dependent on any other non-prime attribute of R.

I understand both these definitions. The Silberschatz definition is the second definition on the wiki page and the one from the video is (I'm guessing) the first definition on the same page.

I'm having a hard time understanding how they are equivalent. I can't understand how they seem so distinct from each other, and yet, at their core, are saying the same thing.

Can someone explain why saying one thing is the same as saying the other?


texts: How does O transform this sum like that?

texts:
I'm in the process of self-studying the CLRS book. My mathematical background is poor so I'm trying to learn the maths as I go along too.

I don't understand the math in CLRS section 6.4 where they go from:

$$ \sum_{h=0}^{\lg n} \frac{n}{2^{h+1}} O(h) $$

to:

$$ O\left(n \sum_{h=0}^{\lg n} \frac{h}{2^h}\right). $$

I understand that the $n$ is moved out to before the sum. But how does the remaining $1/2^{h+1}$ become $h/2^h$?


texts: Why must uncommitted transactions be undone in backwards order?

texts:
I have a database log where some transactions win (they are committed before crash) and some lose (not committed yet). We learned in class that the losers' actions have to be undone backwards.

Is there any reason for doing this backwards? Can anyone give a simple example of a log where forward undos would give wrong results?


texts:
I'm wondering if PDAs with more than one initial states are also accepting context free languages.

If found that question on this site about NFAs and would like to know if this answer is also valid for PDAs if one defines a new single initial state and connects this with the former initial states using  $\epsilon : \epsilon \to \epsilon$ transitions?


texts: Batch processing in increase-key function using binary heap

texts: Is there an algorithm to perform batch processing in the increase-key operation? Let us say, a binary heap (min-heap) is used. In the normal increase-key function, if we perform increase key on one node, then we have to traverse paths from the node towards the children to re balance the heap. If we want to increase the keys of five nodes in the heap, we need to call the increase-key function five times. Is it possible to call only one increase-key function and perform increase-key on five nodes simultaneously?


texts: Why do we have to make variables unique when evaluating $\lambda$-calculus?

texts:
I'm studying $\lambda$-calculus and came across a problem that I'm not sure how to understand. More specifically, it's about evaluating $\lambda$-calculus expressions using $\beta$-reduction.
I was taught that the basic steps for performing $\beta$-reduction are to

Find reducible expressions in the form of ($\lambda x.$$e_1$) $e_2$.

Rewrite the expression by substituting every free occurrence of $x$ in $e_1$ with $e_2$.

I've solved some exercise problems which seemed fairly simple to understand, but came across one that I couldn't understand the answer.
The expression in question is ($\lambda x.$($\lambda y.x$)) $y$, and after following the rules above I ended up with the result of $\lambda y.y$ after replacing the free occurrence of $x$ with $y$ in $\lambda y.x$. However, the correct answer seems to be $\lambda y.x$.
The rationale that I've been able to find is that before applying $\beta$-reduction, we have to change variables to be "unique."
Could someone explain the reasoning behind this for me please?


texts: Is Constant Folding a type of Memoization?

texts:
I was reading about Constant Folding and it sounds very similar to Memoization so I suspect that it indeed is a type of memoization but I've done some searching and can't find a solid answer (in academic papers, etc.) on that.

Is Constant Folding a type of memoization?


texts: What is the exact relation between programming languages and Turing machines?

texts:
I don't know much about yacc, bison, flex or lex and please correct me if I'm wrong but a programming language is also a Turing machine and a Turing machine is defined as the tuple $(Q, \Gamma, b, \Sigma, \delta, q_0, F)$ where $Q$, $\Gamma$, $b \in \Gamma$, $\Sigma \subseteq \Gamma \smallsetminus \{ b \}$ as input, $\delta: Q \times \Gamma \rightarrow Q \times \Gamma \times \{ L, R, N \}$ as transition function where $L$ = number of steps to the left, $R$ = number of steps to the right, $N$ = "standby", $q_0 \in Q$ is the initial state and $F \subseteq Q$ is the set of end states.

How similar is implementing a programming language to implementing a Turing machine? Can it be said that what is done when a programming language is implemented is that a Turing machine like the above is defined? If yes, how come we can't just use a model that looks like the definition of a Turing machine when a programming language is defined? Instead something else like BNF seems to be the standard.


texts: Handwritten character recognition as characters are being traced

texts: I'm looking for an OCR technique (PCA or SVM or anything else) in a peculiar setting. I want to detect the motion of the finger so that if someone writes something in front of the camera in the air, I want to recognize the characters online (meaning as soon as they are written).


texts:
Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it?

  Problem ("Maximum Stacking Height Problem")

  Given $n$ polygons, find their stable, non-overlapping arrangement
  that maximizes their stacking height on a fixed floor under the
  influence of gravity.

Example

Three polygons:

and three of their infinitely many stable, non-overlapping arrangements, with different stacking heights:

Clarifications

All polygons have uniform mass and equal density
Friction is zero
Gravity is acting on every point into the downwards direction (i.e. the force vectors are all parallel)
A configuration is not considered stable if it rests on an unstable equilibrium point (for example, the green triangle in the pictures can not balance on any of its vertices, even if the mass to the left and the right of the balance point is equal)
To further clarify the above point: A polygon is considered unstable ("toppling") unless it rests on at least one point strictly to the left and at least one point strictly to the right of its center of gravity (this definition greatly simplifies simulation and in particular makes position integration etc. unnecessary for the purpose of evaluating whether or not an arrangement is stable.
The problem in its "physical" form is a continuous problem that can only be solved approximately for most cases. To obtain a discrete problem that can be tackled algorithmically, constrain both the polygon vertices and their placement in the arrangement to suitable lattices.

Notes

Brute force approaches of any kind are clearly infeasible. Even with strict constraints on the placement of polygons inside the lattice (such as providing a limited region "lattice space") the complexity simply explodes for more than a few polygons.
Iterative algorithms must bring some very clever heuristics since it is easy to construct arrangements where removing any single polygon results in the configuration becoming unstable and such arrangements are unreachable by algorithms relying on every intermediate step being stable.
Since the problem smells at least NP- but more likely EXPTIME-complete in the total number of vertices, even heuristics would be of considerable interest. One thing that gives hope is the fact that most humans will recognize that the third arrangement in the example is optimal.


texts: Is global non-convex optimization NP-complete?

texts:
Assume I have some non-convex function $f(x_1, x_2, ...)$ and I want to optimize it to find a global minimum. I feel like it is easy to show that this problem is in the class NP with the decision problem

Is there a set of points such that f < C?

Where C is some constant. However, I am not sure if these problems are in the class of NP-Complete, and if so, what would you say the size of the input is? Complexity of the function?

Thanks!


texts: "Term Rewriting and All That" - Exercise 3.10

texts:
I am studying Term Rewriting by reading Baader/Nipkow's book "Term Rewriting and All That". I am in chapter 3 - Universal Algebra, in the section 3.2 - Algebras, homomorphism and congruences. I am trying to do exercise 3.10:

Let $\mathcal{Z}$ be the additive group of integers.
(a) - Determine all subalgebras of $\mathcal{Z}$ and all congruences on $\mathcal{Z}$.
(b) - Characterize those subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$.
(c) - Given the integers $a, b, c \in \mathbb{Z}$, we define the mapping $h_{}: \mathbb{Z} \rightarrow \mathbb{Z}$ by: $$h_{(a, b, c)}(z) := az^2 + bz + c.$$
For what triples (a, b, c) is $h_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$?
(d) - Given the integers $a, b$, we define the mapping $g_{(a, b)}: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$ by $$ g_{(a, b)}(z_1, z_2) := a z_1 + b z_2 .$$
Show that $g_{(a, b)}$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$. For what tuples $(a, b)$ is $g_{(a, b)}$ onto?

I think I was able to do items (a), (b) and (c), but I am having problems with item (d).
For item (a):

The subalgebras of $\mathcal{Z}$ are all of the form $\mathcal{nZ}$ where the carrier is $\mathbb{nZ} \ := \ \{ n z \ |\ z \in \mathbb{Z} \}$. This subalgebra is generated by $\{ n \}$.
The congruences on $\mathcal{Z}$ are all of the form $\equiv_{n} := \ \{(z_1, z_2) \ | \ n \text{ is a divisor of } z_1 - z_2 \}$.

For item (b):

A subset of cardinality 2 $\{ z_1, z_2 \}$ generates $\mathbb{Z}$ if and only if it generates {1}. This happens if and only if $gcd(z_1, z_2) = 1$. So, the subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$ are of the form $\{z_1, z_2 \ | \ gcd(z_1, z_2) = 1 \}$.

For item (c):

It suffices to guarantee that $h(z_1) + h(z_2) = h(z_1 + z_2)$ for all $z_1, z_2$. Notice that:
$h(z_1) + h(z_2) = a (z_{1}^{2} + z_{2}^2) + b (z_1 + z_2) + c $
$h(z_1 + z_2) = a (z_{1} + z_{2})^2 + b (z_1 + z_2) + c$
Since this equality must hold for all $z_1, z_2$, we must have $a (z_{1}^{2} + z_{2}^2) = a (z_{1} + z_{2})^2$ for all $z_1, z_2$. This is only possible if $a = 0$. There are no restrictions on $b$ and $c$. So, the triples $\{(0, b, c) \}$ make $h_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$.

For item (d), I was able to prove that $g(a, b)$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$:

Taking arbitraries $z = (z_1, z_2)$ and $z' = (z'_1, z'_2)$ in $\mathcal{Z} \times \mathcal{Z}$ we have:
$$g(z) + g(z') = (a z_1 + b z_2) + (a z'_1 + b z'_2) = a (z_1 + z'_1) + b (z_2 + z'_2) = g(z + z')$$

But I couldn't prove for what tuples $(a, b)$ we have that $g_{(a, b)}$ onto.
Can anyone help me with this part of item (d)?
Also, are my proofs of items (a), (b) and (c) correct? Thanks in advance.


texts: Let's assume that we have to generate huge number of 256-bit symmetric keys. How to do it and how to be sure that it is safe. Perhaps it requires a strong mathematical backend. Don't hesitate to reference me somewhere.


texts: Algorithm to change article reading level

texts: I was wondering, are there any famous algorithms in NLP or NLG that can take some text (say a news article online) and transform it to a lower reading level?


texts: Correct nomenclature: Hamilton path, Hamilton's path or Hamiltonian path?

texts:
What is the correct way?
Hamilton path, Hamilton's path or Hamiltonian path?
To be clear, I am referring to the correct way to name a graph such that there exists a single path (without repeated vertices) through all the vertices.

In Wikipedia it says "Hamiltonian path", whereas in an article I found "Hamilton path".


texts: A road-map for mathematics needed in CS?

texts:
Before asking my question, I have to give some background about myself. I live in Iraq and this made my education a total disaster. My middle/high school math skills are not that great and I never realized that until I got into college. I found out pretty late that great colleges cover a lot of maths materials in their curriculum. And now I'm a junior majoring in CS and still I don't feel really confident about my skills. I wish to continue studying CS and maybe acquire a masters degree. I searched about the maths needed for an undergraduate, and it seems that I need to focus on three important subjects:

Calculus
Discrete Maths
Linear Algebra

Do you have any books recommendation or a road map to follow to achieve a good level of understating for the subjects mentioned above?

P.S: I don't care how long or complicated the materials or books are, I have all the time in the world and I can dedicate 5 hours daily(10 in the summer).


texts: Are all MST minimum spanning trees reachable by Kruskal and Prim?

texts:
I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for Prim's algorithm?

EDIT: To be more precise, I want to know if given an MST for a connected, undirected, weighted graph, is it guaranteed that there is a sequence of steps using Kruskal or Prim which generates this MST. E.g. There are different choices for Kruskal when there are multiple edges with the same weight. Similarly for Prim.


texts: Without fancy math, how does the MC-AIXI algorithm work?

texts:
How does the MC-AIXI algorithm work? I tried to read the paper, but I got lost in the math. I understand the concept of AIXI very well, but I don't get two things:

1) Where does MC-AIXI get its models from?? Kolmogorov complexity is non-computable! Why can MC-AIXI get models?

2) How exactly does the decision tree work? I kinda get the concept, but how does it know what it will do in the future without doing another calculation, and so on ad infinitum?

I would like enough information do make my own version of it. Thank you so much for your help!


texts: If $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ is $L_1=L_2$

texts:
If the same $f$ reduces $L_1$ to $L$ and also $L_2$ to $L$ does it imply that $L_1=L_2$?
My intuition says no, but I couldn't find a counterexample.


texts:
I have the following grammar:

S -> Xb | Y

Y -> X | a

X -> S | c

Here the lowercase letters are terminals.

I have an algorithm to find the cycle in this grammar. It is S->Y->X->S and in fact there is a smaller cycle buried in there, namely S->X->S.

I've tried to devise an algorithm to remove these cycles, without too much thought, but I've come up with nothing.

Any help would be appreciated.


texts:
I have to implement a compiler for a given language as part of an assignment.
The language is kept simple enough such that it can be fully expressed through REs.
My question lies with two of the REs provided:

DIGIT := [0-9]?
INTEGER_LITERAL := DIGIT DIGIT*

When I saw the RE for INTEGER_LITERAL I sort of thought to myself:

"Well that's just DIGIT+"

Am I right to think so?


texts:
prove that in binary heap buildheap function does at most 2N-2 comparison
I don't know how should I prove it I need some hint thanks.
buildheap procedure: we have n element and we build a heap at first and then we start from the first node which is not leaf(floor of n/2) and for each step we have 2 comparison(each node should be compared with min of children and to find min also there is 1 comparison)
so we compare this node and we go back until we get to root(and all of these steps are recursive and keeps continuing till we reach the node or right place of node)
buildheap():
    for i ← size / 2 till i > 0
        Max-Heapify(i)
        i ← i-1

Max-Heapify(A, i):
    left ← 2×i
    right ← 2×i + 1
    largest ← i

    if left ≤ length(A) and A[left] > A[largest] then:
        largest ← left

    if right ≤ length(A) and A[right] > A[largest] then:
        largest ← right

    if largest ≠ i then:
        swap A[i] and A[largest]
        Max-Heapify(A, largest)

I wrote number of comparisons:
node          comparison
 1                 0
 2                 1
 3                 2
 4                 3
 5                 6
 6                 7
 7                 8
 8                 11
 9                 14

I think the worst case is when we have new level with one node(3,5,9,.. node because it has 2 less than the most we have)
but I have another idea:
we have n/2 node which don't move down
n/4 moves one level down
n/8 moves 3 level down
and each moving from level to level needs 2 comparison
so we have
$\frac{n}{2} \times 0 + \frac{n}{4} \times 1 + \frac{n}{8} \times 2 + .... = n \times (\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$
sum of $(\frac{1}{4} + \frac{2}{8} + \frac{3}{{16}} + \frac{4}{{32}} + ...)$ is $1$ and it will be multiplied by 2(because of 2 comparison for each move) but we have 2n here not 2n-2
did I make a mistake or the idea is wrong?


texts: The Communication Complexity of Majority, What does Bob send to Alice? Can Bob just wait for Alice's input?

texts:
I'm following along the examples in https://people.csail.mit.edu/rrw/6.045-2020/note-cc.pdf
and in specifically the following text:

What’s a good protocol for computing MAJORITY? The natural thing to do
is to have Alice and Bob send the vote counts! Over multiple rounds,
when it’s Alice’s turn, she sends bits of the integer $N_x$ which is the
number of 1s in $x$, Bob computes $N_y$
which is the number of 1s in $y$, and Bob sends 1 to Alice if and only if $N_x+N_y$ is greater
than $n$. (Note the total number of voters is $2n$.) If Alice sends $N_x$
encoded in binary, this takes $O(\log n)$ rounds. We therefore have:

If Alice is sending her total number of 1s over $\approx \log n$ bits to Bob ... what is Bob sending in back in return before the Alice is done with her input? I assumed or thought that in communication complexity, Alice and Bob are always taking turns back and forth right? Can Bob not send anything and just wait for Alice to send the $\log n$ bits?


texts: Is the ambiguity of a regular tree grammar decidable?

texts:
Is there an algorithm which decides whether a regular tree grammar $G$ is ambiguous, i.e. there exists a tree $t\in L(G)$ which can be parsed by the grammar in more than one ways, using only leftmost derivations?

Is there a proof available about the decidability, or a cite to a paper which proposes such an algorithm?


texts: How to evaluate recommendation engine without ground truth?

texts:
I have developed an algorithm which recommends geographical locations to users based on popular trends and their own interests. The dataset is created by my organization. So the user selects a few categories and based on his interest and rating by other people he is presented with recommended places for him.

How do you evaluate or use metrics for such system given that ground truth doesn't makes sense in this case ?

EDIT:
I meant that how to evaluate the accuracy or quality of results in such case especially for published work.

EDIT 2 (as per the request for details in the comments)

Details of the system

The user indicates his preferences from a predefined set of tags (cultural, mountains etc)
Users can also rate different places on a scale of 1-5.
Users profile (geographical location, places already visited etc are already stored in his profile)
Based on user's choice and other heuristics(rating etc), a set of places is recommended by the system.


texts: How hexadecimal representation is more compact and intelligible for documentation?

texts:
My textbook says,
                    "Instead, it is far better to use a hexadecimal representation for documentation purposes. Whether or not a code represents a binary number, it can be treated as such and converted to the corresponding hexadecimal number. This makes the representation more compact and, as a result, more intelligible."
                 would any body explain it to me plz? Thanks!


texts:
I'm trying to simulate a boardgame what can be played on a board with an arbitrary lattice, anything from triangles to heptagons to 37-sided regular polygons is allowed. Moreover the shape of the board is also arbitrary.

I need to represent this board in a data structure in which each tile has as its property a list of all its neighbouring tiles.

I was wondering if there is already some work done related to this that I might find helpful?

The way I'm trying to approach this problem is as follows: I first devise a coordinate system. Then I situate the virtual board within the coordinate system. Then I lay down the first tile and recursively lay down all neighbouring tiles until I cross the border. The approach is quite ugly and there is some uncertainty involved as I'm using angles and such to figure out the coordinates of each tile and it's all very messy. There must surely be a better way.


texts: Why the alphabet of the digital information is composed of 2 elements?

texts:
please don't offer an answer about "it's an electronic thing" or something like that, just keep reading.

I don't understand why we use a dictionary, a lexicon, with just 2 elements to express the entire digital world.

My point is about the fact that information is entropy, things that are predictable or just don't vary over time don't carry any information, so if you want information you want entropy, and if you want entropy why you stick with just 2 elements for your alphabet ? It's like the minimum before making the thing completely "flat" and meaningless like an array full of 0 or Z, an array of 0 and 1 it's just the next step after that .

But the main reason why I don't accept the answers with "electronics in them" is that this kind of studies were based on math and theoretical stuff, Boole wasn't even a regular student, He was a self taught mathematician, and chances are that he was trying to solve or study a practical problem without even caring about electronic devices given the times he was in .

If you also consider the information as a bingo where you can call numbers from 1 to 100, and you can call 1 number for each session, you have 1% of probability to call any number in the range, and this probability doesn't change between sessions . But this doesn't grant you any entropy, it's just probability .

For example if you consider a single char a number in the Bingo and the fact that every char is contributing to a word with its positional value, the fact that the hello word is composed over time by

h
he
hel
hell
hello

with each char having the same probability this consideration, on its own, doesn't give you any entropy.

Things change when you introduce a dictionary of a given language and you associate it with the pool of chars you are fishing from. If you have that dictionary the word hello becomes predictable, and thus with less entropy and more order, by the time you write hel or h or he depending on the context and semantics .

So I guess the answer is that we use binary because no one speaks binary and there is no dictionary of words in binary and the binary is not sensitive to the context and thus retains more entropy ? Because the context plays a big role in lowering the entropy and let things appear more ordered then what they really are, and entropy can be also taught as just something "random" with less order because you don't know what to expect because there is no semantic. And I don't think that the positional value can be considered as a giveaway for semantic, you have the same probability of picking either 0 or 1 in your next cell of information, positional value doesn't change anything.

I'm probably terribly confused and confusing, but why we use binary ?


texts:
$F(z_1,...,z_n)$ is a Boolean expression. The assignment of variable ($x_1,...,x_n \in {0, 1}$) is the answer of $F$, if $F$ for that assignment equals to $1$.
If that case is true and the conditions are met, then both of them are considered to be NP-Hard.

A) The number of answers of $F$ in $DNF$ format.
B) The number of answers of $F$ in $CNF$ format.

DNF and CNF are HERE

Can anyone describe to me in clear, simple, and concise words why both of them are true?


texts: How to deal with parallel edges between two vertices in cycle detection using BFS in an undirected graph?

texts:
I am new to Programming and learning Algorithms and was studying BFS when I read that BFS could be used for cycle detection. I tried to implement the same on an undirected graph G with Adjacency List Representation.
What I did is as follows:

• Do a simple BFS Traversal using a Queue while maintaining the parent node of nodes enqueued in the queue.
• If I come across a node u that has a neighbor v such that v is already visited but v is not the parent of u then that means there is cycle in the graph.

Pseudocode:
#adjList is the adjacency list given as a dictionary
#myQueue is a double-sided queue containing node and its parent node ([Node, parNode])
#visited is a set containing visited nodes

while(myQueue):
    currNode, parNode = myQueue.pop() #dequeue operation
    visited.add(currNode) #Marking currNode as visited
    for childNode in adjList[currNode]: #Traversing through all children of currNode
        if currNode not in visited:
            myQueue.appendleft([childNode, currNode]) #Enqueue operation
        else:
            if childNode!=parNode: #Main logic for cycle detection
                print('CYCLE DETECTED')
                break

The above approach is working except in cases when I have more than 1 edge between 2 vertices for e.g. in following case we have 2 edges between vertices 0 and 1:

Adjacency list of above graph is: adjList = {0:[1, 1, 2], 1:[0, 0], 2:[0]}. Here we can clearly see that the graph contains a cycle (In the adjacency list, it is represented by the fact that 1 appears twice in the adjacency list of 0 and 0 appears twice in the adjacency list of 1) but above algorithm is not able to detect the same because when BFS will reach vertex 1, vertex 0 is already visited but vertex 0 is also the parent of vertex 1 so this cycle will go undetected.
My question is how I can modify above algorithm to detect such cases?
Edit: I tried the same logic on directed graphs also, and I am facing similar problem i.e. case when I have a directed edge from vertex 0 to vertex 1 and another directed edge from vertex 1 to vertex 0


texts: Show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem on $n$ points?

texts:
The question is to show that there are $(n-1)!/2$ distinct tours for a Euclidean traveling salesman problem (ETSP) on $n$ points.

My attempt was using induction. So I start by:

If $n=3$, then we have a triangle and there is only one tour.
Assume that there are $(n-1)!/2$ distinct tours for a ETSP on $n$ points. Prove that there are $n!/2$ distinct tours for a ETSP on $n+1$ points?

Here I proceed like this:

for each tour $t$ from the $(n-1)!/2$ distinct tours do: add one point $n+1$.
for each edge $e=\{v_i, v_j\}$ in $t$ do: remove $e$ and create two edges $e_1=\{n+1,v_i\}$ and $e_2=\{n+1, v_j\}$. We have a new tour and in total we can create $n$ distinct tours.

Since there are $(n-1)!/2$ distinct tours, we will have $n(n-1)!/2=n!/2$ distinct tours.

This gives the desired result but somehow long and complicated.


texts: How does 2PL protocol apply to schedule of multiple transactions?

texts:
If a schedule follows the two-phase locking protocol, does every transaction have to follow 2PL, or is it the case that all locks must appear all unlocks in the whole schedule?
I am a little confused because the following schedule would be 2PL under the first understanding, but not a 2PL under the latter definition.
$T1$: begin lock-S(X) read(X) lock-S(Y) read(Y)
$T2$: begin lock-S(Y) read(Y) unlock(Y) commit
$T1$: upgrade(Y) write(Y) unlock(X) unlock(Y) commit


texts: Shortest unambiguous representation of a graph over an alphabet

texts:
I just started reading a book on theoretical computer science and here are a couple of beginner questions about graphs, which I am struggling to answer:

  Given the graph with the matrix representation
  \begin{bmatrix}0&0&1&1\\0&0&1&1\\0&1&0&1\\0&0&0&0\\\end{bmatrix}
  what is its shortest possible unambiguous representation over the boolean alphabet? How about over any alphabet?

Thank you :)


texts: Can we apply binary search for finding key 'x' in unsorted array?

texts:
Suppose we are given A, an array of size n, comprised of an increasing sequence of numbers followed immediately by a decreasing one. What is worst case time complexity of optimal algorithm to determine if a given number x is in the array?

The explanation given on the this site is confusing to me. How we can apply binary search on unsorted array?

They have provided following explanation => This is an application of Binary search, which has time complexity $Θ(log n)$ in worst case.


texts: Shortest sequence over alphabet $\{1, 2, ..., k\}$ which is not a subsequence of $A$ and $B$

texts: I have two sequences - $A$ (of length $n$) and $B$ (of length $m$). They consist of numbers from the alphabet $\{1, 2, ..., k\}$. How want to find the shortest sequence $C$ such that $C$ is not a subsequence of $A$ and $C$ is not a subsequence of $B$? It should be made from numbers from $\{1, 2, ..., k\}$. For example if $k = 2$, $A = 1,1,1,2,2,2$ and $B = 2,2,2,1,1,1$ then the shortest sequence $C$ has length $3$ and an example would be $C = 2,1,2$


texts: Is there an efficient algorithm for determining the probability a large randomly chosen integer is not divisible by any integer of some set?

texts:
Given a set of 10 integers $A = a_1, a_2, \cdots a_{10}$, is there an efficient algorithm which can tell me what's the probability a randomly chosen integer between $1$ and $10^{10}$ is NOT divisible by any member of this set.

I understand the Inclusion-Exclusion principle can be used to solve this problem but I can't figure out how to implement it so that it works efficiently.

Note: When I say "efficient", I mean polynomial time, yet I am not entirely sure what qualifies as polynomial time is this case as both variables are fixed.


texts:
I am aware of the complexity classes $P$, $NP$ and $L$. But I am not clear what $NL$ or Non-deterministic Log Space intuitively means. The part what I am unclear about is what is the meaning of Non-deterministic Space?

A Turing machine in a $L$ case would read an input, read/write on the work tape that is logarithmic in size, update its internal state, move the read write head on the work-tape and read head on the input tape. And at appropriate time it halts.

What does Non-determinism on work tape mean and how does the Turing Machine behave. I am totally lost on this one? An intuitive explanation would help.


texts: Since reading Ken Thompson's Reflections on Trusting Trust I am trying to formalize the idea of a program which mutates its own behaviour; specifically, a program that would be self-reproducing except that it would reproduce itself with a mutation. With this definition I wish to differentiate this kind of program from self-reproducing programs and will call them programs with self-propagating behaviour (due to the nature of propagating its own mutations). I am familiar with Hoare Logic, LTL, CTL, and CTL*, but am unsure what to use for the formulation since Hoare Logic requires a concrete implementation of a program and I am trying to represent not a program but a kind of program, and am also unsure if/how I could express this idea in LTL, CTL, or CTL*.


texts: Difference between an a microcontroller and a system on a chip?

texts:
I pulled this right from Wikipedia to compare, staring with an SoC:

  A system on a chip or system on chip (SoC or SOC) is an integrated circuit (IC) that integrates all components of a computer or other electronic system into a single chip.

And to compare, here's the microcontroller:

  A microcontroller (sometimes abbreviated µC, uC or MCU) is a small computer on a single integrated circuit containing a processor core, memory, and programmable input/output peripherals.

What is the difference? If they are both small computers that integrate all components on a single integrated circuit, and are limited, why are they regarded as different concepts or terms? A microcontroller has everything an SoC has, so why are they claimed to be different?

To elaborate further, what draws any tangible line here on any noteworthy differences?

They both are in the area of embedded systems, but aside from minimal differences, they are both seemingly exact in almost every way.


texts: Uniform generation of random bipartite bi-regular graphs?

texts:
I want an algorithm that takes the following

Input: $M,N,k,d$ positive integers such that $kM = dN$.

and produces the following

Output: Random bipartite graph, with $M$ vertices all of degree $k$ on one partition, and $N$ vertices all of degree $d$ on the other partition. No loops allowed. The output should be uniformly distributed among all possible graphs.

Does an algorithm like this exist? If so please provide a reference.


texts:
Here's the exact problem I'm having with Grover's search algorithm.. Given a function f:{0,...,N-1} -> {0,1}, Grover's problem is to find x such that f(x)=1, provided that there exists such x.

The phase inversion step: Invert the phase of the "key value".

So my question is, when we can already distinguish the key from the others, there is nothing to solve. Why do we need to solve the problem at all when we can already separate the key value? I am missing a point here but I don't understand what it is.

Many thanks for your help.


texts: prove that minimal number of comparisons to find median among five elements is 5

texts:
I would like to prove that we need at least five comparisons to find median amoung five numbers.

And my proposition:
Let's consider tree of comparisons. There are at least $5 \cdot {4\choose 2} = 30$  possiblities, so in our tree we have at least $30$ leaves. So what is minimal height of this tree when we have at least $30$ leaves. (height is number of comparisons).
So $$height \ge \log_2(30) > 4$$
Hence, $height \ge 5$.

Is it correct proof ?


texts: Fixing changing characters a regular expression

texts:
I have a regular language $L$ from characters of $\Sigma_1$, we define: $\Sigma_2=\Sigma_1\cup \{+,-\}$ and
$$L^{+-}=\left\{a_1\cdot p\cdot a_2\cdot q \cdot a_3\cdot\ldots \cdot a_k\mid a_1,a_2\ldots,a_k\in L,p\in\{+,-\},q\in \{+,-\}\setminus\{p\}\right\}$$
I want to show this is still a regular language. To do so with an DFA is easy, so I would like to do so using only regular expressions and basic closure rules of regular languages.
But since the $+$ and $-$ need to alter, this is getting complicated. I try proving by induction on the length of the regular expression $r$ for $L$, but I find it hard to see how to do when $r=(r_1)^*$. For a concatenation of $r_1\cdot r_2$ I can manage. But how do I approach $*$ when the symbols $+$ and $-$ need to alter?


texts: What is the signal going from the computer to the screen?

texts:
Im sorry if it is a weird question, but I cant seem to find an answer for this. What does the signal going to the screen look like in more abstract sense? Does it code the values of each pixel in a huge matrix, is it a computational stream that instructs the screen what to present?

In other words, can I grab this signal by a "listening" device for example and deconstruct it with algorithms? Not just grab the signal and present it on another screen. For example, if it is a matrix of pixel values, then I can run face recognition algorithms for example, to see if the signal sent to the computer is a picture of face or not.

It might also depend on the type of screen? Say that it is a LCD screen.

edit: To elaborate, if I wanted to take the signal sent to the screen and scan it for text (NSA style), could I? If so, what should I know of the signal that Im collecting to actually do this?
Disclaimer: Im not interested in spying on anyone.


texts: The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?

texts:
To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards
the stick and moves on to the next stick. Note that Py can compare relative lengths of all already
seen sticks.

Note that: The answer is considered correct if the absolute or relative error does not exceed 10e-7

Constraints: 1 <= N <= 10e5

Sample Inputs and Outputs:(n -> probability)

1 -> 1
2 -> 0.5
3 -> 0.5
10 -> 0.398690476190

Notes:
In the first test, Py chooses the first stick because it is the only one stick.
In the second test, it does not matter if he/she chooses the first or the second stick. The probability of
choosing the longest one is 0.5.
In the third example, he bypasses the first stick, because if Py chooses it the probability would be
1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first
one Py moves on to the third one.

My Attempt:
I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?


texts:
I have a B-Tree of order 5. So the keys are between $\lceil n/2 \rceil- 1 \leq keys \leq n - 1$ and children are between $\lceil n/2 \rceil \leq children \leq n $. Am I doing it right? So a full node would be of 4 keys, how do I split that, because when I split that full node, I get uneven keys in any of the children.

Example:
$\{G\}$ at level $0$,
$\{A, C, E\}$ and $\{H, K, N, Q\}$ at level $1$

Here $\{H, K, N, Q\}$ is a full node, when I insert T, I must pre-split $\{H, K, N, Q\}$, I get one key in either of the subtree which is wrong as the selection of keys suggest that they must be between 2 and 4.

What am I doing wrong?


texts: Prove that a $k$-regular bipartite graph with $k \geq 2$ has no cut-edge

texts:
Although this seems rather obvious, I couldn't prove it rigorously. Any ideas how to prove it? The graph is assumed to be simple and connected.

Explanation of the terms:

$k$-regular means that all vertices have degree $k$;
bipartite means that there are 2 sets of vertices $X, Y$, where vertices from $X$ only have edges with vertices $Y$ and vertices from $Y$ only have edges with vertices from $X$;
cut-edge is an edge which removal disconnects the graph;

This is b) part of the exercise, maybe a) part can help:

a) If all vertices $v \in G$ have an even degree, $G$ does not have cut-edge

From a) it actually follows that for even $k$, b) is true, thus only case with odd $k$ left to prove.


texts: How to determine Isomorphism of Non-Symmetric Matrix when Permutation-Set is given?

texts:
Consider, two  $m \times n$ matrices $A, B$ such that  there is a permutation $\kappa$ that  such that such that $A^{\kappa}=B$  (Wielandt's notation), i.e. $A, B$ are isomorphic but not equal.

Since, permutations of rows are independent of   permutations of columns, so $\kappa = \sigma \pi$ where $\sigma$ is a row permutation that acts on rows of non-symmetric matrix and $\pi$ acts on columns of matrix.

A set of column-permutations $\beta_k$  is a subset of the set of  all possible permutations of columns of $A$. So, $\beta_k \subseteq S_n$.

A set of column-permutations $\gamma_k$  is a subset of the set of  all possible permutations of columns of $B$. So, $\gamma_k \subseteq S_n$.

We consider 2 different set due to different labeling of columns in $A, B$ .

$\pi$ is in the set $\beta_k, \gamma_k$  but with different label.

Problem: $A,B, \beta_k, \gamma_k$ are given where  $A \neq B$ and $\sigma$ is unknown.

How can we show that A and B are isomorphic using $\beta_k, \gamma_k$ ?

In other words, can we construct an algorithm to show $A, B$ are isomorphic?

Edit:

Consider that $\beta_k \subset S_n$ instead of $\beta_k \subseteq S_n$ where size of $\beta_k$ is not as big as exponential.
Note that we can $partition$ sets of permutation $\beta_k, \gamma_k$ based on $automorphism$ of matrices $A, B$.

Some help will be appreciated !


texts: Difference Between Residual Neural Net and Recurrent Neural Net?

texts:
What is the difference between a Residual Neural Net and a Recurrent Neural Net?

As I understand,

Residual Neural Networks are very deep networks that implement 'shortcut' connections across multiple layers in order to preserve context as depth increases. Layers in a residual neural net have input from the layer before it and the optional, less processed data, from X layers higher. This prevents early or deep layers from 'dying' due to converging loss.

Recurrent Neural Networks are networks that contain a directed cycle which when computed is 'unrolled' through time. Layers in recurrent neural network have input from the layer before it and the optional, time dependent extra input. This provides situational context for things like natural language processing.

Therefor, a recurrent neural network can be used to generate a basic residual network if the input remains the same with respect to time.

Is this correct?