texts: Why is my trivial reasoning for $PSPACE = PH$ wrong?

texts:
If $\sum_i^p$ denotes $ith$ polynomial hierarchy. And $\sum_i TIME( T(n) )$ denotes set of languages accepted by $T(n)$ time alternating Turing machine $M$ whose initial state is labeled $\exists$ and sequence of choices leads $M$ to change at most $i-1$ times from states with one label to another.

Then I know $\sum_i^p= \cup_c\sum_i Time ( n^c)$. Then by taking summation on $i$ both sides we get $PH=\cup_i \sum_i^p=\cup_i\cup_c \sum_i TIME(n^c)=\cup_c\cup_i \sum_i TIME(n^c)=\cup_c \sum_i TIME(n^c)=\cup_c \ TIME(n^c)=AP=PSPACE$
where $AP=\cup_c ATIME(n^c)$ ie. set of languages having polynomial runtime using an alternating Turing machine.
Thus we get $PH=PSPACE$, which I know does not have a proof. I am misunderstanding something trivial, but cant figure out what ?


texts: Efficient algorithm to approximate membership in a set of strings

texts:
I devised an algorithm / data structure and I would like to ask whether it already exists. The problem statement is: after having added some number of strings to the set, determine whether a given string is definitely not in the set. I have attempted searching it but discovered no similar algorithm.For reference, I'll name the set I devised Blake Set.

The set supports add and query operations however no removal operation. The query operation can either return 'value definitely not in set' or 'value possibly in set'. In this sense, the set is similar to a Bloom Filter in behaviour - though it operates entirely differently.

A Blake Set is represented as a singly linked list of size m where m is the number of characters in the longest inserted string. Each node stores a sequence of $k$ bytes, all initially zeroed, where $k$ is the number of different values for characters divided by four. For instance, if we were to store ASCII-strings $k$ would be 256/4 = 64. Additionally, every character must have a number associated with it that is at least 0 and at most $4k - 1$ hence every character has an unique number that can act as a valid index in an array of length $4k$

Adding a string s to the set works as follows:

for every character c in s
    let i be the index of c in s
    let v be the i-th node in the singly linked list
    let id be the number associated with c
    set the id-th high-order bit in v to 1
    if c is the last character in s
        set the id-th low-order bit to 1

So the first half of the number in any node stores whether a given character has been added and the second half stores whether it was the last character in the string. Subsequently, to query whether a given string $s$ is in the set, we perform the following operation:

for every character c in s
    let i be the index of c in s
    let v be the i-th node in the singly linked list
    let id be the number associated with c
    if the id-th high-order bit in v is not set
        return false
    if c is the last character in s and the id-th low-order bit in v is not set
        return false
return true

If a character's corresponding bit in any node is not set, its string was never added. The same is true for checking the last character. The second half of the byte sequence is not necessary but it decreases the probability for a false positive. It should be trivial that the time complexity is $\mathcal{O}(m)$ ($m$ being the size of the longest added string) as we perform a constant number of operations for every character. The space complexity is also $\mathcal{O}(m)$ as we always store $m$ nodes with constant size in the singly linked list.

The set described has some similarities with the bloom filter in terms of querying but the two structures are certainly different. Do any algorithms that you know match the description that I have given?


texts: Check whether it is possible to turn one BST into another using only right-rotations

texts:
Given two binary search trees T1 and T2, if it is possible to obtain T2 from T1 using only right-rotation, we say that T1 can be right-converted to T2. For example, given three binary search tree T1, T2 and T3:

For example, given three binary search tree T1, T2 and T3:

 Tree 1                Tree 2              Tree 3
    a                    b                   a
   /                    / \                 /
  b                    d   a               d
 / \                      /                 \
d   c                    c                   b
                                              \
                                               c

T2 can be right-converted from T1, T3 can be right-converted from T1. But T3 cannot be right-converted from T2, T2 cannot be right-converted from T3.

Given two arbitrary BST, how to determine whether they are right-convertible with respect to each other?


texts: Hamiltonian path greedy and anti-greedy algorithms

texts:
I had this question on a problem set recently, but I wasn't sure how to solve it.
Given a complete weighted undirected graph $G$, here are two "algorithms" to find a Hamiltonian path:

greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with smallest weight
anti-greedy: start at one vertex at random, and greedily choose the edge that leads to an unvisited vertex with largest weight

The question is, does there exist a $G$ so the anti-greedy algorithm is better than the greedy algorithm (smaller path weight)?


texts:
Let sensitivity be defined as in Sensitivity and Block sensitivity

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose average sensitivity is $O(\log n)$?

Is there an example of a boolean function in $n$ variables that depends on all $n$ inputs whose sensitivity and average sensitivity is $O(\log n)$?


texts: Decide whether a context-free languages can be accepted by a deterministic pushdown automaton

texts:
Given a context-free grammar G, there exists a Nondeterministic Pushdown Automaton N that accepts exactly the language G accepts. (and visa versa)

There may also exist a Deterministic Pushdown Automaton D that accepts exactly the language G accepts too.  It depends on the grammar.

By what algorithm on the productions of G can we determine if D exists?


texts: Linear time algorithm for finding $k$ shortest paths from $s$ to $t$

texts:
Definition. Given a graph $G=(V,E)$ and two vertices $s$ and $t$,
  the $k$-shortest-paths problem is finding the $k$ shortest simple paths
  between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem.

I have looked at a few papers in the literature, such as "A New Implementation Of Yen's Ranking Loopless Paths Algorithm" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "Finding the k shortest paths" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem?


texts: Algorithm for minimizing the number of "inversions" in a graph

texts:
Given the following graph:

With the assumptions below:

A node on the left is linked to several nodes on the right
Nodes on the right are paired together: one is black, one is white
Each pair of nodes on the right can be swapped (black becomes white and white becomes black)
A node on the left is green if linked to only white or only black; red if linked to two colors.

The idea is to minimize the amount of red nodes, by flipping some black and white nodes. What is the best algorithm to do that?

(I think this problem has something to do with some sort of cycle detection? This problem is probably well-known on some equivalent form.)

Of course it will be often impossible to make all nodes green; here node V can never be (it is linked to B0 and B1). Some cycles also make all green impossible.

Extra question — same as above, but with a weight associated to each edge. Minimize the sum (for each node) of absolutes delta between white and black (difference between the sums of weights for white and black for each left node).

Where does this problem comes from?

A transit network is composed of stops, routes and trips.

Each trip belongs to one route
Each trip has one natural direction (0 or 1, inbound/outbound)
Each trip goes through a list of stops.
The direction of all trips within a route is arbitrary; so it is possible to invert the direction of all trips of a given route (but all trips together).

If all trips passing through a stop do have the same direction (all 0 or all 1) we can compute a "natural" direction for the stop. Otherwise we cannot. The idea is to flip route trips direction to minimize the number of stops where we cannot compute this "natural" direction.

Here the nodes on the left are stops, pair of nodes on the right routes, with black/white all trips for each route direction.


texts: Regarding Turing Machine Halting Problem

texts: All problems solved by standard today's general purpose computer can be solved by standard Turing machine.As general purpose computer can't do more than Turing machine so The Turing machine halting problem must also be  unsolved by today's general purpose computer.How can I realize the fact that halting problem can't be solved by todays general purpose computers.


texts: Binomial basis and the usual basis of polynomial algebra $\mathbb C(X)$

texts:
Consider the polynomial algebra $\mathbb C[X]$. Then the set $\{1, X, X^2,\dots,\}$ forms a vector space basis for this algebra. In general, we know that the set $\{P_n(X) \in \mathbb C[X]: n \ge 0 \text{ and  degree}(P_n) = n\}$ forms a basis. We consider the binomial basis defined as follows: $\binom{X}{n} = \frac{(X-n+1)(X-n+2)\cdots (X)}{1 \cdot 2 \cdot \, \cdots \, \cdot n }$.  Then $\binom{X}{n}$ is a polynomial of degree $n$. Therefore $\{\binom{X}{n}: n \ge 0\}$ is yet another basis for $\mathbb C[X]$. I have the following questions.

Is there any instance where the binomial basis is preferred over the usual basis?
Is there any algorithms to switch between the usual and binomial basis?
Is there any paper where they talk about the computation complexity of converting a polynomial expanded in binomial basis to the usual basis? Kindly share some references.

I have Theorem 1 and 2. Theorem 1 gives an expression for a polynomial in the usual basis and Theorem 2 gives an expression for the same polynomial in the binomial basis. I have to justify Theorem 1 is computationally preferred to calculate the polynomial over Theorem 2. But I am not sure how to approach this.
Thank you for your valuable time.


texts: Constructing a new graph. G'. What does it mean v ∈ S_{i+1}?

texts:
John lives in a city whose streets has the same length. His apartment is located at a specified node H. John need to do his  errands where he visits each of k different shop in order. However, each store have more than one location in his city. More particularly, for each 1 ≤ i ≤ k there is a set $S_{i}$ of vertices at which a branch of the $i^{th}$ shop is located (you can assume that the $S_{i}$ are disjoint). Construct a new graph G' as following:

  Create a new graph G' whose nodes are given by both a node of G,
  representing John’s current location, and a number 0 ≤ i ≤ k, giving the number of stops that John has successfully made. In particular, the vertices of G' are exactly given by (v, i) with v ∈ Node and i ∈ {0, 1,..., k}.  Edges in G' are between (u, i) and (v, i) if (u, v) is an edge of G, or between (u, i) and (v, i + 1) if (u, v) is an edge of G and v ∈ $S_{i+1}$.

What does it really mean by "between (u,i) and (v,i+1) if (u,v) is an edge of G and V v ∈ $S_{i+1}$"?

Let's say we have simple graph G as below:

Here is my attempt of constructing the new graph G'.

How many new nodes do we need to make, 3  or 4 copies? I only make 3 so far since there are only 3 errands. Please let me know if my G' is correct. Thank you.


texts: Can someone explain me the Credit-Debit proof method for calculating operations?

texts:
I've started taking a data structure course and we are currently learning about different data structures. We also learned when to increase the capacity of an array by creating another array with double the size of the original one.

The proof used to demonstrate this was a credit-debit proof where each operations has a cost. ex: doubling an array cost 2 dollars reducing an array by half cost 1 dollar.

I simply don't understand how proof of that type works. Doing a quick online search I haven't find the term credit-debit used to refer to this. Maybe It's not its name? Would be nice if someone could give me some links that explain those proofs.


texts: Asymptotic order of a recursive function

