texts:
Questions:
Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$?
Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $h_k(y)$ (or $y$ itself) tells us if $y$ is very close to $x$ (e.g. the Levenshtein distance or Hamming distance of $x$ and $y$ is less than a fixed constant $c$)?

Background:
By information topology on $\Sigma^*$ on I mean the topology space with points $\Sigma^*$ and with the base $\{x\Sigma^* : x \in \Sigma^* \}$.
A nice way to think about topology is considering open sets as properties of points which are affirmable/verifiable (i.e. if it is true, it can be verify/observe that it is true). With this in mind, closed sets are refutable properties.
A function $f:\Sigma^* \to \Sigma^*$ is continuous if the inverse image of opens sets are open. In our case this means that for all $y \in \Sigma^*$, there is $I \subseteq \Sigma^*$ such that
$$f^{-1}(y\Sigma^*) = \bigcup_{x\in I} x\Sigma^*. $$
A nice way to think about the information topology is looking at it as a tree of binary strings. Each subtree is a an base open set (and other open set can be obtained from taking a union of base open sets).
This is sometimes referred to as information topology of strings because each point in $\Sigma^*$ can be considered as a finite approximation to a binary string/sequence. $x$ approximates $y$ iff $x$ is an initial substring of $y$ ($x \sqsubseteq y$).  E.g. $0011\Sigma^*$ is an approximation to $00110^*$ because $0011 \subseteq 00110^*$.
And for continuity, if we take a sequence $\{x_i\}_i$ which approximate and converge to binary sequence $y$ (think of $y$ as an infinite branch in the tree and $x_i$s as points on that branch) then $\{f(x_i)\}$ converge to $f(y)$, $$f(y) = \bigsqcup_i f(x_i).$$


texts: Copying items in arrays while checking their indexes

texts:
Array $P$ of length $n$ is a permutations of $\{0, ..., n-1\}$

  Write a code, which would in $O(n)$ create an array $R$ of length $n$, so
  for values $x_i, x_j \in P$,  $R[x_i] < R[x_j]$ if $x_i$ is on the left of $x_j$ ($i<j$).

This is a algorithmization problem that's recurring in the final's test each year and I'm stuck with it for weeks. I know that I'm supposed to show my work before asking here, but I didn't know how to start.

Could you at least point me to the right direction? What technique do I use, dynamic programming? Is this a problem for a specific algorithm?


texts: Difference between free and global variables

texts: Is there any difference between free variable and global variable? Or they are just  synonyms? In which situations I should use one or another?


texts: What do we call an algorithm that finds approximate solution sometimes and fails some other times?

texts:
Suppose you have a minimization problem $\Pi$. You know that finding a feasible solution to $\Pi$ is NP-hard. You have designed an algorithm $\mathfrak{A}$ to solve $\Pi$ and you prove the following:

If $\mathfrak{A}$ finds a feasible solution to $\Pi$, then its value is upper bounded by $\rho\mathit{OPT}$ for some $\rho >1$ where $\mathit{OPT}$ denotes the optimal value of $\Pi$.
If $\mathfrak{A}$ fails to find a feasible solution to $\Pi$, then it could return $0$ or in general something less than $\mathit{OPT}$. (Of course it violates some constraints of $\Pi$.)

What do we call such an algorithm in the literature?

I know that this is not an approximation algorithm by definition. Also, bi-criteria approximation algorithm would not produce a solution that is better than $\mathit{OPT}$. Is there a name for this algorithm?


texts:
So I am in the process of learning about LL(1) grammar and converting an ambiguous one into LL(1). I know how to figure out if a grammar (G) is ambiguous, however, I am having trouble converting it to a LL(1) using left factoring.

From my understanding, left factoring is basically factoring out prefixes which are common to two or more productions. So for example,

 A -> X | X Y Z

Becomes

A -> X B
B -> Y Z | ε

However, if we take an example such as the following grammar G,

A -> acB | da
B -> abB | daA | Af

How would I go about applying the left factoring to convert G to LL(1) since there is no common prefix based on what I can see. I am assuming I would have to use substitution (right corner substitution), correct?

The following is my attempt at converting G to LL(1), did I do it correctly?

A -> acB | da
B -> abB | daA | Af

A -> acabB | daA | Af | da     //sub B into A

A -> E | Af | da               //left factor
E -> acabB | daA | 1


texts: Alternatives to directly connected networks for representing frequently-updated graphs

texts:
What are the relative merits of the various graph representations, such as adjacency matrix, edge list, adjacency list, directly connected network etc. Given that this graph will be frequently updated, split, joined to other graphs?

Business Context: I am writing a molecule editor in C# and have currently used a directly connected network.  By this, I mean each edge maintains direct object references to each node, and each node supports a collection of edges, although this has proven to present problems when updating. I am looking for a better way of doing this.

The model should support

Adding and removal of nodes
Adding and removal of edges
Splitting connected graphs into two separate graphs
Joining graphs together

EDIT:  by a 'directly connected network' I imply the following.  Vertices are Atom objects.  Edges are Bond objects.  Each Atom has a collection of Bonds, and each Bond has a StartAtom and EndAtom.  The collections hold object references, so it is possible to directly retrieve the Atoms by calling Bond.StartAtom and Bond.EndAtom.  Setting the StarAtom or EndAtom requires that both Bond collections on each atom be update in synchrony.

Also, Atoms and Bonds reside within a Molecule, each being stored in one of two dedicated collections, and each Atom and Bond holds a direct reference to its parent Molecule.  Also, Molecules may contain an arbitrary number of child Molecules, and each of these has a reference to its parent.

The major difficulty with this approach is book-keeping.  Molecular graphs, when being edited are constantly being updated.  A typical operation is to remove a linking bond between to portions of a Molecule, which would split it into two separate Molecules.  Or to perform the revers operation, joining the Molecules into one combined Molecules, simply by drawing a bond between two disconnected Atoms.

The current approach is challenging to maintain easily and reliably.  When you add the requirement that you must support Undo and Redo then it becomes near impossible.  So I am looking for any approaches or design patterns that would simply this task though abstracting the representation.  I am currently experimenting with an edge-list approach.  I want to know if there are any better ways of doing it.


texts: How are binary trees represented on disk

texts:
Assume I have a word document, the contents in it are stored on the disk as bits. Nothing so complex here. When the word processor reads those bits, it just knows how to display on screen.

But what about binary trees. They are just not data, they have route node, child nodes. How are they actually represented on disk?

I tried searching using this term "binary trees representation on disk". But I didn't find anything useful.

Let me know if I am not clear

Update:
I was looking for details on how actually they are stored on disk. Given this simple binary tree:

Any data is stored in bits on disk. How are these stored?


texts: I am interested in simulating any turing machine with a turing machine that is allowed only to move right. I guess that it should be pretty standard material and likely it is trivial (or known to be false). Does anyone have a pointer to a reference?


texts: How to know whether a formula is common knowledge in Kripke structure?

texts: Suppose that we have a formula A which is valid in all states of Kripke structure and some transition relations. Is it generally possible to derive if formula A is common knowledge between particular agents directly from the structure?


texts: Is subset sum with a fixed target sum NP-complete?

texts:
I've read that subset sum is NP-complete. What happens when I change the decision problem to look for a  constant number? So the decision problem would look like this:

  Input:
  A collection of nonnegative integers A and a nonnegative integer b,

  Output:
  Boolean value indicating whether some subset of
  the collection sums to 10

Would this still be NP-complete? I don't believe you would be able to reduce every other NP-complete problem to it.


texts: On the recurrence $T(n) = T(n/a) + T(n/b) + n^c$

texts:
Consider the recurrence
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c).$$
What is the condition on $a,b$ that guarantees $T(n)=O(n^c)$?
With substitution I get
$$T(n)=T(\tfrac{n}{a}) + T(\tfrac{n}{b})+O(n^c)\le (\tfrac{n}{a})^c +  (\tfrac{n}{b})^c + n^c =  n^c ((\tfrac{1}{a})^c +  (\tfrac{1}{b})^c + 1)$$
I need $(\frac{1}{a})^c +  (\frac{1}{b})^c + 1$ to be less than one if I want to show that it is $\le n^c$.
So $\frac{1}{a^c} +  \frac{1}{b^c} \le 0$. But I have trouble with that and I don't know if my idea of showing this is right.


texts:
I was asked to find write a pseudocode of an algorithm that extracts the Log(N) largest elements in an array and return them in a sorted list, my attempt is
largestLogn(Arr)

n = Arr.length
j = 0
ans = new array of size Log(n)

Arr = Quicksort(Arr,1,a)

for i=(a-log(n)) ➜ a
ans[j] = Arr[i]
j++

return ans

From my limited understanding, the time complexity of this algorithm is $O(n\log n)$ for the QuickSort and $O(\log n)$ for the loop but in the question they hinted that the time complexity has something to do with the fact that $(\log(n))^{a}=O(n^{b})$ for any $a,b>0$ and now I'm not sure of my answer.


texts: Converting decision problems to grammars?

texts:
I'm struggling to understand some concepts related to the relationship between language and computability theories.

Can we convert decision problems to the corresponding grammars describing the languages? Can every decidable decision problem be converted to a context-free or context-sensitive grammars?

If it does not make sense at all, what is the relationship between the decision problems and languages?


texts: Why does Union-Find have time complexity O(N + M lg* N) with the "log star N"?

texts:
The time complexity of Weighted Union-Find with Path Compression, for M union-find ops and N objects is said to be

$$ O(N + M \lg^*N) $$

and the $ lg^*N $ is "log star N" and is iterated logarithm. It can be almost taken to be a constant, as $ lg^*2^{65536} $ is only equal to 5. Why is it $ lg^*N $ and what kind of operations / algorithm typical can produce $ lg^*N $?


texts:
Here is the problem is want to solve:

I want to connect nodes with directed labelled edges, but this two nodes are potentially themselves graphs, hypergraphs or the current structure I don't have a name for.

Here is a simple example with a graph $(v_1,e_1,v_2)$ where nodes $v_1$ and $v_2$ are connected by $e_1$. I want to have the following structure:
$((v_1,e_1,v_2),e_2,(v_3,e_3,v_4))$

in this case, the $v_i$ hold a single value (i.e. classical graph nodes)

What I don't know is:

What is the name of such a structure ?
If it's a well known data structure, are there some efficient implementations ?


texts: How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?

texts:
I am trying to solve this recurrence relation for a while but not getting anywhere. Actually, the sequence is given as,

  F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

where, F(0) and F(1) will be given. I added 1 on both sides to factorize it. I tried to solve it by taking log on both sides but unable to come to a conclusion.

P.S. I can't use simple for loop as n can go upto 10^9 so it'll result into a timeout.


