texts:
The collision entropy is defined as the Renyi entropy for the case $\alpha = 2$. It is given by

$$\mathrm{H}_{2}(X)=-\log \sum_{i=1}^{n} p_{i}^{2} \tag{1}$$

Take two random variables $X$ and $X'$ which follow the same probability distribution. The probability of a collision is then simply $P_{\rm coll} = \sum_{i=1}^{n} p_{i}^{2}$. I would then expect that we say the collision entropy is just $H(P_{\rm coll})$ i.e.

$$-\left(\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(\sum_{i=1}^{n} p_{i}^{2}\right) - \left(1 -\sum_{i=1}^{n} p_{i}^{2}\right)\log\left(1-\sum_{i=1}^{n} p_{i}^{2}\right)$$

This is in analogy with the binary entropy but with the probability replaced with the probability of a collision.

What is the motivation behind choosing $(1)$ to be the definition of collision entropy?


texts: Eliminating left recursion and left factoring this grammar

texts:
I have a grammar S-> SS* | SS+ | a
Really confused on how to remove the left recursion and do left factoring

My attempt on removing left recursion :
S -> aS'
S' -> S+S' | S*S' | epsilon
If this is correct, I'm stuck in left factoring. Help!


texts:
So i'm relatively new to computer science and have been learning set theory and am stumped on a question in it.

The question specifies that we're only looking at subsets of universe U = {0,...,n-1}. For a set S ⊆ U, the characteristic vector denoted by Xs is an n-bit string where j is 1 if and only if j ∈ S.
Example, n = 4, S = {1, 3} Xs = 1010.

it is asking what is XØ and XU. I think I am completely overthinking this but I can't figure out what XØ and XU are referring to.


texts: Many-one reductions between the set of true sentences and a particular arithmetical set

texts:
Never used this site before so not sure the best way to get help. However, I've been looking at many-one reductions in relations to sentences in logic.

Let TH(N) = {ϕ : ϕ is a first order sentence in the language of arithmetic and N |= ϕ} (Where N is the standard model of arithmetic - , x, <, +, 0, and the successor; S)

Let γ(x) be some formula with exactly one free variable, namely x. Then assume X = {n : γ(n)} to be the arithmetical subset of the natural numbers defined by γ(x).

My question is: Is there a way to show either of X or TH(N) many one-reduce to each other?


texts: References for wearable e-health systems for biosignal based health monitoring

texts:
Ubiquitous computing refers to "information technology and computer power, which in principle pervade all everyday objects" (see Friedewald and Raabe, 2010). A similar form is wearable computing, where the computing device is placed on a persons cloth/body. This topic currently gets much attention: smart watches (e.g., Apple) or glasses (e.g., google glass).

I'm interested in the topic of wearable e-health systems. As I'm just getting started with my research in this area, I'd like to ask for recommendations for good review papers, journals etc. to be used as a starting point.

The European Union has a special policy for eHealth, including various initiatives. Wearable systems [1] allow for light-weighted, cost-effective, 24h patient monitoring - especially for elderly people - that does not interfere with everyday life.

I am specifically interested in the display and monitoring of clinical relevant biosignals, for instance heart activity measured by ECG, oxygen staturation measured by puls oxygen meters. I am not intersted in patient records, health information systems, patient medication monitoring, privacy, security, compliance, etc., which are also part of eHealth.

A quick search revealed the following references.

Review papers:

Chan, Marie, et al. "Smart wearable systems: Current status and future challenges." Artificial intelligence in medicine 56.3 (2012): 137-156.

Mosa, Abu Saleh M., Illhoi Yoo, and Lincoln Sheets. "A systematic review of healthcare applications for smartphones." BMC medical informatics and decision making 12.1 (2012): 67.

Wearable eHealth devices:

Chung, Wan-Young, Young-Dong Lee, and Sang-Joong Jung. "A wireless sensor network compatible wearable u-healthcare monitoring system using integrated ECG, accelerometer and SpO 2." Engineering in Medicine and Biology Society, 2008. EMBS 2008. 30th Annual International Conference of the IEEE. IEEE, 2008.

Watanabe, Hyuma, et al. "Wearable ECG Monitoring and Alerting System Associated with Smartphone: iHeart." International Journal of E-Health and Medical Communications (IJEHMC) 4.4 (2013): 1-15.

Further topics:  there are more specific topic like papers on sensors, security & privacy, protocols & wireless networks, signal analysis & diagnosis from biomedical signals, etc.

Pantelopoulos, Alexandros, and Nikolaos G. Bourbakis. "A survey on wearable sensor-based systems for health monitoring and prognosis." Systems, Man, and Cybernetics, Part C: Applications and Reviews, IEEE Transactions on 40.1 (2010): 1-12.

Q:
What are your recommendations for papers in the area of technical aspects of wearable e-health systems, specifically the monitoring and display of biosignals such as those of the cardiovascular system excluding the aspect of security, privacy or compliance?


texts:
We have a group of employees and their company will assign a prize to as many employees as possible by finding the ones probably better than the rest. The company assigned the same $2$ tasks to every employee and scored their results with $2$ values $x, y$ both in $[0, 1]$. The company selects the best employees among the others, if there is no other employee with a better score in both tasks.

Knowing that both scores are uniformly distributed in $[0, 1]$, how can i proof that the number of the employees receiving the price is estimated near to $\log n$, with $n$ the number of the employees, having high probability?

I need to use Chernoff bound to bound the probability, that the number of winning employees is higher than $\log n$.


texts: How to prove the following language is not in R

texts:
Let $c\in \mathbb{N}$. Denote: $L _c= \{ \langle M \rangle \mid \exists _{U \subseteq \Sigma ^* }$ s.t. $|U| $ is infinite and for each $w\in U $ the TM $M$ accepts $w$ within no more than $c$ steps $\} $.

I would like to prove that for any given $c$ the language $L_c \notin R $.

I would like to find a language $L \notin R$ and find a reduction $L \leq L_c$, but Im having trouble as to which $L$ should I aim for.

I tried with $L_{acc}$, $L_{\Sigma^*}$ , but could not find what my reduction should be.

Im not necessarily looking for a complete solution, but even a hint from which language and how my reduction should look like (an idea behind the reduction) would be also great, sonce I feel Im at a loss here and dont know whre to start from.


texts: Proof that L(M) = {accepts the string 1100 } is undecidable

texts:
Let $$L_\ = \{\langle M\rangle \mid M \text{ is a Turing Machine that accepts the string 1100}\}\, .$$

To proof that the language $L$ is undecidable I should reduce something to $L$, right?

I tried with the classic $A\ TM$, but I could not figure out how to reduce properly.

How I can I proof that $L$ is undecidable?


texts: What are some problems people can solve but computers cannot

texts: I want to create a program that makes problems that people can solve but computers would struggle with. I've read that human language is very difficult and CAPTCHA looks pretty promising. Basically I want to make puzzles, riddles, and codes that a person could figure out with some effort but that cannot be automated. Any ideas or easy to understand reading materials on the subject would be appreciated, most of what I have been able to find goes right over my head haha.


texts: Are non-ordered (Slabbed) Neural Networks in wide modern use and what does Fiesler (1994) mean by Clamping Function and Ontogenic function?

texts:
In Fiesler (1994) Neural Network Classification and Formalization, he talks a lot about a more general version of neural networks, one that is not ordered into layers, but rather the network is called slabbed and the "layers" are instead called clusters. Unlike for feed-forward networks, slabbed networks may be cyclical and terminate when a stable state has been reached, rather than when propagation has reached output neurons.
Much of this paper is outdated (terminology in particular). Is this an outdated concept or are these types of networks being used and/or researched?
Also from this paper, he mentions "clamping functions", but I am not sure what he means. Here is an excerpt where he talks about clamping functions:
"clamping functions, which determine if and when certain neurons will be
insusceptible to incoming information, that is, they retain their present
activation value independent of external stimuli"
I have seen a few more recent uses of "clamping" in literature, but they tend to be referring to something different. What exactly is he talking about here and is there a modern name for this?
Similarly, he refers to ontogenic functions and ontogenic networks, which I believe we call dynamic networks, but what is the ontogenic function? I understand it dictates how the network changes, but mathematically what are the inputs and outputs? What triggers the change to start and/or stop?
I am very interested in this formal definition of neural network as a mathematical object (this tuple with topology, interconnection structure, transition functions and intial state), does anyone know of a source that gives a similarly rigorous definition of a neural network, but with more modern terminology and ideology (I imagine some developments in theory may have allowed for networks to be more general)?


texts: For which class of graphs can a minimum spanning tree always be associated to a shortest path tree?

texts:
Given a connected graph $G=(X,E)$ with positive edge weights. We assume that $G$ contains a unique min weight spanning tree $T_{\min}$ (this is true for example when for all the cuts, the edge with the minimum weight is unique). What is the necessary and sufficient condition that insures that the following holds:
There exists a vertex $x$ for which the shortest path tree obtained by starting Dijkstra from $x$ coincides with $T_{\min}$.
Example:
Without the uniqueness assumption, here is an example graph

The following  R code shows that every shortest path tree must use an inner edge that is not part of any MST:
x<-c(1,2, 1,8, 2,3, 2,11, 3,4, 4,5, 4,10, 5,6, 6,7, 6,12, 7,8, 8,9,
   #inner edges that are not part of MST due to their relatively big   weight
   9,10, 11,12)
m<-matrix(x,byrow = T, ncol = 2)
y <- c(2,2,2,1,2,2, 1,2,2,1,2,2,
     #inner edge weights
     3.5,3.5)
arcs <- cbind(m,y)
#we check only for the three vertices, the others are symetrical to them
for(i in c(1,2,9)){
   cat("\n Source:",i,"\n")
   getShortestPathTree(nodes, arcs, algorithm = "Dijkstra", source.node = i, directed = FALSE)
}


texts: Is time complexity of the greedy set cover algorithm cubic?

texts:
I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements.

Question: true or false?

Approximation Algorithms, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

  $C \leftarrow \varnothing$
  While $C \neq U$ do
   Find the set whose cost-effectiveness is smallest, say $S$.

  Let $\alpha = \frac{c(S)}{|S - C|}$, i.e., the cost-effectiveness of
  $S$.

  Pick $S$, and for each $e \in S - C$, set $\text{price}(e) = \alpha$.

  $C \leftarrow C \cup S.$

  Output the picked sets.

In the first iteration, the cost-effectiveness of $M$ sets have to be computed.

In the second iteration, the cost-effectiveness of $M-1$ sets have to be computed.

Since everything between $1$ and $M$ iterations may be needed to find the sets that cover all elements, in the mean it may be $M/2$ iterations.

I.e. in the worst case we need to compute $M + (M-1) + (M-2) + ... + 1 = M(M+1)/2$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $M^2N$.

EDIT

If the greedy algorithm outlined above does not have time complexity of $M^2N$, where's the flaw in estimating the computation time?

The following diagram shows the computation time per atomic operation versus the test index of 65 tests I ran my code on. The tests range from 6 sets to 1215 sets, and the values on the y-axis are computed as

$$
\text{computation time per atomic operation} = \text{cpu time used} / (M^2N).
$$

From what I can tell, the assumed time complexity $M^2N$ seems to model the behavior well. Otherwise, the computation time per atomic operation wouldn't be that stable. Small values for the y-axis are either due to the computation time being too short to be measured, or if the number of elements is substantially smaller than the number of sets ($N \ll M$).

EDIT (Sun APR 19 2020)

This post cites exercise 35.3-3 taken from Introduction to Algorithms (3e) claiming that the (unweighted) set cover problem can be solved in time

$$
\mathcal{O}\left(\sum_{S \in \mathcal{F}}|S|\right),
$$

where $S$ is a set of the problem description, and $\mathcal{F}$ are all the sets in the problem description.

Compared to the naming convention I'm using, this would mean that the problem can be solved in quadratic time $\mathcal{O}(MN)$. But how?

The algorithm still requires to find the set with the maximum number of elements involved, which requires to evaluate every set modulo the recently added one. Hence,

$$
M + (M - 1) + ... + 1 = (M + 1)M / 2,
$$

which is quadratic in $M$ again.

Or is there a more efficient way to do so?

EDIT (Mon APR 20 2020)

My initial estimate of $\mathcal{O}(M^2N)$ does not seem to be that bad. Refering to Introduction to Algorithms (3e), page 1119, last paragraph of section A greedy approximation algorithm, it is said

  a simple implementation runs in time
  $\mathcal{O}(|X||\mathcal{F}|\min(|X|, |\mathcal{F}|))$

where $|X|$ is the overall number of elements, and $|\mathcal{F}|$ reflects the overall number of sets.

Dividing the cpu time by this new upper bound, the variance of the time per atomic operation is clearly smaller compared to the upper bound used initially:


texts: Can this DFA be converted to a regular expression?

texts: I want to make the regular expression of this language but I can't: I tried but the regular expression didn't match some strings that it should. Is it even possible?


texts:
I'm reading the "Art of Assembly" 2nd Edition by Randall Hyde. In the book the author seems uses his own language called High Level Assembly (HLA). Coming from a C Background, I question how useful this is in learning (real x86/NASM for use on Linux) Assembly. But, looking it up there seems to be a term "High Level Assembler" (wikipedia) that gives some credibility to calling HLA "Assembly".

HLA provides ENUMs; bounds checking; multi-dimensional arrays; constant, static, and readonly variables; operators; a standard library; some error-catching; alignment and a lot of other stuff.

Where is the line drawn between an Assembler and a Compiler. From the book, it seems there is even some addressing modes not supported by HLA,

  Actually, the 80x86 does support addressing modes involving certain 16-bit registers, as mentioned earlier. However, HLA does not support these modes and they are not useful under 32-bit operating systems.

If it is a compiler, then does it "compile" the Assembly, or "assemble" the Assembly? Or is "High Level Assembly" just a procedural programming language that has little to do with Assembly?


texts: NP-complete problem of partitioning into several sets with a Hamiltonian cycle

texts:
How to prove the $NP$-completeness of the language $L$ = $\{$$(G, k)$: the vertices of an undirected graph $G$ can be partitioned into $k$ pairwise disjoint sets of pairwise different sizes so,
that all the corresponding induced subgraphs have a Hamiltonian cycle}.
I had no problems how to prove that this language is in the $NP$, but it is not clear to me how to prove that this language is in the $NP-hard$ class.


texts: Determining the set of valid next terminals when generating from a CFG

texts:
I am trying to generate random sentences from a context-free grammar. During each step, the next non-terminal to be generated is determined according to some probabilistic criteria irrelevant to this question. Where I am stuck is, given a grammar and the partial sentence generated so far, how do I determine the set of non-terminals that can be generated at the next step according to the grammar?

Below is an example grammar in BNF and a partial generation.

<expr> ::= <term> "+" <expr> | <term>
<term> ::= <term> "*" <factor> | <factor>
<factor> ::= "(" <expr> ")" | <const>
<const> ::= "0" | "1" | "2" | "3" | "4"

Supposed generated sequence so far: ( 1 +. In this case, we can easily see that the next token to be generated should come from the set {"(", "0", "1", "2", "3", "4"}.

Is there an algorithm to determine this set given a general grammar and a partial generation, or generate the sentence in a way that makes this set available at each step?


texts: Approximate cache size & cache line size from optimal tile size

texts:
I wrote a program that multiplies two $N\times N$ matrices represented as 2D arrays by tiling the matrices into subsets with variable tile size. Each matrix element is an 8-Byte integer. I tested the runtime with a number of tile sizes ranging from $1$ to $N$ and found that the runtime is optimal with a tile size of $S$.

I ran this program on a computer that has 3 cache levels and I know the cache size, line size, and associativity of each but suppose I didn't. Is there a way that I could approximate the cache size and cache line size of one or all components of my memory hierarchy using the information I wrote in the first paragraph?


texts: Heuristics and libraries for the knapsack problem

texts:
A student of mine is studying the knapsack problem (0-1 with a single objective). She is also talking to an industry partner who has realistic problems she can try solving (between 1000 to 10000 items).

We're having some trouble finding good references and existing implementations, mostly because I am not an expert in this area, but I ended up working with the student anyhow. I would appreciate some help with:

What are some reasonable heuristic and/or approximation 0-1 knapsack algorithms that are not too complicated that the student could study? (References please.)
Are there existing libraries which look for solutions or approximate solutions?


texts: Does there exist a subset of substrings for reconstructing another string?

texts:
I am looking for a high performance algorithm to check whether I can reconstruct a given string using a given set of substrings. More details:

Let's say our strings are over the alphabet $\Sigma$.

Inputs:

A string $S \in \Sigma^*$
A finite set of strings $A = \{a_1, a_2, ..., a_n\} \subset \Sigma^*$.

Output:

Whether $\exists m: \exists b_1, b_2, \ldots, b_m \in A: b_1+b_2+\cdots+b_m = S$

where $+$ is string concatenation.

For example, if $S={}$"$abcd$" and $A = \{$"$ab$"$,$"$cd$"$,$"$ac$"$\}$, the answer is True.
For the purposes of this question, assume that strings in $A$ can be reused multiple times if necessary.


texts: What structure is used for accessing the most frequent elements top k over a stream of elements?

texts: Let's say you want the top k elements. Then given the array, there is an O(n) O(n) space approach. But what if you have a stream of elements, this means that each time you'd append an element to the end of your list, you'd have to do this O(n) time O(n) space approach. Let's say your elements are distinct elements of a set. You can maintain a frequency map, but you'd still have to do the O(n) approach to find the top k elements. Is this is what is done in production? What data structure is used to efficiently keep top k elements with updated frequencies?


texts:
So, I'm currently studying Newton method used for finding the 0's of a function, however my professor has only announced  that the speed of this algorithm can be more than quadratic, however I'm wondering when this happens, since in the demonstration used by him to explain the quadratic case, there is no evidence about the "more than quadratic"
Using Taylor and Lagrange
$f(\xi)=f(x_n)+f'(x_n)(\xi-x_n)+\frac{f''(z_n)}{2}(\xi-x_n)^2$
$-\frac{f(x_n)}{f'(x_n)}=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$
$x_{n+1}-x_n=\xi-x_n+\frac{f''(z_n)}{2f'(x_n)}(\xi-x_n)^2$
$e_{n+1}=\left|x_{n+1}-\xi\right|=c_ne_n^2 \quad \text{with} \quad c_n=\frac{1}{2}\frac{\left|f''(z_n)\right|}{\left|f'(x_n)\right|}$
Can someone please tell me when (example) the order of the convergence is cubic, and why?=


texts: Constructing a crown graph given an independent set

texts:
A crown in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:
(a) The set of neighbors of vertices in $C$ is precisely $H$, i.e. $H = N(C)$,
(b) $C = C_m \cup C_u$ is an independent set, and
(c) There is a perfect matching between $C_m$ and $H$
Theorem:
Any graph $G(V,E)$ with an independent set $I$, where $|I| ≥ \dfrac{2n}{3}$ , has a crown $(H, C)$, where $H ⊆ N(I), C ⊆ I$ and $C_u \ne ∅$, that can be found in time $O(nm)$ given $I$. $(n=|V|, m = |E|)$

I am trying to code an algorithm to find such a crown in $O(nm)$ time
The only way I could think of finding a crown given an independent set is to take subsets of the set: $I$ and check for all the three conditions of a crown. However, taking all subsets of $I$ will take exponential time right? How to find it in $O(nm)$ time. I just want an algorithm with polynomial time. It need not be $O(nm)$... It can be in the form $O(n^c m^d)$ where $c,d$ are constants.


texts:
We see that there is a sign, exponent, and mantissa part for the notation. But, there is no location for the significant bit.

Why isn't it necessary to store an integer part of significant in IEEE754 floating point notation?


texts:
I'm working on a website which gets a list of objects like this:

Object { model: "modelhandler.comment", pk: 5, fields: Object }

where the field objects contains this:

Object { user: "TestUser",id: 6, video: 7, description: "test new video comment lol", reply_to: 5, uploaded: "2018-01-12T09:14:24.281Z", updated: "2018-01-12T09:14:24.281Z", indent: 0}

The goal of the site is to find all comments which have reply_to set to a number (not null) and increment it's indent value and all it's children's indent value.

for example consider this list of comments:

comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 0, reply_to: 1)
comment 4 (id: 4, indent: 0, reply_to: 3)
comment 5 (id: 5, indent: 0, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

Now I want to run trough the list and set all indent values according to the reply_to value. so the list becomes:

comment 1 (id: 1, indent: 0, reply_to: null)
comment 2 (id: 2, indent: 0, reply_to: null)
comment 3 (id: 3, indent: 1, reply_to: 1)
comment 4 (id: 4, indent: 2, reply_to: 3)
comment 5 (id: 5, indent: 1, reply_to: 1)
comment 6 (id: 6, indent: 0, reply_to: null)

Now this has to happen inside a for loop which allready runs trough the list once:

for(var i = 0; i < array.length; i++) {
    //do stuff here
    //set the indent value here
    if(reply_to)
        indent++;

    //do more stuff here
}

this was my idea for achieving this but it will only increment indent once as it travels trough the list only once. is there a better way to do this?


texts: Why should small o notation has to satisfy the equation for all values of the constant

texts:
Big-O of a function i.e. f(n) = O(g(n)) is such that both c and $\textbf{n}_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the following condition exists:

f(n) = o(g(n)) means for all c > 0 there exists some $\text{n}_0$ > 0 such that
0 ≤ f(n) < cg(n) for all n ≥ $\text{n}_0$. The value of $\text{n}_0$ must not depend on n,
but may depend on c.

But for the conditions,

for all c > 0
$\text{n}_0$ may depend on c

we can simply select the value of $\text{n}_0$, based on the value of c,  so that the equation is satisfied. So why should it satisfy for all values of c ?


texts: Calculating Unique Addresses In Word Addressable Memory

texts:
According to a textbook assigned for my class, if I have memory that is
4M X 16, to address this memory (assuming word addressing), we need to be able to uniquely identify $2^{12}$ different items, which means we need $2^{12}$ different addresses. I've been racking my brain, and I can't seem to figure out how they're coming up with the value of $2^{12}$ unique addresses.. Can anyone help me out here?


texts: What is the difference between a problem and an algorithm?

texts:
I can say that $x * y$ is a problem, but I can also say that $x * y$ is an algorithm for finding a rectangle area.
I have been reading Wikipedia about an algorithm and a problem, but I am not sure about their definitions. Could you please explain it to me in more detail?


texts: How can I translate (i.e. reduce) an arbitrary instance $(S, t)$ of Subset Sum into an instance of 0-1 Knapsack? I'm also given a hint: you may assume that all members of $S$ are positive integers.


texts: Verifying if a greedy solution is optimal for a specific instance (Set cover)

texts:
Say I have an instance of the Set Cover problem, and use the typical greedy algorithm to obtain a solution.

Is there an efficient way of verifying if, for that particular instance, the given solution is optimal?


texts: What does $\alpha_r\supset\beta_r$ mean in the tolerance definition of System Z?

texts:
I'm reading up on System Z introduced by Judea Pearl (in System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning). A central definition is that of tolerance of a subset $R'$ of a rule set $R$ for a rule $r = \alpha_r\to\beta_r$ (denoted by $T(r\ \vert\ R')$). Tolerance of $R'$ for $r$ is defined to be the set of satisfiable formulas $$(\alpha_r\land\beta_r)\bigcup_{r'\in R'}(\alpha_{r'}\supset\beta_{r'})$$
(see page 2 of the article by Pearl).

I don't understand what $\alpha_{r'}\supset\beta_{r'}$ is supposed to mean. Can anyone explain?


texts: Is there a good way to hash abstract binding trees?

texts: The hash function should be invariant under alpha-renaming. Using de Bruijn notation seems to be possible, but it requires alpha-converting the whole tree when a binding is created, and has the unhappy consequence that a substructure of an abt is not a well-formed abs (since the de Bruijn indices are broken). So, is there a good (neat, elegant and/or efficient) way to construct such a function? By the way, is there any study on this matter? Any help is appreciated!


texts: Suggestions for a source of algorithm design problems?

texts:
I’m finishing up Roughgarden’s two-part algorithms course on edx, and it was good, but I didn’t actually ‘design and analyze’ many algorithms, the questions mostly tested whether you understood the textbook.
I’m looking for some problems where I can drill a bit with the core concepts from the course (divide and conquer, graph algorithms, greedy algorithms, dynamic programming, algorithms for NP-hard problems).
Ideally, they would be challenging but accessible to an undergraduate/early-graduate student, and have detailed solutions.
Any suggestions?


texts: Transform PDA with acceptance of final state + empty stack to just final state

texts:
"It is a well known result that every PDA with acceptance condition of an
empty stack and reachability of a final state can be transformed to an equivalent PDA with acceptance
condition requiring only reachability of a final state. Transform PDA ____ to an equivalent PDA with
acceptance requiring only reachability of a final state."

I'm just a bit confused on what steps I have do to. My thought process is...final state + empty stack acceptance is a subset of just a final state acceptance? When I try to 'transform' my PDA, it ends up looking exactly the same as the original.


texts: N-dimensional generalization of map and reduce?

texts:
Is there any conceptual generalization of higher-order functions like map and reduce but for N-dimensional objects (e.g. arrays or tensors)?
For mapping, I guess it would be a point-wise generalization. In the case of reduction, I have more doubts because the iteration is not trivial. Perhaps it would take an additional argument specifying the dimension (or dimensions?) along which the reduction is applied?
Are such higher-order functions defined in algebra? E.g. do they have a specific name and are studied as such?


texts: Changing variables in recurrence relations

texts:
Currently, I am self-studying Intro to Algorithms (CLRS) and there is one particular method they outline in the book to solve recurrence relations.

The following method can be illustrated with this example. Suppose we have the recurrence

$$T(n) = 2T(\sqrt n) + \log n$$

Initially they make the substitution m = lg(n), and then plug it back in to the recurrence and get:

$$T(2^m) = 2T(2^{\frac{m}{2}}) + m$$

Up to this point I understand perfectly. This next step is the one that's confusing to me.

They now "rename" the recurrence $S(m)$ and let $S(m) = T(2^m)$, which apparently produces

$$S(m) = 2S(m/2) + m$$

For some reason it's not clear to me why this renaming works, and it just seems like cheating. Can anyone explain this better?


texts: Irregularity of $\{a^x b^y c^z : x=2y \lor y>z\}$

texts:
Show that $L=\{a^x b^y c^z : x=2y \lor y>z\}$ is not regular using the pumping lemma.

I know that in order to use the pumping lemma, I have to assume that $L$ is regular. Then I know that there is a $p$ such that every $w \in L$ such that $|w| \ge p$ can be represented as $xyz$ with $|y| \ne 0$ and $|xy| \le p$, so that $xy^iz \in L$ for all $i \geq 0$. But I have not been able to choose $w \in L$ that serves me to finish with the lemma, taking into account the restrictions that $L$ has.


texts: Giving a regular grammar for the language

texts:
I am trying to brush up on my regular grammar knowledge to prepare for an interview, and I just am not able to solve this problem at all. This is NOT for homework, it is merely me trying to solve this.

I want to give a regular grammar for the language of the finite automaton whose screenshot is below, please help me, and if you can, a step by step answer would be of great assistance. Thank you!


texts: How to prove that a language is not context-free using pumping lemma

texts:
I'm trying to prove that that language isn't a context free:

$ L = \{ w11w \mid w\in \Sigma^* = \{0,1\}\}$

I succeed to prove that $L = ww$ isn't context free, but not the language above.   What am I doing wrong?


texts: Regular expression for all binary strings avoiding 0110

texts:
Consider the language
$$ L = \{ w : w \in {0,1}^* \text{ and } w \text{ doesn't contain } 0110 \text{ as a substring.} \} $$
What is a regular expression for this language?
I thought of $1(1)^*0(0)^*$.
But this seemed to not contain any strings starting with $0$. If I do $1(1)^*0(0)^* | 0(0)^*1(1)^*$ then it can contain $0110$. How can I improve my answer to this question?


texts: What is the difference between multi-layer, multiplex and heterogeneous networks?

texts:
I know when we have multiple networks connected to each other, we can call every network a layer and the whole network is called multi-layer. But I don't know what is the difference between multi-layer and multiplex and heterogeneous?

Thanks


texts:
It is a joke with the title of a book I am reading: "But how do it Know? - The Basic Principles of Computers to Anyone".
The author is explaining a basic unit of memory with NAND gates:

I think I get the idea behind this component. 's' is what determines when memory is set, and 'i' is what gets "stored". So if it starts with both inputs on, the changes in 'i' are relevant, because the output 'o' mirrors 'i'. If 's' is switched off, no change in 'i' is relevant. The result being the previous state of 'i' is stored in 'o', in other words, its state when 's' was on.
Now, my question. Let's say I start with both 'i' and 's' on, 'o' will be the same as 'i'. And after that, if I switch 's' off, the author says 'o' will retain its previous state:

I have trouble understanding what happens in gates 3 and 4 in the second point in time. I am assuming there's no current left in the wire connecting 'o' to gate 4, so I am picturing the following:

wires a and b are on
the wire connecting 'o' to gate 4 and wire c are off
gate 4 outputs off, so c is still off, and gate 3 also outputs off
the output 'o' gets changed from on to off, and nothing is stored from the previous point in time.

I'm sort of visualizing a "racing condition" between 'a' and 'b', but that's most likely not the right mindset. What is missing in my line of thought? How does wire 'o' remember it was previously on? I hope my question is not too confusing.
At earlier points in the book, the author says two things about gates that caught my attention:

“(...) how do you get electricity at the output if both inputs are off?” Well, that is an excellent question, and the excellent answer is that every one of these devices is also connected to power.

Scott, J Clark. But How Do It Know? - The Basic Principles of Computers for Everyone (p. 18). John C Scott. Kindle Edition.

A computer gate generates a third bit from two other bits, it doesn’t open and close or stop or let anything through. The meaning of this computer term “gate” doesn’t seem to fit into the common meaning of the word, but sorry, I didn’t make up the name, that’s just what it is called.

Scott, J Clark. But How Do It Know? - The Basic Principles of Computers for Everyone (p. 19). John C Scott. Kindle Edition.
Does it mean that each gate does not depend only on the current that comes from the inputs, that if needed, it can be powered by a third source, which keeps it on, preserving the previous state of 'o' that gets to gate 4?
I really hope this is not too confusing. I'm giving my first steps into this topic and I'm not a native-speaker.


texts: When is a permutation k-wise independent?

texts:
I am a bit confused about what it means for a permutation to be k-wise independent.

If I pick a permutation uniformly at random from $\sigma \in S_n$ then isn't it true that for any $k$ integers, $i_1,i_2,..,i_k$ $\in \{1,2,..,n\}$, the numbers $\sigma(i_1),\sigma(i_2),..,\sigma(i_k)$ are k-wise independent?


texts: Sanity check about a linear programming problem

texts:
given the linear program:

minimize $x+y$

subject to,

$ax+by \leq 1$

$x,y \geq 0$

I need to find real numbers $a,b \in \mathbb{R}$ such that the program (a) is infeasible, (b) is unbounded, and (c) has a unique optimal solution.

Since we are asked to minimize the sum of two non-negative numbers the solution for all $a,b \in \mathbb{R}$ is $(x,y)=(0,0)$, right?

I cannot see any potential values of $a,b$ which would make the program infeasible or unbounded, because we are always looking to minimize the sum of non-negative numbers.


texts: What are some advanced background topics I'll need for distributed systems and networks research?

texts:
I am a new graduate student in Computer Science who would like to be able to read and understand modern and new distributed systems research papers. My current background / courses and understanding is in the level of undergraduate and beginner graduate level courses in:

Networks (TCP/IP stack and applications)
Distributed Systems (Graduate level course with Time (logical/vector clocks), 2PC and 3PC, Multicast and membership, election, Consistency , Consensus and Quorums (Paxos), DHTs and Overlays and some modern applications like ZooKeeper etc)
Undergraduate Algorithms, Discrete Mathematics and Theory of Computation (basic DFA/NFA and intro to Turing Machines with no rigorous mathematics)

However, I find this background insufficient to read modern research in networks and distributed systems and in particular, I am not aware of modern protocols like QUIC and the formal methods mentioned in the papers which I believe include some sort of model checking and the likes. Also many of the topics I have mentioned above in distributed systems - I lack the background to verify and prove correctness of these protocols and even follow the proofs that they have given.

Any suggestions on a reading list that can prepare me to be in a position to understand modern research in this area would be very helpful.


texts: Why floating point representation uses a sign bit instead of 2's complement to indicate negative numbers

texts:
Consider a fixed point representation which can be regarded as a degenerate case of a floating number. It is entirely possible to use 2's complement for negative numbers. But why is a sign bit necessary for floating point numbers, shouldn't mantissa bits be using 2's complements?

Also why do the exponent bits use a bias instead of a signed-magnitude representation (similar to the mantissa bits) or 2's complement representation?

Update: Sorry if I didn't make it clear. I was looking for the reason of how floating point representation is shaped. If there is no strong implementation trade-off between the alternatives, then could someone explain the historical aspects of the floating point representation?


texts: permutations sampling by probability matrix

texts:
I am looking for effective and reliable algorithm which is able to generate random samples of permutations by square doubly stochastic probability matrix $P$ (n x n) distribution ($\sum_{i}p_{i,j} = \sum_{j}p_{i,j} = 1$, $i,j = 1,2,...,n$).

Probability matrix elements $p_{i,j}$ define probability of $i = \pi(j)$ and $0 <= p_{ij} <= 1$.

The sampled permutations should correspond to the defined probability matrix $P$ and probability of each permutation should correspond to the following permutation probability

$$p(\pi)=\frac{\prod_{i} p_{i,\pi(i)}}{\sum_{all \pi}\prod_{j} p_{j,\pi(j)}}=\frac{\prod_{i} p_{i,\pi(i)}}{perm(P)}$$

Example: Probability distribution matrix

$$ P = \left( \begin{array}{ccc}
0 & 1 & 0 \\
1/2 & 0 & 1/2 \\
1/2 & 0 & 1/2 \end{array} \right) $$

produce only two permutations $\pi_1 = (2 1 3)$ and $\pi_2 =(2 3 1)$ with the same probability $p(\pi_1) = p(\pi_2) =1/2$

This question is a follow-up to Random permutations by probability matrix

I tried a few variations of node histogram based sampling algorithm (NHBSA) by Shigeyoshi Tsutsui. This method is used as a main tool on permutation optimization problems. But the results are not very promising. So, I ask this question here, to learn what is current state of art on this topic.

I tried to test a few algorithms, but all these methods produce permutations with more or less distorted probability matrix even for small n (3 <= n <= 10 ). This is the reason why I am asking for help.

  Some comments here states that interpretation of matrix $P$ and permutations probability $p(\pi)$ are not clear enough to define unique permutations distribution.

  So, is possible to use $\prod_{i} p_{i,\pi(i)}$ for ranking of permutation probabilities, where permutations $\pi$ are generated randomly only by (0,1) restriction matrix via Hungarian algorithm for bipartite graph matching?

Comment:
I am convinced now, that only "simple" way how to solve my problem is to generate arbitrary (random) permutations $\pi$ which satisfy to (0,1) restrictions in probability matrix only (elements $p_{i,j}>0$ should be transformed to $p_{i,j}=1$) and then rank all these permutations by $\prod_{i} p_{i,\pi(i)}$ probability.

The problem how to effectively generate (0,1) restricted permutations (permutations with restricted positions) is different problem.


texts: I want to know where there is the flaw in my argument

texts:
I came across following problem to finding whether the following language is decidable or semi-decidable or not even a semi-decidable.

$L: \{\langle M\rangle: M\space is\space a\space TM\space and\space |L(M)| \ge3\}$

Now thinking intuitively I conjectured that this language is semi-decidable. We can say yes when the input does belong to $L$. But, we can not say no when the input does not belong to $L$.

Now, I formulated following reduction from complement of halting problem $\overline{HP}$ which is not semi-decidable (non $RE$).

$\overline{HP}: \{\langle M, w\rangle : M\space is\space TM\space and\space it\space does\space not\space halt\space on\space string\space w.\}$

$\tau(\langle M,x\rangle) = \langle M'\rangle$.

$M'$ on input $w$ works as follows. It  erases w, puts $M$ and $x$ on its tape, and runs $M$ on $x$ and accepts if $M$ doesn't halt on x. Otherwise it rejects.

Proof of validity of reduction:

$\langle M,x\rangle \in \overline{HP} \implies M\space does\space not\space halt\space on\space x \implies M'\space accepts\space all\space inputs\space \implies|L(M')| \ge 3\implies M' \in L$

$\langle M,x\rangle \notin \overline{HP} \implies M\space does\space halt\space on\space x \implies M'\space rejects\space all\space inputs\space \implies|L(M')| < 3\implies M' \notin L$

According to above reduction $\overline{HP}$ should be recursively enumerable$(RE)$ which it is not. So, $L$ should not be $RE$ but it indeed is $RE$. So, my reduction must be flawed.

Please point out where I messed up.


texts: Can one find the minima of a convex function efficiently?

texts:
Say I have a real valued convex function $f$ on the hypercube $[-1,1]^n$ and let $f'$ be its restriction on the discrete hypercube $\{-1,1\}^n$.

Is there any $poly(n)$ algorithm that for any class of $f$ (and $f'$) can find the minima of it?
Is there any relation known between the point where $f$ minimizes and the vertex where $f'$ minimizes?  Like if knowing one of them helps find the other in $poly(n)$ time?


texts: Configurations and CNF formula for neighboring configuration

texts:
A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its configuration graph $G_{M,x}$ as a directed graph whose nodes correspond to all the possible configurations and there is an edge from a configuration $C$ to $C'$ if $C'$ can be reached from $C$ in one step.
First question:
In Arora-Barak (snapshot below), they say that these nodes can be encoded in a binary string of length $O(S(n))$. Such encoding contains the state, all symbols under the head, and non-blank content of work tapes with special marking to denote the location of the head. I think this is not correct since such an encoding doesn't contain the input head position. If we don't store the input head position, which requires O(\log n) bits, then two nodes can map to the same encoding, which seems wrong. Am I right? Although storing the input head position will not increase the length of the encoding since we are assuming in the book that $S(n) > \log n$.
Second question: Next Arora-Barak says that we can construct a CNF formula $\phi_{M,x}$ such that for any two strings $C$ and $C'$, $\phi_{M,x}(C,C') = 1$ iff $C$ and $C'$ encode two neighboring configuration in $G_{M,x}$. I am not able to figure out the proof of this claim with the kind of encoding that I have described above i.e. encoding in which we also store the index of input head. Suppose a configuration C has $q_1, q_2, \dots, q_c$ bits for state, $h_1,h_2, \dots, h_{O(\log n)}$ bits for input head positions, $w_1, w_2, \dots, w_{S(n)}$ bits for work tape content and $wh_1, wh_2, \dots, wh_{S(n)}$  bits for work tape head position, where $wh_i$ is equal to 1 if the head is on the $i$th cell, else it is equal to 0. Then how with such an encoding we can construct a CNF formula as described at the beginning of this question?


texts: Minimal, "natural" set of operations to manipulate a binary tree

texts:
Consider binary trees with some abstract values at the leaves. A tree t2 is said to be "derivable" from a tree t1 iff the set of values in the leaves of t2 is included in the set of values in the leaves of t1. In particular, some values can be removed and some can be duplicated.

I'm looking for a minimal set of somewhat "natural" operations on binary trees that can be composed to transform a tree into any of its derivable trees.

By natural I mean operations which are local to the root of the tree or its vicinity, happen in constant time,  and can be somewhat visualized.

For instance, swapping the left and right subtree of the root of performing AVL like rotations would qualify as natural operations.


texts: Coin Change Problem Recurrence Relation with one parameter

texts: I have been looking through the recursive formulation for the coin change problem here and am wondering if it is possible to define the function $ C(N, m) $ in one parameter as $C(N)$, therefore not depending on the set $ S_{m} $? What would this function look like in general? If a concrete example is needed what would it look like for the set of coins {3 cents coin, 4 cents coin, 5 cent coin}?


texts: Finding the point with minimum x-ordinate, lying between two y-ordinates

texts: Given a set of points $P=p_1,p_2,..p_n$ in $R^2$ in where $p_i=(x_i,y_i)$,finding the point with smallest x-ordinate having y-ordinates between $y_1$ and $y_2$, where $y_1$ and $y_2$ are given as inputs. I can compare the point with other points which gives me an $O(n)$ time algorithm ? Can this be improved any further ?


texts:
Does $(0 + 10^{*}1)^{*}$ simplify to the following language: Set of all binary strings with even number of ones.
In specific, does the * inside the brackets get evaluated first or the outer * gets evaluated first. Or does it even matter while simplifying as what we finally need is the set of all strings possible with this expression?


texts: Does the following algorithm has amortized constant time per element?

texts:
Consider the following streaming ``algorithms'':

When an element $x$ arrives, flip a fair coin until it shows ``heads''.
Fix a random hash function $h:U\to\{0,1\}^\infty$ (i.e., it maps elements into infinite bit strings). When an element $x$ arrives, do $LZ(h(x))$ operations, where $LZ$ is the number of leading zeros in $h(x)$. Notice that for any element $x$, the distribution of time spent is same as in (1).

Clearly, both algorithms spend in expectation $O(1)$ time per element, and their worst case is unbounded.

The key difference is that algorithm (1) makes the coin flips independently for each arrival, and (2) fixes a distribution such that every time $x$ arrives, it spends the same amount of time.

(1) should clearly be called amortized constant time.
(2), however, might spend more than constant time if the input consists of many appearances of an element $x$ for which $LZ(h(x))$ is large.

  Would you consider (2) to have an ``amortized'' constant time?

If not, is there anything more accurate than saying that it has "expected constant time per element"?

While these ``algorithms'' are clearly useless, there exist algorithms with a runtime similar to (2) (e.g., see here).


texts: Computer Architecture, Memory Interleaving. Decoding step can be interleaved?

texts:
A CPU has a cache with block size $64$ bytes. The main memory has $k$ banks, each bank being $c$ bytes wide. Consecutive $c$ − byte chunks are mapped on consecutive banks with wrap-around. All the $k$ banks can be accessed in parallel, but two accesses to the same bank must be serialized. A cache block access may involve multiple iterations of parallel bank accesses depending on the amount of data obtained by accessing all the k banks in parallel. Each iteration requires decoding the bank numbers to be accessed in parallel and this takes $k/2ns$.The latency of one bank access is $80ns$. If $c=2$ and $k=24$, the latency of retrieving a cache block starting at address zero from main memory is:
One of explanation I found is:

Cache block = 64 bytes.
Each bank in memory is 2 bytes and there are 24 such banks. So, in 1
iteration we can get 2*24 = 48 bytes and getting 64 bytes requires 2
iterations.
So, latency = k/2 + 80 + k/2 + 80 (since in each iteration we need to
select the banks and the bank decoding time (k/2) is independent of
the number of banks we are going to access)
= 12 + 80 + 12 + 80 = 184 ns
But total memory capacity here is 2*24 = 48 bytes

What I'm unable to understand is, when 1st memory access is going on, can't we decode the 2nd bank request.
So, that would make it, $12 + 80 + 80$ as in the 1st memory access of $80$, we have decoded the 2nd bank req and as soon as 1st memory access is completed, we will start the 2nd memory access which is decoded.
Are my thoughts conceptually correct? Or am I missing something?


texts: Parsing text, then searching it: one entry per position, vs. 1 JSON column per text

texts:
I have a Rails application using Postgresql.

Texts get added to the application (ranging in size -- as short as a few words, to as long as, say, 5,000 words?).

The text gets parsed, both automatically and by hand, to associate each word/position in the text with specific information (part of speech, grammar tags, lemma, definition_id).

Given a lemma, or a part of speech, or grammar tags, or a definition_id (or a combination), I need to be able to find all other text positions in the database that contain the same information (lemma / part of speech / definition_id / etc.).

There are only two options (that I can think of):

A table to store each word position, with columns for each of the above attributes. Finding what I need would be a breeze, my life would be super easy.
A JSON column on the Text object, to store all the word positions. Would be fewer entries, but, a) Constructing a query would be difficult, b) That search would probably be slow, and c) It might take up more storage space than a separate table.

Can I choose option 1? Is storing 1 entry for every word a very bad idea? That’s a lot of entries!

If there is another option I haven’t considered, please enlighten me.

Thanks,
Michael King


texts: Update labels of a tree depending on ancestors of nodes in linear time

texts:
You are given a tree $T=(V,E)$ along with a designated root node $r \in V$.The parent of any node $v \ne r$, denoted $p(v)$, is defined to be the node adjacent to $v$ in the path from $r$ to $v$. By convention, $p(r) = r$.

  For $k > 1$, define $p^k(v) = p^{k−1}(p(v))$ and $p^1(v) = p(v)$ (so $p^k(v)$ is the $k$-th ancestor of $v$).

  Each vertex $v$ of the tree has an associated non-negative integer label $l(v)$. Give a linear-time algorithm to update the labels of all the vertices in T according to the following rule: $$l_{new}(v) = l(p^{l(v)}(v)).$$

This is problem 3.20 in Dasgupta's Algorithm.

My thoughts so far:

The problem comes down to how you find the $l(v)$-th parent of a node $v$, for all $v \in V$, in linear time.
Since chapter 3 is about depth first search, I'm trying to use it. The only way to get the parent once we have the child is to do something in the post-visit routine

explore(v):
  v.visited = true
  previsit(v)
  for all u adjacent to v:
    if u.visited == false:
      explore(u)
  postvisit(v)

If $l(v) = 3$ then somehow we need to send this information up 3 levels in the recursion. But depth first search only moves one level at a time. I don't know how we can preserve the information across multiple calls.


texts: Show that any LL(k) grammar is unambiguous

texts: I am confused on several areas of this. First, this is so obvious I am finding it hard to prove. Second, what are some definitions, axioms, or lemmas of an ll(k) grammar that I can use to build up a contropositive argument that for any ambiguous grammar it cannot be an LL(k) for any k? I've found this to be my best approach. Feel free to answer as opening or as theoretically as felt necessary, this was poorly explained in lecture and quite frankly any addition theory or hints is appreciated.


texts: Find a partition of multiset of binomial coefficients with constriants

texts:
Given the multiset $S$ where the elements are defined by the binomial coefficient ${n \choose k}$ where $n \in \mathbb{N}$ and $
0\leq k \leq n$ find the partition $P$ of $S$ such that the sum of elements in the subsets is smaller or equal to the largest binomial coefficient and the number of subsets in the partition is minimized.

For example take $n = 4$.

$S = \{{4 \choose 0}, {4 \choose 1}, {4 \choose 2}, {4 \choose 3}, {4 \choose 4} \} = \{ 1, 4, 6, 4, 1\}$

Then the partitions

$P = \{ \{4,1\},\{4,1\}, \{6\} \}$

$Q = \{ \{4,1,1\},\{4\}, \{6\} \}$

are the partitions we are looking for. The largest binomial coefficient $6$ has to be on it's own by definition. Then we have $\{1,4,4,1\}$ left and there cannot be any sum larger then six so we have make two sets of $\{1,4\}$ or make the set $\{1,4,1\}$ once and $\{4\}$. I am more interested in getting the $P$ then $Q$ since the sums are closer together but this is not a hard requirement.

I wonder if a non brute-force algorithm exists for this since we do know a little bit of the contents.


texts: Bipartite Graph - How to determine largest subsets that are all connected

texts:
I have a bipartite graph $G = (U,V,E)$, where $U$ and $V$ are disjoint node sets and $U \cup V$ is the set of all vertices, and $E$ is the set of all edges.
I'm looking for subsets $U' \subseteq U$ and $V' \subseteq V$ such that there exists an edge $\{i,j\} \in E$ for all $i \in U', j \in V'$ and
$|U'| + |V'|$ is maximum.

Ideally, I'm looking for the absolute best solution (a single one is sufficient if there is more than one), but happy to find any solution so that $U'$ contains at least 50% of $U$ and $V'$ contains at least 50% of $V$ (and no solution if no such solution exists).

The naive algorithm (construct all subsets, calculate if they satisfy the requirements and pick the largest) does not seem very promising to find a quick solution.

I'm not that familiar with the terms in graph theory, so I'll be perfectly happy with references to "standard problems" if that's what I'm looking for.


texts: Conditions for a node to be a leaf node on DFS tree

texts:
Question:
Consider the DFS tree generated by a DFS on a connected graph. Write below the necessary and sufficient condition for a node v to be a leaf node on the DFS tree. The condition must be in term's of v's discovery time d[v] and finishing time f[v].

I honestly have no idea what the answer to this question from a past exam may be...


texts: Are there any context-free languages that are not regular but can be generated using a right-linear or left-linear grammar?

texts: I understand that every regular language can be generated using either a right-linear or left-linear grammar, however, does that go the other direction? In other words, do there exist any context-free grammars that are not regular that are either right or left-linear?


texts: Regular language is closed given transposition of rightmost character to leftmost

texts: It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I've been unable to come up with a generalized 'concept' or 'proof'  that shows it's true for all regular languages. Could anyone help me out? It's on occasions like these that I see the value of formal definitions for DFA (instead of just drawings), however it's been a while since I've studied those.


texts: Distributed algorithm can be executed in a single process

texts:
Looking at a "Distributed" algorithm from a textbook on distributed algorithms (e.g. Building a spanning tree, Broadcast/Convergecast.) I found that one can implement it using Golang's concurrency primitives (i.e channels and goroutines)

AFAIK "distributed" means things are happening on multiple machines. But this is running in a single process. (the fact that all threads are sharing memory is irrelevant since the algorithm's implementation doesn't depend or make use of it)

So can we call the system consisting of the threads + channels a distributed system?
This seems to have all characteristics:
- threads run independently and in parallel much like nodes (assuming enough processors)
- communication via message-passing

If we choose to not call it a distributed system, then why is the algorithm labeled distributed if it can run on a non-distributed system?


texts:
Consider $$ \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad  \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$

My lecture notes say that this is an equality, can someone point me to the theorem (or explain) why this is ?

I've observed that one power of the logarithm in the exponent disappeared but I couldnt find a theorem resembling any of the above.


texts: Proof high-entropy sequences are hard to compress

texts:
When comparing random-variable sequences generated from probability distributions, what's a formal proof that a distribution with higher entropy produces a sequence that's "harder" to compress?

In background reading, I haven't come across this analysis for a general, abstract probability distribution. The information theory texts I've looked at, rather, tend to focus their analysis on comparing compression algorithms rather than comparing the distributions producing the data.


texts: Determining the particular number in $O(n)$ time and space (worst case)

texts:
$\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]$ is an odd number. Try to find the number whose occurrence is an even number.

There is an $\Theta(n\log n)$ algorithm: we sort $A[1\ldotd n]$ into $B[1\ldotd n]$, and break $B[1\ldotd n]$ into many pieces, whose elements' value are the same, therefore we can count the occurrence of each element.

I want to find a worst-case-$O(n)$-time-and-$O(n)$-space algorithm.

Supposing that $m=\Omega(n^{1+\epsilon})$ and $\epsilon>0$, therefore radix sort is not acceptable.
$\DeclareMathOperator{\xor}{xor}$
Binary bitwise operations are acceptable, for example, $A[1]\xor A[2]$.


texts: Approximate algorithms for class P problems

texts:
As a part of my Algorithm course we studied Approximate Algorithms for NP-complete or NP-hard problems, e.g. "set cover", "vertex cover", "load balancing", etc. My professor asked us as an extra activity to learn an approximate algorithm for a P problem. I searched a lot on google but all I found were approximations for NP problems.

I was wondering if anybody can help and tell me a approximate algorithm for a problem with already a exact polynomial algorithm?

It will be very much better if the algorithm be a short and easy one.


texts: Is {|M prints more than 300 non-blanks on input w} decidable?

texts:
Let

$$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$

Is $L_{300}$ decidable?

My intuition is it is decidable because given $M$ and $w$, we need to check for a bounded number of steps which would be a function of the number of states in the finite automata of $M$, input alphabet and the length of the input $w$. Can someone give an intuition for getting the exact bound or tell if its undecidable ?


texts:
I've been trying to understand why, for instance, even though there are oracles $A$ for which $P^A \neq NP^A$, we still don't know if $P=NP$.

As I understand it, it's because it's easy to construct languages that can only be efficiently taken advantage of in a non-deterministic settings. For example, pick a single arbitrary string and call that your language; then all you need is non-determinism to try every string and you're okay in $NP$, yet still trapped into brute force in $P$.

My question is, what exactly separates this from a regular $NP$ problem? Why is this fundamentally different from an $NP$ problem that accepts only on some arbitrary predetermined certificate (or is it even possible to construct such a problem)?

Is it just the fact that $NP$ problems are required to have some sort of structure, whereas in the relativised case we're free to build our language arbitrarily? Or is there some deeper difference I'm missing?


texts:
I am trying to prove the statement in the title. I have a hard time proving it is true. The way I go about it is by using the definition of $\omega$:

$c\times g(n) < f(n)$; So that if $f \notin \omega(g)$, then $\mathrm{NOT} (c\times g(n)<f(n))$ means that $c\times g(n) \geq f(n)$. And that by definition is Big-Oh.

Is this a correct way of proving the statement in the title?

Thanks,
Lukasz

Remarks:

The definition of $\omega$ is that $f(n)$: for all constants $c > 0$, there exists a constant $n_0>0$ ...

So, the negation of that would be: There exists $c\times g(n) \geq f(n)$, correct? Can you think of an example that would disprove the statement?

Note to the comments:

I think I understand what you are saying. Since the definition states that "for all $c>0$, there exists a constant $n$ ..." The negation of that is: "There exists a constant $c>0$, for which this is not true..."

However, for any $c>0$ there is a constant $n$ big enough that will make the statement true. Am I wrong?


texts: Is the set of pairs of TMs at least one of which accepts the empty word semi-deciable?

texts:
L = { < M1,M2 > | M1,M2  are TM's and Ɛ ∈ L(M1) ∪ L(M2) }

Where Ɛ = Epsilon

I know that this language is undecidable, but why it is semidecidable too.

What i have tried is =>

Using Rice's Theorem, part 2

T(no) = (0,1)^+ and T(yes) = (0,1)*

Which gives that T(yes) is not a subset of T(no), and this says that it is semidecidable.

Is my understanding right ?


texts: When did polynomial-time algorithm become of interest?

texts:
I would like to understand why and when polynomial algorithms became of interest.

When did people realize the role and importance of efficient versus non-efficient algorithms? Did that happen when the concept of an algorithm was discovered, or the the term algorithm used.

For instance, I've looked at some textbook of Algorithms such as the one by Cover, Leiserson, Rivest, and Stein "Introduction to Algorithms" 3rd ed. they states in the Preface "Before there were computers, there were algorithms. But now that there are computers, there are even more algorithms, and algorithms lie at the heart of computing".

Would it be the case that, before computers were invented, we were more interested in finding new ideas for solving problems, and were not so concerned with the time it took.

So I am interested in knowing when people became conscious of the importance of efficiency,  started to study it more systematically.

Are there some reference papers on the subject, on the history of algorithms and their motivations, and on the concern with efficiency.

[note from the translator]
The topic of the question may seem a bit wide, as I tried to keep the meaning without betraying the author. But it seems a good and useful general question that can be adressed with a few general remarks and some facts and examples


texts: Relation/use of irrational or transcedental numbers in computer science?

texts:
I'm wodering about the relationship between the theory that studies irrational/transcendental numbers and computer science. For example, I found this paper (but was unable to get the full text)
Pseudo-random number generator based on irrational numbers

I found the paper because I started looking for a RNG that uses the property that irrational/transc. numbers don't have repeating decimals.
I wanted to know in what other ways we can use or have a motivation to study irrational/transcendental numbers, because of their use in CS.

I'm ignorant on the matter, so I appreciate if someone more knowledgeable can provide examples when the two subjects connect themselves. Like the paper above.


texts: What is a make sense (meaningful) example of language that an unrestricted grammar could generate?

texts:
I have learned that:

Unrestricted grammar is used to define (or describe) a formal language.
Unrestricted grammar is used to define recursively enumerable set [https://en.wikipedia.org/wiki/Recursively_enumerable_set][1].

I’d like to find a meaningful example or a meaningful application for #1 case which is similar to below context sensitives grammar example to learn the purpose of unrestricted grammar. I could find a meaningful example for context sensitives grammar but I could not find a one for the unrestricted grammar yet. Could you help me?
Language for “Network racing game record” with below record instances:
Mr. Bean Male Player 1
Ms. Emma Female Player 2
Mr. Hải n/a Computer 3
Ms. Tú n/a Computer 4
Production rule:
S ⟶ Title Name TAB Sex UserType TAB Rank
Title WomanName ⟶ "Ms. " WomanName
Title ManName ⟶ "Mr. " ManName
WomanName TAB Sex "Player" ⟶ WomanName TAB "Female" "Player"
ManName TAB Sex "Player" ⟶ ManName TAB "Male" "Player"
Name TAB Sex "Computer" ⟶ Name TAB "n/a" "Computer"
Name ⟶ WomanName
Name ⟶ ManName
Sex ⟶ "Male"
Sex ⟶ "Female"
UserType ⟶ "Player"
UserType ⟶ "Computer"
Rank ⟶ "1"
Rank ⟶ "2"
Rank ⟶ "3"
Rank ⟶ "4"
WomanName ⟶ "Emma"
WomanName ⟶ "Tú"
ManName ⟶ "Bean"
ManName ⟶ "Hải"
TAB ⟶ "\t"
Thank you for your reading,


texts: What does exactly theoretical computer science entail?

texts:
I am confused by the term "theoretical computer science". How can I distinguish which part of computer science are considered "theoretical" and which not?

To expand further, take Machine Learning. Is the study of Machine Learning Theoretical Computer Science? To me it is, because we are studying the computational qualities of learning, without declining our study into a particular technology or application, but usually, I hear machine learning spoken as a part of applied CS or engineering.


texts: Are regular languages closed against an intersection that keeps words with the same number of ones?

texts:
How can we show that the class of regular languages is closed under the following operation?

Let $L_1$ and $L_2$ be laguages over $\Sigma=\{0, 1\}$.

The operation is: $$\{x \in L_1 \mid \text{ for some } y \in L_2, \text{ strings } x \text{ and } y \text{ contains equal numbers of } 1s \}$$

Is the only way to show this to create a NFA of the new language?

I have done the following:

Let $M_{L_1}=(Q_{L_1},\Sigma ,\delta_{L_1},q_{L_1},F_{L_1})$ the DFA that recognizes $L_1$ and $M_{L_2}=(Q_{L_2},\Sigma ,\delta_{L_2},q_{L_2},F_{L_2})$ the DFA that recognizes $L_2$.

Let $M=(Q,\Sigma ,\delta,q,F)$ the NFA that recognizes the operation.

$Q=Q_{L_1}\times Q_{L_2}, \ \ q=(q_{L_1},q_{L_2})$.

Is this correct? Which is the transition function?


texts: How to show that this algorithm for evaluating polynomials works?

texts:
I'm having trouble showing how to solve this problem in particular the part where it asks "To Show that the following pseudo-code fragment finds the value of the polynomial..."

How do I exactly show that? I don't understand what that would entail and my professor isn't exactly that helpful he says to prove it for all $n$, but I don't understand how to show that mathematically through programming. He says not just to give a particular example, but rather show it works for all polynomials.

The whole question is this:

  It is required to find the value of the polynomial $$P(x)=\displaystyle\sum_{k=0}^n a_k x^k$$

  Show that the following pseudo-code fragment finds the value of the polynomial, given the coefficients $a_0,a_1,a_2,...a_n$ for a value of $x$.

y = 0;
i = n;
while (i >= 0) {
   y = a[i] + x * y;
   i = i - 1;
}


texts: Is there a way to perform calculations of Mandelbrot set using only integer numbers?

texts:
I would like to create program in JavaScript (JS) which draws Mandelbrot set with arbitrary precision (zoom). In JS there is build in integer type BigInt which support simple operations like +,*,/,power on arbitrary precision integer numbers. JS not support calculations on arbitrary precision floating point numbers.

Question: Is there a way to perform calculations of Mandelbrot set using calculations based only on integers (with arbitrary precision) - if yes how to do it?


texts: Running time for threshold function evaluation?

texts:
A threshold function is a function $f: \{0,1\}^n \to \{0,1\}$, defined by $n$ integer-valued weights $w_1, w_2, \ldots, w_n$ and an integer valued threshold value $w_0$. It works as follows:
$$f(x_1, x_2, \ldots, x_n) = \begin{cases}0 \text{ if } \sum_{i=1}^n w_ix_i \ge w_0 \\ 1 \text{ otherwise.} \end{cases}$$.

I'm confused about the running time of evaluating $f(x)$ for some input $x \in \{0,1\}^n$. If we evaluate the running time as a function of $n$ (the number of bits that $f$ receives), then will this depend on the number of bits needed to represent $w_0, w_1, \ldots, w_n$?


texts: Complexity of a decision problem: system of linear equations over finite field with restricted solutions

texts:
I have a system of linear equations over a finite field $\mathbb F_p \cong \mathbb Z_p$, and I'm interested in the decision problem of whether there exists a solution where all of the variables $x_i$ are in the set $\{0, 1\} \subset \mathbb F$. In particular, I'm trying to determine whether this problem is $\mathcal{NP}$-hard.
Example
One system of equations over $\mathbb F_3$ is:
$$
  \begin{alignat*}{2}
  &x_1\begin{bmatrix}1 \\ 1 \\ 0\end{bmatrix} +
  x_2\begin{bmatrix}0 \\ 0 \\ 0\end{bmatrix} +
  x_3\begin{bmatrix}0 \\ 2 \\ 0\end{bmatrix} +
  x_4\begin{bmatrix}1 \\ 0 \\ 1\end{bmatrix} \\ + \,
  &x_5\begin{bmatrix}2 \\ 1 \\ 0\end{bmatrix} +
  x_6\begin{bmatrix}0 \\ 1 \\ 1\end{bmatrix} +
  x_7\begin{bmatrix}1 \\ 0 \\ 0\end{bmatrix} +
  x_8\begin{bmatrix}1 \\ 2 \\ 0\end{bmatrix} =
     \begin{bmatrix}0 \\ 0 \\ 2\end{bmatrix}.
  \end{alignat*}
$$
This system of equations is satisfiable with entries in $\{0,1\}^8 \subset \mathbb F^8$, namely $$
  \begin{align*}
  (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8) &= (0,0,0,1,0,1,1,1) \hspace{1em}\text{or}\\
  (x_1, x_2, x_3, x_4, x_5, x_6, x_7, x_8) &= (0,1,0,1,0,1,1,1).
  \end{align*}
$$
An unhelpful (?) reduction
One suggestion that was given to me was turning this into a system of quadratic equations in the following way: define auxiliary functions coordinatewise $$
\begin{align*}
  w_1 &= x_1 + x_4  + 2x_5 + x_7 + x_8 \\
  w_2 &= x_1 + 2x_3 +  x_5 + x_6 + 2x_8 \\
  w_3 &= x_4 + x_6 - 2,
\end{align*}
$$ and use these to solve the system of quadratic and linear equations $$
  w_1 = w_2 = w_3 = x_1^2 - x_1 = \cdots = x_8^2 - x_8 = 0.
$$
However, the MQ-problem (Multivariate Quadratic equations over a finite field) is $\mathcal{NP}$-hard, so this reduction doesn't help. However, this set-up is a quite special case, so I'm holding out some hope that the original problem might still be in $\mathcal{P}$.

Is there a polynomial-time algorithm for determining the existence of a solution of linear equations over a finite field with restricted variables? Or is it known if this problem is $\mathcal{NP}$-hard like the MQ-problem?


texts: Solve Max 3 color problem using 3 color decision problem

texts: I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute force searching every combinations of edges?


texts: Proving $L'=\{uv : u \in L \; \land v \in L^R \; \land |u|=|v|\}$ is a CFL with closure properties

texts:
Given a language $L$ over $\Sigma=\{a,b\}$ let us define
$L'=\{uv : u \in L  \; \land v \in L^R \; \land |u|=|v|\}$

Prove: if $L$ is regular, then $L'$ is a context free language.

I know how to solve it by building a push down automaton and proving it acceps $L'$, but I'm trying to solve it by using closure properties of context free languages (e.g closure under homomorphism, intersection with a regular languae, etc.) but I couldn't think of such solution. Any ideas?


texts: Regular expression for words longer than 2 containing at most two x-s

texts:
I want to make a regular expression for the language consisting of words whose length is at least 3 and which contain at most two $x$'s, that is,
$$\{w\in \{x,y\}^* \mid |w|\geq3\text{ and the number of }x\text{'s in }w \text{ is at most } 2\}$$
I wrote:
$$
x^+(x+y)^+y^+
$$


texts: I wonder whether the following language is regular:  $$ L = \{ \ w \in \{a, b, c\}^* \ | \ w = uv \ \ and \ \ \#_a(u) + \#_b(u) = \#_b(v) + \#_c(v) \  \} $$ where $\ \#_x(w) $ is the number of occurrences of$\ x $ in$\ w $.


texts: How hard is recovering an invertible binary matrix from its check sums?

texts:
This is a follow-up question on my previous one, How hard is recovering a binary matrix from its check sums?.  Consider the following problem, which adds an extra restriction that the matrix be invertible:

Parity Problem

INPUT: Two vectors $R_{n*1}$ and $C_{1*n}$.

QUESTION: Is there an invertible binary matrix $A_{n*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$?

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

  What is the time complexity of the Parity problem? Is it NP-complete? Is it efficiently solvable?

I care about invertibility over GF(2).  A square matrix is invertible (over GF(2)) if and only if it has non-zero determinant (after reducing modulo 2).


texts: Having trouble understanding blatantly non-private definition because of Little-o notation

texts:
I was pretty confident that I understand asymptotic notation until now. However, I am having a hard time understanding some basic definition that use asymptotic notation, specially little-o.

Definition 8.1.A mechanism is blatantly non-private if an adversary can
construct a candidate database 'c' that agrees with the real database 'd' in
all but o(n) entries, i.e.,‖c−d‖0∈o(n).

A bit of context. 'd' is a database where each row is one individual 'i' with 'n' individuals in total. the database has just one column representing some important questions. The values of the column can be 0 or 1.
'c' is a candidate database, a database that will try to be as similar as possible to the database 'd', it has the same structure one row for each individual and values for the column of {0,1}. Both are treated as a vector.
I watched a lecture and the informal description of the professor was "database 'c' will agree with database 'd' in 99,9..% of the cases".
But my interpretation of the definition is exactly the opposite "database 'c' will agree with database 'd' in all entries except 99,9..%".
My definition seems a bit odd to a "blantly" non-private mechanism. But I cannot understand how "except o(n)" would mean that a minority of the entries would not be equal in both databases.


texts: Owned state in MOESI protocol-transitions?

texts:
I understand that MESI is a subset of the MOESI cache coherency protocol. But what does the Owned state in the MOESI protocol represent? What are the differences in state transition due to the extra Owned state in MOESI as compared to MESI?

For example consider same cache line in processor P1 is in OWNED state & processor P2 is in SHARED state. What happens when there is a write request to P2?


texts: Given a Bayesian network, say a -> b -> c, all binary random variables (I won't show the CPTs, assume they are given). You are told b and c are true. How do you calculate the P(a=True)?


texts: Queue, moving the element at the tail to the head

texts:
Suppose I have a queue where I pull from left and push to the right, and suppose I have the contents in the queue as $a b c @ d e$ (from left to right, left is head, right is tail).

Is there a simple algorithm that doesn't require extra structures that makes $e$ at the head? meaning to get us to the queue $eabc@d$?

P.S.: I need an algorithm like that for the purpose of a queue automaton.


texts: Third Normal Form and Boyce Code normal form

texts:
I know that this is not a question answer site but for sake of explaining my doubt I have to post the entire question..

  Consider the following statements.

If relation R is in 3NF and every key is simple, then R is in BCNF
If relation R is in 3NF and R has only one key, then R is in BCNF

Both 1 and 2 are true
1 is true but 2 is false
1 is false and 2 is true
Both 1 and 2 are false

Ans given is $a$, but how can it be so?

I agree with the first statement but for the second one consider that we have a relation $R={\{A,B,C,D\}}$ where $AB$ is the key, and say $C->B$ then it satisfies $3nf$ right? But  it is $NOT$ in $BCNF$ right? as here we have $non-prime$  $deriving$  $a$  $prime$  $attribute$


texts: Checkers algorithm - find the best last move in the game given the positions of all pieces

texts:
This is the FinalTurn task of the Manganum 2017 challenge.
This is the problem and I need to solve it in a timely and performance-efficient manner, which I have not been able to do so far:

  A checker game on an infinite board between players A and B is in progress. There are two types of pieces in checkers: pawns and queens. Pieces can move only diagonally and forward. A  queen can move any number of steps in one of these two directions. If there is a piece belonging to player B on the line of player A's queen's movement, player A can beat it by leaping over it and optionally passing some more empty fields. Player A can beat only one of player B's pieces in one move. After beating one of player B's pieces in this way, player A can continue his turn and make another move, but only if he can beat another piece. Player A gains 1 point for beating a pawn and 10 points for beating a queen. Player A is left with his last piece: a queen. Now it is A's turn − the last turn in the game. Player A wants to know the maximum number of points he can score in a single turn. Can you help?

  $T is a string of N characters with pieces values. "p" and "q" represent player B's pawn and queen, and "X" represents player A's queen. Arrays $X and $Y are the x and y coordinates of pieces.

  For example, given:

$X = [3, 5, 1, 6];
$Y = [1, 3, 3, 8];

  $T = "Xpqp";

  the function should return 10

Do you know a good DP (dynamic programming) algorithm that would find the solution for the problem efficiently? In my solution:
-I used the buffer for already found maximum possible scores for individual fields, so I don't do double checks.
-Also, I put all enemy (player B) pieces in a two dimensional array, for easier detection if there is enemy piece on a certain field (if [x][y] is not set, then there isn't).
-I am doing the check for each field that it didn't cross the border of no possibility of getting any more points (no more pieces to be beaten beyond this point), so there are three borderlines:
a) one that limits the height (if we are on the same level as the highest enemy piece, no use checking if any more can be beaten, because there isn't)
b) two borders that are left and right diagonal that form the imagined border angle.
Despite this, I only got 46% on the assessment online test.


texts: What is the shortest total path between pairs of points?

texts:
I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.
Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.
Any pointers welcome.


texts:
My question is about the control in the Turing Machine. As far as I know, the control of the Turing Machine is just a set of states. If the Machine needs to record something, it needs to write on the tape.

The following is an excerpt from Michael Sipser's Theory of Computation, the passage is about how a Turing Machine can find the leftmost Cell. What is written is pretty straight forward. But what I don't understand is the part written in bold.

  "A trickier method of finding the left-hand end of the tape takes
  advantage of the way that we defined the Turing machine model. Recall
  that if the machine tries to move its head beyond the left-hand end of
  the tape, it stays in the same place. We can use this feature to make
  a left-hand end detector. To detect whether the head is sitting on the
  left-hand end, the machine can write a special symbol over the current
  position while recording the symbol that it replaced in the control.
  Then it can attempt to move the head to the left. If it is still over
  the special symbol, the leftward move didn’t succeed, and thus the
  head must have been at the left-hand end."

What does he mean by this exactly? What does recording a symbol in the control mean? Isn't the only (and infinite) memory of the TM the tape?


texts: Interval scheduling with shared resources between steps

texts:
I'm working on a (real life!) scenario that involves scheduling workers on an assembly line. Let's say it involves steps a -> b -> c -> d -> e, and each step takes a different amount of time. There are a lot of orders coming through the assembly line, all with different due dates. So an order might come in on May 3rd and need to be finished by May 11th, and another could come in on May5th and need to be completed by May 9th. In this case, it's trivial to switch from one order to another that is higher priority.

Here's the challenge: some workers are responsible for multiple steps. So for example, steps b and d may involve the same 4 workers. Any configuration is possible and can change hour by hour. So there could be 4 workers on b and 0 on d at the start of the day. Then 3 and 1 around lunch, and then 0 and 4 at the end of the day.

The only limitation is that using a resource at either b or d reduces the capacity for the other step by 1.

I'm unclear how to handle this with the standard greedy approach. If the steps each had different workers, I would simply prioritize each task based on earliest due date.

With the constraint of shared resources, does it still make sense to consistently pick the task with the earliest overall due date? For the following jobs,

A: Start: May 3 Due: May 11
B: Start: May 5 Due: May 9

and the restriction that b and d each use the same workers, this approach would lead to all 4 workers working on (job A, task b)  at first, then all switching to B->b as soon as job B is available, then B->d, before all switching back to A->d.

Is this approach correct? Does it matter how long the individual tasks take?


texts:
What is the terminology used for speaking about complexity, when we don't study it asympotically (but exactly) ?

Thank you


texts: Proving P = NP without mathematical statements / computer program

texts:
This is my first post after being a passive user for some time now.
I wish to ask some questions if I may.  I am not a mathematician but my question relates to the field of maths/computer science.  In particular, the P vs NP problem.  I am aware that this is a problem that elite professionals have not yet been able to solve ...

Regardless, I would like to ask:

If a person who is neither a mathematician nor a programmer were to come up with a flowchart or a series of steps written in basic English that allegedly provides a solution to one of the P vs NP problem, would that be counted as 'proving' that P = NP .. in order to claim the Clays Institute prize :) ? Or is it a must for one to write the solution as mathematical proofs / computer program?

Thank you.


texts: Convolutional Neural Networks - Where should I start from?

texts:
I will soon be starting a part-time job within a start-up and I've been assigned to a project where I'll have to build a CNN that recognizes and counts people in various kinds of videos.

My CEO knows I have no training or experience in Computer Vision and he suggested that I should spend all my working hours in the first month on understanding the necessary concepts behind CNNs and then proceed with the implementation for the next two months.

I know that mathematics are a huge part of understanding the necessary concepts. I'm a CS 3rd year undergrad and my relevant studies in math are comprised of the following:

Calculus $I - IV$
Linear algebra and differential equations (didn't study partial differential equations)
Complex analysis

I've managed to pass these courses with maximum scores. Since mathematics is a very dear interest of mine, I spent a lot of time on actually understanding each and every concept I've studied so far.

So, my questions is, are there any textbooks on CNN(preferably free) you could recommend, given my experience and goal?

Also, since my mathematical training may not be enough, I would also appreciate insights (or textbooks) on what should I learn, or improve while studying the concepts behind CNNs.


texts: Selection problem on the union of two ordered dictionaries

texts:
Suppose we are given two ordered dictionaries S and T each with n items, and that S and T are implemented by means of array-based ordered sequences. Describe an O(log n) time algorithm for finding the kth smallest key in the union of keys from S and T. (assuming no duplicates)

I am confused on what the question is asking. I am assuming the keys are not ordered, otherwise all you would have to do is compare the first key in each dictionary, or is that what array-based ordered sequence means? Also are we creating a larger dictionary that holds both S and T inside? Would this add to the complexity if so? For the search algorithm, would we use a binary search since its complexity is O(log n)?


texts:
https://en.wikipedia.org/wiki/Type_erasure says

  type erasure refers to the load-time process by which explicit type annotations are removed from a program, before it is executed at run-time. Operational semantics that do not require programs to be accompanied by types are called type-erasure semantics, to be contrasted with type-passing semantics. The possibility of giving type-erasure semantics is a kind of abstraction principle, ensuring that the run-time execution of a program does not depend on type information. In the context of generic programming, the opposite of type erasure is called reification.

Are both reification and type passing semantics  opposite to type erasure?
What are the relation and differences between reification and type passing semantics? Do they mean the same?

The best that I can find about them are from the two following books. But I am still not quite sure about my question.

About type erasure vs type passing, Types and Programming Languages by Pierce says:

  23.7 Erasure and Evaluation Order

  The operational semantics given to System F in Figure 23-1 is a type-passing
  semantics: when a polymorphic function meets a type argument, the type is
  actually substituted into the body of the function. The ML implementation of
  System F in Chapter 25 does exactly this.
  In a more realistic interpreter or compiler for a programming language
  based on System F, this manipulation of types at run time could impose a
  signiﬁcant cost. Moreover, it is easy to see that type annotations play no signiﬁcant role at run time, in the sense that no run-time decisions are made on
  the basis of types: we can take a well-typed program, rewrite its type annotations in an arbitrary way, and obtain a program that behaves just the same.

  For these reasons, many polymorphic languages instead adopt a type-erasure
  semantics, where, after the typechecking phase, all the types are erased and
  the resulting untyped terms are interpreted or compiled to machine code.

About type erasure vs reification, Programming Language Pragmatics by Scott says:

  C# 2.0 was able to employ an implementation based on reiﬁcation rather than
  erasure. Reiﬁcation creates a different concrete type every time a generic is instantiated with different arguments. Reiﬁed types are visible to the reﬂection library (csNames.GetType().ToString() returns "Arbiter 1[System.Double]"),
  and it is perfectly acceptable to call new T() if T is a type parameter with a zero-argument constructor (a constraint to this effect is required). Moreover where
  the Java compiler must generate implicit type casts to satisfy the requirements of
  the virtual machine (which knows nothing of generics) and to ensure type-safe
  interaction with legacy code (which might pass a parameter or return a result of
  an inappropriate type), the C# compiler can be sure that such checks will never
  be needed, and can therefore leave them out. The result is faster code.

Thanks.


texts: Is O(ln n) "exponentially faster" than O(n)?

texts: I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear the phrase "exponential speedup". I'd like to avoid overselling my work.


texts:
I must show that this language is decidable but I think it's not

{D, Ρ} | D is a DFA and P is a ΡDA which L(D) ∩ L(Ρ) = ∅ }
Here what I think

I give a reduction from E(TM). I suppose that this language is decidable.
Let T be a Turing machine that decides it. Then we can construct a Turing machine T´ deciding E(TM), that behaves as follows on input .
(a) Simulate T on input , where D´ is a Turing machine recognizing the empty language.
(b) Accept if and only if T accepts.
Suppose that D accepts the empty language. Then T accepts , and so T´ accepts.
But suppose that D accepts some string. Then T rejects , and so
T´ rejects. Thus, T´ decides (ETM).

Can anyone help?


texts: Defining the halting problem for non-deterministic automata

texts:
The primary definition of Turing machine (TM), at least in my own reference
textbook (Hopcroft+Ullman 1979) is deterministic.

Hence my own understanding of the halting problem is primarily for
deterministic TM, though I am aware that it may be considered for other kinds of automata.

I also noticed that determinism is often more or less implicit in the way
people often refer to TM or to the halting problem. The wikipedia page
on the halting problem is a good example of that.

But, there seem no reason for such a limitation. Given a family
$\mathcal F$ of automata that can be non-deterministic, the halting
problem for $\mathcal F$ may be defined as:

  Is there a uniform decision procedure such that, given an automaton $A\in\mathcal F$ and an input $x$, it can decide whether there is a
    halting computation of $A$ on input $x$.

(This is not quite the same as saying that the computation of $A$ with input $x$ will terminate.)

Indeed, that seem the only way to give some sense to discussions about
the halting problem for Linear Bounded Automata (LBA) which are
primarily non-deterministic automata.

So my question is whether I am correct, and whether there is a reason (and which reason)
for this apparently second class treatment of the halting problem for
non-deterministic automata.


texts: How to prove that a predicate is prefix closed

texts:
Suppose we have the predicate

$\qquad A.p.q ≡ (∀i \mid p≤i≤j<q : X.i≤X.j)$

which says that $X[p..q)$ is ascending.

Apparently, the predicate holds for empty segments, is prefix closed and is postfix closed.

I would like to prove that the predicate above is indeed prefix closed, but I am not able to; that is, I am unable to prove that

$\qquad A.p.q \implies (∀s \mid p≤s≤q : A.p.s)$

and I wondered if somebody could help?


texts: Why do derivation tree not make sense for context-sensitive grammars?

texts:
I don't understand the line in the paper "Mappings and Grammars on Trees" by William C. Rounds, the passage:

  Transformational theory, as developed by Chomsky
  [7] and many others, deals with the notion of phrase-structure grammar, and with certain mappings defined on derivation trees associated with the grammar. Derivation trees do not make much sense for context-sensitive grammars, because they depend on the order of carrying out a derivation. We will therefore assume that mappings are to be defined on context-free derivation trees.

Thank you.


texts: What was the first public reference to bloom filters where the number of hash functions vary?

texts:
In traditional bloom filters, each item is hashed some fixed number of locations. One variant of this is to hash items a varying number of locations within the same bloom filter.

This idea is presented in Zhong et al., Optimizing data popularity conscious bloom filters, PODC '08 and Bruck et al., Weighted Bloom filter, IEEE Information theory '06. However, I know of an independent and roughly contemporary "discovery" of this idea in industry that wasn't published.

This idea seems like the kind of thing that may have been independently discovered multiple times and I'd like to find the earliest public reference to cite. It's possible this exists somewhere in the IR literature as a variant of "signature files", or elsewhere with terminology that I'm not familiar with.

In the IR literature, there's Faloutsos et al., Design of a signature file method that accounts for non-uniform occurrence and query frequencies, VLDB '85, which is quite close but if I'm reading the paper correctly the paper only does the math for splitting terms into two separate classes and doesn't generalize the math like Zhong et al. or Bruck et al.


texts:
I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable.
I would say that $L_1$ is decidable because we can build a decider S.
S="on input w": (rough outlined)

breadth first search
(a) if no accept state was found, accept
(b) else reject

Am I wrong with my guess?
$\overline{A_TM}$={<M,w>|M is a TM and does not accept w}


texts: Vertices reachable from negative-weight cycles in Bellman-Ford

texts:
TLDR: I want to know if there's a simple way to fill in distances for all vertices reachable from negative weight cycles (not just ones on the cycle itself) once Bellman-Ford has found a negative-weight cycle.
The Bellman-Ford algorithm finds single-source shortest distances $d$ for a graph of $|V|$ vertices by making $|V|-1$ passes through all $|E|$ edges with weights $w$, and then checking each edge $u \rightarrow v$, with weight $w(u,v)$, for negative-weight cycles. If $v.d > u.d + w(u,v)$, then we know that there exists a negative weight cycle consisting of some path from $v$ to $u$, then the edge $(u,v)$. It's straightforward to find every vertex on that cycle and set all their $d$ to $-\infty$.
However, this also must mean that any vertices reachable from but not on this cycle must also have $d = -\infty$. One way to update all their distances is to collapse each cycle to a vertex and then perform DFS from each such "cycle vertex", setting $x.d = -\infty$ for every reachable vertex $x$.
I'm wondering if there's a faster way to update all the distances, involving perhaps a smaller modification to Bellman-Ford?


texts:
I'm trying to implement L-BFGS but I can't quite figure out how to do step sizes. I tried small fixed step sizes, but for some reason the iterates always explode whenever memory < variable size (which is kind of the whole point). So I thought I'd try some back tracking line search.

My issue is, I don't want to re-evaluate the function or gradient, because those are the most expensive steps. I have all the current iterates $g$ gradient, $s=x-x_{prev}$, $y=g-g_{pref}$, $H^{-1} y$, $H^{-1} g$ etc available, and I can do operations of  order of the variable size.

Are there any line search methods that can be used especially for this purpose, that basically don't require recomputing any function, gradient, or hessian for the intermediate points?

Thanks!


texts: Undecidable predicate logic is decidable by people?

texts:
Logic in computer science (By Michael Huth,Mark Ryan, second edition, page 132) says

  Every φ can, in principle, be discovered to be valid or not, if you
  are prepared to work arbitrarily hard at it; but there is no uniform
  mechanical procedure for determining whether φ is valid which will
  work for all φ.

For me, it sounds contradictory because I take your ability to decide any formula as a uniform mechanical procedure. If you can do it, then you have a uniform mechanical procedure. What do I fail to understand?

Just to be clear what validity means here, the discussion happens in the context of validity definition:

  Given a logical formula φ in predicate logic, does ⊨ φ hold, yes or
  no?


texts: Is there a pda with maximum 3 state for every CFL?

texts:
This is the first question I'm asking here
I'm trying to understand whether we can construct a PDA with a maximum of 3 states for every possible CFL or not? if so how?


texts: Merge $k$-sorted arrays - without heaps/AVL tree in $O(n\log(k))$?

texts:
Given $k$-sorted arrays in ascending order, is it possible to merge all $k$ arrays to a single sorted array in $O(n\log(k))$ time where $n$ denotes all the elements combined.

The question is definitely aiming towards a Min-heap/AVL tree solution, which can in fact achieve $O(n\log(k))$ time complexity.

However i'm wondering if there exists a different approach, like a merge variant which can achieve the same result.

The closest I've seen is to merge all the arrays into one array which disregards their given ascending order, than doing comparison-based sort which takes $O(n\log(n))$ but not quite $O(n\log(k))$.

Is there an algorithm variant which can achieve this result? Or a different data-structure?