texts:
\begin{gather*}
T(n)=T(\frac{n}{\log n})+O(1)
\end{gather*}
\begin{gather*}
T(1)=O(1)
\end{gather*}
I try to use substitution method to solve $T(n)$, but because of $\log n$ get stuck. Can we use substitution method for solving $T(n)$?
My attempt:
One step of my extending of $T(n)$:
\begin{gather*}
T(n)=T(\frac{n}{\log n})+O(1)=T(\frac{\frac{n}{\log n}}{\log \frac{n}{\log n}})+O(1)+O(1)
\end{gather*}


texts: Expressing the condition as a set of linear constraints

texts: Express the condition "$x = 0$ if and only if $y = 0$" as a set of linear constraints, where $x,y$ are integers such that $ - 5 \le x \le 8$ and $0 \le y \le 1$


texts: Intersection and union of a regular and a non-regular language

texts:
Let $L_1$ be regular, $L_1 \cap L_2$ regular, $L_2$ not regular. Show that $L_1 \cup L_2$ is not regular or give a counterexample.

I tried this: Look at $L_1 \setminus (L_2 \cap L_1)$. This one is regular. I can construct a finite automaton for this: $L_1$ is regular, $L_2 \cap L_1$ is regular, so remove all the paths (finite amount) for $L_1 \cap L_2$ from the finite amount of paths for $L_1$. So there are a finite amount of paths left for this whole thing. This thing is disjoint from $L_2$, but how can I prove that the union of $L_1 \setminus (L_1 \cap L_2)$ (regular) and $L_2$ (not regular) is not regular?


texts: Is it possible to simulate/emulate non-euclidean geometry using computer graphics?

texts: I am aware of the frequent use of "smoke and mirrors" in order to achieve the effect of non-euclidean geometry, but I was wondering it if it possible to implement spherical (sometimes called elliptic) and hyperbolic geometries.  If so, how would we do that?


texts: Show this function is partially computable

texts:
Let B(x) be a computable predicate. Show that
\begin{equation}
G_B(r)=
\begin{cases}
1 \;\;\;\;\;\text{ if there are at least r numbers n such that B(k) = 1 }  \\
\uparrow \;\;\;\;\; \text{ otherwise}
\end{cases}
\end{equation}
I want to write a program with just these four instructions to compute $G_B$(r)

\begin{array} \\
\;\;\;\;\;\;\;\;\;Y \gets 0 \\
\;\;\;\;\;\;\;\;\;\text{IF } X \neq 0 \text{ GOTO } A \\
[E] \;\;\;\text{ GOTO } E \\
[A]\;\;\;\; Y \gets Y+1
\end{array}

The book gives examples for writing programs to compute $G(x_1,x_2)$ but does not give any when predicates are involved. Could someone give just an example for even a completely different function with predicates or just point me in the correct direction.


texts: Algorithm chalenge: find minimum range to cover all houses with light

texts:
N houses are located on a straight street which has K streetlights. Each streetlight has range R. Given N and K how to find minimum value for R?
N is an array containing location of each house.
K is an integer value.
I am unable to identify the algo for this. I tried solving by taking location of 1st and last house, then dividing by K, this will give me max range of each streetlight. However, assume N=[3,4,5,10,13] and K=3. With division this wont work.


texts:
Consider a context-sensitive grammar $G$, such that all the productions of $G$ have the form $A\to \alpha$ or $Ab \to \alpha b$ (in other words, the left context is always empty and the right context is either empty or consists of just one terminal).

Is the language defined by such a grammar necessarily context-free ?

In all the toy examples I considered, the original context-sensitive grammar can be enlarged into an equivalent context-free one.


texts: Neighbourhood design in Variable Neighbourhood Search

texts:
Variable Neighbourhood Search (VNS) is a metaheuristic for solving (combinatorial) optimization problems. It iteratively explores growing neighbourhoods to find better local optima in each iteration.

I'm trying to apply VNS to a problem where a/the solution is represented by a finite vector in which each element is a finite strictly positive scalar (e.g. [1, 2, 6, 22, 6])

What are general guidelines for the design of neighbourhoods? How should neighbourhoods relate to each other? Can the quality of neighbourhoods be somehow measured? What are good references on this topic?

Maybe this could be a reference question.


texts: How is functional property guaranteed in type theory when function type is defined?

texts: I understand that functions are not defined in type theory the same way they are defined in set theory, hence functional property is not directly defined when defining function type in type theory. But I want to know which part of function type definition in type theory guarantees functional property even if it is done so indirectly and implicitly?


texts: Decidable properties of computable reals

texts:
Is "Rice's theorem for the computable reals" -- that is, no nontrivial property of the number represented by a given computable real is decidable -- true?

Does this correspond in some direct way to the connectedness of the reals?


texts:
I hope you could help me as you have done before (thanks again)

In a previous exam I saw this question; it is asked to identify if the language is Regular, CFL or Non CFL.

In my opinion this language is CFL... but, again my opinion is not good ! :/

I have think about the problem as followed :

For the first part (before the  intersection) the language is a^i b^j c^k | i != j or i != k or k != j. This is a CFL since it's the union of multiple CFL languages. Am I right ? (Thanks Draconis)

Then for the second part, this is also a CFL since I could easily write a CFG of it or a PDA.

Then the intersection, it means that now the language is :