texts:
I was learning about segment trees and came across this:

  We have an array arr[0 . . . n-1]. We should be able to
  1 Find the sum of elements from index l to r where 0 <= l <= r <= n-1

  2 Change value of a specified element of the array to a new value x. We need to do arr[i] = x where 0 <= i <= n-1.

  A simple solution is to run a loop from l to r and calculate sum of elements in given range. To update a value, simply do arr[i] = x. The first operation takes O(n) time and second operation takes O(1) time.

  Another solution is to create another array and store sum from start to i at the ith index in this array. Sum of a given range can now be calculated in O(1) time, but update operation takes O(n) time now. This works well if the number of query operations are large and very few updates.

This is quoted from this web page.

The paragraph which I'm confused with is marked as bold. I think that the sum of a given range will only be calculated in O(1) time if l = 0, which is not always the case. Also, I can't seem to understand why did the update operation now takes O(n) time.

I hope it's just a small problem that can be easily explained. You can even explain the whole concept of segment trees here. I appreciate any help in any ways. Thanks.


texts: Show that Vertex-Cover is NP-complete, using Stable-Set

texts:
My task is to give proof, the Vertex-Cover problem is NP-complete, assuming it's already shown that the Stable-Set problem is NP-complete, too.

My approach: i know, Stable-Set is NP-complete, and all Problems that are NP-complete can be reduced to each other. If i could solve one NP-complete problem, i might be able to solve all NP-complete problems. It should be possible to create a function with polynomial complexity to reduce Vertex-Cover to Stable-Set. At least, this was, what my Professor told.

Now all i have to do, is to find this polynomial function, in order to Show that Vertex-Cover is NP-complete. But here is where i am stuck.. so i need some advice how to build such functions.


texts: Is an intersection between NPC and coNPC always DPC?