{a^i b^j c^k | (i != j or i != k or k != j) and ( i = j ) }
==> {a^i b^j c^k | i = j != k}     <=== this is probably my mistake. (I don't understand why)

But my result is a CFL... unfortunately, my result is wrong.

Please help me to understant, my exam is soon and looking at my answer it doesn't look good...

Thnaks a lot in advance !


texts: Build a balanced binary tree from list in linear time

texts: I couldn't figure this one out. Given an unsorted list, we want to build a balanced binary tree (not a search tree, namely - left child is of lower key, and right child of higher key). Can we do it in linear time? Thanks!


texts: Complexity of exponential algorithm, optimised with memoization?

texts:
I was solving a problem, where one part of it was the following:

"Given a m-sided dice ([1,m] values) that will be rolled n times, calculate the possibility that the total sum of rolls will be higher than b"

Initially, I implemented a naive exponential solution, discovering the whole state space (DFS-like). Then, I realised that this algorithm repeats the calculation for a given number of remaining rolls and current sum. So, I optimised it, saving these calculations and using them later. For example, let's say we have a 4-sided dice that will be rolled 2 times (m=4, n=2). The below image shows the state space:

With green color are the values that were cached from previous computations and will be returned directly from memory. With red color are the values that will be normally computed. I have been trying to calculate the complexity of the algorithm:

The initial algorithm, where there is no "caching" of values, has obviously an exponential complexity of O(M^n)
The iterations needed for the optimised algorithm follow the below pattern:

For (m=4,n=2): 11 = 4 + 7 = 4 + [(4*2)-1]

For (m=4,n=3): 21 = 4 + 7 + 10 = 4 + [(4*2)-1] + [(4*3)-2]

For (m=4,n=4): 34 = 4 + 7 + 10 + 13 = 4 + [(4*2)-1] + [(4*3)-2] + [(4*4)-3]

...

This seems to be a mathematical sequence, but I can't calculate the exact formula. Any help much appreciated.


texts: How to teach abstraction needed for programming?

texts:
I experience that my students are fixed to compute with concrete values and are not keen to think in terms of general solution like creating a mathematical function $f(n)$ , needed to write programming functions f(n).

What is a good method of teaching them this lesson, becoming able to think in abstractions like functions on natural numbers?


texts: How to use Pumping Lemma for $L = \{www | w∈\{0,1\}^*\}$

texts: I'm trying to understand how to use a contradiction proof via the Pumping Lemma to prove a language is not regular. Everybody always uses examples like $\{ 0^n1^n | n>=0\}$, where it can be broken up into two parts $xy$ and $z$ and where these parts are different. How can I apply it to a language consisting of the concatenation of 3 identical strings?


texts: Does dijkstra works when I multiply weights of successive nodes

texts: Consider a complete bidirectional weighted graph. Weight of each edge (a,b) is the probability of getting from a to b. So all weights are in range (0,1]. Probability of going from a to b through the pass a-c-b is w(a,c)*w(c,b). So if I want to find the probability of getting to all the other nodes from a can I use multiplication instead of addition in dijkstra? Or should I convert multiplication to addition using log? More generally does dijkstra always work if the cost of the path always gets worse regardless of the function we use?


texts:
While familiarizing myself with polynomial hierarchy, I used this book which is written by Ingo Wegener. Now I'm practicing, and on page 132 I met this exercise:

Let us consider a Boolean formula $\phi$ on the variables $x_1, ...,x_n$. Each $n$ bit vector $\overline x \in \{0,1\}^n$ is a possible assignment to variables and these vectors can be naturally classified in alphabetical order. The ODD-SMALLER-SAT-DECISION  problem is to determine, being given $\phi$, if the smallest assignment $x$ which is satisfactory is such that $x_n = 1$.

How to prove that this problem is part of the complexity class $\Delta_2$?


texts: Maintain statistics over a sliding window (robust & efficient)

texts:
I am looking for an algorithms to maintain several statistics over a sliding window. The setup is as follows: There is a datastream consisting of (real value,timestamp) tuples. The values for the last x seconds are stored. In each iteration at least one new tuple arrives and between zero and more values are retired.
Now I want to maintain mean and variance without recomputing everything from scratch. There are methods if values are never retired, e.g. Welford's method. But what if values are retired?

The second problem I am facing is, how to compute covariance between two sliding windows in a similar fashion?

Are you aware of a solution or references?


texts: Is there any relationship between time complexity and space complexity of an algorithm?

texts:
For example:

If algorithm A takes an input of size n, and has a time complexity of O(a^n) and a space complexity of O(1)

Is there a way to increase the space complexity to something like O(n^2) that would guarantee that the time complexity would decrease?


texts: How a swapper manipulates entire processes in the operating system?

texts:
The below-given lines are written in the book of the operating system (Page -307), details of the book are as follows:
OPERATING SYSTEM PRINCIPLES, 7TH ED., Abraham Silberschatz, Peter Baer Galvin, Greg Gagne. Wiley India Pvt. Limited, Nov 27, 2006
"A lazy swapper never swaps a page into memory unless that page will be needed. In the context of a demand-paging system, the use of the term swapper is technically incorrect. A swapper manipulates entire processes, whereas a pager is concerned with the individual pages of a process. We thus use pager, rather than swapper, in connection with demand paging."
Can you please kindly explain how a swapper manipulates entire processes?


texts: From what I’ve read, the CPU has to send the data to the GPU before the GPU can do anything with it. But, if that’s the case, won’t any time saved using the GPU be negated by the time taken to transfer that data? Wouldn’t that kind of defeat the whole purpose of a GPU?


texts: Functor in category theory: The free theorem for fmap

texts:
According to nLab article:
https://ncatlab.org/nlab/show/functor

Definition
External definition
A functor $F$ from a category $C$ to a category $D$ is a map sending each object $x \in C$ to an object $F(x) \in D$ and each morphism $f : x \to y$ in $C$ to morphism $F(f) : F(x) \to F(y)$ in $D$, such that

$F$ preserves composition: $F(g\circ f) = F(g)\circ F(f)$ whenever the left-hand side is well-defined,

$F$ preserves identity morphisms: for each object $x \in C$, $F(1_x) = 1_{F(x)}$.

So, functor is often called "structure preserving".
However, there is an interesting article:
https://www.schoolofhaskell.com/user/edwardk/snippets/fmap

The free theorem for fmap
When we write down the definition of Functor we carefully state two laws:

fmap id = id
fmap f . fmap g = fmap (f . g)

These are pretty well known in the Haskell community.
What is less well known is that the second actually follows from the first and parametricity, so you only need to sit down and prove one Functor law when you go to supply a Functor!
This is a “folklore” result, which I've used in conversation many times before, but it continues to surprise folks, so I decided to write up a slow, step by step proof of this result as it is a fun little exercise in equational reasoning.
To prove this we're going to need the free theorem for fmap and a few lemmas.

So, my question is does this apply not only to the category of set and function composition but also category theory in general?
Thanks.


texts: What is the language generated by a given grammar

texts:
Given the grammar
  $s \to aSb \mid bSb \mid a \mid b$;
  what is the language generated by the grammar over the alphabet $\{a,b\}$?

When I was solving this question I was a bit confused
about  the language generated by this grammar. Would be set of all palindromes?
Or would the language generated by the above grammar be that of all odd length palindromes?

Is it possible that a palindrome generated by above grammar be of odd length only as there is no rule for $S \to \varepsilon$?


texts: Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

texts:
The following is the definition for Proximate Sorting given in my paper:
An array of distinct integers is k-proximate if every integer of the array is at most k places away
from its place in the array after being sorted, i.e., if the $i$th integer of the unsorted input array is the
$j$th largest integer contained in the array, then $|i − j| ≤ k$.
The following is the proof for time complexity of k-proximate insertion sort:
To prove $O(nk)$, we show that each of the n insertion sort rounds swap an
item left by at most $O(k)$.
In the original ordering, entries that are $≥ 2k$ slots apart must already be ordered
correctly: indeed, if $A[s] > A[t]$ but $t − s ≥ 2k$, there is no way to reverse the
order of these two items while moving each at most $k$ slots. This means that for
each entry $A[i]$ in the original order, fewer than $2k$ of the items $A[0], . . . , A[i−1]$
are less than $A[i]$. Thus, on round $i$ of insertion sort when $A[i]$ is swapped into
place, fewer than $2k$ swaps are required, so round $i$ requires $O(k)$ time.
My problem with the proof is this line : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are less than A[i]". The preceding statements just proved that $t-s < 2k$, otherwise the elements are sorted (as elements with distance greater than $2k$ cannot be swapped.) Isn't the correct statement : "This means that for each entry A[i] in the original order, fewer than 2k of the items $A[0], . . . , A[i−1]$ are greater than A[i]"?


texts: Why doesn't my object code/machine code contain 1's and 0's

texts:
I know when I compile my C program to machine code it gets compiled into something that specific computer can understand

But I thought computers can only understand 1's and 0's (high/low) so why doesn't my program look like a bunch of strange symbols and not 1's and 0's?

ie: "UHâÂHÉÏHç=7∞Ë1…âE¸â»HÉƒ]√êˇ%¶LçïASˇ%ÖêhÈÊ"

There must be one last piece I'm missing where these symbols get converted to 1's and 0's somehow


texts: First-order mutual-recursive functions Turing-complete or incomplete?

texts:
Assume we have a C-like programming language with no pointer/heap semantics (i.e. there is no concept of memory; everything is on the stack). The only datatype supported is Integer, but suppose the Integer is infinitely large (i.e. without 32-bit, 64-bit, or any size limit).
Is it true that this language is Turing-incomplete, but becomes complete if we add pointer/heap semantics (i.e. access to RAM-like memory)?


texts: Is the base of natural logarithms $e$ efficiently computable?

texts:
Is $e = 1 + \frac{1}{1!} + \frac{1}{2!} + \frac{1}{3!} + \frac{1}{4!} +\ldots$ efficiently computable? To be more specific, we say that a real number $r$ is efficiently computable if there is a polynomial time algorithm that takes a positive integer $C$ as input and outputs a rational number $y$ such that $r−\frac{1}{C}\leq y \leq r+\frac{1}{C}$.
If it is computable, what would the high-level algorithm be? Or how do we argue that it is not computable?


texts:
I am working with a particularly forgiving interpretation of $\Box$ in Modal Predicate Logic. $M, w, g \models \Box \varphi$ iff for every $w' \in W$ such that $wRw'$, $M, w', g \models \varphi$ IF $\varphi$ is defined in $w'$. This mostly means that, for any constant $a$ that is nominated in  $\varphi$, if $a \notin D_{w''}$, then $w''$ does not count for whether or not $\Box \varphi$ is true at $w$, even if $w'' \in W$ and $wRw''$.

Is the following principle valid on all frames: $(\Box \forall x \varphi) \to (\forall x \Box \varphi)$?

Intuitively, I would say so. However, when I try tu write a proof by induction on the complexity of formulas, starting with the base case of $\varphi$ being atomic, I struggle to prove it. I can prove the base case, but I am at loss for proving anything else.

I believe that my problems resides in the fact that I do not see how to apply the induction hypothesis. Otherwise, if my intuitions are wrong, I can't seem to find a counter-example.

I don't know whether or not $\varphi$ depends on $x$. If that gives two different answers, I would love to know.


texts: I'm trying to compare two functions, such as f(n)=n^n and g(n)=n^10^10. I'm unsure if f(n) is O(g(n)) or vise-vera where g(n) is O(f(n)). From my understanding, n^n can be worse than n! and although g(n) is being raised to a large constant, it can be bounded by f(n) if multiplied by a certain constant. I am new to this topic, how can you see if a run time function can be bound by another, such as these?


texts: Multi-level paging where the inner level page tables are split into pages with entries occupying half the page size

texts:
A processor uses $36$ bit physical address and $32$ bit virtual addresses, with a page frame size of $4$ Kbytes. Each page table entry is of size $4$ bytes. A three level page table is used for virtual to physical address translation, where the virtual address is used as follows:

Bits $30-31$ are used to index into the first level page table.
Bits $21-29$ are used to index into the 2nd level page table.
Bits $12-20$ are used to index into the 3rd level page table.
Bits $0-11$ are used as offset within the page.

The number of bits required for addressing the next level page table(or page frame) in the page table entry of the first, second and third level page tables are respectively
(a) $\text{20,20,20}$
(b) $\text{24,24,24}$
(c) $\text{24,24,20}$
(d) $\text{25,25,24}$
I got the answer as (b) as in each page table we are after all required to point to a frame number in the main memory for the base address.
But in this site here it says that the answer is (d) and the logic which they use of working in chunks of $2^{11} B$ I feel ruins or does not go in with the entire concept of paging. Why the system shall suddenly start storing data in main memory in chucks other than the granularity defined by the page size of frame size. I do not get it .


texts: What is a sort in programming language semantics?

texts:
In Chapter 1 of Practical Foundations for Programming Languages, the author mentions that abstract syntax trees are associated with sorts.

Intuitively, sorts are like types, but I'd like to know if they have a precise definition. I'd be glad if some references are provided as well.


texts: How is $A.in$ an inherited attributed in $2nd$ production in $(1) S \rightarrow A_1A_2\{ A_1.in := 1; A_2.in := 2 \}(2) A\rightarrow a\{print(A.in)\}$

texts:
Below is an excerpt from the Red Dragon book.

$$(1) \quad S \rightarrow A_1 \quad A_2 \quad\{ A_1.in : = 1;\quad A_2.in : = 2 ;\}$$
$$(2) \quad A  \rightarrow a \quad \{ print(A.in) \}$$
We find that the inherited attribute $A.in$ in the second production is not defined when an attempt is made to print its value during a depth-first traversal of the parse tree for the input string $aa$.

Now the authors define inherited attributes as:
An inherited attribute is one whose value at a node in a parse tree is defined in terms of attributes at the parent and/or siblings of that node.
But in the above excerpt, $A.in$ for the nodes $A$ of the parse is not defined in terms of attributes at the parent or siblings. But rather it is sort of based on itself.


texts: Does RAM take the copy of the program or does it load programs from the hard disk?

texts: I guess it copies, since it is a temporary memory, it will erase if power is not supplied, so, that will lead to data loss right, but still, I need clarification.


texts: Which CNF boolean formulas blow up exponentially at conversion to DNF?

texts:
If I'm correct, some boolean formulas in CNF require exponential size when being  converted to an equivalent DNF version (and vice versa).

But what is an example of such a formula (and is there a general way to capture their structure - if the first question is too easy, and I'm just too stupid to see it)?

In this post, the parity function is discussed as an example of a function which blows up exponentially when converted to both CNF and DNF from a non-NF version: Formulas for which any equivalent CNF formula has exponential length

But what about just CNF <=> DNF? And how frequent are these "bad" formulas? (Very rare, I'd suspect, but can it be proved?)


texts: Here i want to discuss about Linear Voronoi game. The game consists of two players, and a  finite set of users placed along a line. Each player has 2m facilities, where m>0 is a fixed integer. The game starts by the first player, placing 2 facilities on the line, followed by which  the second player places 2 facilities, and this continues for multiple rounds.  Assuming that each user is served by a facility closest to it, the payoff of each player is defined as the number of users  served by the facilities of that player. The goal of each player is to maximize his payoff. I am trying  to find an optimal strategies for last move of both players to find their best placements in the game.


texts:
Say we have a simple OS with a filesystem, and some programs on that filesystem. How then does a program get executed by the OS?

My understanding is that the executable file gets loaded into memory, but after that I'm a little fuzzy. I understand the OS creates a process, but I'm not sure exactly how it works. How does the OS tell the machine code to run, and how does the scheduler interact with the program to start, pause and resume execution per scheduling policy?


texts: Decremental connectivity on general graphs

texts:
I'm looking for an efficient solution to the problem of tracking the number of connected components in a general graph under edge deletions.

General connectivity algorithms like that from
 Holm, Lichtenberg and Thorup solve this problem and also feature edge insertion and connectivity queries, which I dont really need, but have an amortized poly-logarithmic update time and need log-linear space (which is most troublesome to me).

So I wonder if there is some more efficient approach (especially in terms of space complexity) considering the relaxations of the problem. I tried different approaches based on DFS and tremaux trees but eventually couldnt get some working solution...

Thanks in advance


texts:
Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.
Hint: Use the exact cover problem.

The exact cover problem is the following:
Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?
First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following?
A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and then verify that it sums to exactly k in linear time.
Is this correct?
To show that it is NP-complete how could we reduce the exact cover problem to subset sum? Is it as follows?
The exact cover problem has a solution iff every element is in exactly one set.
We consider the set $S$ and the number $k$ such that each number corresponds to a set of elements and $k$ corresponds to the whole set. Suppose there are $n$ elements and $k$ different sets.
We replace each set S with a number that is $1$ in its ith position if i is in S and has a $0$ in its ith position otherwise.
We set k to a number that is $n$ copies of the number $1$.


texts: How much can we trust mathematical software when working with large numbers, and how much memory it needs to work with these numbers?

texts:
For example, I want to evaluate the expression:

$3^{3^{{3}^{3}}}$

so I used wolframalpha.com (it's free, and I don't own any software), which returned the scientific notation of the number above, namely:

$ 1.258014290627491317860390698... × 10^{3638334640024}$

Which is huge. However, for the number below

$4^{4^{{4}^{4}}}$

Wolfram can't return a scientific notation, probably because it's a much larger number and it needs a lot of memory.

  Questions: a) How much can we trust that

$3^{3^{{3}^{3}}} \approx 1.258014290627491317860390698... × 10^{3638334640024} $

  b) how much memory (aproximate) it needs to evaluate

$3^{3^{{3}^{3}}}$

and

$4^{4^{{4}^{4}}}$

I'm guessing a lot of terabytes and something that a home computer can't handle. But for the first number, Wolfram can, and the second number, it can't. How do we even find how much size we need to calculate these numbers?


texts: Identifying events related to dates in a paragraph

texts:
Is there an algorithmic approach to identify that dates given in a paragraph correlate to particular events (phrases) in the paragraph?
Example, consider the following paragraph:

In June 1970, the great leader took the oath. But it was only after May 1972, post the death of the Minister of State, that he took over the reins of the country. While he enjoyed popular support until Mid-1980, his influence began to fall thereafter.

Is there an algorithm (deterministic or stochastic)# that can generate a 2-tuple (date, event), where the event is implied, by the paragraph, to have occured on the date? In the above case:

(June 1970, great leader took oath)

(May 1972, took over the reins)
or better yet

(May 1972, the great leader took over the reins)

(1980, fall in influence)

#Later addition


texts: I want to know difference between propagation speed and bandwidth in digital communication.I know bandwidth is no of bits in one second and propagation speed of signal is distance traveled by signal is one second.Is there any relation between them or they are totally different.Can anyone tell me exact definition to differentiate these twos.


texts: Find all $k$ local maximums in an array of length $n$ in $O(n \log k)$ time

texts:
Given a sequence of numbers $a_1, a_2, ..., a_n$, a number $a_i$ is called the $k$ local maximum $\iff i > k$ and $a_i$ is the largest number among the $(k+1)$ numbers $a_{i-k}, a_{i-k+1}, ..., a_i$. Given a sequence of $n$ numbers $a_1, a_2, ..., a_n$, and an integer $k$, I am requested to find all $k$ local maximums in $O(n \log k)$ time.

At first, this seems like a dynamic programming problem, where I first calculate the solution for $k'=1$, and goes from there to $k'=k$, but this approach seems to take $O(nk)$ time.

I have found a possible solution to my problem here
, but this also seems to take $O(nk)$ time for my problem, as

Build a Cartesian tree of the first $k$ elements. $O(k)$
Insert and check whether the $(k+1)$th element is the $k$ local maximum (also remove the leftmost element). $O(k)$
Repeat step two until reaching the end of the sequence.

The overall complexity seems to be $O(k) + O((n-k)k) = O(nk)$.

Any help is appreciated. Many thanks.


texts:
We have given an array of size $N$, consisting of positive integers, and an integer $H$. We also know that an array is stable iff $|A_i - A_{i-1}| \leq H$ for each $1<i<N-1$. We can modify the element by adding +1 to some element or by adding -1 to some element, we don't have a limit on how much we can use those operations, but we want to make the array stable in minimum moves.

I started solving the task by writing a dynamic programming relation, described by the state $f(i, j)$ meaning the minimum moves to stabilize the first $i$ elements of the array, such that the last element is equal to $j$.

However it seems that this method is slow for big values of $N$. How would you approach solving this problem?


texts: Matching two people. One has 7% in common with the other. The other has 70% in common. What's a fair match score?

texts:
I am exploring some ideas around dating site matching, and I can do with some ideas as to which is the better solution

Senario: We have a boy and girl, the boy has completed his profile/bio thoroughly while the girl hasn't or maybe she just doesn't like a lot of things, so this is what the data looks like

Boy likes:                  Girl likes:
---------                   -----------
Painting                    Painting
Movies                      Movies
Long walks                  Long walks
Harry Potter                Harry Potter
Dogs                        Dogs
Pizza                       Pizza
Computer Science            Computer Science
Mercedes                    Ford
Traveling                   Daisies
Diving                      Psycology
...

Total things
---------------------------------------
100                         10

They share 7 things in common. To the girl the boy is a 70% match which is great
But to the boy the girl is only a 7% match

Maybe the girl would have more in common if she had more in her list of likes so maybe giving their match a 7/100 is a match missed and maybe that's all she likes and 7/100 is the best they'll ever match but even then, it still might be a good match because maybe the boy over filled his list of things he likes while the girl chose carefully what she really likes.

I am looking for ideas for an algorithm that would give the best match score to order them in lists with other people/matches who might have small percentage in matches because their lists of things they like are 1000s of entries long for example

Edit: I will not be matching strings, each of strings in the table above will have a unique ID in an RDBMS database. A table will be used to link users and topics


texts:
Consider a three word machine instruction

ADD A[R0], @B

The first operand (destination) “A[R0]” uses indexed addressing mode with R0 as the index register. The second operand (source) “@B” uses indirect addressing mode. A and B are memory addresses residing at the second and third words, respectively. The first word of the instruction specifies the opcode, the index register designation and the source and destination addressing modes. During execution of ADD instruction, the two operands are added and stored in the destination (first operand).

The number of memory cycles needed during the execution cycle of the instruction is:

a. 3
b. 4
c. 5
d. 6

My work till now:- As per my knowledge instruction execution has decode sub phase.So it will take 2 MR in decode phase to fetch the instruction.Then to read indexed addressing mode operand it will take one memory reference and since this is the destination also so in total it will have 2MR and then to read second operand it needs 2 MR. so in total i will go with 6 as the answer here.
But i want to clear whether is it actual 6 or is it 4?4 because if we consider that decode phase is not part of the execution cycle.


texts: Number of inversions in an array of pairs of integers

texts:
I have a problem like this:
we have an array of elements like this :
(a0,b0)
(a1,b1)
.
.
.
(an,bn)

and I wanna find the number of elements which have one of this two condition:
1) if ai>aj and bi<bj then:count:=count+1
or
2) if ai<aj and bi>bj then:count:=count+1
I've already found an algorithm that is $O(n^2)$, but I need the  faster algorithm.
Example:
suppose we have this:
(1,5)
(4,7)
(8,2)

I wanna find the number of time that condition satisfied, so
1<8 and 2<5 so condition is satisfied but 1<4 and 5<7 so condition is
not satisfied.


texts:
Is this grammar LL(1)? Would it be a problem that S can be both E/S and E?

S -> E / S
S -> E
E -> letter
E -> ‘ S ’

Can it derive ‘a / e / ‘g / s’ ’ / q like this?

S - >  E / S
S - > ‘S’ / S
S - > ‘E / S’ / S
S - > ‘a / S’/ S
S - > ‘a / E / S’ / S
S - > ‘a / E / ‘E / S’’ / S
S - > ‘a / e / ‘g / s’’ / q


texts: How does reduction of a decision problem work?

texts:
I am given the following problem description:

Given $l$ lists, $L_1$, $L_2$, . . .$L_l$ each containing $N$ bit vectors of $n$ bits each, we want to find tuples $(x_1,···,x_l)$ with $x_i$ in the corresponding $L_i$, such that:$$⊕_{i=1}^l x_i = S $$ for some target n-bit vector $S$.  In other words, we want to find one element from list such that the XOR of the chosen elements is the target $S$

Now I am required to show that if we can solve the equation in the case where $S=0$, we can for the same cost solve it for an arbitrary value (with exact same parameters, $N$, $n$, and $l$).  I am given a hint to proceed by reducing an instance with $S \neq 0$ to an instance with $S=0$.
What am I missing that I am not able to reduce it?


texts: Efficiently compute parallel matrix-vector product for block vectors with FFTs?

texts:
Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product
$$w = (E\otimes I_N)v$$
in parallel, where $\otimes$ is the Kronecker product, $v = (v_1, ..., v_P)^T$ is the stacked vector consisting of all local vectors $v_p$, $E = (e_{pj})_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I_N$ is the identity matrix of size $N\times N$, I can basically do $P$ parallel sums using binary trees.

$N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v_p$ together) does not fit into each processor's memory.

Depending on the application, the matrix $E$ could be a Fourier or DFT matrix, i.e. computing
$$w_p = \sum_{j=1}^P e_{pj} v_j$$
should be possible using an FFT. For each of the components of the vector $v_j\in\mathbb{R}^N$, the FFT would not change. Do I still have to do $N$ FFTs or is there a "block-wise" FFT idea/implementation?


texts: How are matchings a lower bound for an approximate vertex cover?

texts:
I am reading Algorithms by Dasgupta et al and they mention maximal matchings as approximations for vertex cover.
They mention that the 2-approximation ratio is a lower bound. How is a maximal matching a lower bound? Does it mean that it is the lowest approximation value we can get compared to $\log n$ of the greedy algorithm that is polynomial?
The images below show the optimal vertex cover = 8 but and a maximal matching of 12.

I decided to find another matching which I later discovered is called a maximum matching from Wikipedia. Since a maximum matching is also a maximal matching, I assume that this the worst that we can get, a maximum matching of 16 vertices.

How can one improve on the edges picked then? My 16 vertices versus the book's 12?