texts:
The class DP is defined as the set of all languages $L$ such that $L = L_1 \cap L_2$ where $L_1 \in NP$ and $L_2 \in coNP$.
For example, the language SAT-UNSAT is defined in the following manner ($\varphi$ is a $3-CNF$ formula):
$\{( \varphi, \varphi'): \varphi \in SAT \wedge \varphi ' \in UNSAT \}$. This language is the intersection of:
$$L_1 = \{ (\varphi, \varphi'): \varphi \in SAT \} $$
And:
$$ L_2  = \{ (\varphi, \varphi'): \varphi' \in UNSAT \}. $$

Given $L_1$ which is known to be a NP complete problem, and $L_2$ which is known to be coNP complete problem, does $L_1 \cap L_2$ necessarily DP complete?
(I believe that the answer is yes, because I can use the reduction of $L_1$ and $L_2$. But I am still not very confident in this idea.)


texts: Heuristic algorithms for the dense assignment problem

texts:
Given a dense assignment problem ($n$ tasks assigned to $n$ workers, where each worker can do any one of the tasks), I understand the best complexity is $O(n^3)$, using the Hungarian Algorithm or variants.

However, if $n$ is large, $O(n^3)$ may not be feasible from a timing perspective. Moreover, storing the complete $n^2$ cost matrix may require a prohibitive amount of memory.

Are there heuristic algorithms that give "good enough" solutions, with are significantly faster? I have seen some algorithms that claim to be faster, but they assume the number of edges is smaller than $O(n^2)$, which is not true in the dense case.


texts: Constructing a connected graph with given degree sequence

texts: I am interested in constructing simple connected graphs where each vertex has a fixed number of edges (degree) ahead of time. I had originally assume I could use some modification of the Havel-Hakimi algorithm to do this, but Havel-Hakimi isn't actually guaranteed to produce connected graphs. Are there any known algorithms to do this?


texts: Impossibility for Byzantine Generals Problem where $n \leq 3m$

texts:
Wiki: https://en.wikipedia.org/wiki/Byzantine_fault_tolerance

In the paper "Reaching Agreement in the Presence of Faults", M. Pease et al. proved that there is no protocol (of some kind) to solve the problem for $n \leq 3m$, where $n$ stands for the number of generals and $m$ stands for the number of traitors. The key of their proof this the impossibility of the case $n=3,m=1$. However, the method they used does not look like an information theoretic proof. Thus, it seems like that their result is not "impossibility of arbitrary protocol".

  My question: Is there a infomation-theory-based proof for the case $n=3,m=1$? More formally, is there a proof or counterexample for the proposition "there does not exist any kind of protocol, which solves Byzantine generals problem where $n=3,m=1$"?

Note: The typical protocol $\mathrm{SM}(m)$ (it works for arbitrary $n,m$) suggested by L. Lamport et al. is NOT a suitable counterexample, because it needs a signature mechanism, which is NOT perfect reliable in the sense of information theory, if we assume that traitors have infinity computing resources.


texts:
I would love to have a direction for the following exercise (the material for this exercise is greedy algorithms):
Let $G = (V,E)$ an undirected graph whose vertices $V = \{v_1,\dots,v_n\}$ appear in this order on the real line (meaning forall $1 \leq i < j \leq n$, $v_i$ appears before $v_j$).
A $d$-divison of $G$'s vertices is a division into $d$ different intervals, meaning the choice of $d-1$ indices $1 \leq i_1 < i_2 < \dots < i_{d-1} < n$ which define the intervals:
$$ [v_1,\dots,v_{i_1}], [v_{i_1+1},\dots,v_{i_2}],\dots,[v_{i_{d-1}+1},\dots,v_n]. $$
A $d$-division is called independent if there are no two neighboring vertices in the same interval. Meaning, the division is independent if forall $0 \leq r < d$ and forall $i_r < j_1 < j_2 \leq i_{r+1}$ we have $\{v_{j_1},v_{j_2}\} \notin E$, where $i_0 = 0$ and $i_d = n$.
Offer an algorithm with time complexity $O(V+E)$ that finds an independent $d$-division of $G$ such that $d$ is minimal. Prove the correctness of the algorithm.
Notice: The division in this exercise is "continuous". For instance, if $v_1$ and $v_3$ are on the same interval, then $v_2$ is on the same interval with them. Also, there are no edges between any two vertices in the same interval. For instance, if the first interval in the division is $[v_1,v_2,v_3]$, then $\{v_1,v_2\},\{v_2,v_3\},\{v_3,v_1\} \notin E$.
Thanks a lot,


texts: Effective Instruction Execution Time with TLB and page Fault

texts:
Consider a system with a two-level paging scheme in which a regular memory access takes 150 nanoseconds, and servicing a page fault takes 8 milliseconds. An average instruction takes 100 nanoseconds of CPU time, and two memory accesses. The TLB hit ratio is 90%, and the page fault rate is one in every 10,000 instructions. What is the effective average instruction execution time?

(A)645ns

(B)1050ns

(C)1215ns

(D)1230ns

What I got is

Average Instruction Execution time=100ns(CPU Time)+ 2 Memory Access.

Since, Each memory access may include TLB hit and page fault

So,

Average Memory Access Time=TLB hit rate*(TLB access time+1 Memory reference(150ns))+ TLB Miss*((Page fault rate x Page Fault service time) +(1-page fault rate)*(3 Memory reference because of 2 level paging.))

Since, TLB access time not given, assuming it to be 0.

So, average memory access time=$0.9(150)+0.1*(10^{-4}(8*10^6)+(1-10^{-4})(450))=259.9955ns$

So, Average Instruction Execution Time: $100+2*(259.9955)=619.991ns$

But my answer came to be wrong and it is given 1260ns.

Can somebody help me where I am wrong?


texts:
In the CLRS chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:

  $$e^x = 1 + x + Θ(x^2).$$

How is it to be interpreted, what is the role of asymptotic notation here?


texts: Is it NP hard to partition a graph into 2 vertex sets with minimum degree of 2 and 3?

texts:
The following problem is from my algorithms class:

  Given a graph $G=(V, E)$, decide whether a partition of $V=(V_1, V_2)$ exists such that $\delta(G(V_1))\ge 2 $ and $\delta(G(V_2))\ge 3 $, where $G(V_1)$ denotes the subgraph induced by $V_1$ and $\delta(G(V_1))$ denotes the minimum degree of graph $G(V_1)$. Prove this decision problem is NP complete.

I'm trying to prove
$$\text{PARTITION} \le_p \text{This-Problem}$$
but haven't came up with a solution until now. I've never met a problem dealing with the minimum depth of a graph. Is there any theorem about it?  Could anyone help me out here?


texts: Changing preference in Gale-Shapley algorithm?

texts:
Suppose, in the context of the classic marriage problem, two equal size groups of $n$ men and $n$ women are being matched, with the GS algorithm.

If a man were to switch the order of a pair of women, low on his preference list, say $x$ and $y$, would this yield any sort of advantage with regards to being matched with a woman higher than $x$ and $y$?

This seems like a fairly simple problem; I don't see how switching a pair low on the preference list would increase the chance of being matched with something higher on the list. How would one prove the existence or non-existence of such an advantage?

I've come to the conclusion that this would not yield an advantage, but would still appreciate some guidance with regards to proving that.


texts: Complement of halting problem Co-RE or non R.E

texts:
Can someone please tell me if complement of halting problem(L) is Co-RE or non R.E ?

I think that it is Co-RE as L' (L complement) is R.E but everywhere its given non R.E


texts: What NP decision problems are not self-reducible?

texts:
So we just learned about self-reducibility in class.  My professor and our textbook would not commit to saying that all problems in NP are self-reducible, but there didn't seem to be any examples of problems that are not.  I was wondering if there are any examples, or if it's just a situation where you can't prove a negative easily.  Wikipedia only says It is conjectured that the integer factorization problem is not self-reducible.

Googling found one result, which seems to state that planar graph 4 coloring is not self-reducible because LF-k coloring for a planar graph reduces to that reduction, but I couldn't quite follow the proof right now.

Is this an actual example of a self-reducibility disproof, and are there others?


texts: Why does P/Poly can also receive bad advice?

texts:
(from my class's slides)

"NP and P/Poly both use an external string for computation. However, for L in NP, any witness is rejected if x $\notin$ L. For L in P/Poly, there can be bad advice!"

I'm having a hard time understanding why this is true. My intuition is that if there are indeed 'bad advice', i.e advice that make the Turing Machine return bad answers, doesn't it mean that a situation where ALL of the advice are 'bad' is technically possible?


texts: Prove that a language is bounded if and only if it's finite

texts:
Let's assume $L$ is a language. $L$ is bounded if for some natural number $n \in \mathbb N$ applies $|x| ≤ n$, where $|x|$ is a length of a string, with every $x \in L$. Let's also assume that $L$ lies in a finite set of alphabets $\Sigma$.

How to prove that $L$ is bounded if and only if it's finite?


texts: Problem class of assigning N persons to N tasks, zero costs with prefs

texts:
I am looking for the general problem class / computational complexity / algorithms for the following problem:

N tasks must be accomplished by N persons. 1 task to be done by exactly 1 person and vice versa. There is a binary preferences matrix whose (i,j) entry is 0 if person i can not do task j, and 1 if it can.

There are no costs involved, no weights and the number of tasks equals the number of people.

I was searching for it but all I could find was the Assignment Problem which has costs/weights associated with each assignment.

As a last resort, perhaps I can transform my preferences matrix to a cost matrix if person can not do job then cost is infinite else cost is zero?


texts: Meaning of ⟨_⟩ in the context of verifiers

texts:
A verifier for a language A is an algorithm V, where $$A = \{w \mid V
\text{ accepts $\langle w,c \rangle$ for some string $c$}\}$$ ($c$ is called a certificate or
  proof)

What's the definition of $\langle , \rangle$ here?


texts: Analysis of the reduction of a function using (outermost) graph-reduction

texts:
I want to determine the time and space complexity of the following functions:

subs [] = [[]]
subs (x:xs) = subs xs ++ map (x:) (subs xs)

subs' [] = [[]]
subs' (x:xs) = yss ++ map (x:) yss where yss = subs xs

The language I'm considering is using (outermost) graph-reduction (also known as call-by-need or call-by-name + sharing). Knowing that would it be correct to assert the following?

both definitions have the same reduction graph
their time complexity is $O(n^2)$
their space complexity is $O(2^n)$

Thanks!


texts: Which types of mathematical functions are the least complex for a computer to compute ?

texts:
Let's consider these four function types : Polynomial, Exponential, Logarithmic and Trigonometric.

Considering that both input and output values are floating point numbers.

How do they rank in terms of time complexity (of computing an output value for a given input value) ?


texts: Floyd Warshall's All pair shortest path problem does not evaluate all possible paths

texts:
We know that the FW all pair shortest path is a Dynamic Programming (DP) approach to solving the problem. Being a DP, it smartly evaluates all possible options before deciding the final option at each stage.

I have manually evaluated and traced a 5 node graph with this algorithm. The actual graph is not important here. I will take the example of the evaluation of path(V4,V5) in iteration 1 and 2 only:

Stage 1: min{(4,5),(4,1,5)} of Stage 0

Stage 2: min{(4,5), (4,2,5)} of Stage 1

So if we expand this, then by the end of Stage 2, we have actually essentially evaluated the paths {(4,5) , (4,1,5), (4,2,5), (4,2,1,5), (4,1,2,1,5)} and selected the minimum.

As seen, we are evaluating cyclic paths as well e.g. (4,1,2,1,5) from above. If we continue tracing the algorithm till the end, we find that we never evaluate the path (4,2,1,2,5) for this specific example. Does this mean, not all paths are evaluated with this algorithm? I know not evaluating it won't harm as it will definitely not be the shortest path but my point is that should have been the case with (4,1,2,1,5) too. It looks like although the output is correct and consistent, yet theoretically speaking certain paths are not evaluated because of the way the algorithm is structured and not out of merit. Am I missing something here?


texts:
I was reading an article on Clone an Undirected Graph, It says I have do do bfs and have to keep track of visited/cloned nodes.

I have another approach- I will initialize an empty adjacency list and then traverse the original adjacency list and copy it. Its time complexity is O(V+E) and I don't have to keep track of anything.

Is there anything wrong with this approach?


texts: What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

texts:
I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in Vector Spaces (say in the context of linear algebra and functional analysis) but I had never seen this term being used in the context of boolean functions. In those other contexts it roughly means the following equation is true:

$$ f(x+y) = f(x) + f(y) $$

however, when I went to wikipedia to find out what linearity means for boolean functions I came across a weird paragraph that seem to define it but didn't seem to have a clear succinct way to define linear functions or its relations to the more standard way of defining linearity.

Can someone explain to me how the definition from wikipedia relates to the more traditional way of defining linearity over Vector Spaces? In other words, why is the detailed definition on wikipedia the way it is?

For ease, here is wikipedia's definition:

  In Boolean algebra, a linear function is a function ${\displaystyle f}$ for which there exist $ {\displaystyle a_{0},a_{1},\ldots ,a_{n}\in\{0,1\}} a_0, a_1, \ldots, a_n \in \{0,1\} $ such that:

  $$ f(b_1, \ldots, b_n) = a_0 \oplus (a_1 \land b_1) \oplus \cdots \oplus (a_n \land b_n), \text{ where } {\displaystyle b_{1},\ldots ,b_{n}\in \{0,1\}.} b_1, \ldots, b_n \in \{0,1\}. $$

  A Boolean function is linear if one of the following holds for the
  function's truth table:

  -> In every row in which the truth value of the function is 'T', there
  are an odd number of 'T's assigned to the arguments and in every row
  in which the function is 'F' there is an even number of 'T's assigned
  to arguments. Specifically, f('F', 'F', ..., 'F') = 'F', and these
  functions correspond to linear maps over the Boolean vector space.

  -> In every row in which the value of the function is 'T', there is an even
  number of 'T's assigned to the arguments of the function; and in every
  row in which the truth value of the function is 'F', there are an odd
  number of 'T's assigned to arguments. In this case, f('F', 'F', ...,
  'F') = 'T'. Another way to express this is that each variable always
  makes a difference in the truth-value of the operation or it never
  makes a difference.


texts: As suggested by the title, $AMBIG_{NFA}$ consists of descriptions of all NFAs that accept some string along two computation branches. The original question is to show that it's decidable. Although I'm aware of some solution using the idea from the DFA-NFA conversion algorithm. I just thought of a alternative solution, but I'm not sure it works. So the idea is just to take the original NFA and make many copies of NFA that has one transition removed, and convert all these to DFAs, take the intersection, and see if it's empty. I feel like you would have a string accepted in at least two different ways iff every diminished NFA still accept that string, because we only remove one transition in each of the NFAs. The question is that if my proposal really works. Thanks!


texts: What is the most efficient algorithm to compute polynomial coefficients from its roots?

texts:
Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$. To get the coefficients (i.e. $y = \sum_{i}^n a_i x^i$), a straightforward expansion requires $O(n^2)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct with each other. The problem is equivalent to polynomial interpolation with $n$ points: $(x_1, 0), (x_2, 0), \dotsc, (x_n, 0)$. The fast polynomial interpolation algorithm can be run in $O(n\log^2(n))$ time.

I want to ask whether there is any more efficient algorithm better than $O(n^2)$? Even if there are duplicated values among $\{x_i\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e. $x_i \in \mathbf{F}_q$.


texts: Bug in wikipedia page for Van Emde Boas tree?

texts:
The Wikipedia page for vEB trees (specifically the version from 27 September, 2018),
gives the following pseudocode for finding the successor element of x in the vEB tree (of universe of size M):

function FindNext(T, x)
    if x < T.min then
        return T.min
    if x ≥ T.max then // no next element
        return M
    i = floor(x/√M)
    lo = x mod √M
    hi = x − lo
    if lo < T.children[i].max then
        return hi + FindNext(T.children[i], lo)
    return hi + T.children[FindNext(T.aux, i)].min
end

Consider the very last return statement. Shouldn't it instead be

    y = FindNext(T.aux, i)
    return y√M + T.children[y].min

Seems like a bug to me but I wanted to confirm.


texts: What is the resulting set for {0,1}*\{0}*?

texts:
If we have a language $L = \{0\}^*$ over the alphabet $\Sigma=\{0,1\}$, what is $\Sigma^*\backslash L$?

That's what I think:

$\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... \}$
$\{0\}^* = \{\epsilon, 0, 00, 000, 0000, ... \}$
$\{0,1\}^*\backslash \{0\}^*= \{1,01,10,11,001,...\}$

In other words, the resulting set should contain everything from $\Sigma^*$ except the empty string and any string that contains 0s but not 1s.

If my thinking is correct, then how can I express $\{1,01,10,11,001,...\}$ more succinctly using set notation? I was thinking of something like $\{0,1\}^*\{1\}\{0,1\}^*$ but I'm not sure if it's correct or if there's a better way.


texts: How to choose the right input(s) to test my algorithm?

texts: Suppose i want to trace an algorithm (think of it as a flowchart) to understand how it works, i need an input(s) for this algorithm, the question is: how can i determine the right input(s) that goes through all the cases ? Is there any "scientific" method to determine this input?


texts: Minimizing $\sum_{i=1}^n x_i/y_i$ over a polytope

texts:
I want to solve a linear programming problem in the $2n$ variables $x_1, \ldots, x_n$ and $y_1, \ldots, y_n$ where the cost is of the form $x_1/y_1 + \cdots + x_n/y_n$. Specifically, I want to solve
\begin{align*} & {\rm minimize}~ \sum_{i=1}^n x_i/y_i \\
&\mbox{ subject to } Ax + B y \leq c \\
& x>0, y>0,
\end{align*} where $A$ and $B$ are given matrices and $c$ is a given vector.

This feels like it should be NP-hard due to the non-convexity of the objective, but I have no idea how to show this, or even whether I'm missing some kind of clever trick that makes it convex. If the matrices $A$ and $B$ were positive, you could plug in $x_i=e^{u_i}, y_i = e^{v_i}$ and the problem would become a convex problem that you could solve via geometric programming, but positivity is not an assumption. I'm not even sure what would be a natural combinatorial problem to try to write in this format, so any suggestions would be very welcome.


texts:
I would like to know if there is a known decision problem with the following characteristics:

Represented in unary, the problem is decidable in polynomial time.
Represented in binary, the problem is not decidable in polynomial time (and this fact has been proved, not just conjectured).

For example, Subset-Sum is in $P$ when represented in unary, but it is $NP$-complete in binary. However, this problem does not satisfy my second requirement because we do not know whether $P=NP$.


texts: Is there an intuitive proof for the existence of hard functions?

texts:
I am referring to the theorem on page 115 of the book by Arora and Barak, which states that, ``For every $n>1$, there exists a function $f:\{0,1\}^n \rightarrow \{0,1\}$ that cannot be computed by a circuit $C$ of size $\frac{2^n}{10n}$"

Can someone give a more intuitive proof of this than the one presented there?

For example he proof there at one point claims with little justification that there are at most $2^{0.92^n}$ circuits of size at most $\frac{2^n}{10n}$. Why? I couldn't reproduce this ``0.92" thing!

It seems that one even improve this theorem to  higher lower bound of $\frac{2^n}{n}$. Can someone kindly help do that? How much up can one get this?


texts: Is there a name/interest for regular languages that have a non-ambiguous ending?

texts:
The basic idea is to have one or more symbol that clearly indicate the end. For example:

Non-ambiguous:

  $ab^*c$
  $(a|b)c$
   $ab^+c$
   $ab?c$
   $a(b|c)$
   $c(ab)^*ccc$
   $acc^*d$
   $abc|bcd$

Ambiguous:

  $abc^*$
  $abc^+$
  $abc?$
  $acc^*$ or $ac^*c$

An alternative definition of a non-ambiguous ending would be that the corresponding DFA can have multiple final states, but none of them can have a outgoing transition.


texts: Efficient way to implement periodic events

texts:
I need to implement a system that can schedule and dispatch periodic jobs and needs to support a very high load (millions of jobs per second). Each job in the system has a period that is some multiple of 15 seconds, with the maximum allowed period being 1 day.

The system needs to support adding new jobs and removing / replacing existing jobs. However, these occur relatively infrequently (aside from when the system starts up and has to add the initial batch of jobs), so it is okay to make trade-offs with regards to insertion / deletion time.

Jobs scheduling times should be spread out so as to avoid "spikes" in number jobs dispatched. For example, if we had a million jobs that all had a period of 15 seconds, we wouldn't want to dispatch all of them at the exact same time every 15 seconds, and then wait another 15 seconds not doing anything before doing it again. It would be better to spread them out so around 60-70k jobs are dispatched every second, as long as each job is still scheduled to run 15 seconds apart.

Currently, around 10% (maybe less) of the jobs in the system have a period of 15 seconds (the minimum possible), while the remaining jobs have periods between 30 seconds and 1 day.

Our current implementation uses something like a hashed timer wheel, which has 15,000 buckets representing the number of milliseconds in every 15 second interval. Jobs are added to a random bucket in the wheel, and on every tick of the wheel, we iterate through every job in the bucket, dispatching the ones that are "expired" and incrementing a counter for the remaining jobs. For example, a job with a 60 second period would only be dispatched once every 4 turns of the wheel, even though it is iterated over on every turn of the wheel. The problem here is that on each tick of the wheel, the majority of the jobs in the next bucket are not actually ready to be dispatched, but we have to iterate over them anyways to increment their counter.

Is there a better algorithm / data structure I can use to make this more efficient? I am considering implementing hierarchical timing wheels, so that the only times we need to iterate over a job are when it is re-inserted into a lower wheel, or when it is ready to be dispatched. My concern with this approach though, is that unlike the current hashed timer wheel approach, we need to remove and re-insert the job every time its period expires.


texts: Inventory planning problem solved through dynamic programming

texts:
I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).

15-11: Inventory Planning, p.411
The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $n$ months. For each month $i$, the company knows the demand $d_i$, that is, the number of machines that it will sell. Let $D  = \displaystyle\sum_{i=1}^{n} d_i $ be the total demand over the next $n$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $h(j)$ for $u = 1, 2, ... , D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j+1)$ for $j \le 1 \le D - 1$.
Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $n$ and $D$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.
So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem:
Let $MinCost(i,j)$ be the function that returns minimized cost of operation for past $i$ months, $j$ is the number of unsold machines left at the end of the month $i$.(Goal, is to calculate $MinCost(n,0)$, in other words, at the end of planning period(month $n$), there are no unsold machines.)
So, the DP recurrence is given by $MinCost(0,0) = 0$ and
$\quad MinCost(i,j) = \min\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \}$
for $i+j > 0$; here, $c(k,j,i)$ is the function that calculates the costs of the production.
If my optimal sub-problem is correct, how do I create an algorithm to solve it?


texts: Finding number of edges with weight less than k on the path between two nodes in a tree

texts:
You are given a tree with $n$ nodes and $n-1$ edges. Each edge has a weight. There are $m$ queries. In each query you have to answer the following question:

How many edges are there in the path between node $a$ and node $b$ with weight less than $k$?

$a$, $b$, and $k$ vary in each query.  You're allowed to preprocess the tree to make it easy to answer each query.

Consider the tree with edges

          1
 weight=4/ \weight=5
        2   3
weight=4|
        4
weight=4|
        5

Between nodes 3 and 5, the total number of edges with weight less than 5 is 3, i.e. {1-2, 2-4, 4-5}.

I was trying to solve by brute force method by checking each path.

I want to know if there is a better way of solving this.


texts: Proving "QUESTION" is NP-Complete by reduction from n-variable 3SAT

texts:
I'm struggling with a problem in my theory of computation course that asks us to prove "QUESTION" is NP-complete by reduction from n-variable 3SAT. I've done a number of other similar reductions but I keep getting stumped on this particular problem.

We define a question as a string over the alphabet $\{0,1, ?\}$ and say that a question covers all of the strings where substituting ?? with 0s and 1s yields a string such as $0??1$ covers the four strings $0001$, $0011$, $0101$, $0111$.

We have to reduce the 3SAT problem to QUESTION= {A : A is a set of questions, each of length $n$, such that there exists a string $w$ of length $n$ where no question in A covers $w$}. To show that it is NP-complete.

I recognize that some instance of QUESTION will "cover" less than $2^n$ strings but I'm pretty stumped on how to go forward as all of the things I've tried end up not working out.


texts: How to prove the optimization version problem (whose decision version is NP-complete) can be solved in poly-time iff P=NP?

texts:
I have proved the decision version of my problem to be $\mathcal{NP}$-complete. And I know that if I can solve the optimization version in poly-time, then I can just compare the obtained minimum (or maximum) with target value in decision version. Thus, the decision version can be solved in poly-time as well. Since, the decision version is $\mathcal{NP}$-hard, so is the optimization version, i.e., the optimization version is $\mathcal{NP}$-hard.
My question is how to prove the converse direction: if the decision version can be solved in poly-time, can the optimization version be solved in poly-time as well?
I in advance thank you for any suggestions!


texts: What mathematical background is enough to go through the entire Knuth's TAOCP?

texts:
I am an undergrad. I can do mathematics fine and am a lot more interested to explore.
I turned towards TAOCP as it is highly mathematically oriented so as to excel at maths and programming at the same time.
But I am stuck. I have only studied calculus, numerical analysis and probability (undergrad level) but the first few pages of the first volume itself is too difficult to get through.
Also, the problems are ranked according to their difficulty level. What all can I do to solve those problems? I really need to get better at mathematics.

What books(mathematics) should one read to be able to understand TAOCP? I am ready to go to a series of books just to get better at it.

Also, any suggestion(s) on how to learn/practice MIX(the TAOCP assembly)?


texts: Machine Learning algorithm for predicting a user's rating on an item?

texts:
I'm trying to build an supervised learning algorithm that deals with the regression problem of predicting a user's rating of a new incoming item based on the user's previous ratings on items. The ratings will be in the range of 1 - 5 (1 = best, 5 = worst).
Features a item will probably have:

author (nominal)
release channel (nominal, can be empty)
length in minutes (most likely something between 2 and 15, but can be higher)
release year (nominal)

The outcome of the algorithm should be a rating for an previously unrated item. (Should be a decimal value - for ordering the predictions, like something between 1.0 and 5.0, or normalized 0.0 to 1.0)
What type of algorithm would suit this prediction problem best and how would i implement it?


texts: Memory cells (addresses) read into a cache

texts:
How does one determine what memory cells (addresses) are being read into a cache?

For example if we read at adress "C000EAFCH", which memory cells will be read into the cache if the cache is 64 byte and each cacheline is 8 byte?

If we use direct mapping, would one say that there are the 4 previous bytes and the 4 next bytes from the address that are being read?

In that case I would say that addresses C00EAF8H to C00EAFFH are being read. That would mean 4 bytes before the address, then the byte on the address and 3 more addresses are read.

However the one who asked this question wrote that the correct answer is C00EAF8 to C00EAFFH. I don't know why the 'H' disappeared in C00EAF8 but maybe it's a typo. To be honest I don't even know what the 'H' stands for, as it is not a hexadecimal character. Maybe someone can clarify this?

I also wonder, why doesn't one read the byte on the address, and then the next 7 bytes? Does this reading 4 bytes before and 3 bytes after have to do with direct mapping?


texts: In Data Mining, what does it mean to be greedy?

texts:
I am looking at a number of algorithms in Data Mining and some are described as being greedy. My issue is that they seem to be using the term greedy in different ways, which seems contradictory.

For example, with Hierarchical Clustering the decision to merge clusters is described as greedy. However, a filter attribute selection method where we select a subset of the attributes which possess the highest Information Gain is also described as greedy because it does not cope well with the interaction of attributes.

What does the term greedy mean in terms of Data Mining?


texts:
Given set of grammar rules, how to find if they correspond to Context-free or unrestricted?

Just for Understanding (don't solve the below one),
eg:

\begin{align}
S &\rightarrow B/A, \\
1B &\rightarrow 111B, \\
1A0 &\rightarrow 00
\end{align}


texts:
What's the intuition behind a ''Graph fourier transform'' ? I'm not so much interested in mathematical details or technical applications. I'm trying to grasp what a graph fourier transform actually represents,and what aspects of a graph it makes accessible.

To clarify the issue:
Graph-structured data appears in many modern applications like social networks, sensor networks,
transportation networks and computer graphics. These applications are defined by an underlying
graph (e.g. a social graph) with associated nodal attributes (e.g. number of ad-clicks by an individual).
A simple model for such data is that of a graph signal—a function mapping every node to a scalar real value

The classical Fourier transform is the expansion of a function $f$ in terms of the eigenfunctions of the Laplace operator;  i.e.,
$$ \hat{f} = \langle f, e^{2\pi i \xi t } \rangle$$
Analogously, the graph Fourier transform  $\hat{f}$ a function $f \in \mathbb{R}^{N}$ the vertices of graph $G$ the expansion of $f$ in terms of the eigenfunctions of the graph Laplacian. It is defined by

$$\hat{f}( \lambda_{l}) = \langle f , \chi_{l}\rangle = \sum_{n=1}^{N} f(n) \chi_{l}^* (n) .$$

It should be mentioned

the following article claims that,"we generalize one of the most important signal processing tools – windowed Fourier analysis – to the graph setting and When we apply this transform to a signal with frequency components that vary along a path graph, the resulting spectrogram matches our intuition from classical discrete-time signal processing. Yet, our construction is fully generalized and can be applied to analyze signals on any undirected, connected, weighted graph."

(https://arxiv.org/abs/1307.5708)

I am looking for some simple concrete examples of the ways in which real problems go through  graph signal processing and how  graph Fourier transforms are obtained.


texts: How does a PDA compare two configurations of accepting histories?

texts:
In Michael Sipser's book, they prove that ALL_CFG = { G | G is a CFG and L(G) = Σ∗ } is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation)does a PDA go on to compare two configurations and figure out that the first properly yields the second.
I know that the computation histories are encoded in a convenient manner (reversing), but I couldn't seem to figure out how and what the PDA really does.


texts: Can you substitute functions in Big-$\Theta$ notation?

texts: Say we have some function $f(n)=\Theta(\log n)$ and another function $g(n)=\Theta(n+\log n)$. Is it valid to substitute $f(n)$ for $\log n$, giving us $g(n) = \Theta(n + f(n))$? This seems obvious to me but I'm not sure if there is a weird edge case where this isn't true.


texts: What programming language should I use to run physics simulations of CO2 being absorbed by different materials?

texts: I want to model the absorption of CO2 with multiple different materials such as cement, limestone, wood, etc? I know Matlab is capable of these types of physics simulation according to this research paper: Research Paper, however, I am not sure if Python or another programming language could complete this task easier.


texts:
Given set of points (in the plane), find in a linear time the smallest width annulus (annulus is the region between two concentric circles) that contains all the points.

Because of the time constraint we can't use any type sort/tree, also I've tried to think about using selection algorithm, but I can't think of a way to find the circles center point accordingly.

Can you think about any solution?


texts: Is my lambda calculus reduction correct and final form valid in simply typed lambda calc?

texts:
I'm looking at some lambda calculus at the moment and came across this question:

0:R

1:R

plus: R->R->R

(lambda f:T . lambda g:U . (f 0) (g 0)) (plus 1) (plus (plus 1 1))

Is it well typed given appropriate types for T and U?

I'm new to lambda calc but I gather that we substitute (plus 1) for f and (plus (plus 1 1)) for g.

This will reduce to
(plus 1 0) (plus (plus 1 1) 0)
The right hand side (plus 1 1) will reduce to an R and then we will have (plus R 0) which will reduce to an R. The left side will reduce to an R so the whole expression reduces to the form R R.

Is this correct? Then f and g are of type R -> R (from currying) to make it valid. Is it an issue that the final expression will be of the form R R. Does this mean R gets applied to R then, so R would have to be an 'automorphic' function (mapping from a type to the same type)... is this something related to not having recursion in simply typed lambda calc?


texts: Counting pairs of intervals where one is a subset of the other

texts:
Given a list of intervals with nonnegative endpoints, e.g. $ [3,5][1,7][2,60] $, the goal is to find the number of pairs of intervals $I,J$ such that $I$ is a subset of $J$.
In this particular case the total number is 2 because $[3,5]$ is a subset of $[1,7]$ and a subset of $[2,60]$.
Furthermore we were asked to find a solution to this problem with time complexity less than $O(n^2)$.

At first I thought of sorting the given sets based on their lower bound and in this example the order would be $ [1,7] \to [2,60] \to [3,5] $  so the time complexity so far is $O(n\log n)$, but I can tell nothing about the total number of pairs cause of the order of the upper bounds of the sets is a mess. Then I thought of sorting them based on their middle element and then performing a Binary Search based on this sorting so my time complexity would still be $O(n\log n)$. However now I am stuck and a direction would be appreciated.


texts: $\mathsf{PSPACE}$ membership in exponentially many steps?

texts:
I am trying to argue that a certain problem is in $\mathsf{PSPACE}$ and my question is, essentially, whether it is ok to have an algorithm that takes an exponential number of steps as long as, overall, the whole thing stays in polynomial space.

The context for this is that I have a naive algorithm which, it seems to me, shows $\mathsf{PSPACE}$ membership, but I am not entirely certain of the logic behind it.

I can be more concrete. Say we have a set $M$ and a transitive binary relation $>$ on $M$. $M$ is exponentially large (think all possible assignments), and $>$ can be partial and have cycles. If $a>b$, for $a,b\in M$, then we say that $a$ dominates $b$. If $a$ dominates every element in $M$ (including itself), we say that $a$ is dominating.

I know that, given $>$ and some $a\in M$, determining whether $a$ is dominating in $>$ is $\mathsf{PSPACE}$-complete. Call this the $\mathsf{DOMINATING}$ problem, and we can take it as a given that it is $\mathsf{PSPACE}$ complete.

The problem I am faced with is now is what we could call the $\exists\mathsf{DOMINATING}$ problem:
given $>$, determine whether there exists a dominating element in $>$.

My naive algorithm for $\exists\mathsf{DOMINATING}$ is as follows: take every element in $M$, ask whether it is dominating in $>$, and stop if one is found.
This, it seems to me, is in $\mathsf{PSPACE}$: even though we might have to go through an exponential number of $\mathsf{PSPACE}$ queries, we stay in polynomial space throughout.


texts: Conceptual overview: Self-information, Mutual information, uncertainty, entropy

texts:
I would like to have a compact conceptual explanation that allows me to gain some feeling with the concepts. The following list uses $x_i, y_i$  as events of experiments $X, Y$.

Self-information, denoted as $I(x_i)$
Mutual information, denoted as $I(x_i; y_i)$
Uncertainty (which is closely related to self-information and/or mutual information, I believe).
Average mutual information, denoted as $I(X, Y)$.
Entropy, denoted as $H(X)$, which is average self-information, I believe.

Next, there are a couple of "conditional ..." defined.

Can you sketch a compact overview of these concepts and how they relate, all intuitively?


texts: Algorithm for calculating the Grundy value of a green-hackenbush graph

texts:
I need an algorithm to convert a green hackenbush graph to it's equivalent tree so that I can find the Grundy value of the Graph using colon principle.

I thought of finding the bridges in the given graph and compressing cycles into one node using the fusion principle but I fail to implement it when there are cycles within cycles.

Can someone provide an easy to implement algorithm that can find the Grundy value (using Sprague-Grundy theorem) of a given Green - Hackenbush graph.


texts: Is it possible for the runtime and input size in an algorithm to be inversely related?

texts:
I'm wondering if it's possible for algorithms that have monotonically decreasing runtime with the input-size - just as a fun mental exercise. If not, is it possible to disprove this claim? I haven't been able to come up with an example or counterexample so far, and this sounds like an interesting problem.
P.S. Something like $O(\frac{1}{n})$, I guess (if it exists)


texts: Why is there the regularity condition in the master theorem?

texts:
I have been reading Introduction to Algorithms by Cormen et al. and I'm reading the statement of the Master theorem starting on page 73. In case 3 there is also a regularity condition that needs to be satisfied to use the theorem:

... 3. If
$\qquad \displaystyle f(n) = \Omega(n^{\log_b a + \varepsilon})$
for some constant $\varepsilon > 0$ and if
$\qquad \displaystyle af(n/b) \leq cf(n)$      [this is the regularity condition]
for some constant $c < 1$ and for all sufficiently large $n$, then ..

Can someone tell me why the regularity condition is needed? How does the theorem fail if the condition is not satisfied?


texts: How does asynchronous operations save time in I/O

texts:
I'm reading a book CLR via C# which says how Windows does asynchronous I/O:

To read data from the file, ReadAsync internally allocates a Task object to represent the pending completion of the read operation. Then, ReadAsync calls Win32's ReadFile function (#1). ReadFile allocates its IRP (I/O Request Packet) and then passes it down to the Windows kernel (#3). Windows adds the IRP to the hard disk drive’s IRP queue (#4), but now, instead of blocking your thread, your thread is allowed to return to your code; your thread immediately returns from its call to ReadAsync (#5, #6,
and #7). Now, of course, the IRP has not necessarily been processed yet, so you cannot have code
after ReadAsync that attempts to access the bytes in the passed-in Byte[]. Using the task object, you can call ContinueWith to register a callback method that should execute when the task completes and then
process the data in this callback method. Or, alternatively, you can use C#'s asynchronous function
feature to simplify your code by allowing you to write it sequentially.

The author also describes a scenario of how asynchronous operations save time in I/O:

let's say that your application wants to download 10 images from various websites and that it takes 5 seconds to download each image. If you perform this work synchronously (downloading one image after another), then it takes you 50 seconds to get the 10 images. However, if you use just one thread to initiate 10 asynchronous download operations, then all 10 are being performed concurrently and all 10 images will come back in just 5 seconds! That is, when performing multiple synchronous I/O operations, the time it takes to get all the results is the sum of the times required for each individual result. However, when performing multiple asynchronous I/O operations, the time it takes to get all the results is the time required to get the single worst-performing operation.

I don't understand how async operations can reduce the time from 50 seconds to 5 seconds. Let's change the NTFS Disk Driever to network adapter driver and change the read file async code to download file async code.
My understanding is, it is true that asynchronous operations allow fewer worker threads to handle incoming client's I/O requests, contrasted by synchronous operations, every I/O request need a worker thread to handle, and when the synchronous operation takes time to complete, the worker thread gets blocked too and therefore it cannot return to the thread pool to serve other requests. But for the network adapter driver, can still only complete one I/O operation one at a time.
For example, let's say the network adapter driver is handling the first I/O request (represented as an IRP queue) to download the first picture. Even though you use asynchronous operations, the worker thread that serves the first I/O request did return to the thread pool to serve the second I/O request, but the network adapter driver is still processing the first I/O request to download the first picture, so the second I/O request as an IRP is still queuing in the network adapter driver. The network adapter driver only handles the second IRP after the first one is completed, so the network adapter driver still serves the second I/O request after 5 seconds, and so on, so it still needs 50 seconds to download 10 pages. In other words, it is not worker threads blocking, it is the network adapter driver that's blocking.
so how can how async operations can reduce the time from 50 seconds to 5 seconds? Unless the network adapter driver itself is a small powerful computer that has multiple CPUs that can serve requests concurrently, but this is obviously not true, drivers like network adapter drivers are cheap devices, it can't be having expensive components like CPUs?


texts: Putting as many items as possible with weight and size limit

texts:
I am trying to design a greedy algorithm that has to take in multiple factors when making a greedy choice.

Any item has an item weight of Iw and item size of Is, these are both numerical values. Item sizes are originally translated from the values very small, small, medium, large, extra large to .1, .5, 1, 2, 2.5, respectively.

Imagine you are trying to optimize a box to have as many items in it as possible while being under a weight limit Tw and a size limit Ts. Also, the distribution of the size types (small, medium, etc) has to be a sort of bell curve where most of the items are medium, a smaller portion are small/large, and the least are extra large/very small.

I am familiar with creating a GA with only one variable, but am not sure how to do it with all of these factors.


texts: Implicit complexity and interpretation of total languages

texts:
In implicit complexity theory we construct languages that characterize what can be computed in various complexity classes. One major result is Bellantoni and Cook where they show that $FP$ can be characterized by such a language (called system $B$).

I have the following beliefs about system $B$

System B can encode all functions which can be computed in polynomial time
All terms in System $B$ normalize in polynomial time
Because all System $B$ terms normalize (in any amount of time) System $B$ is total
Because all System $B$ terms normalize in polynomial time System $B$ can interpret System $B$

I have the following beliefs a computability as well

If a language can interpret itself then it is not total
System $B$ can interpret it self so System $B$ is not total

So I seem to believe contradictory things now; namely that System $B$ is total and that System $B$ is not total. Writing out like this makes me realize that the error is almost certainly in the last line of my beliefs about System $B$. So it must be the case that System $B$ can't interpret itself but I don't actually understand why this is the case. Is there a program input pair such that interpreting it takes greater than polynomial time? Further still System $B$ is just one such system among all characterizations of complexity classes on which I could apply this faulty reasoning so the answer should not be specific to System $B$ but to all such implicit characterizations of complexity classes.


texts: Isomorphism problem on bounded degree digraphs

texts:
By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.

Is isomorphism problem tractable (or GI-complete) on edge-directed graphs with bounded degree?


texts: Effective Procedures and P vs NP Problem

texts:
If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two explicit queries:

If an effective procedure cannot be given which yields a solution, in what sense is the S actually a solution? Does this defy the formal definition of solution? I am assuming that an effective procedure is equivalent to a proof.
If there is no effective procedure to arrive at an accepted solution, this implies that solution is not a syntactic consequence of problem. According to formal definition, syntactic consequence is equivalent to an effective procedure. If solution to a hard problem is not a syntactic consequence of problem, what is it?


texts: Question about the difference between radix trees and patricia trees

texts:
I've already done some research on this topic, but it still isn't quite clear to me.

According to this post patricia trees are radix trees with $r = 2$. Every patricia tree I've seen so far is used to store alphanumeric symbols. Assuming that there are used 8 bits to represent one symbol, $r$ is the number of bits compared and the radix of a radix tree is $2^r$ shouldn't the radix of a patricia tree be $2^8 = 256$?

If you have a look at a PATRICIA Tree with the following inputs (in this order):

smile
smiled
smiles

According to the linked post a Patricia tree should then look like this:

smile - - - smiled - - - smiles

But intuitively (by the alphanumeric representation) it should look like this

       d
      /
smile
      \
       s


texts: What is the difference between these two Edit Distance Algorithm

texts:
Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why first algorithm doesn't work while second one does.
  public int find (String word1, String word2, int i, int j, int count) {
    if (i >= word1.length()) return  count + word2.length() - j;
    if (j >= word2.length()) return  count + word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j] = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

Notice, how I'm passing the cost of edit in method argument. Now, the algorithm which works. Here I'm not passing the edit distance in the method parameter instead of I'm adding 1 to recursive method.
  public int find (String word1, String word2, int i, int j) {
    if (i >= word1.length()) return  word2.length() - j;
    if (j >= word2.length()) return  word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j]  = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

I'm not able to think why first algorithm fails. Appreciate, if you can point my error in understanding.


texts: Efficient way to reduce a binomial coefficient as a fraction

texts:
Here is the full problem.

You need to calculate Euler's totient function of a binomial coefficient $C_n^k$.
Input
The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$.
Output
Print one number $\varphi (C_n^k)$ modulo $10^9+7$.

My thoughts:
It is known that $$\varphi(a)=a \prod_{p|a}(1-\frac{1}{p}) $$
where $p$ are prime numbers divide $a$.
Hence, if we can obtain somehow vector<int> multipliers that contains divisors of $C_n^k$ then we can easily do the following steps in order to calculate $\varphi(C_n^k)$:

Multiply all elements of that vector modulo $10^9+7$. Let's call the result by result
Then we can iterate through all prime numbers that divide any element of multipliers(these prime numbers can be obtained by a minor modification of sieve of Eratosthenes). Since $1-\frac{1}{p}=\frac{p-1}{p}$ we can update the result by:

result = divideMod(multiplyMod(result, p-1), p)

where divideMod and multiplyMod are functions doing corresponding operations modulo $10^9+7$.
And yes, we can do modulus division since $10^9+7$ is prime.
By doing all that stuff we get what we needed: $\varphi(C_n^k)$ modulo $10^9+7$. This all idea now requires just a vector multipliers. Here is my attempt to get it:
I need to write a function calculates the combinations number $C_n^k$. The function shouldn't return the total result of the operation(because it can be too large since $(0 \le k \le n \le 500000)$). It should return the vector<int> which contains divisors of that number. Let's do some math:
$$
C_n^k = \frac{n!}{(n-k)! k!} \\
=\frac{n(n-1)(n-2)...(n-k+1)}{k(k-1)(k-2)...1}
$$
So now I need to reduce this fraction. And the question is: what is the most efficient way to do this(in terms of time)?
I've tried the following. Consider the numerator and denominator are represented by vector<int> numerator={n, n-1, ..., n-k+1} and vector<int> denominator={k, k-1, ..., 1} respectively.
    vector<long> numerator(k);
    vector<long> denominator(k);
    for (int i = 0; i<k; i++) {
        numerator[i] = n-i;
        denominator[i] = k-i;
    }

    vector<long> multipliers;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (numerator[i] == 1)
                break;

            long greatest_common_divisor = gcd(numerator[i], denominator[j]);
            numerator[i] /= greatest_common_divisor;
            denominator[j] /= greatest_common_divisor;
        }
        if (numerator[i] != 1)
            multipliers.push_back(numerator[i]);
    }

As you can see I just go through all numbers in numerator and denominator and divide them by their greatest common divisor.
Time complexity of this algorithm is $O( k^2 log(nk) )$
It's too big and for this solution contest system returns time limit exceeded.($0 \le k \le n \le 500000$)
Does there exist more efficient way?


texts: AVL tree balance property states for the two subtrees of a node, their height can differ at most one. Why can't it be zero?

texts: I was thinking that if they were equal, say they are required to be zero this would be enforce the balance property more effectively. Can anyone explain why 1 is a satisfactory rather than just them being 0?


texts: Where is pivoting done in the Crout decomposition algorithm?


texts:
I'm having hard time understanding time complexity of my solution for combination sum problem. The problem is as follows:

  Given a set of candidate numbers (candidates) (without duplicates) and a target number (target), find all unique combinations in candidates where the candidate numbers sums to target.

  The same repeated number may be chosen from candidates unlimited number of times.

Below is my solution written in Java using recursion:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
    Arrays.sort(candidates);
    List<List<Integer>> results = new ArrayList<>();
    recurse(results, candidates, target, 0, new ArrayList<>());
    return results;
}

private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        if (candidates[i] > target) {
            return;
        }
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

One can observe that the problem size of each recursive step is potentially not changed and the depth of the recursion is bound by target value e.g. if the candidates array contains number 1 the recursion will happen target times. If I simplify the code the interesting part is:

private void recurse(List<List<Integer>> results, int[] candidates, int target, int idx, List<Integer> acc) {
    if (target == 0) {
        results.add(new ArrayList<>(acc));
        return;
    }
    for (int i = idx; i < candidates.length; i++) {
        acc.add(candidates[i]);
        recurse(results, candidates, target - candidates[i], i, acc);
        acc.remove(acc.size() - 1);
    }
}

Which feels like O(candidates.length * target) for the most pessimistic candidates input with number 1.

Since my solution is not really a divide and conquer algorithm I guess that I can't apply the master theorem. It feels like a  backtracking algorithm but I'm not familiar with finding upper bound for that type of algorithms.

Can someone please advise how to approach complexity analysis of above code?


texts: What is a good metric to choose the degree of a B-Tree?

texts:
What is a good metric to pick the degree of a B-Tree? I assume this depends on the number of expected elements? Degree 2 gives us a 2-3-4 tree (each node contains 1-3 items and 2-4 children).

How can I decide this? I am looking to store a couple of thousand keys in it.


texts:
Can anyone explain how to find the $\Theta()$ of this equation...
$$T(n) = 3T(n-4) + cn$$
When I solve this problem I get this using the $k$ -th iteration...
$$T(n) = 3^{k}T(n-4k) + 3^{k-1}c(n-2(k-1)) + 3^{k-2}c(n-2(k-2)) + ... + cn$$
I factor out c and get this...
$$T(n) = 3^{k}T(n-2k) + c(3^{k-1}(n-2(k-1)) + 3^{k-2}(n-2(k-2)) + ... n)$$
I'm not sure if we need to find an upper and lower bounds or solve the geometric series. Any suggestions? I need to find $\Theta()$ and we didn't cover master theorem so this is how my class was taught to approach these.


texts: Prove that $H$ reduces to $H\varepsilon$

texts:
I have to prove that $H_\varepsilon = \{<M> \mid M\ \text{halts on input }\varepsilon\}$ reduces to $H$ (the halting problem).

I am very confused how to PROVE it, I mean it is clear that we can take a TM $M$ that decides $H$ and then build a TM $M\varepsilon$ that decides $H\varepsilon$ by taking the input $<M1>$ and simulating $M$ on input $(<M1>, \varepsilon)$, then accepting when $M$ accepts.

But how do I prove I can do that, how do I prove that this mapping from $H$ to $H_\varepsilon$ exists?


texts:
What is the correct term for the maximal running time of a given algorithm on all inputs of length bounded by given $n$, on which the algorithm halts?  Assume, if necessary, that the halting problem of the given algorithm is decidable (with unknown complexity).

How is this time function of $n$ called?  Is it studied in complexity theory, or does one only consider the running time of universally halting algorithms?


texts: Direct and Associate Cache - Offset, Index, and Tag

texts:
I have two questions:

An 8-kB (8192 bytes) direct-mapped cache has 16-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

A 16-kB (16384 bytes) 4-way set associative cache has 8-byte lines.
The system has 64-bit addresses numbered from 0 on the right to 63 on the left.
Which bits are associated with the offset, index, and tag?

For offset, it's: tag bits = address bit length - exponent of index - exponent of offset, correct?

Then the Index for a direct mapped cache is the number of blocks in the cache, and the Tag bits are everything else, right?

How would I calculate these? Because I'm a little confused on an associated cache vs a direct-map cache.


texts: I know the algorithms, but i still don't know how to approach the questions

texts:
I study Graphs Analysis by myself and i understood most of the material just fine. But, there is one huge problem with my approach that prevents me from solving tests. I don't know how to build new Graphs based on requirements and i'll give an examples:

Question: G = (V,E) is a directed graph with no cycles (DAG) and w: E->R for each edge. There is an efficient algorithm that in given vertices s and t in the graph it finds the minimum weight path contains with at least 3 edges.
So far it great - i understand the question just fine.

Step 1:  For each vertex v in V, we mark:
v1 = (v, 1), v1 = (v, 2), v3 = (v, 3), v4 = (v, 4)

Given G = (V, E), we'll build new graph G'=(V',E') where:
V'={v1, v2, v3, v4| for each v in V}

E' = {(v1, u2), (v2, u3), ____(1)____}

for each (ui, vj) in E', w(e) = {w(u, v)| (u, v) in E and (ui, vj) in E'}

(1) = ?

a. (v3, u4), (v4, u4) - the correct answer

b. (v3, u3)

c. (v3, u4),(v4, u3)

d. (v3, u4)

step 2: Apply DAG algorithm from s1.

step 3: return the weight of the path from s1 to t4.

I know how DAG works, but i don't know how to build the new graph in order to see it, how do i build the new graph?

i don't need to know what to do in every situation, i just don't know how to deal with it and build a new graph according the demands. The steps are derived from the question itself, but i didn't get the first step in the creation of the new graph. Why there is a need to create a new graph at all?


texts:
I'm currently trying to improve my algorithm skills and I was trying a simple algorithm :
Given a list of integers. We want to find the one that is the closest to 0. If we have a number and his opposite, we want to return the positive one.
My current complexity on this algorithm is O(n). Is it possible to get a lower one ?
My current solution looks at all the values. I was thinking about a binary search, but we're not looking for a specific number, and the list of integers is not sorted.
Thanks for the help !


texts: Determining whether $L^*$ is a finite union of $L^n$ for unary regular $L$

texts:
Give an algorithm that, given an NFA over a one-letter alphabet, determines whether the language it generates has the property that for some $n$, $$ L^* = \bigcup_{k=0}^n L^k. $$

I need some tips how to solve that.