texts: Linear algorithm to measure how sorted an array is

texts:
I've just attended an algorithm course, in which I've seen many sorting algorithms performing better or worse depending on how much the elements of an array are sorted already. For example, for what I've heard, quicksort is preferred most of the times, yet still it has $O(n^2)$ complexity in case the array is sorted already.

My question is if there is a way to measure in linear time how sorted the array is, and then decide which algorithm is better to use. By measure I mean an algorithm that outputs 1 if the array is sorted already, values closed to 1 if just a few values are unordered, 0 if the input is sorted from the highest to the lowest value. Depending on this output, we could decide if it's a good idea to use quicksort, or we should use some other sorting algorithm.


texts: invite 12 person from 24 that we have 6 men and 6 womens

texts:
i had a question and its

"A man has 5 female and 7 male friends and his wife has 7 female and 5 male friends. In how many ways can they invite 6 males and 6 females if husband and wife are to invite 6 friends each?  Answer. 267,148."

i tried to have cases by that each person invited six and total of 6 females and 6 males

1 = 5 mens * 1 female
  +  1 man * 5 females
and cont

and then sum them up but the answer was less than the answer given it was 1848


texts: I'm reading on small-depth circuits. Since every formula can be turned into a CNF formula, which has depth at most 3, why should we study deeper circuits? Is it because convertion to CNF may result in an explosive blow-up? If so, can you give an example?


texts:
Suppose that someone found an algorithm A for a NP problem (that is not NP-complete) that uses an algorithm B for PSPACE-complete or #P-complete problem during execution. (Remaining part of the algorithm takes polynomial time.)

Then suppose there is also an algorithm C for a NP problem that uses the polynomial-consuming part of the algorithm A. The rest of the algorithm C is actually an algorithm that solves NP-complete problems.

Then would this mean that PSPACE-complete or #P-complete collapse to NP-complete?

If so or if not, why would it be like that?

I am asking this question, because I seem to get confused during reading my computation textbook.

Edit:
I was a bit confused as in (or more accurately scalar function) math, if g(x)=f(h(x)) and g(x)=f(q(x)), h(x) and q(x) must be virtually the same. So, my question was virtually the aforementioned. That was the parallel I was making between algorithm A and C.


texts: Is IEEE 754 float arithmetic associative, commutative, distributive, etc? Why?

texts:
Does the associative/commutative/distributive/etc property hold for arithmetic performed with IEEE 754 floats?

Obviously the answer is no to most of those questions, but do any of the properties of standard arithmetic hold? How can one formulate proofs (or at least proof-like statements) explaining why any particular property does or does not hold?


texts: What does "context" in "context-free grammar" refer to?

texts:
There are lots of definitions online about what a Context-Free Grammar is, but nothing I find is satisfying my primary trouble:

What context is it free of?

To investigate, I Googled "context sensitive grammar" but I still failed to find what the "context" was all about.

Can someone please explain what the context term refers to in these names?


texts: Best approach to resource allocation problem

texts:
Problem

The enemy army has taken $n$ of our cities. In each city $i$ the enemy has placed $e_i$ soldiers. We have $n$ teams, each team $j$ with $d_j$ soldiers. If we place more soldiers in a city than the enemy, we retake the city. Our aim is to distribute our teams so that we maximise the number of retaken cities if:

We can only place one team per city
There is no limit to the number of teams we can play in each city.

Question
I'm trying to figure out which approach might be best for each option (greedy algorithm, divide-and-conquer, dynamic programming, backtracking). I'm not necessarily looking for the particular algorithm, although I'd be happy to get it too.
Previous work
One team per city
The best approach would be a greedy algorithm, which would assign to each city the smallest team which can defend it, starting from the smallest team. If at some point the smallest remaining team cannot take the smallest remaining city, we can simply dump that team.
No restriction for the number of teams per city
I can think of a greedy algorithm similar to the previous one, in which we assign the smallest teams to the smallest city until it's defended, and then move to the next one. However, I am not certain this would lead to an optimal solution, unlike the previous case.
Backtracking explores the solution space exhaustively, so it would work but it's ineffective. Dynamic programming looks promising, as this superficially looks like a variation of the knapsack problem, but I know that generalisations/variations might not necessarily be tackled with the same approach.


texts:
The requirement is that two adjacent vertices have different colors, and max. 42 colors.

I show that $ \text{42-COLOR} $ is in NP and then I must reduce it from $ \text{3-COLOR} $. Here it becomes complicated.

Is it similar to $ k\text{-COLOR} $ for any $k$?


texts: Optimal algorithm to traverse all paths in the order of shortest path

texts:
I have to generate all possible paths in a directed, acyclic weighted graph with edge costs. I also have to sort them in order of shortest path.

The simplest way that comes to mind is to do a depth-first search (DFS) for all paths, accumulating their edge costs as I traverse the paths, and then doing an NlogN sort on the result.

But I wondering if there is a better way to do this task. Are there any algorithms that could optimize this problem (combining DFS and a shortest path algorithm such as Dijkstra's maybe?).


texts: Why is a regular language called 'regular'?

texts:
I have just completed the first chapter of the Introduction to the Theory of Computation by Michael Sipser which explains the basics of finite automata.

He defines a regular language as anything that can be described by a finite automata. But I could not find where he explains why a regular language is called "regular?"  What is the origin of the term "regular" in this context?

NOTE: I am a novice so please try to explain in simple terms!


texts: Are there any known W[3] or W[3]-hard problems?

texts: We are currently working on a variant of domination parameter and we have shown that it is in W[3] with regard to parameterized complexity. To show it is W[3]-complete, we must show the problem is W[3] hard i.e, reduce an already known W[3] hard problem to ours. But unlike W[1] and W[2], where many famous problems are proved those classes, surprisingly we have not come across a single problem that is W[3] hard and not even in just W[3]. Of course there is the general W[t] case which we can go for, but any result for W[3] in particular would help a lot.


texts: Is this language countable : $L= \{ w : w \in (1 + 0)^{*} \}$

texts:
This is my take :

Epsilon ---> 1

0 -->  2

01 ---> 3

10 ---> 4

11 ---> 5

001 ---> 6

010 ---> 7

.
.
.

So therefore we can count them.

But  based on this video : https://www.youtube.com/watch?v=oe-ZAJQz9Cc&index=5&list=PLsFENPUZBqiqbnD-WatYxUhRWLMNDoMun

They should not be countable, but i did not understand that video, the guy says all possible languages over $\{0,1\}^{*}$ are uncountable!


texts: How are punishment and negative reinforcement handled in reinforcement learning using neural net function approximation?

texts:
Punishment is reducing a behaviour due to bad outcome e.g. A cow stops touching an electric fence because it gets a shock.

Negative reinforcement is increasing a behaviour that reduces a bad outcome.  e.g. Put on a seat belt to stop the car bleating.

In this context, how are neural nets trained by Reinforcement Learning (RL) to approximate pi(s) and Q(s,a) ? Must negative neuron activations be allowed in hidden layers to enable negative reinforcement ?  Are there practical issues with value ranges ?


texts: Efficient algorithm to translate/shift polynomials

texts:
I have a polynomial $P(x)$, and given some constant $d$, I need to find the polynomial $P(x+d)$. For example, if $P(x)=x^2$ and $d=1$, then the result would be $P(x+1)=(x+1)^2=x^2+2x+1$ (with the coefficients stored in an array/vector).

I know the algorithm with $O(n^2)$ time complexity, which is based on Horner's method: $$a_0+(x+d)(a_1+(x+d)(a_2+...+(x+d)a_n))$$
However, it is not efficient enough for my needs. Is there an algorithm that is more efficient for solving this problem?

P.S. The coefficients and $d$ will always be integers, if that helps.


texts: Determine the number of reachable states in a subset construction?

texts: Is there a polynomial time algorithm to determine the number of reachable states in the subset construction of a NFA to a DFA without having to construct the entire DFA?


texts: Definition of deterministic pushdown automaton

texts:
Wikipedia Pushdown automaton (as of aug 16, 2013) states:

  In general, pushdown automata may have several computations on a given input string, some of which may be halting in accepting configurations. If only one computation exists for all accepted strings, the result is a deterministic pushdown automaton (DPDA)

My professor gave this as an example that we shouldn't trust Wikipedia but rather consult a textbook. Is he right?


texts: Why is Clique NP-complete while k-Clique is in P for all k?

texts:
I just stumbled upon this question here Why is the clique problem NP-complete?
 and I am confused by the given answer.
The question about about whether $k$-clique is NP-hard for a fixed $k$ and the answer is no. However, we know that clique in general is NP-hard. Also we know that $0 \leq k \leq n$ must hold (for a graph of size $n$).

What is wrong about the following reasoning:
Assume I have some algorithm $A_i$ that solves $i$-clique for some fixed $i$ in polynomial time.
Now given some general clique problem without a specific $k$ (these problems are supposedly NP-hard), I simply run $A_i$ for $i=1$ to $n$. Now since $n$ is poly and every $A_i$ runs in polynomial time $p_i$, the resulting algorithm also runs in polynomial time $\sum p_i$, but this cannot be the case, since clique is NP-hard.

What is wrong about my reasoning?


texts:
I'd like to ask a question about MAX CUT and MIN CUT on graphs with unit edge-weight. I know that MAX CUT is NP-Hard, but MIN CUT is in P (i think)?

Barahona, in 1982, showed (Lemma 1) finding a cut of at least k on a unit-weight graph is equivalent to finding a cut of at most -k on a graph in which each edge is replaced with a chain of edges, each of weight +1 except for one with weight -1. http://yaroslavvb.com/papers/barahona-on.pdf

Is this not technically MIN CUT on that extended graph? Wouldn't this show that MAX CUT can be reduced to MIN CUT, and therefore belong in P or is there something about MIN CUT I don't understand properly?


texts: Next-Word Prediction, Language Models, N-grams

texts:
I was looking into how a next-word prediction engine like swift key or XT9 can be implemented.

Here's what I did.

I read about n-grams here - en.wikipedia.org/wiki/N-gram and aicat.inf.ed.ac.uk/entry.php?id=663
I read about Language Models/Markov Model/n-grams/training/Smoothing/Back-Offs - en.wikipedia.org/wiki/Language_model & www.stanford.edu/class/cs124/lec/languagemodeling.pptx & www.statmt.org/book/slides/07-language-models.pdf.
I read about the T9 engine design for next-word prediction based on Tries - courses.cs.washington.edu/courses/cse303/09wi/homework/T9files/T9_Tries.pdf
I came across SRILM, a popular toolkit for building & applying Language Models here - www.speech.sri.com/projects/srilm/ (the toolkit) & www.speech.sri.com/cgi-bin/run-distill?papers/icslp2002-srilm.ps.gz (the documentation)
I came across the blog where Google's Peter Norvig made an announcement to share it's huge training corpus of one trillion words to the entire world - googleresearch.blogspot.in/2006/08/all-our-n-gram-are-belong-to-you
I came across an n-gram viewer based on google books' corpus - books.google.com/ngrams/
I came across Microsoft's N-gram services - web-ngram.research.microsoft.com/
I came across an algorithm for N-Gram Language Models which is as fast as but smaller (in memory footprint) than SRILM's model (not based on tries, uses encoding) - nlp.cs.berkeley.edu/pubs/Pauls-Klein_2011_LM_paper.pdf (I need to do more work here.)
I had a look at some open-source engines available like AnySoftKeyboard - github.com/AnySoftKeyboard. That's is a huge amount of code with no documentation!

Some discussions on stackoverflow:

Implementing T9 prediction engine - Implementing T9 text prediction
A discussion on implementation of autocomplete using tries vs. ternary search trees vs. succint trees - stackoverflow.com/questions/10970416/tries-versus-ternary-search-trees-for-autocomplete

The major players in this area:

Swift Key - en.wikipedia.org/wiki/SwiftKey & www.swiftkey.net/en/
XT9 by Nuance - en.wikipedia.org/wiki/XT9 & www.nuance.com/for-business/by-product/xt9/index.htm

Can anybody guide me how to proceed further.

I am relatively new to this site. So please guide me if my question is inappropriate for this site.


texts:
Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia):

  Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.

  Heap property: the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children, according to some total order.


texts: How does quicksort handle case when we choose the first number as pivot and all the remaining elements after the pivot is greater

texts: For example, we have an array [4,7,6,13] and I choose the first item 4 as the pivot. Now I have a pointer i that goes through the array from index 1 to index 3; and I have another pointer j that starts at index 1, increases whenever we find an element that is smaller than pivot and we swap this element with the element j is now pointing to. Now since all elements are greater than 4, when my i reaches the end of the array, j is still at index 1. Now I have to switch 4 and 7, which doesn't make sense. However, according to the algorithm, we need to swap them. Did I miss anything here?


texts: Bit representation of the hashing multiplication method

texts:
In the picture below from CLRS, I fail to understand why exactly $h(k)$ = the $p$ highest-order bits of the lower w-bit half of the product.

For context, this is supposed to compute
$h(k) = \lfloor m (k A \;  \text{mod} 1) \rfloor $

For further context, CLRS mentions the following, but I still don't quite get why those $p$ highest-order bits are the ones we are looking for.


texts: Big-O Notation for Menezes-Vanstone Elliptic Curve Cryptography?

texts:
I need someone help me about . how can compute time complexity for this algorithm (Menezes-Vanstone Elliptic Curve Cryptography).
I have spent much time reading journals and papers but as yet have been unable to find any record of that performance complexity.
It is known that the algorithm is
encryption function is :

$C1 = k1 * m1$  mod  p

$C2 = k2 * m2$  mod p

The decryption function is:

$m1 = C1 * k1^ {-1}$ mod p.

$m2 = C2 * k2^{ -1}$ mod p.

I think the encryption function it take $O(N)^{2}$

where
$T(C1) = O(\log n)^2$ bit operations.

$T(C2) = O(\log n)^2$ bit operations.

and the decryption function it take $O(N)^{3}$.
where

$T(m1) = O(\log n)^2 + T(k1^{-1})$.

$T(k1^{-1}) = O(\log n)^3$, by extend Euclid’s method.

$T(m1) = O(\log n)^2 + O(\log n)^3$ bit operations.

$T(m2) = O(\log n)^2 + O(\log n)^3$  bit operations.

Is that true?.


texts: How can Turing machines loop forever given that the input is finite?

texts:
How Turing machine can loop forever when input length is always finite?
I think this is a basic doubt but unable to understand how TM go into infinite loop? I think it can make transition forever on empty string. What are the other cases? Can it make without any empty alphabet ?


texts: Is there a strictly non-deterministic one-counter language whose complement is one-counter?

texts:
Let
$A= \{L \mid L \;\text{is one-counter and \(\bar{L}\) is also one-counter} \}$

Clearly, $\text{Deterministic one-counter} \subseteq A$

Is it the case that $ A = \text{Deterministic one-counter}$?

I know that for context-free languages the analogue is not the case. For example,
let $P =\{ ww^r\}$.
Then both $P$ and $\bar{P}$ are context-free but $P$ is not deterministic.
Hence $A$ defines a (strict) subset of the context-free languages.

The question is: can we construct a similar one-counter example for which the same holds?


texts: Cocke-Younger-Kasami (CYK) algorithem for the word $baabb$

texts:
With the context-free grammar in Chomsky's form:$$S\to BA|AC|b\\A\to AA|AB|CC|a\\B\to AS|BB|CA\\C\to AB|SS|b$$

I need to:

  run the CYK (Cocke-Younger-Kasami) algorithm and decide if I can derive the word $baabb$ from the context.
  write the left derivation.

My try:

$1.$

$$
\begin{array}{c|lcr}
i\bigg/j &  1 & 2 & 3 &  4 & 5 \\
\hline
1 & \text{C,S} & \text{B} & \square& \square &\square \\
2 & \quad\blacksquare & \text{A} & \text{A} & \square & \square \\
3 & \quad\blacksquare & \quad\blacksquare & \text{A} & \text{S,B} & \square \\
4 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} & \text{A,C} \\
5 & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \quad\blacksquare & \text{C,S} \\
\end{array}
$$

$S\Longrightarrow BA \Longrightarrow CAA \Longrightarrow bAA\Longrightarrow bAACC\Longrightarrow baabb$

I'm stuck here in the table construction. How should I fill in the empty squares?


texts: Does Paxos consensus algorithm scale linearly?

texts:
I'm trying to build a P2P web application using Paxos to obtain a consensus value.

How well does Paxos scale? linearly? or what kind of distribution can you expect? E.g. in using 10 to 10,000 users in the network.

If not, are there consensus algorithms that scale well?


texts: What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?

texts:
On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem:

  You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. Find the maximum number of dominoes you can place on the board so that each domino covers exactly 2 squares and no dominoes overlap.

I solved it quite easily: the solution is just floor(M*N/2).

I read that in order for a problem to be solved Greedily, it needs to have "optimal substructures". For this problem, what were the "optimal substructures"?

Thank you in advance.


texts: executing threads with no synchronization

texts:
suppose Threads 1 and 2 are executing concurrently with shared integer variables A, B, and C. Thread 1 executes:A=4, B=5, C=B-A; Thread 2 executes: A=3, B=6, C=A+B;

I'm trying to find what can the possible values of C be after execution of this fragment when synchronization is not implemented.

I know if there is no synchronization then the reads see writes that occur later in the execution order and it will be counter intuitive ( execution will be happens-before consistency)

I am confused what can be the possible values of C. Can the possible values for C be 1,2,3,8,9,10 after substituting the all possible values for A & B from both thread 1 and thread 2 for C=B-A & C=A+B


texts: Least probability of collisions using rgb as a hash map

texts:
I need to rewrite a short utility library, to get it working with the Brave browser (My actual question isn't about brave per se.)
canvas-color-tracker - example of it being used and src/index.js  is short
The HTML canvas is used for mouse over and clicks to determine what object is under the cursor.
To use it with circles, you register your circle to get a color, then draw the circle in that color. Then to determine what is under the cursor, you get the color with getImageData.
The trouble is what to do about anti-aliasing, the browser doesn't allow that to be turned off, and I want to be able to return nothing rather than collide with another uninvolved circle when it's edges blend into another color)

Assuming the anti-aliasing blends linearly How to create an ordering of points in 8bit RGB space, such that the minimum number of points are colinear without knowing the final total number of points? What is a reasonable heuristic for this?

Addendum, I am doing this because Brave will choose a color channel at random and randomly vary the lowest bit of it - bit fiddling as a privacy feature prevent fingerprinting.
I figure that if I improve on the algorithm as well as drop the lowest bits for Brave, the maintainer will be happy to use my version (or I will just use my fork anyway)


texts: I have trouble to understand pattern calculus, could someone explain it in simple terms?

texts:
I am trying to understand the basic ideas of pattern calculus and do not have a lot of time to read through a rather long book. Can someone explain this in simple terms and give an example of how pattern calculus works?

http://bondi.it.uts.edu.au/

http://www.amazon.com/dp/3540891846/?tag=stackoverfl08-20

I don't understand "The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator." as explained here in the Wikipedia article. If someone could work through an example showing how the patterns were transformed and why they were transformed in that way, that would be useful to me, thanks.


texts: Range of values for Kolmogorov complexity

texts:
Let $n$ be a positive integer. Is it true that for all $1\leq i \leq n$  there exists a length $n$ binary string $w$ such that $K(w) = i$. Where $K(w)$ is the Kolmogorov complexity of $w$.

For each $i$ there are clearly $2^i$ programs of that length. But can we be sure at least one of them (when executed) generate a length $n$ binary string?


texts: 3SAT instance with EXACTLY 3 instances of each literal

texts:
I'm trying to solve a question which requires me to

prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined)  and each clause contains exactly 3 literals is always satisfiable.
Find a polynomial time algorithm to find a satisfying assignment for it.

My Solution

I'm not sure how to prove part 1.
I'm trying to solve 2 by reducing it to an instance of Vertex Cover in which each literal has 2 nodes - one positive, one negative - and each node is connected to the other literals its in a clause with. A vertex cover of size m = # of literals will give us the assignment needed.

Im not sure of I'm along the right path or not? Any help would be appreciated!


texts:
We are trying to solve variant of the n-peg Tower of Hanoi problem.
There can be limitations on possible moves among the pegs.
In the graph vertices are pegs, and an edge
from vertex to another tells us we can move a disk from
the first peg to the other.

We need to find out what are the necessary and sufficient conditions
the graph must have so that the problem of Hanoi can be solved,
and if there is an algorithm for solving it.

Help will be much appreciated.


texts: Better algorithm for aggregating data from various LDAP systems

texts:
I have 10 LDAP systems which contain users and groups in the form of objects. Each user / group is identified by a distinguishedName like name/systemName where name is name of user or group.

Group objects store which users are members of the group.

GroupA = {UserA, UserB, UserC ....}
GroupD = {UserF, UserB, UserK ....}

This information is not stored in the users object. User objects have user related attributes.