texts:
The Computer Science text book I own describes how an interrupt is handled in an operating system:

At some point at the end of an instruction the processor checks if there are any outstanding interrupts
If there are, the priority of the present task is compared with the highest priority interrupt
If there is a higher priority interrupt, the current job is suspended
The contents of the special registers are stored so that the job can be restarted later (aren't general purpose registers preserved as well? or do ISRs do not use these?)
Interrupts are then serviced until all have been dealt with
Control is returned to the original job
If the current task has more priority than the interrupt, it is queued and serviced later

The last point "If the current task has more priority than the interrupt, it is queued and serviced later". Does this mean that if an I/O interrupt is generated but the current tasks are all very high priority, they will not get serviced (ignored)? moreover, how does the computer determine when to service these if the current task is more "important"?


texts: Arguing that $L= \{a^n | n\geq 0\} \cup \{a^nb^n| n\geq 0\}$ is not $LL(k)$ for any $k$

texts:
Consider the language  $L= \{a^n \mid n\geq 0\} \cup \{a^nb^n\mid n\geq 0\}$ and the following statements.
$\quad\quad\text{I. }L$ is deterministic context-free.
$\quad\quad\text{II. }L$ is context-free but not deterministic context-free.
$\quad\quad\text{III. }L$ is not $LL(k)$ for any $k$.
Which of the above statements is/are TRUE?
$\quad\quad\quad$ A. $\text{I}$ only
$\quad\quad\quad$ B. $\text{II}$ only
$\quad\quad\quad$ C. $\text{I}$ and $\text{III}$ only
$\quad\quad\quad$ D. $\text{III }$ only
(GATE-CS-2020)

My doubt is only regarding a part of the above question, i.e. arguing about statement $\text{III}$.
Most of my mates are arguing as :

"Since $a^n$ for any arbitrary $n$, on just seeing $a^n$ on the input we cannot decide whether it is a part of $a^m$ or $a^mb^m$ for $m>n$ so the language is not $LL(k)$ for any $k$ since we cannot have an arbitrary or finite $k$ ".

But while reading the automata text by Peter Linz I came across an example as:

Example 7.11  The grammar $$S \rightarrow SS |aSb| ab$$
not an $LL (k)$ grammar for any $k$.

The above grammar in the Linz text is the grammar generating the positive closure of $\{a^nb^n|n\geq 1\}$ or simply it generates the set of strings having well formed parenthesis structure.
Now here the thing to be noted is that : Linz talks about the "grammar" not about the language as a whole. Talking about the language seems a bit difficult to me.
The author says that the "grammar" is not $LL(k)$ for any $k$ with the following argument:

To see why this is so, look at the derivation of strings of length greater than two. To start, we have available two possible productions $S \rightarrow SS$ and $S \rightarrow aSb$. The scanned symbol does not tell us which is the right one. Suppose we now use a look-ahead and consider the first two symbols, finding that they are $aa$. Does this allow us to make the right decision? The answer is still no, since what we have seen could be a prefix of $a$ number of strings, including both $aabb$ or $aabbab$. In the first case, we must start with $S \rightarrow aSb$, while in the second it is necessary to use $S \rightarrow SS$. The grammar is therefore not an $LL (2)$ grammar. In a similar fashion, we can see that no matter how many look-ahead symbols we have, there are always some situations that cannot be resolved.

The above explanation which my mates gives, quite matches with that of Linz, but the difference is that my mates are talking about the language and Linz talks about the grammar.
I came up with a grammar for the language in $\text{GATE-CS-2020}$ paper.

$$S\rightarrow S_1 | S_2$$
$$S_1 \rightarrow aS_1 b | \epsilon$$
$$S_2\rightarrow aS_2| \epsilon$$

which is not $LL(k)$ for any $k$ using similar logic as in Linz text. But proving that a grammar is not $LL(k)$ for any $k$ does not say anything about the language, as Linz says:

This observation about the grammar does not imply that the language is not deterministic or that no LL grammar for it exists.

then Linz removes the problem with the grammar and comes up with a "more not obvious form" (but does not explain how) which is $LL$ and equivalent to the original grammar in example 7.11

$$S_0 \rightarrow aSbS $$
$$S \rightarrow aSbS| \epsilon$$

So given such a question about the "language" as in the $\text{GATE-CS-2020}$ paper, how should one proceed? Or what should be the thinking approach?


texts: Algorithm: Dimension increase in 1D representation of Square Matrix

texts:
Consider the matrix with dimension $m \times m$:

$$
M =
\begin{array}{cc}
1 & 1 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
$$

Its 1-D representation:
$$ M^* = \begin{array}{cc} 1 & 1 & 1 && 0 & 1 & 1 && 1 & 0 & 1\end{array}$$

Now, another dimension added, so that the matrix becomes:

$$
N =
\begin{array}{cc}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{array}
$$

$$ N^* = \begin{array}{cc} 1 & 1 & 1 & 0 && 0 & 1 & 1 & 0 && 1 & 0 & 1 & 0 && 0 & 0 & 0 & 1\end{array}$$

Update
The data structure can be any linear data structure (Array, Single LL, Double LL) not necessarily contiguously linear. The goal is to dynamically add or remove dimensions from the Matrix with least number of operations.

The best I can think of is to repopulate $N^*$ in $\theta(N^2)$ every time a new dimension is added.


texts: Would using mouse position in the below scenario generate true random numbers?

texts:
I'm having trouble wrapping my head around random number generation so I figure it would be better to ask now, rather than screw up later.

Let's say I want to write a function that generates a random lucky number from 0-9 when the user clicks on a button.

I'm thinking of using the last digit of the multiple of the x and y coordinates of the click position as the output.

Assuming that the user have no intention of gaming the output, would this be true randomness because there's no way for a 3rd party to predict where on the button the user will click next?


texts: O(nlogn) or O(n) alternative for Needleman-Wunsch algorithm

texts:
So I am a computer science student and I was recently looking at the subject of comparing DNA sequences.
Probably the most widely used algorithm is the Needleman-Wunsch algoirithm and while it might be suitable for most cases, It bothers me that an $O(n^2)$ algorithm is used to compare large batches of text, both from the time and required space perspective. The space requirement bothers me the most, considering the number of nucleotides that need to be compared in a typical application, taking up gigabytes if not more memory.
Although some improvements are made to the algorithm, making it up to 80% faster (the FOGSAA algorithm) I still think that I am missing something. Are there any algorithms for this problem that run faster than $O(n^2)$ asymptotically? From the application perspective - are non-square algorithms used in the field?
I was thinking suffix trees might be useful for this but as far as I know they are only used for sequencing, not comparing sequences.


texts: Where to get graphs to test my search algorithms against?

texts:
I am implementing a set of path finding algorithms such as Dijkstra's, Depth First, etc.

At first I used a couple of self made graphs, but now I'd like to take the challenge a bit further and thus I'm looking for either

graphs used in benchmarks;
graphs of real world cities (or a way to download that kind of info off google maps, or any other kind of source, if possible).

I'd like those sources to either have or allow me to easily create frontiers such that I can try my algorithms for different sized sets of graphs, if possible.

I'm looking for simple solutions, as I'd prefer not to be diverted from main goal (compare a set of different algorithms), so I'd need a quick way to convert that graph data into my own format (basically, a set of connected (x, y) points).

To be more concrete, what I'm looking for are 2D cyclic graphs. If those graphs reflect real world city streets (taking into consideration one-way streets, two-way streets, etc, better yet!).


texts: Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

texts:
I tried to solve the above NP-completeness exercise by making a bipartite graph from a general one (undirected) by inserting a vertice in the middle of every edge of the first (general) graph. This generates problems as suggested here: Finding the flaw in a reduction from Hamiltonian cycle to Hamiltonian cycle on bipartitie graphs
Anyone can give a hint on how to make a bipartite graph from a general one without using the above method and how the hamiltonian property can be passed to it?


texts: Is randomly building a BST different from random sampling whole trees?

texts: What is the difference between a randomly built binary search tree (using n keys )and choosing a binary search tree (of n key) from a random distribution


texts: What is the query complexity of the following quantum search algorithm?

texts:
Problem statement: The search space A involves elements $|0\rangle $, $|2\rangle$... $|d-1\rangle$. An oracle is provided for the function $f(x)$ where

\begin{align}
f(x)&=1 \quad x=x^{'}\in A \\
f(x)&=0  \quad x \neq x^{'}
\end{align}

The aim is to find $x^{'}$.
We have an oracle U corresponding to $f(x)$ whose action is the following
$$|x\rangle |y\rangle \rightarrow |x\rangle |y \oplus f(x)\rangle$$
We can consider the search space as the states of a d-level quantum system. If we input the superposition

$$
\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1} |x\rangle \otimes |\phi\rangle
$$
 where $|\phi\rangle=\omega^d|0\rangle+\omega^{d-1}|1\rangle+\cdots + \omega|d-1\rangle$, $\omega=e^{\frac{2\pi i}{d}}$ is the $d^{th}$ root of unity into the oracle corresponding to $f(x)$, using phase kickback we can create the superposition

$$
|\Psi\rangle=\frac{1}{\sqrt{d}}\sum_{x=0}^{d-1} \omega^{f(x)}|x\rangle.
$$

Let us write $|\Psi\rangle$ as
$$
|\Psi\rangle=\sum_{x=0}^{d-1} c_x|x\rangle$$
where $c_x=\frac{1}{\sqrt{d}}\omega^{f(x)}$.

We can use quantum state tomography (for example using weak value measurements as described in this paper) to find the coefficients $c_x$. The $|x\rangle$ corresponding to $c_x=\frac{\omega}{\sqrt{d}}$ is the required search result.

But, quantum tomography requires an ensemble of the unknown quantum state so as to reduce the statistical error.

Suppose $M_0$ is the required size of the ensemble such that the error in the measurement is small enough to determine the search result $x^{'}$. This requires $M_0$ identical copies of $|\Psi\rangle$. But, as the state $|\Psi\rangle$ is unknown according to No-Cloning theorem we cannot make copies of $|\Psi\rangle$ using $|\Psi\rangle$ alone. Hence, the ensemble has to be made by querying the oracle $M_0$ times with the uniform superposition (4). But, note that $M_0$ is decided on the basis of the acceptable amount of error in the tomography process and hence it does not scale with the size of the search space A.

From this can I conclude that the query complexity of this algorithm is O(1)?


texts: Solving or approximating recurrence relations for sequences of numbers

texts:
In computer science, we have often have to solve recurrence relations, that is find a closed form for a recursively defined sequence of numbers. When considering runtimes, we are often interested mainly in the sequence's asymptotic growth.

Examples are

The runtime of a tail-recursive function stepping downwards to $0$ from $n$ whose body takes time $f(n)$:

$\qquad \begin{align}
  T(0) &= 0 \\
  T(n+1) &= T(n) + f(n)
 \end{align}$
The Fibonacci sequence:

$\qquad \begin{align}
  F_0 &= 0 \\
  F_1 &= 1 \\
  F_{n+2} &= F_n + F_{n+1}
 \end{align}$
The number of Dyck words with $n$ parenthesis pairs:

$\qquad\begin{align}
    C_0 &= 1 \\
    C_{n+1}&=\sum_{i=0}^{n}C_i\,C_{n-i}
  \end{align}$
The mergesort runtime recurrence on lists of length $n$:

$\qquad \begin{align}
  T(1) &= T(0) = 0 \\
  T(n) &= T(\lfloor n/2\rfloor) + T(\lceil n/2\rceil) + n-1
 \end{align}$

What are methods to solve recurrence relations? We are looking for

general methods and
methods for a significant subclass

as well as

methods that yield precise solutions and
methods that provide (bounds on) asymptotic growth.

This is supposed to become a reference question. Please post one answer per method and provide a general description as well as an illustrative example.


texts: Question about non recursively enumerable language

texts:
Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?

In other words, let $R$ be the set of languages (including languages over alphabet having infinite symbols).
For all $L$,  belonging to $R$,  that are not recursively enumerable, can it be said that $L$ is uncountable?

Is any language (in the set $R$ defined above) recursively enumerable and uncountable?

NB : I am asking about the (un)countability of a language (set of strings) and not a set of languages.


texts: Proving existence of a language $L\in DTIME(n^{\log n})$ which is not in $Avg-P$

texts:
I'm struggling with the following question:

Define $Avg-P$ the class of all languages $L$ for which there exists a polynomial time Turing Machine $M$ such that for every $n$, for all but $\frac{2^n}{n}$ of the $2^n$ strings of length $n$, $M$ gives the correct answer to whether $x\in L$ or not.
Prove that there exists $L\in DTIME(n^{\log n})$ which is not in $Avg-P$.

My attempt: I thought about using diagonalization. First we enumerate all Turing Machinges $M_1,M_2,M_3,...$. Now we define the following TM: for input $x$ of length $n$, simulate $M_n$ on input $x$ for $n^{\log n-1}$ steps. If the simulation halted, answer the opposite. Otherwise, reject. Now lets define $L(T)=L$. It's easy to see that $L\in DTIME(n^{\log n})$. Now let's assume towards contradiction that $L\in Avg-P$. Then there exists $M_i$ that gives the correct answer to whether $x\in L$ for all but $\frac{2^i}{i}$ of the $2^i$ strings of length $i$. But because $T$ simulates $M_i$ and answers the opposite, this is a contradiction.

The problem: I didn't find a way to make sure the simulation indeed halts for $M_i$, and answers the opposite as wanted. Any ideas how I can fix this solution/solve in another way?


texts: Show that run time complexity of operations on 2-4 tree is $O(\lg n)$

texts:
I just studied about this 2-4 tree which is a self-balanced tree. Various sources and textbook often mentioned that the insertion, deleting and searching of this tree is $O(\lg n)$.

However, none of them explain the detailed reasons for that run-time complexity. Neither of them also explains them mathematically for the reason behind that run-time complexity.

Therefore, I would like to ask how do i basically show that the run time complexity to process a 2-4 with n keys is $O(\lg n)$?


texts:
While doing the multiplication 1.4*0.8 in a python program, I got the result as 1.1199999999999999.

Why didn't I get 1.12 exactly?

In C programming language, the same expression gives 1.1200.


texts: Can only information(data) be stored in ram?

texts: Basic question, but is only information/ data stored in ram? Are computer files such as a word file considered information/ data? This is one of the questions in a summer assignment for ap computer science.


texts:
I have calculated the boolean functions for $r$ and $f$:
$f = \overline{s_1} \cdot s_0 + s_1 \cdot \overline{s_0}$.
$r = \overline{s_0 \cdot s_1 \cdot s_2 \cdot s_3}$.
Do you have an idea what an application for this circuit can be? I don't know where we would use it.


texts: When to use Context-(in)Sensitive Inter-procedural Data Flow Analysis

texts:
I've been exploring the differences between Context Sensitive Analysis (CSA) and Context Insensitive Analysis (CIA), members of inter-procedural static analysis.  The problem I'm coming up against is when to use one over the other.

Namely, suppose the following context:

The input program is in Static Single Assignment form.  We have a machine that has no memory hierarchy.  All it can do is store things in registers.  We want host languages to support functions, including non-tail recursion.  Which is to imply, when we call a function, we need to save all variables live across the function into registers and then calculate space requirements to see if we have enough registers to execution the function.

To do so, we need to use both CIA and CSA.  Though I'm not entirely sure why that is the case.  I've speculated a few ideas:

reaching definitions require a tighter bound,
invalid paths through recursion could ruin analysis,
there is some dark magic here that I'm unaware of.

But ultimately, given the context, I'm not sure why we need both CSA and CIA to compute space requirements across function calls.


texts: What is the complexity of classification with SVMs?

texts:
I'm interested in how fast SVMs can classify new data with $c \in \mathbb{N}_{\geq 2}$ classes and $n \in \mathbb{N}_{\geq 1}$ features.

Example for Neural Networks

For neural networks, this depends very much on the architecture. For supposing you only have one hidden layer with $3n$ neurons, you would have a $n:3n:c$ topology and hence

one multiplication of a $n$-dimensional vector with a matrix in $\mathbb{R}^{n \times 3n}$,
then a multiplication of a vector in $\mathbb{R}^{3n}$ with a matrix in $\mathbb{R}^{3n \times c}$
and of course $3n+c$ applications of the activation functions.
Adding the biases is dominated by the matrix multiplications.

This results in an overall complexity of $\mathcal{O}(n^2 \cdot c)$.

Question

I would be interested in a similar analysis of the classification complexity (NOT the training!) of SVMs, preferably with a reference to literature.


texts: Analog of PP for computability rather than complexity?

texts:
The complexity class PP can be defined in many ways, one of which involves randomness - a language $L$ is in PP if there is a polynomial-time, randomized TM $M$ such that $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2.

I'm curious whether there is a name for the complexity class that can be obtained by relaxing the definition so that the randomized TM doesn't necessarily have to run in polynomial time. Specifically, consider the class of languages $L$ such that there is a TM $M$ where $w \in L$ if and only if the probability that $M$ accepts $w$ is greater than 1/2. There is no requirement that this TM halt on all inputs.

Where does this class of problems lie? This class contains RE because any recognizer accepts a string $w \in L$ with probability 1 and accepts any string $w \notin L$ with probability 0. I doubt that it's equal to RE, though, since I can't see how you could convert this "majority recognizer" for $L$ into an actual recognizer for $L$. I tried placing it somewhere in the arithmetical hierarchy, but I don't see how to encode the concept "more than half of the computation branches accept" into some first-order formula involving alternating quantifiers.

Does this class of problems already exist and have a name? If so, what is it?

Thanks!


texts: Turing Machines: Arbitrary alphabet equivalence with binary alphabet

texts:
Think of an $n$-ary alphabet as $\{0, 1, ..., n-1, n\}$. For example, a binary alphabet is $\{0, 1\}$.

  Do Turing Machines with binary alphabets decide the same set of languages as Turing Machines with $3$+ symbol alphabets?

I am unsure of how to show equivalence. Clearly, any $3$+ symbol TM can simulate a TM with $2$ symbols, but I don't know how to show the other direction (if one exists).


texts: Efficiently enumerating all paths from i to j of given length in a graph

texts:
I've been trying to efficiently solve this problem : given a integer p > 0 and a directed graph whose nodes are 0, ..., N-1, enumerate (not simply count) all the paths (not necessarily elementary) from a node i to a node j of length p. For instance, i->j is of length 2 if the edge i->j exists, i->k->j is of length 3, etc...). The graph is either given as an adjacency matrix or adjacency lists.
In my very special case, I'm searching for cycles 0->...->0 of given length, but I'm pretty sure I'm gonna need the more general case i->...->j.

Right now, I'm dynamically storing paths from k to j of length q in a matrix Z[k][q], and since I need Z[i][p], I first compute all the Z[j][p-1] for i->j, then append i to them.

The problem is that this approach uses an awful lot of memory and doesn't scale very nicely for large graphs. Any advice on this ?


texts: How can I convert a list with duplicates into a set for a reduction to the set cover problem?

texts:
I'm trying to come up with a reduction for a problem whose description is more or less identical to the first problem given here.

Here's a condensed version of the problem:
You're given a collection of refrigerator magnet letters that may contain duplicates. You have a limited vocabulary of words made of combinations of those letters (again, a word may contain the same letter twice). Can you choose words from the vocabulary to build with the magnets such that all of the magnets are used and each magnet is used in only one word?

It's suspiciously similar to the set cover problem, so I've been trying to come up with a way to convert (in polynomial time) a collection of symbols that potentially contains duplicates into a set. This would allow the collection of symbols to be used as U and the child's vocabulary to be used as S for set cover.

I've had no luck so far, so a hint or even a suggestion for a more appropriate NP-complete problem to reduce to would be greatly appreciated.