UserA = {name="ABC", dob="x/x/x", }
UserB = {name="PQR", dob="x/x/x", }

I want to make a system, which will query all systems to get user and group objects and show them on GUI this way

UserA = {name="ABC", dob="x/x/x", memberOf=[GroupA]}
UserB = {name="ABC", dob="x/x/x", memberOf=[GroupA, GroupB]}

There are millions of users and millions of groups in these systems overall.
The software I have created runs on various machine simultaneously. The software is written in Java.

I am using this approach to achieve this:

Start my program on one machine - Machine#1
Get all group objects from all the systems one by one and store them in memory store with key as user and value as list of group names
Once all the groups are queried and stored in memory store, then fire my program on other machines too
Other machines will copy the memory store created on Machine#1 to their machine (using third party lib - ehcache)
Program on each machine will query some set of Systems (Machine#1 will query system 1,2,3; Machine#2 will query 4,5,6 .. and so on)
Get all user objects and as I receive each user object, query memory store to see if user has any groups attached. If yes, pick them and store in DB?
Once all the programs on all machines are finished, we have result in DB which can then be shown anywhere

This approach has following disadvantages:

Consumes lot of memory (memory stores uses 20 GB RAM on one machine)
Memory store which needs to be replicated on other machines is not so stable process
Memory store is only built on single machine. This takes about 3 hrs to complete. During this time, other machines are idle, which is waste of resources.

End goals of application should be:

Best performance possible
Minimal wastage of computing time
Data (user objects showing groups) should be available in said format. The format cannot be changed as there is dependency with other downstream systems.

Is there a better approach to achieve the same ?


texts: I want to know if there is any good book or material that fully explains and fully covers all combinatorics.I even did not find even Kenneth H.Rousan for this.So can anyone tell me any Discrete Mathematics book or any material to fully  explain Combinatorics even to advance level.that provide classification to combinatorics problems(most important).


texts: Range bit inversions and range set bit queries with a binary indexed tree

texts:
I am trying to solve this problem using a binary indexed tree. The problem can be summarized as follows:

  You are given a series of commands that operate on an array initially
  all zeroes.

  1) Invert all bits from [a, b] (1 becomes a 0 and vice-versa)

  2) Find the number of set
  bits from [a, b] (bits that have value 1).

I know that one way to solve this is using a segment tree with lazy propagation, but I want to see whether it can be solved using a binary indexed tree.

To start, I know that binary indexed trees can be used to do range increments and range sums as per my previous question.

Further, I know that the structure of a binary indexed tree is that the node $i$ stores a function of values form $i - 2^h + 1$ to $i$ where $h$ is $i \text{ and}-i$ which is sort of similar to a segment tree in which each node stores the merged value of its left and right children (2i and 2i + 1 in the array representation).

Binary indexed trees only operate on functions that are associative and have an inverse, (that is, function[a..b] = function[0..b] - function[0..a-1]). On the other hand, segment trees only need a function that is associative, as the range is built directly from smaller segments rather than being a difference of two other ranges.

Finding the number of set bits does seem to be a function where numSetBits[a...b] = numSetBits[0...b] - numSetBits[0...a-1]

except that inversion is not such a function. Could binary indexed trees somehow be cleverly modified (like was done to support range queries and updates) in order to solve this problem?


texts: Degrees of Separation Minimization & Pathfinding Elimination Strategy for Large Networks

texts:
Assume you have a graph/network N;

 Boundary Conditions:

each vertex/node $n \in N$ can support a maximum number of $e_{max}$ connections
Nodes can join and leave the graph.
Each node $n$ has an address $0 < a < 1$, e.g. $v_{0.123987144}$.
The addresses are roughly uniformly distributed.
Each node can destroy any connection between itself and a neighbor.
Each vertex can build a connection between itself and any other node in the network.
No node can ever know $|N|$ exactly.
Each node knows only the addresses of the vertices it is connected to.
Blind requests possible: When building a new edge, a node has to send a request with a specific address to one of its neighbors. That neighbor can choose to relay the request to one of its neighbors, and so on. Alternatively, any recipient node can choose to accept the request and "impersonate" the goal vertex.

 Initial Conditions:

The network is fully connected: $|N|<e_{max}$, but growing rapidly.

 Goal:

Minimize degrees of separation
make paths predictable, given two addresses (no pathfinding required/heuristics are perfect)
Prevent feedback loops and make it "stable"
Prevent mitosis (graph separation)

 Strategies needed

What address requests should a vertex send into the graph, and when?
Which edges should a vertex drop, and when?
When should a vertex honor a request?


texts: Cores, threads and sockets: what does it mean the calculation $T = tcs$ and the number on windows task manager performance?

texts:
Well, suppose then we have an CPU system such as:

Thread(s) per core $\equiv t$ :    4
Core(s) per socket $\equiv c$:    4
Socket(s) $\equiv s$:             1

Then, we must to perform a simple calculation such as: $ 4 \cdot 4 \cdot 1 = 16 $
Therefore, in general we have:
$$ T = t\cdot c \cdot s \tag{1}$$
I guess that the equation $(1)$ gives you then the total number of threads which your system can handle simultaneously.
On the other hand, consider the figure, of windows task manager, in the following:

In the red box we clearly see the number of "Threads". So I would like to know:
What is the difference between the number given by formula $(1)$ and the number given by windows task manager?


texts: What are the theoretical and practical contributions of Multiagent Systems to science?

texts:
Speaking about multiagent systems (MAS) is about as fuzzy as talking about artificial intelligence systems (AI). They are in essence the distributed counterpart of AI.

While there are no so-called "AI theorem", AI research had given rise to many subfields, algorithms and scores of theorems (e.g. game solving, fuzzy logic, expert systems, A*, logical programming... as well as Bayesian networks and constraint satisfaction). But I fail to see a similar impact from MAS.

As far as I know all the subfields related to MAS preexisted them. For instance:

results about distributed computing (e.g. Fischer Lynch Paterson theorem, replication and load balancing strategies, decentralization, resilience, distributed algorithms...)
results from operation research (e.g. makespan measure in scheduling)
results about voting (e.g. Arrow's theorem in social choice theory)
results about competitive systems (e.g. Nash equilibrium in game theory)
results about interoperability (e.g. ontologies in natural language processing)

As far as I have seen "original" MAS contribution consist in the straightforward distribution of well known problem solving algorithms into distributed ones, whose most notable change seem to be at the epistemological level.

When the problem is decomposable, distribution actually consist in allocating subproblems to different agents:

e.g: constraint satisfaction -> distributed constraint satisfaction: most notables change: variable now belong to agents, algorithms are unchanged.

When the problem is not decomposable, distribution consist in replicating problems at the level of each agent, or having a central agent solve it:

e.g. reinforcement learning -> distributed reinforcement learning: agent apply independantly from each other the standard RL algorithm.
e.g. transport problem -> standard transport problem in operation research (no distribution)

The only really original MAS algorithm I can think of is the Contract Net Protocol, which is in essence just a broadcasting algorithm.
The only design constraint introduced by MAS that I can think of is privacy.
Mutlirobots systems, often given as an example of MAS, have been developping from standards robotics largelly ignoring MAS literature.

Therefore, what are the original contributions of MAS?

Corrolary question: Why are they relevant as a standalone research field rather than being a common placeholder name for different fields preexisting them?


texts: Let say we have a relation with 5 attributes {A, B, C, D, E}. Let say we have two candidate keys as A and B,C. Let us say we have a partial dependency as B -> E with regards to the candidate key B,C. The database designer decides that A will be the primary key of the relation. Now since we had B -> E, will it be called a partial dependency or a transitive dependency? Is the relation 2NF or not even 2NF?


texts: Plain-language example of how a functional style makes parallel programming easier

texts:
I read a few "function >> imperative/OOP" articles because I heard there was a move in imperative OOP languages toward a functional style of coding, especially encouraging pure functions when possible. One recurring argument is that by not mutating state, you don't have to worry about race conditions and locking.
I do get the logic behind that: no two processes would mutate the same data, so locking and race conditions are irrelevant. Problem is I hadn't done any parallel programming or know any functional languages, so it's hard for me to really understand. I got as far as reading about persistent data structures as replacements for large mutable structures, but I hit a wall. I'm looking for an example, in plain language, of a parallel algorithm in an imperative style and a functional style that illustrates this recurring argument.
If it helps to provide a programming problem, let's say I have an array of integers (A). People submit commands (A[i] += 1) in real time to increment an element of that array by 1 (at a valid index i). Different elements are intended to be incremented in parallel. I can imagine the imperative solution does this but it locks an index during an increment. What would a functional solution look like? I will accept answers as simple as naming a functional data structure, if I could understand it by looking it up.


texts: What are some applications of 2 stack pushdown automata?

texts: What are some real world application for 2 stack pushdown automata, as i can only find pushdown automata applications in the internet


texts:
$L_1=\{a^ku \mid u \in \{a,b\}^* $ and $u$ contains at least $k$ a's, for $k\geq 1\}$.

If it is regular, I haven't found its regular expression or any closure property to prove it.

If not, it seems pumping theorem holds for it...

Also, what about the language where the above "at least" is changed to "at most"?


texts: Algorithm for efficiently sorting large lists based on user preference

texts:
I’ll preface this question by saying I’m having a difficult time even formulating the problem, so my explanation might be fuzzy and/or I might be missing obvious solutions.

I have a list of 479 books which I would like to sort based on a “Fuzzy” criterion such as “which books would I like to read before the others in this list?”.

I took a stab at solving this by storing a record for each book in a database, and pre-populating a rank column with a unique sequential number from 1 to 479. For any particular rank, I’d like to read the corresponding book more than a book with a higher rank number. If the rank number is closer to 1, the corresponding book is one I wish to read earlier.

I created an interface that presents me with a choice between two books selected randomly from the database. After I click the book I would rather read first, the following happens:

If the rank of the selected book is already lower (more interesting) than the other, I don’t change the rank of either book;
If the selected book has a rank that’s higher (less interesting) than the other, I change the selected book’s rank to be the same as the other book, and add 1 to the rank of all the other books where the rank is more than or equal (including the other book, which would now be ranked directly below the selected book).

Finally, for each book I also store a counter of the times it has been evaluated. After I make a selection between two books, this counter increases for both the books that were presented to me. This allows me to avoid presenting books that have already been evaluated a certain number of times until all other books have been evaluated the same number of times.

I found the algorithm to be utterly ineffective: after going through all 479 of the books once, I looked at the list sorted by rank and noticed the list does not reflect at all my own perception of how I’d prioritize these books.

I’m looking for an algorithm that:

Allows me to organize the list in an order that I would perceive to be accurate based on my personal notion of which books I’d like to read first;
Can prioritize the aforementioned list with as little effort required as possible (i.e. an algorithm that requires the user to compare every book with every other book in the list in order to come to a valid sorting order isn’t ideal).


texts: Analog computers and the Church-Turing thesis

texts:
I'd like to quote from Nielsen & Chuang, Quantum Computation and Quantum Information, 10th anniversary edition, page 5 (emphasis mine):

  One class of challenges to the strong Church–Turing thesis comes from the field of
  analog computation. In the years since Turing, many different teams of researchers have
  noticed that certain types of analog computers can efficiently solve problems believed to
  have no efficient solution on a Turing machine. At first glance these analog computers
  appear to violate the strong form of the Church–Turing thesis. Unfortunately for analog
  computation, it turns out that when realistic assumptions about the presence of noise in
  analog computers are made, their power disappears in all known instances; they cannot
  efficiently solve problems which are not efficiently solvable on a Turing machine. This
  lesson – that the effects of realistic noise must be taken into account in evaluating the
  efficiency of a computational model – was one of the great early challenges of quantum
  computation and quantum information, a challenge successfully met by the development
  of a theory of quantum error-correcting codes and fault-tolerant quantum computation.
  Thus, unlike analog computation, quantum computation can in principle tolerate a finite
  amount of noise and still retain its computational advantages.

Is this a statement that noise scales faster than some power of the problem size, or can someone point me in the right direction so that I can find out more about whether these scaling limits are fundamental or merely an "engineering issue"?

To be clear, I am asking if analog computers cannot beat Turing machines in efficiency due to noise.


texts: Intersection of Deterministic Context-Free Languages

texts: If deterministic context-free languages (DCFLs) are not closed under intersection, does this mean that the intersection of two DCFLs will always be context free but may not be deterministic? Or does it mean their intersection may not be context-free?


texts:
In my lecture notes, the definition of the class NP is given as:

A language $L$ is in the class NP, if there exists a turing machine $M$ and polynomials $T$ and $p$ such that:

For every input $x$, $M$ terminates after at most $T(|x|)$ steps
If $x\in L$, then there is a "proof"(or certificate) $t\in\{0,1\}^{p(|x|)}$ such that $M$ accepts the string $\langle x,t \rangle$
If $x\notin L$, then for any string $t\in\{0,1\}^{p(|x|)}$, $M$ rejects $\langle x,t \rangle$

Firstly, are we saying that $M$ here is a universal turing machine, i.e. $M(\langle x,t\rangle)=M_x(t)$, also is it necessary to use the same $t$ for all $x$.
Also $M$ is checking whether or not $x$ lies in the $L$, so shouldn't we run just input $x$ on $M$, why is the $t$ necessary. Is there any particular reason why $t$ is called a certificate? Any help with understanding this definition would be greatly appreciated.


texts: A pda that accepts all strings over an alphabet

texts:
If you were asked to construct a pda that recognizes all strings over the alphabet {a,b,c,d}, that is

L={w | w belongs to (a,b,c,d)*}

How would that be constructed? My idea is to have one state as the initial and final state and have all transitions loop on the same state without pushing or popping anything from the stack, is that correct?


texts: Removing left-recursion in grammar while maintaining left-association of operator

texts:
I have a problem with this exercise:

  Let G be the following ambiguous grammar for the λ-calculus:

  E → v | λv.E | EE | (E)

  where E is the single non-terminal symbol, λv.E represents abstraction w.r.t. the variable v in E, and EE represents application.

  Define an LL(1) grammar G′ such that L(G′) = L(G) and the ambiguity of G is resolved by imposing the following usual conventions:

  abstraction is right associative;
  application is left associative;
  application has higher priority than abstraction.

  Show the LL(1) parsing table for G′ and the parse tree obtained when parsing the string λv1. λv2. v1v2v1.

I eliminated ambiguity setting precedence and association, obtaining this grammar:

E -> EF | F
F -> λv.G | G
G -> (E) | v

which is not LL(1), since the production E -> EF is left recursive.
However, eliminating left recursion from that production I obtain:

E -> FE¹
E¹-> FE¹ | ɛ
F -> λv.G | G
G -> (E) | v

that does not comply with requirement 1.2.

I looked for a solution on the Internet, but it seems like it is not possible to eliminate left-recursion preserving left associativity.

However, this exercise appeared on the compilers exam some years ago, so there must be a correct answer.

Thank you for your help.


texts: Decide given complexity of given function

texts: I'm trying to determine correct notation for the given functions which are $f(n) = n$ and $g(n) = (log(n))^{100}$. Moreover, I don't understand while calculating its complexity using limit because calculator shows that it goes infinity, so  f(n) is growing faster than g(n). But, I found vice versa. Could you explain me where I'm doing wrong?


texts: Considering a DFA that has an alphabet of {A,B}, and where number of characters A > number of characters B. I don't think such a DFA is possible. Can I proof the impossibility with a Pumping Lemma?


texts: Examples of context-free grammars with worst-case complexity

texts:
What are some examples of context-free grammars that necessarily trigger cubic worst-case complexity for GLR parsers?

I have seen a mention of the example S $\rightarrow$ SSS | SS | "a" but I would be interested to find more information on this and also find proofs of their worst-case complexity. Can anyone refer to papers that would cover this?


texts: Sorting an array of length $n$ in $O(m+n)$ time

texts:
I need to find a method to sort an array in $O(m+n)$ time complexity.
I understand it should be a variation on Radix sort, however I am not familiar with it or its implementation...

Input: an array $A$ of length $n$, containing values from $-m$ to $m$
Output: a sorted array $A$

Any suggestions will be appreciated, thanks!


texts: How many snakes there can be in the "snakes and ladders" game?

texts:
How to calculate the maximum allowed number of snakes in the game of "snakes and ladders" from mathematical/algorithmic point of view assuming that there is a nxn board?

UPD: My thoughts are simple, but they might be incorrect:
I suppose once any two fields on the board cannot be involved twice forming a snake it means that in nxn board there can be nxn/2 snakes


texts: Computing the rank of a multiset after inserting another element

texts:
What is the procedure for computing the rank of a multiset after inserting an element?

For instance, lets say we have a set $S = (0,1)$ containing $n = 2$ distinct elements.

The multiset $M = (1,1)$ has rank $5$ because there are $4$ multisets less than it based on lexicographic ordering: $(0), (1), (0,0), (0,1)$.

If we insert $0$, we get $(0,1,1)$ which has rank $8$. If $1$ were inserted instead we'd have $(1,1,1)$ with rank $9$.

Is there a function $f(r,x,n)$ which takes a rank $r$, an element $x$, and $n$, and returns the new rank after inserting $x$?


texts: Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$

texts:
How can I construct a PDA which accepts the language   $\{a^i b^j c^k \mid k\geq \min(i,j)\}$
I think about different solutions such as building a stack with two-state. one state is for $i < j$ and another is for $i > j$, But I think it doesn't work.
also, The idea of poping and pushing a and b is not good. I tried it. Can Someone give me a little hint?


texts: Why is Adleman's molecular algorithm for Hamiltonian Path linear?

texts:
In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability.

He claims that "The number of different oligonucleotides required should grow linearly with the number of edges", and this makes sense given the molecular encoding of the edges described in the paper, but he also claims that "the number of procedures required should grow linearly with the number of vertices in the graph".
Why is this last claim true? In other words, why isn't the assembly of edge molecules counted towards this calculation? If it were, the complexity of lab procedures would be $O(|V|^2)$, as the number of edges in a graph is bound by this function.

Thank you.


texts: How to compute number of possible paths in directed Traveling Salesman problem?

texts:
If we have directed modification of TSP, so that some routes are possible in one direction, given directed graph, could you compute number of possible tours?

What if we have supercomputer, does it make dTSP more feasible?

edit:The number of different Hamiltonian paths in undirected graph is (n−1)!/2 in fully directed version it is (n−1)!, exact number could be computed from adjacency matrix

yes but if i delete city or two from connection like this example will not be fully and this is my case:

1 to 2,3

2 to 3

3 to 1,2,4,5

4 to 2,5,1

5 to 1

so i convert dTSP to simple graph my problem is to know how many paths can i create by my edited dTSP graph so
if i have

1 to 2,3

2 to 1,3

3 to 1,2

i will have number 3!= 6 paths
but if i edit it to be like that

1 to 2,3

2 to 3

3 to 1

i will have 3 paths only

i found that if one city is delete from connections can cut paths maybe by double as i try and error with small numbers of cities so i want to know if i possibly can calculate number of paths that created by this given connections


texts: concatenation of context sensitive and context-free is context sensitive or not?

texts:
Assume that $L_1$ is context sensitive language and $L_2$ is context free language, is the language $L_1 * L_2$ context-sensitive or not?

I almost sure that is not, but can't prove it.


texts: Is it decidable whether a Turing machine M will reach state q on input s?

texts:
Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$?

As we are not given anything about the word length, I assume that we have a finite length word. Then I believe this problem is decidable. After all, we only have to check whether we come across state $q$ when we feed $w$ to $M$.

But my solution manual claims that it is an undecidable problem.

Am I correct or is the manual correct? Do we ever take into consideration a word with infinite length during such analysis?


texts: Is there any better way to find the closest points' distance?

texts:
The problem is:

  Suppose you're given $n$ points in the coordinate plane, and for convenience assume that no two of their $x$ or $y$ coordinates are the same. Design an algorithm that finds the shortest possible distance between a pair of these points. What is the time complexity of your algorithm?

Ofcourse there is a easy way to find the shortest distance in $\mathcal{O}(n^2)$. But, is there any better algorithm? I am out of idea.

Note: I am a Math major and not familiar with CS way to solve problems very much.


texts: Does there exist context-free grammar with words of length n^2 or n^3?

texts: Does there exist context-free grammar with words of length $n^2$ or $n^3$? I can't see any, we can produce all grammar with words of length $n$ ($S \to Se$), but then it seems to be impossible to substitute each $S$ with sequence of $S$'s of length $n$.


texts: How can I prove that $T(n)=\sqrt{n}T(\sqrt{n})+n$ grows as $\Theta(n\log \log{n})$?

texts:
How can I prove that if $T(n) = \sqrt{n}T(\sqrt{n}) + n$ then $T(n) = \Theta(n\log\log n)$?

I tried to define $T(n)$ by $G(n)$, prove about $G(n)$, and then to return to $T(n)$, but it's not working..