texts: Efficient algorithm to find the nth number in a base-k numeral system with only different digits

texts:
I am looking for an efficient algorithm for the following problem.

There is a base-k numeral system, and we want to have some k-length numbers, but all of the digits must be different ones.

It would be useful, if all of the possible feasible numbers would be unequivocal sortable (so the given nth number is always the same one).

An example to be clear:

k=5

possible digits: 0 ... (k-1) -> 0, 1, 2, 3, 4

we have a base-5 numeral system

we need numbers with length 5

possible feasible numbers:

01234

10234

02134

...

43210

The goal is, to find a way, that if I say, I need the 8th number, it will give me for example 34210 (and it will give me always this number, if I ask for the 8th one).

It is also important, that this algorithm should be efficient, if it is possible in O(1), or in P.

It would be also great, if the algorithm would not generate and store all of the possible feasible solutions, but somehow it could generate only that one appropriate number, which is the answer for the input.

I guess, there is no known P solution for this.

The brute-force and probably not the most efficient way would be, to generate and store all of the possible feasible solutions in a given order, and then we could answer any input, and the same input would generate always the same output. This solution satisfies all of the above criteria, but maybe there is a much more efficient algorithm to do this.


texts: Multi-level cache for which inclusion holds

texts:
For inclusion to hold between two cache levels L1 and L2 in a multi-level cache hierarchy, which of the following are necessary?

L1 must be a write-through cache.
L2 must be a write-through cache.
The associativity of L2 must be greater than that of L1.
The L2 cache must be at least as large as the L1 cache.

This was a multiple-choice question with the following possible answers:

(A) 4 only
(B) 1 and 4 only
(C) 1, 2 and 4 only
(D) 1, 2, 3 and 4

I think L2 cache must be at least as large as the L1 cache but I am confused what the need for writeback is for this cache.


texts:
For the language, $L(aa^*ba) \cup L(abbb^*)$ and the grammar

\begin{align*}S&\to aAba \mid abbB\\
A &\to Aa \mid \lambda\\
B &\to Bb \mid \lambda
\end{align*}

Would the grammar above constitute as LL? I'm having trouble recognizing what exactly constitutes an LL grammar.


texts: Neural Network weight selection using Genetic Algorithm

texts:
Hi I want to ask about weight selection in neural network using genetic algorithm.

Right now what I understand is

Initialize population
Encode the weight of the neural network to the chromosome
Calculating the error and fitness
crossover and mutation
looping until satisfy the condition

Is it the right thing?

if yes what I'm still not sure are :

If I have 50 chromosome in one population that means I must create 50 neural network?
Let's say I have 100 different input and I want the network to learn it by using weight selection only (not using backpropagation) and how I calculate the error? Testing and calculating the error of every input(using MSE) and divide it by 100?

I think that's all for now

Thank you


texts: Time Complexity for matrix multiplication?

texts:
How can I find out the time complexity for the brute-force implementation of matrix multiplication for:

Two square matrices ($n \times n$),
Two rectangular matrices ($m \times n$) and ($n \times r$)?


texts: Where have I gone wrong in "proving" this big-O identity?

texts:
(From CLRS -- 3-4,d)

Let $f(n)$ and $g(n)$ be asymptotically positive functions.

I tried to prove that $$f(n) = O(g(n)) \implies 2^{f(n)} = O\left(2^{g(n)}\right) .$$

I know that the above statement is false, so where have I gone wrong in my proof?:

  Suppose $f(n) = O(g(n)).$ Then there exist positive real numbers $c, n_0$ such that for all $n \geq n_0:$
  $$0 \leq f(n) \leq c g(n).$$ Raising all sides to the power of 2, we have:
  $$0 \leq 2^{f(n)} \leq 2^{cg(n)}$$ (we can do this because $2^n$ is an increasing function).

  From this, we can say that $$0 \leq 2^{f(n)} \leq \underbrace{2^c}_{\text{arbitrary constant}}\cdot 2^{g(n)}$$ so if $d = 2^c$, we can say that $2^{f(n)} = O(2^{g(n)})$.

(I now know that $f(n) = 2n, \ \ g(n) = n$ is an easy counterexample, but I'm still struggling to find the flaw in my "proof").


texts: A,B decidable: proof that A\B is decidable too

texts:
For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.

My idea is as follows:
If B is empty or doesnt have elements in common with A, then A\B is decidable because A\B=A.

If B is not empty and intersects with A, A\B is just a smaller subset of A and therefore decidable.

I have a feeling that this is either the wrong idea or not formalized enough.
I would really appreciate any hints regarding that.

EDIT:
A subset of a decidable language is NOT always decidable too, this was a misconception.

Thanks in advance


texts: What is the theory foundation of the binary encoding of data digits into an EAN-13 barcode?

texts: In the Wikipedia, there is explanation about EAN-13 and several table, which are called "Structure of EAN-13" and "Encoding of the digits", but I did not know what theory  the contents of the two table are based? For example, in "Structure of EAN-13",  0 correspondings to LLLLLL and RRRRRR, but in "Encoding of digits", 0 corresponds to 0001101, 0100111 and 1110010. Why or what am I missing ?


texts:
Brain-Flak is a minimalistic, stack-based, Turing complete, esoteric programming language.

A big concern among Brain-Flak enthusiasts is a concept informally called "stack cleanliness".

The basic idea for stack cleanliness is that only certain values on the stack will be edited and all other values will remain unchanged

More formally:

Given an input arity (a tuple of positions on the active and inactive stack before the program runs), and an output arity (another tuple of the same sort after the program runs) and a function that maps between the two, a program is is considered stack clean iff it performs the function, ends on the stack it started, and the values on the stack that are not in the input remain the same regardless of the conditions of the stack.

The question is: Given a program that is known to halt for all input, a function and the two required arity tuples, is stack cleanliness computable?


texts: To what factor can I compress information from binary to Quinary

texts:
I am trying to think if we can have an injective mapping $\mathcal{f}$, say something like $\Sigma_{bool}= \{0,1\}^* $ to $\Sigma_{5} = \{0,1,2,3,4\}^* $ such that $|x| \leq 2.|\mathcal{f}(x)|$

The motivation here is simple, consider I have a word $110110110110110110110$, so i can compress and represent that as $(110)^7$ or $110,111$ so what can i do if i am allowed to use symbols from $\Sigma_5$?

I hope my question made sense :)


texts: Algorithm for shortest continuous line to join N points

texts:
I have a set of points in a 2D plane. I'm searching for an algorithm that:

Draws a continuous line passing through all the points starting from a
random point.
Optimizes for the minimum total line length in Euclidean distance.
The line should end at the point it started but not cross any
other point more than once.

In plain terms, suppose we had a paper with N dots on it. We'd take a pencil starting from a random point and try to go through all the points without lifting the pencil and conclude by reaching the point we started at.

I looked into Euclidian minimum spanning tree, but what I'm looking for is a closed loop and not a graph-tree like line. What I'd like in approximation is a Convex Hull that would go through all the points and not just form the perimeter.

Can someone direct me to the right family of algorithms?


texts:
I am given with this information:
"CMP OP1,OP2 will compare registers OP1 and OP2 if they are equal,
flag values will be ZF=1, CF=0,
if the first
operands value is greater flag values will be ZF=0, CF=0,
if the first operands value is less than the
second operand flag values will be ZF=0,CF=1."
I need to design instruction set architecture for this compare operation but I couldn't understand how to add ZF and CF values inside CMP instruction


texts:
In their original paper, Storing a sparse table with O(1) worst case access time (Fredman, Kolmos and Szemeredi, Proc. FOCS '82, IEEE, 1982), the authors show that a perfect hash function must exist, provided that the table is the square of the number of elements in the key space.

The key part of the proof bounds the number of possible keys that can produce a particular collision.

Namely, given positive natural numbers, $p$, $s < p$, $a < s$, $b < s$, where $p$ is prime, the authors claim that there are fewer than $(p-1)/s$ solutions to

$$a' \equiv b' \pmod s\,,$$
where $a', b' \in \mathbb{N}_p$, $a' \equiv a\pmod p$, and $b' \equiv b \pmod p$.

This is done by asserting that if $k$ is a solution, then $k(a-b)$ must be congruent, mod $p$, to exactly one of $\{s, 2s, ..., p-s, p-2s, ... \}$.

I do not understand this argument. Could someone please elaborate?


texts: Find if a sequence of node is a result of a binary tree preorder traversal

texts:
Assume we have a sequence of 0's and 1's: $n_0, n_1, ..., n_N$, in which 0 stands for a leaf node, and 1 stands for an uncertain node (it may or may not be a leaf node). How to check if this sequence is a valid result of a binary tree preorder traversal?

Ex. $1, 1, 0, 1, 1, 0, 0, 1$ is a valid sequence.


texts: What is the difference between formal language, regular language and regular expression?

texts: I want to know the difference between these three languages and it would be great if you would give some examples as well.


texts: Why do I get different results from two calculation methods?

texts:
I am wondering what the reason for the following is

We know that ,

exponential has a taylor representation :
$$exp(x)=1+x+\frac{x^{2}}{2!}+\frac{x^{3}}{3!}+...$$

Using the first n  terms , in R , I compute

$\exp(-10)$ and get one answer.

However, if I compute $\frac{1}{\exp(10)}$, I  get a slightly different answer.

For example, when I use the first 30 terms of the Taylor Series,

I get

$\exp(-10)=0.0009703416$

but $\frac{1}{\exp(10)}=4.539993\times10^{-5}$

Once I get to a large enough number of iterations, both converge to the correct value.

So why do we get differing answers when I use the same method, only replacing by a division of 1 over?

Thanks!


texts: Can I express 100 as a three-digit 9's complement number?

texts:
Reading the Appendix A (Binary numbers) of Structured Computer organization by Tanenbaum I've found this exercise:

  Signed decimal numbers consisting of $n$ digits can be represented in $n + 1$ digits without a sign. Positive numbers have $0$ as the leftmost digit. Negative numbers are formed by subtracting each digit from $9$. Thus the negative of $014725$ is $985274$. Such numbers are called nine’s complement numbers and are analogous to one’s complement binary numbers. Express the following as three-digit nine's complement numbers: $6$. $-2$, $100$, $-14$, [etc].

Ok, it all works fine with $6$ for instance: using the given rule it is $006 \mapsto 993$. That makes sense: as Tanenbaum says this system for negative-value representation is similar to one's complement: it has two different zero representation ($000$ and $999$) and it has negative possible value as much as the positive ones.

What I don't understand is how can $100$ fit in this scenario. To me, with 3 digits I ca only represent value in range $[-900, 099]$; moreover $100$ is not considered a positive number --it shoudl have a $0$ as leftmost digit.

Is there an error in Tanenbaum-exercise?, if not, where I'm wrong?


texts: Maximize vertex cover weights with bounded edge weights in a connected subgraph

texts:
Similar questions were asked elsewhere, but no satisfying answers occurred yet.

In a graph with weights for both vertices and edges, I want to find a subgraph, whose sum of internal edge weights is bounded and the sum of internal vertex weights is maximum. Is this problem NP-hard? Please note that the subgraph has to be connected, and the sum of internal edge weights is calculated by the weight of Minimal Spanning Tree of this subgraph. An example is shown in  attached.

Attention: previously someone suggested that we can set the bound to 0 to reduce the problem to Maximum Independent Set. However, by setting all the bound to 0, the problem should be reduced to finding the node with maximum weight, for the nodes in the independent set are not connected which would cost infinite cost.


texts: Is it posssible to calculate the intersection area of rectangles with sweep Line and Interval or Segment Tree

texts:
I am curently working on automatic label placement, so for evaluating a model, one metric is to calculate the Area A:
A is the sum of every part of a rectangle covered by another. So if two rectangle overlap, A = 2 * Arectangle, if three rectangle overlap A = 3 * Arectangle, ...
Because i am working in real time, i need to calculate this as fast as I can, so I went with a sweep line for the x-axis. But I don't understand how can i use an interval or a segment Tree to calculate the length for the x point. So I wanted to know if there is a way to use one of these tree or if i am condamned to use another sweepline on the y axis.
Here is an example for the 1d problem:

Here the return value should be :
L = 2 * (8-5) + (8-7) + 2 * (10 - 8) + 2 * (18 - 17) = 6 + 1 + 4 + 2 = 13


texts:
This is a question concerning Kripke automaton. My answers seem a little short and I was wondering if I was missing something?
Transition table of a Kripke automaton:

A -> red light is on

B and D -> blue light is on

C -> both light are on

1) Is the test 001blue satisfied by any state?

Attempt: No

2) Is the test 001red satisfied by every state?

Attempt: Yes but I dont know how to show it.

3) Which test could tell difference btw A and C?

Attempt: test = 100both; C satisfies test, A doesnt

4) Can any test distinguish B and C?

Attempt: Yes, test = 10001blue; B satisfies test, C doesnt

5)Show that no test can tell the difference btw B and D.

Attempt: Their observations are different.


texts: How are the questions framed in Turing tests? I mean what factors would one consider before framing questionnaire for the Turing Test.How the questions should be framed to make the test unbiased for a machine and humans?


texts: If an array is full of the same integer, like 0s or 1s, are they all the peak of the array?

texts:
I am learning the MIT course Introduction to Algorithms.

The professor is saying

  In particular, as an example, position 2 is a peak if, and only if, b
  greater than or equal to a, and b greater than or equal to c. So it's
  really a very local property corresponding to a peak.

My question is, if an array if full of the same integer, like 0s, or 1s, are they all the peak of the array?


texts: Decision problem - vertex with path to all other vertcies

texts:
Consider the following decision problem: Given a directed graph $G$, is there a vertex $v$ that has path to all other vertcies.
I am able to place this problem in NL, similarly to the strongly-connected graph problem. But is this problem NL-complete? Thinking about reduction from $stCON$ problem, but can't get it through.


texts: Algorithm for fewest moves in 1's, 10's, 100's, etc

texts:
I'm building a math application (not homework) and I want to build a component that allows players to drag-and-drop 1's, 10's, 100's, etc to complete problems and a bonus reward if they do it in the fewest moves possible--How can I calculate this? e.g.

50 + X = 96

where X is a randomly generated integer and the player is modifying X during play. So, the player needs to make X=46, but starts at 121. For example,

if X is initially 121, and player needs to get to 46

player thinks, "cool, i'll just subtract 75"

remove 7x 10's, remove 5x 1's - 12 moves

but it turns out, there's a faster way to do it:

remove 1x 100's, add 2x 10's, add 5x 1's - 8 moves

Is there an existing algorithm for this? It would be helpful to calculate this for anything up to 10,000 where I can calculate the minimum number of moves required.


texts: Is the set of TMs whose language reduces to a fixed CFL also CFL?

texts:
L = {  < M > | M is a TM and L(M) <= { $0^n 1^{2n}$} }

Here <= means polynomially reducible to

Is L CFL?

If L(M) can be polynomially reduced to a CFL then L(M) should also be CFL as if "A" is reducible to "B" then we can solve "A" if we know how to solve "B" ? Where am I going wrong?


texts: How post correspondence problem is undecidable?

texts:
An undecidable problem is a problem that cannot have any algorithm to solve it.

Post correspondence problem can be solved using a brute force approach. Then how can it be an undecidable problem?


texts:
I know a lot of computer languages and they all use tokens. E.g. in very early BASIC you could say LET answer = 42, which is composed of seven tokens, LET, answer, =, 42, and three space tokens.

It seems that every character must be part of some token, including comments, which can be considered free-form tokens after the initial identifier.

Are there any languages completely or partially without tokens? Is it even possible for such a language to exist? What would it look like?


texts: Asymptotic Notation sanity check for f(x) and g(x)

texts:
For each of the 2 pairs of functions I need to figure out the following:

g(n) = Θ(h(n))?
g(n) = O(h(n))?
g(n) = Ω(h(n))?
g(n) = o(h(n))?
g(n) = ω(h(n))?

Pair one
g(n) = (64)(n/4), h(n) = 256(n/8)
Pair two
g(n) = n1024, h(n) 2(lg(n)*lg(n)), lg is base 2
For pair one, I have the limit as n->inf for g(n)/h(n) = inf. Therefore:

g(n) = Θ(h(n)). No, given g(n) = O(h(n)) is not true
g(n) = O(h(n)). No, if g(n)/h(n) headed towards 0 and not infinity
g(n) = Ω(h(n)). Yes, given g(n) completely overtakes h(n) in speed as n increases
g(n) = o(h(n)). No, given g(n) should never be below h(n) for some n0 > 0.
g(n) = ω(h(n)). I think yes, given g(n) = Ω(h(n)) is true but g(n) = O(h(n)) is not. Which was the same logic for o(h(n)) in pair one.

So for pair two, I have the limit as n->inf for g(n)/h(n) = 0. Therefore:

g(n) = Θ(h(n)). No, given g(n) = Ω(h(n)) is not true
g(n) = O(h(n)). Yes, given g(n) completely overtaken by h(n) in speed
g(n) = Ω(h(n)). No, if g(n)/h(n) headed towards infinity and not 0
g(n) = o(h(n)). Yes, given g(n) = O(h(n)) is true but g(n) = Θ(h(n)) is not
g(n) = ω(h(n)). I'm thinking no, same reasoning as g(n) = Ω(h(n)) being no

Made edits based on user plop comments.


texts:
We know that $EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE$, where $EXPSPACE = DSPACE(2^{poly(n)})$.

Question: Is known any consequences of $EXPTIME \neq EXPSPACE$?

(nothing in complexity zoo or wikipedia)


texts: Sum of distances between points on one-dimensional axis

texts:
We have given integer array of $n$ points, let it be $A$, showing where it is on the x-axis. For this problem we are working only with the x-axis and the y-axis is not important at all. Now for given two indexes $l$ and $r$, such that $0\leq l\leq r \leq n-1$, we want to find the sum of distances from each point whose index is in the range $l, r$ to the point with index $r$.

For example $A = \{1, 2, 4, 6, 8\}$ and $l = 0$, $r = n-1$ The output should be $(8-8) + (8-6) + (8-4) + (8-2) + (8-1) = 0 + 2 + 4 + 6 + 7 =19$

I know that it can be implemented in $O(1)$ after $O(N)$ preprocessing but I don't get the intuition behind that, and the formula is very unclear to me.


texts: computably defined function with non computable range

texts: Are there examples of functions that can be defined computably, though the existence of their range is not computable?


texts:
This question is fairly specific in the manner of steps taken to solve the problem.

Given
$T(n)=2T(2n/3)+O(n)$ prove that $T(n)=O(n^2)$.

So the steps were as follows. We want to prove that $T(n) \le cn^2$.

$$\begin{align*}
T(n)&=2T(2n/3)+O(n)  \\
&\leq 2c(2n/3)^2+an\\
&\leq (8/9)(cn^2)+an
\end{align*}$$
and then my prof went on to do:

$$T(n) \leq cn^2+(an-(1/9)cn^2)\,,$$
which comes out to:

$$T(n)\leq cn^2 \text{ for any }c >= 9a\,.$$

My question is, how were they able to switch from 8/9 to 1/9 while introducing a new term? Is this allowed? She never explained, this was just in her solutions.


texts: Do user level threads take advantage of multi processing?

texts:
I asked this question here on stackoverflow, but maybe because of off-topic over there, it didn't received proper response.

Does user level threads take advantage of multiprocessing ? I read one such answer here. But, it's not clear though.

https://stackoverflow.com/questions/25582876/what-does-it-mean-by-user-threads-cannot-take-advantage-of-multithreading-or-mu

And one other answer here says that it is possible

https://stackoverflow.com/questions/14791801/how-do-user-level-threads-ults-and-kernel-level-threads-klts-differ-with-reg

Am I missing something here with some important details ?


texts: Finding the upper bound of states in Minimal Deterministic Finite Automata

texts:
I have a task to determine the upper bound of states in the Minimal Deterministic Finite Automata that recognizes the language: $
L(A_1) \backslash L(A_2) $, where $ A_1 $ is a Deterministic Finite Automata (DFA) with $n$ states and $A_2$ is Non-deterministic Finite Automata (NFA) with $m$ states.

The way I am trying to solve the problem:

$ L(A_1) \setminus L(A_2) = L(A_1) \cap L(\Sigma^* \backslash L(A_2))$, which is language, that is recognised by an automaton $L'$ with $nm$ states.
Determinization of $L'$ which has $(nm)^2$ states and it is the upper bound of states.

Am I right?


texts: $A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$

texts:
I'm trying to exhibit two formal languages $A,B ⊆ \{0,1\}^*$ such that $A^* = B^*$ and $\{0,1\}$ is contained in $A$ but not in $B$.

Finding a language for $A$ is very easy, but I get stuck on $B$, because since $A^*=B^*$, and A has $\{0,1\}$, that $B^*$ must also have $\{0,1\}$. I can't think of a language that has $\{0,1\}$ in $B^*$ but would not be in $B$. Maybe I'm missing something.


texts: Is this problem decideable programatically?

texts:
Consider the following 3 strings:
1tb hdd 256gb ssd
hdd 256gb
1tb hdd
If you know, that all of these strings are part of a product title, specifically part of the title of a Laptop product, a human can easily read these out, and understand that the specific laptop for which the respective string is part of has either hdd/ssd disk in it, and if it has, he can also decide the capacity of the said disk.
Is there any way to programatically make the same assumption correctly?
I am trying to parse the attributes of some products from their titles, and this exact problem arose: some titles have the ordering of {disktype} {capacity}, some have the ordering of {capacity} {disktype}, and I can't figure out a way to correctly identify the order, so that I can correctly parse the attribute and the data. In some cases, the titles contain , characters, which is very helpful in this situation, but there are a few cases where there are no other delimiters except \s characters.
To make things worse, some product titles only contain the following structure: 1tb ssd 512gb. Based on the human understanding, and the context of the above string, for a human, it is still decidable which type of hard disk the laptop contains, and what capacity does it have, but can a computer do this programaticaly in a safe way also?


texts: How does one choose an optimal alphabet for finding a Huffman encoding?

texts:
Huffman encoding will perform best when the distribution of symbols of an alphabet that the string to be encoded uses is dyadic.

Given an arbitrary bit string S, how can we find the best alphabet for encoding? Suppose S is an ASCII file. Then given the regularity of 1-byte characters that such files exhibit, we would expect that an optimal, or at least pretty good, alphabet should contain, say, 8-bit or 16-bit words (which we then build codes for after constructing the Huffman tree).

Is there an algorithm for finding the optimal word width (assume we use constant-length words).

I would guess that to evaluate an alphabet, it would only be fair if we considered the costs of storing the actual encoding as well. This addresses the case where the alphabet is just one symbol - the entire original string. Technically the message would just be one bit, but the the encoding tree that's stored would have to indicate that the one bit used is a code for the original string, so we've just increased our message by two bits trivially!

(Constant-length encoding information such as width size, encoding table size, etc., need not be considered for the comparisons, of course).


texts: What is a Neural attention model and how can it be used for text summarization?

texts:
We are doing a research on multi-document (one document max 100 words) text summarization. We are looking into abstractive text summarization methods. I need following things to be clarified.

Please explain what exactly in Neural attention model.
How can the Neural attention model be used for abstractive text summarization?


texts:
I have seen 2 answers in stackoverflow:

A "trivial" property is one that holds either for all languages or for none.
The property is trivial if it contains every TM, or if it is empty.

My problem is: Saying that a property is trivial if it contains every TM is not the same as saying that a property is trivial if it contain all the languages (including non RE languages).

Same as for: Saying that a property is trivial if it is does not contain any TM languages is not the same as saying that a property is trivial if it is empty.


texts:
I hope the Computer Science section is the appropriate place to ask this question. I’m working on profiling some data sets and I am a bit tripped up on something, I was hoping I could get some assistance.

Part of my project is to determine whether some of my data is an integer and whether is a continuous or discrete quantity.

I understand that in a simple sense Discrete data is counted and Continuous data is measured. I also know Discrete Data can only take on certain values while Continuous Data can take on any values.

It seems that the size of a computer file (in bytes) could take on either of these descriptions because bytes are based on bits and are based on a power of 2 (which would make it discrete). However at the same time a file size could be Continuous because it could be of any size.

If anyone could help me out it would be greatly appreciated! Also if you are aware if I misunderstood something please let me know!


texts:
Arden's lemma is applied in cases where we have an equation that looks like this: $$ X_{i}=AX_{i} + B, $$ with the condition that $\epsilon \notin A$.

But if I have such situation: $$X_{i}=AX_{i},$$ so there's no B, or simply talking we have $B= \varnothing $, thus by the Lemma, we have $$X_{i}=A^{*}\cdot\varnothing$$ which equals to $$X_{i}=\varnothing.$$

Is my reasoning correct?


texts: Concatenation of the intersection of two languages

texts:
I'm enrolled to a Formal Language And Automata course, and we have to prove this equation on sets of strings:
$$(L_1\cap L_2)\cdot L_3 ≠ (L_1\cdot L_3) \cap (L_2\cdot L_3)$$

I've tried a lot of sets for e.g.
$L1 = \{a,b,c,d\}$,
$L2 = \{a,f,g\}$,
$L3 = \{s,d,h\}$.
but always the LHS comes out equal to the RHS instead of unequal.
Any idea how to prove this?


texts: What is the correct way to define time constructible functions?

texts:
Sipser defines a time constructible function as

  $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $f(n)$ in binary to the output tape in $O(f(n))$ time.

whereas Sanjeev Arora and Barak defines it as

  $f(n)$ is time constructible if there exists a turing machine which given input $1^n$ writes value of $1^{f(n)}$ in binary to the output tape in $O(f(n))$ time.

I am unable to see how are these two definitions equivalent. Isn't there a case where writing value in binary takes less time that writing it in unary ? Also what is the reason for inputs being given in unary rather than binary or some other base $k > 2 $ ?


texts: Find out whose turn it is to buy the croissants

texts:
A team has decided that every morning someone should bring croissants for everybody. It shouldn't be the same person every time, so there should be a system to determine whose turn it is next. The purpose of this question is to determine an algorithm for deciding whose turn it will be to bring croissants tomorrow.

Constraints, assumptions and objectives:

Whose turn it is to bring croissants will be determined the previous afternoon.
On any given day, some people are absent. The algorithm must pick someone who will be present on that day. Assume that all absences are known a day in advance, so the croissant buyer can be determined on the previous afternoon.
Overall, most people are present on most days.
In the interest of fairness, everyone should buy croissants as many times as the others. (Basically, assume that every team member has the same amount of money to spend on croissants.)
It would be nice to have some element of randomness, or at least perceived randomness, in order to alleviate the boredom of a roster. This is not a hard constraint: it is more of an aesthetic judgement. However, the same person should not be picked twice in a row.
The person who brings the croissants should know in advance. So if person P is to bring croissants on day D, then this fact should be determined on some previous day where person P is present. For example, if the croissant bringer is always determined the day before, then it should be one of the persons who are present the day before.
The number of team members is small enough that storage and computing resources are effectively unlimited. For example the algorithm can rely on a complete history of who brought croissants when in the past. Up to a few minutes of computation on a fast PC every day would be ok.

This is a model of a real world problem, so you are free to challenge or refine the assumptions if you think that they model the scenario better.

Origin: Find out who's going to buy the croissants by Florian Margaine. My reformulation here has slightly different requirements.


texts: Stuck on Ejaz and Islam's paper about Masked Face Recognition

texts:
I'm relatively new in machine learning and I am trying to put together my undergraduate thesis on masked face recognition.
I've read Ejaz and Islam's paper (available at https://www.researchgate.net/publication/340690545_Masked_Face_Recognition_Using_Convolutional_Neural_Network) about feature extraction using FaceNet and Facial Verification using SVM, and I am stuck on understanding some parts of the paper.
What is a very deep CNN network supported by L2 normalization and how does it work?
Is triplet loss the only way to increase the accuracy of a CNN architecture?
How do someone retrain the FaceNet model? Isn't a model already trained and can recognize something out of the box?
How does the SVM work in facial verification?
What do they mean by "A masked face similarity is measured upon the masked and non-masked face by estimating an L2 normalization within the features key points collected from the net structure"?
In short, I am confused about the method of their paper as they don't really elaborate much about it.
Thanks in advance guys, I really appreciate some help because I'm really stuck on it.


texts: Heuristics for an Artificial Intelligence problem

texts:
Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in an arbitrary ordering. Our goal is to arrange the tiles such that all white tiles are positioned to the left of the black ones, and one black tile is in the rightmost position. The goal position of the empty space is not specified.
   Tiles can be moved to the empty space when the empty space is at most $N$ cells away. Hence there are at most $2N$ legal moves from each state. The cost of each move is the distance between the tile and the empty space to which it moves ($1$ to $N$).

So I am doing this problem with A* search algorithm with different heuristics(ofcourse admissible).So can anybody suggest me some heuristics.
Thanks


texts: How can I teach computer science without using computers?

texts:
In some places in the world, people don't usually have access to (and hence little knowledge of) computers, and even if they have, hard- and software are outdated and usage plagued by power outages and such. Access to (good) books also tends to be lacking. How can I teach computer science under such circumstances?

I'm worried that without being able to do experiments and apply what they learn, they won't learn (well) at all even though they are incredibly motivated and devote most of their time to this hobby. Is it possible to teach CS only theoretically?


texts: Algorithm Complexity Analysis on functional programming language implementations

texts:
I've learned today that algorithm analysis differs based on computational model. It is something I've never thought about or heard of.

An example given to me, that illustrated it further, by User @chi was:

  E.g. consider the task: given $(i,x_1 ,…,x_n )$
   return
  $x_i$
  . In RAM this can be solved in $O(1)$
   since array access is constant-time. Using TMs, we need to scan the whole input, so it's $O(n)$

This makes me wonder about functional languages; From my understanding, "Functional languages are intimately related to the lambda calculus" (from a comment by Yuval Filmus on here). So, if functional languages are based on lambda calculus, but they run on RAM based machines, what is the proper way to perform complexity analysis on algorithms implemented using purely functional data structures and languages?

I have not had the opportunity to read Purely Functional Data Structures but I have looked at the Wikipedia page for the subject, and it seems that some of the data structures do replace traditional arrays with:

  "Arrays can be replaced by map or random access list, which admits purely functional implementation, but the access and update time is logarithmic."

In that case, the computational model would be different, correct?


texts: Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?

texts:
In Python, we have metaclass and abstract class.

In Java and C#, we have interface and abstract class.

The relation between a metaclass and a class is instantiation, so it extends the instantiation relation between a class and an object.

The relation between an abstract class and a class is inheritance, so it extends the inheritance relation between concrete classes.

The relation between an interface and a class is implementation.

Is this implementation relation an instantiation relation, an inheritance relation, or neither?
If neither, can this relation be viewed as some extension of some relation between some classes or objects?
is an interface more like a metaclass or an abstract class?

Thanks.


texts: Minimization of DFA 3 inputs Table Filling Method

texts:
I do understand how minimization of DFA works where there are 2 words lets say $\{a, b\}$. However, I came across this minimization of a DFA over  the language of $\{a, b, c\}$ $\left(\Sigma, \{q_0, q_1, q_2, q_3, q_4\}, \{(q_0, a, q_1), (q_1, a, q_1), (q_1, b, q_2), (q_2, c, q_3), (q_3, a, q_4), (q_4, a, q_4), (q_4,b,q_2)\}, q_0, \{q_3, q_4\}\right)$

When filling up the table I get some states that brake just because I cannot make a transition from $q_3$ with b.
Then if we investigate the set $\{q_4, q_3\}$ in order to see if we can mark it in the table it gives us a broken transition from $q_3$ with $b$ so it looks like $\{q_4, q_3\}$ with $b$ transition $\{q_2, ? \}$ in this case, do we mark $\{q_4, q_3\}$ in the table or not and why?


texts:
Given a $3\mathsf{SAT}$ form to decide satisfiability takes exponential time.

Any boolean function has an unique polynomial representation. So decide $3\mathsf{SAT}$ satisfiability reduces to whether a given polynomial is identically $0$. However deciding $\mathsf{PIT}$ is believed to be in $\mathsf{P}$ since we think $\mathsf{P}=\mathsf{BPP}$.

However any $3\mathsf{SAT}$ instance can be thought as a boolean function. So does it mean we believe $\mathsf{P}=\mathsf{NP}$ as well? Of course not. However I am unable to figure what mistake I make in my reasoning.

Could someone explain?

I think this has to do with boolean and arithmetic circuit difference. However I am unsure how to correct my misunderstanding.


texts:
Assuming you have a formula in first order logic like

    $$(\forall_x p(x) \land \forall_x q(x)) \rightarrow \forall_x(p(x) \land q(x))$$
    (which seems valid?)

Converting the formula to CNF:

  $$(\neg p(x) \vee \neg q(y) \vee p(z)) \land (\neg p(x) \vee \neg q(y) \vee q(z)) $$

I don't see how I can apply general resolution to get the empty clause in this case which puzzles me since I believe the formula is valid.


texts:
Given a set of $n$ points $p_1,p_2,\ldots,p_n$ on a horizontal straight line (not necessarily in the order from left to right) with associated $x$-coordinates $x_1,x_2,\ldots,x_n$ (not necessarily in ascending orders) and associated weights $w_1,w_2,\ldots,w_n$ such that $\sum_{i=1}^n w_i = 1$. The objective is to find a point $p$ on the straight line such that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum, where $x_p$ is the $x$-coordinate of $p$.
Prove that the sum $\sum_{i=1}^n |x_p-x_i|w_i$ is minimum at a point $p$, where $p$ is such that $\sum_{x_i<x_p} w_i < \frac{1}{2}$ and $\sum_{x_i>x_p} w_i \leq \frac{1}{2}$.

I am trying to use algorithm Select to prove it. The algorithm divides the x-coordinates into $[n/5]$ sublists such that first $[n/5]-1$ sublists contain exactly 5 elements each, while the remaining one contains $n \pmod 5$ elements. Then we find the median of each sublist. Repeat the same process for each sublist.
But I think I get the gist of the problem, I think it is sufficient to prove that if $q$ is any point on the line such that $q≠p$,then $\sum_{i=1}^n|x_q-x_i| w_i≥\sum_{i=1}^n|x_p- x_i | w_i$, where $x_q$ is the x-coordinate of $q$.
But I am going no where with this. Am I using the wrong approach? Should I be using algorithm Min to get this? If yes, can someone explain how to get it?


texts: The difference between theoretical complexity and practical efficiency

texts:
If I have this pseudocode:

for i=0 to n/2 do
   for j=0 to n/2 do
       ... do anything ....

The number of iterations is $n^2/4$.

What is the complexity of this program?
Is it $O(n^2)$?

What is the intuition formal/informal for which is that complexity?

Next, if i have this other pseudocode :

for i=0 to n do
   for j=0 to n do
       ... do anything ....

The complexity is again $O(n^2)$ -- is that correct?

Is there any difference between efficiency in practice and theoretical complexity in this case?  Is one of these faster than the other?


texts: Non-deterministic TM and problems in class P

texts:
Definition:
$P$ is the set of languages that can be decided by a deterministic Turing Machine in polynomial time.

I wonder if:
$P$ equals to the set of languages that can be decided by a non-deterministic Turing Machine in polynomial time?

I think this also has to be true in this case because a non-deterministic Turing Machine can also decide all problems which can be decided by a deterministic Turing Machine. Because of the fact that we have here a language in P this NTM also decides it in P.

Am I right or am I wrong?


texts:
I understand what parity is (Sort of):
A data recovery mechanism where missing data is calculated based on the data that exists. However i have encountered terminology which i can't define or put into perspective of the RAID system.

This terminology is 'dedicated' and 'distributed' Parity. Now i imagine that it is somehow related to the distribution of data among separate disks, but can anyone give a more detailed definition and explanation of 'Dedicated' and 'Distributed' parity?

Thanks in advance.


texts: What's the purpose of Karger's algorithm?

texts:
Suppose I'm given an undirected graph and two nodes: v and u.

If I understand Karger's algorithm correctly, it's used to find a minimum cut of a graph, not the ("the" because there is only one for any given graph) minimum cut such that v is in one part of graph and u is in the other part.

Why don't we simply find the vertex with the minimum number of edges and remove those edges. Thus, we "partition" the graph into two subgraphs: the node which had the minimum number of edges and the rest of the original graph. What am I missing?


texts: Terminology: words with only terminals vs. words which can contain nonterminals

texts:
In the context of formal grammars, is there a standard terminology to distinguish

words (i.e., finite sequences of letters/tokens) which only contain terminal letters/tokens, and
words which may contain nonterminals?

I prefer to use the term "word", unqualified, to refer to the former, because I am discussing various ways to produce words over a fixed alphabet $\Sigma$ (of terminals!), the set of nonterminals can vary from grammar to grammar, so words over them only make sense for a particular grammar.  But I would still like to have a term to refer to words which may contain nonterminals: how should I best call them?

"Nonterminal words" isn't a good term because they might turn out to have only terminals; "possibly nonterminal words" or "not necessarily terminal words" is too long and syntactically awkward.  "Word over $\Sigma\cup N$" is, of course, perfectly clear, but sometimes one doesn't want to introduce any symbols.  What other options are available?  From this related question I'm thinking maybe "symbol string" or "symbol word", but I'm not sure whether it's sufficiently distinctive.  Some other possibilities are "generalized word" or perhaps "form" since the generalized words which can be derived from a grammar are called "sentential forms".  Any other idea?


texts: Term for members of a class that are not inherited

texts:
Is there an explicit term for a member of a class that is not inherited from any parent class?

class Vehicle {
    int weight;
}

class Car extends Vehicle {
    int numDoors;
}

Car car = new Car();
car.weight = 10000; // weight is an "inherited member"
car.numDoor = 4; // what's the term for numDoor?


texts: Subtracting binaries using two's complement

texts:
I am trying to subtract these two binary numbers:

$  1110
- 1011$

First I convert 1011 to two's complement by doing 1011 to 0100 and then adding 1 to get 0101. Then I add the first number to the converted two's complement number:

$1110$

$+$ $0101$

$-----$

$0011$

0 + 1 = 1

1 + 0 = 1

1 + 1 = 0 carry 1

carry 1 + 1 + 0 = 0

For a final answer of $0011$ which is 3 in decimal, however, the answer in my book says it should be 2 or 0010...?


texts: Virtual Memory - Calculating Page Table Size and Other Attributes

texts:
Im struggling to understand the answer to a question:
Consider a system with 2MiB physical memory and 4GiB virtual memory. Page size is 4KiB. If we choose to store seven information bits in each PTE, how big is the page table in bytes?
answer:
VPN contains $log(\frac{2^{32}}{2^{12}})=20 bits$
PPN contains $log(\frac{2^{21}}{2^{12}})=9bits$
9 bit PPN + 7 info bits = 16 bits per PTE
$2^4$ bit PTE * $2^{20}$ PTE's = $2^{24}$ bit page table, or $2^{21}$ bytes
Everything makes sense except the first line. I thought VPN bits $ = log(virtual memory space)$ and that
s 4GiB. Why are we dividing by the page size?
Im also lost on the next part, which asks: The page table starts off empty, then we make the following accesses: 0x00111999, 0x00234567, 0x00555FFF. If the page table begins at addres 0x20000000, at what address can we find the PTE for the first access? (Your answer should be in hex)
It gives the answer:
0x20000222. 0x00111999 has a VPN of 0x00111. Each PTE is 2 bytes, so 0x00111 *
2 = 0x00222. 0x20000000 + 0x00222 = 0x20000222.
I get that each PTE is 2 bytes, but why do we multiply by that?


texts: Undecidability of checking whether all words can be generated from a context-free grammar?

texts:
I know it's undecidable, but how to prove it?

Let me explain the problem clearer. The problem is not to check whether some given word can be generated, but whether ALL words are possible to generate in this CFG.


texts: A closed form expression for # of inputs of a binary tree and its number of nodes

texts:
Is there any closed from expression that can express the number of input pins of a binary tree based on height of the tree and its number of nodes?

In case that the binary tree is a full tree, it is easy to find the number of input pins. In this case we will have $2^{H-1}$ nodes at the last level of the tree ($H$ is the height of the tree). Thus, the # of input pins will be $2^H$ because each node has 2 input pins.

How can we generalize this for a binary tree which is not a full trees?


texts: What is the advantage of Rete algorithm compared to relational database engines?

texts: Per my understanding, the Rete algorithm and relational database engines essentially solve the same problem: answering to a certain query about a (large) set of relational facts. To me, the Rete algorithm is just more special-purpose along with a fancy caching procedure; I fail to see why it is superior to any of the existing state-of-the-art database solutions such as SQL. In terms of flexibility, SQL is certainly superior. In terms of performance, it is not apparent that Rete yields better average performance.


texts: A repository for max flow and mincut datasets

texts:
I am not 100% sure if this is the right stackexchange to ask. I have a  max-flow algorithm and I am also computing the min-cut from that algorithm.

I want to test the correctness and speed of it and I am trying to find if there are some datasets against which I can test my algorithm. The dataset should preferably have the max-flow value and the set of edges belonging to min-cut.


texts:
I understand that essentially we have to prove that

$$c_1(n^2\log n)\le
   (56n^2+106n+48)(\log(264n^2+200))
       \le c_2(n^2\log n)\,.$$

I am confused on how to simplify this further? And correctly find a c value.


texts: Predicate Logic - Natural Deduction; Assumptions about exists-elimination

texts:
I am stuck on how to progress with this proof; i cannot see my next move.

The task is to show $S \to \exists x Q(x) \vdash \exists x (S \to Q(x))$ using natural deduction for predicate logic.

My first attempt was the following;

1: $S \to \exists x Q(x) \space \space \space \space \space \space premise$
2: $x_{0} \space \space S \to Q(x_{0}) \space \space assumption$  (start of scoped box, i do not know how to write them here)
3: $\exists x(S \to Q(x)) \space \space \exists x \space introduction \space 2$ (end of scoped box)
4: $\exists x(S \to Q(x)) \space \space \exists x \space elimination \space 1,2-3$

However, i am not so sure that this is correct. The rule for $\exists$ elimination is
$\frac{\exists x \phi \space \space(And \space we \space manage \space to \space infer \space \gamma \space from \space replacing \space x \space in \phi \space with \space a \space fresh \space variable)}{\gamma}$
I do not know how to render the rule here (bonus question), but here's a link to where it is better described (page 16).

In order to eliminate $\exists x$ i must thus have a formula $\exists x \phi$ as my premise, and the other premise as described in the link above. However, my first premise in this case is $S \to \exists x Q(x)$, which makes me think my second move is illegal.

Can anyone explain if my thinking is correct, and point out my next move, or if i am wrong please explain why i am wrong? (Incidentally the link above describes exactly those rules my course litterature allow me to use, so if i could get help in terms of those rules i would be doubly grateful).


texts: How does Knuth measure the running time of this program?

texts:
I'm reading "Structured Programming with go to Statements" by Knuth, and in it, he gives the following algorithm and a run-time cost analysis of some hypothetically generated code, letting $n$ stand for the number of times around the loop, and where instruction fetch and memory accesses cost one unit, so for example $r2\gets m$ costs two units because it's an instruction fetch, and you need to fetch $m$ from memory.

My question is what does $a$ mean in these equations? How can the instructions associated with the not found label execute more than once, rather than $a$ times? Given the nondeterminism of whether you'll execute the not found instructions depending on the contents of $A$, I can expect there's a special way of dealing with it in the analysis, but I don't follow him in the paper where he claims the total running time based on this analysis is $6n+10$. He says (+ 3 if not found), implying that $a$ is $1/2$, but using that assumption, the total sum comes out to $6n+8.5$, (+3 if not found). Is this some common notation I'm missing? No where in the paper is $a$ defined.


texts: Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

texts:
There is given input - words is sequence of numbers:  $w_i$ is number
  in sequence, $i$ is position.   All of them are in written in binary
  system.

  $$w_1\#,...\#w_k\#i$$    Prove that there exists deterministic
  Turing machine which find $i$-th number in sorted sequence $w$ in
  logspace.

I am not sure if I correctly solved it, so I ask for checking my reasoning.  It seems to be fairly simple.

First of all, what we can do in logspace:
compare two numbers
iter over sequence (move to $n$-th number)

Simply,  we consider one by one each element of sequence and count how many elements is less than currently considered. If we count $i-1$ numbers, then we stop.  It requires logarythmic($k$) memory for counter.  These counter can be reused (for each iteration).

Waht do you think ? Maybe some other approach to proving it ?


texts:
My goal is to create a method that gets an array that only has 1's and 0's in it, and then turns every number into the amount of 'steps' it is away from the closest 0, left or right.

So for example [1] - [1] - [0] - [1] - [1] - [1] - [1] - [1] - [0] - [1]  would be
[2] - [1] - [0] - [1] - [2] - [3] - [2] - [1] - [0] - [1]

I also need to do it as simple as possible in terms of time and space complexity.

I'm not sure how to make it count how far a certain spot is from a 0 if it's from the right of the 0, or if there's another 0 nearby I'm not sure how to make it count which one is closest.

I'm assuming two for loops are needed?

Made a sketch: no idea if it makes sense.

 for (int i=0; i<a.length; i++)
{

    for (int j=i; j<a.length; j++)
    {
     if (a[j]==0)
      {
       if (i<j)
         {
           a[i]=j-i;
         }
        if(j<i)
         {
           a[i]=i-j;
         }
       }
    }
 }


texts:
I am trying to figure out how $(x/y)$ in floating point arithmetic

$fl(fl(x) / fl(y))$ where $fl(x) = x(1-\delta_1)$, $fl(y) = y(1-\delta_2)$, $fl = (1-\delta_3)$

I have:

$= x/y \cdot ((1-\delta_1)/(1-\delta_2))(1-\delta_3)$

after arithmetic

$= x/y \cdot (\delta_3 \delta_1 - \delta_1 - \delta_3 + 1)/(1-\delta_2)$

Not sure how to fully write the rest I believe i have to shorten them using the info that $\delta < \epsilon$ and $\delta^2 \leq \delta$


texts: Understanding How Double Precision Numbers are Stored in a Computer

texts:
I am reading Numerical Analysis by Walter Gautschi. I am somewhat confused by the following quote from page $5$:

  To increase the precision, one can use two machine registers to represent a machine number. In effect, one then embeds $\mathbb{R}(t, s) \subset \mathbb{R}(2t, s)$, and calls $x \in \mathbb{R}(2t, s)$ a double-precision number.

(Here $t$ represents the number of allowable binary digits in the mantissa, and $s$ represents the number of binary digits allowable in the exponent.)

Can someone please explain what is going on here with the "machine register"? Some questions that I have are: instead of using two registers, why not just use one of bigger size? Apparently some registers have a different size, because the exponent is also stored in a register, and $r$ may not equal $s$.

Secondly, double-prevision seems to be defined in terms of a "native precision" already intrinsic to the machine. But on the other hand, I thought double precision was a fixed thing determined by IEEE.

My Background I am a math major taking my first Numerical Analysis course. I do not have any prior experience with computers (except day-to-day use of course) or numerical mathematics.


texts: Is this computational complexity of the k-NN (custom distance) correct?

texts:
I read on a book that in general k-NN (no optimizations), given

$d$ dimensions
$n$ examples

every computation of distance is $O(d)$. Since every example has to be compared with all the other ones, the complexity is $O(dn^2)$

I am doing 1-Nearest-Neighbors with Dynamic Time Warping as distance "metric".

The complexity to my calculations, was, given:

$d$ dimensions
$n$ examples
$m$ instances of feature for each example
(bonus) $c$ classes

$O(m^2)$ complexity of a single comparison of DTW algorithm

$O(d\,n^2)$ complexity of general k-NN

Thus in a single training/test, the complexity for all the computation is:

$O(d\,n^2\,m^2)$

If I have $c$ classes, and $c$ classifiers, one for each class, with each having custom features, the overall complexity is

$O(c\,d\,n^2\,m^2)$

Is this correct? Or I'm missing something?

EDIT:
An example contains temporal data which gives out another dimension.
You can imagine an example as a matrix where $d$ is the number of features (columns), and $m$ the number of instances of features (rows).

So I can have a table like this

<$m$> | $f_1$ | $f_2$ | $f_3$ | ...

$m_1$ | $a$ | $b$ | $c$ | ...

$m_2$ | $a'$ | $b'$ | $c'$ | ...

When I compare for a single feature two examples, the DTW distance is a scalar value for each feature, so the comparison becomes

$dist_1$ | $dist_2$ | $dist_3$ | ...

with $dist_i$ scalar $\forall i$ and $|\{dist_i | \forall i\}| = d$

The time complexity to calculate each $dist_i$ is $O(m^2)$ (DTW algorithm has quadratic complexity, or $m\cdot m'$ if different number of lengths).


texts:
Histograms of oriented gradients for human detection seems to be the paper from which all other papers cite when they use HOG features. However, this was the only description I could find in it:

  [...] In practice this is implemented by dividing the image window into small
  spatial regions (“cells”), for each cell accumulating a local 1-D histogram of
  gradient directions or edge orientations over the pixels of the cell. The
  combined histogram entries form the representation. For better invariance to
  illumination, shadowing, etc., it is also useful to contrast-normalize the
  local responses before using them. This can be done by accumulating a measure
  of local histogram “energy” over somewhat larger spatial regions (“blocks”) and
  using the results to normalize all of the cells in the block. We will refer to
  the normalized descriptor blocks as Histogram of Oriented Gradient (HOG)
  descriptors.

It is not clear to me how the HOG features are now calculated:

How big are the cells? How is that size chosen?
What is a 1-D histogram?
What is a histogram of directions?

Suppose we have the following 5x5 patch of a grayscale image (I hope that is a normal size for a cell - if not, please just copy this block as often as necessary or give another example):

  000 025 255 016 200

  000 255 255 017 201

  010 012 210 012 111

  000 000 000 000 000

  255 254 255 254 255

What would be the HOG features of it?

(Can you give a citable resource for the description?)


texts: Using two separate mutexes for the Exclusive Queue Problem (Little Book of Semaphores)

texts:
I recently read the exclusive queue (exclusive ballroom dancers) problem on the "Little Book of Semaphores" by Allen Downey.

His solution included a single mutex for both the leaders and the followers. Could there be anything wrong with using two separate mutexes for leaders and followers? After all, a check is done at the end of the dance part. Below is my solution.

Initialization:

semaphore leaderMutex = 1;
semaphore followerMutex = 1;
semaphore leaderHasFinished=0;
semaphore followerHasFinished=0;
int numLeaders=0;
int numFollowers=0;

Leader:

leaderMutex.wait();
numLeaders++;
while(numFollowers<=0);
dance();
numLeaders--;
leaderHasFinished.signal();
followerHasFinished.wait();
leaderMutex.signal();

Follower:

followerMutex.wait();
numFollowers++;
while(numLeaders<=0);
dance();
numFollowers--;
followerHasFinished.signal();
leaderHasFinished.wait();
followerMutex.signal();


texts:
You are given functions $f$ and $g$ such that $f(n)=O(g(n))$. Show that $f(n)\log_2(f(n)^c)=O(g(n)\log_2(g(n)))$. (Here $c$ is some positive constant.) You should assume that $f$ and $g$ are nondecreasing and always bigger than 1.

My solution: There exists $c_1$ such that $f \leq c_1 g$. Note that all $\log$ functions are base 2 throughout.

We have that $f \log(f^c) \le c_1 c g \log(c_1g) = c_1 c g \log(c_1) + c_1 c g \log(g)$.

Let expression $(*)$ be as follows:

$(*) \quad c_1 c g \log(c_1) + c_1 c g \log(g) \le c_2 g \log(g)$ for some $c_2 > 0$.

Then $(*)$ holds iff $c_1 c g \log(c_1) < 0$ iff $0 \leq c_1 \leq 1$.

Now put $c_2 = c_1 c$, then:

$c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$ iff $c_2 / c > 1$.

Therefore, we require than $c_2 > c$, which we cannot guarantee as we have already fixed $c_2 = c_1 c$.

What choice of $c_2$ would guarantee that $c_2 g \log(c_2 / c) + c_2 g \log(g) \le c_2 g \log(g)$?

I am looking for a formal argument.


texts: Lower limit on the number of check bits needed to correct single errors

texts:
I was going through Andrew S. Tannenbaum's computer networks book, and on page 206 of it, he has derived the number of check bits needed to correct single bit errors. The derivation goes as follows:

For m data bits, there are 2^m legal messages. Each of these messages has n illegal codewords at a distance on 1 from it. These are formed systematically by inverting each of the n-bit codeword formed from it. Thus, each of the 2^m legal messages requires n+1 bit patterns dedicated to it....

Can someone please explain the last line to me? For an n-bit codeword, we can only flip n bits to get illegal codewords. When does that additional 1 come from?

I am very new to coding theory, so please excuse if this is a very naive question.

Thanks!


texts:
I'm taking a fairly challenging Algorithm course, in which we are learning about algorithms such as Dijkstra, Bellman-Ford etc. as well as the algorithm design patterns such as recursions, DP and various graph construction techniques such as layering. Now I really have some trouble to design correct and efficient algorithm using stuff we learned in the class. To be specific, I'm having trouble with following:

Design an algorithm that's fast enough, i.e., I came up with a $O(n^2)$ algorithm but in fact there is a $O(n log n)$ algorithm.
To find the edge cases for the algorithm I designed. It happened a lot of times to me during exam that I designed some seemingly correct algorithm but will actual fail in some edge cases. I always have some hard time to find those edge cases and therefore falsely believe the algorithm is correct.

I would greatly appreciate any suggestions that can help me deal with my struggle. Also, just for reference, here are the links to the course I'm taking (schedule, and the homeworks)


texts:
I've been reading about System F Omega lately, and I keep stumbling across a construct in typing rules that I cannot find an explanation of: Γ(x) = k. For example, in A Short Introduction to Systems F and F Omega:

Γ(a) = k
--------
Γ ⊢ a : k

I see the same construct in Hereditary Substitution for Stratified System F. I understand the bottom part fine. It would read something like: "In context Γ, a has kind k". I've not been able to find an explanation of the top part, and the sources I referenced both assume familiarity with this construct. If I had to guess, I suspect that it means something like "In context a, running a kind-checking algorithm on a gives you kind k as the result". Is that accurate? What online resources describe this construct?


texts: How can machine learning be used in making sure a document has all the required headings and details?

texts:
We are trying to build a system that would accept fyp proposal documents and then would validate is there something missing, like a heading or a chart that should be in the document according to the template.
The question is how machine learning can be used to solve this problem. As it seems a simple if else sort of a thing.


texts: Complexity of natural language processing problems

texts:
Which natural language processing problems are NP-Complete or NP-Hard?

I've searched the natural-lang-processing and complexity-theory tags (and related complexity tags), but have not turned up any results.

None of the NLP questions that are recommended are helpful, the closest are the following:

https://cs.stackexchange.com/questions/25925/why-is-natural-language-processing-such-a-difficult-problem
https://cs.stackexchange.com/questions/9920/how-is-natural-language-processing-related-to-artificial-intelligence
What aspects of linguistics are necessary or good for natural language processing?

The Wikipedia list of NP-complete problems does not list any complexity results for NLP.

The only lead I've found is the paper Theoretical and Effective Complexity in Natural Language Processing by J. Morin (1995).

Any help or pointers is appreciated!


texts: How does treewidth behave under graph minor operations?

texts:
It is a well-known fact that for any minor H of a graph G (commonly written as $H \leq_m G$), the treewidth of H is smaller than or equal to that of G.

Minors of a graph are created through the operations of (1) vertex deletion, (2) edge deletion and (3) edge contraction. I am curious as to whether one can bound the decrease in treewidth when applying any single operation from (1)-(3).
Of particular interest for me is the question whether said decrease can always be bounded by some constant.


texts: What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

texts: Princeton Algorithms course shows the implementation of Queue using linked list and two pointers - head and tail. I've implemented the same functionality as a circular linked list using only one pointer tail. I'm wondering what's the advantage of two pointers versus one in a circular list. It takes more space as I understand so why did they choose this implementation?


texts: Isn't a small monolithic kernel a micro-kernel, and a big micro-kernal a monolithic kernel?

texts:
I don't understand the last para. I corrected its typos. Please explain like I'm 5. If micro-kernels can be big, and monolithic kernels can be small, doesn't this size gradation collapse the distinction between monolithic kernels and micro-kernels? Is this what a hybrid kernel means?

So.. that's the ELI5 version. Things change, microkernels was going to be the cool logical way to do it, that argument between Tovalds and Tanenbaum really is worth a read. But Monolithic kernels appear (for now) to have won, as they want speed, instant access to resources (like kitchens or GFX cards) and rely on the OS managing processes a bit smarter to figure out who gets what type of access at what time. But just because a kernel is micro doesn't mean it won't take a lot of room up, as it'll then still need all the drivers to do things and be useful. So you can have a monolithic kernel that's small (compiled with only the drivers it needs into the kernel), and a microkernel that's big (compiled for a certain architecture/memory configuration with lots of modules available to handle all sorts of odd hardware to be plugged in). Google will provide more details and far more pros/cons that we can throw here. But again, read that linked Torvalds/Tannenbaum argument, it's the kind of thing that still goes on today.


texts: On uniform randomness of the weight of the remaining edges of a graph after deleting some of them

texts:
Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring edges of $e$. An edge $e$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,

for e in E
if w(e) is locally sub-dominant
    delete e from the graph G
    double weights of all e in  N(e)

My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?


texts: Complexity of enumeration vs complexity of counting

texts:
I have a problem understanding the difference between complexity of enumeration and counting. We can solve every counting problem using enumeration algorithm.
Now, I have problem with the following. Let say that we have to count the number of positive integers less or equal than positive integer $N$. We know that the answer is $N$ and therefore we can solve the counting problem in $\mathcal{O}(1)$. Corresponding enumeration problem is to output every positive number and this can be done in $\mathcal{O}(N)$ steps and I believe that this is pseudo-polynomial complexity and that in fact complexity is exponential.
Are these complexity assumptions correct? Is the number of solutions of counting problem always bounded by the time complexity of corresponding enumeration algorithm?
Any hints or suggestions appreciated.


texts: Infer probabilities, for concatenation of words

texts:
Fix an alphabet $\Sigma$, and a set of words, $W = \{w_1,\dots,w_n\} \subseteq \Sigma^*$.

I have a randomized model that works like this: Alice generates a random sequence of words, using some probability distribution over the words, and then I get to see their concatenation -- but I don't see where the word boundaries are.  I want to infer what distribution on words Alice is using.

More formally, Alice randomly picks a sequence of words, where each word is chosenly randomly and independently at random according to the probabilities $p(w_1),\dots,p(w_n)$; then Alice outputs the concatenation of these words.

With this model, we can work out the probability of any particular string $x \in \Sigma^*$.  It is the sum of $p(s_1)  \cdots  p(s_k)$, taken over all sequences of words $s_1,\dots,s_k$ whose concatenation is $x$ and such that $s_i \in W$ for all $i$:

$$P(x) = \sum_{s_1 \dots s_k = x} p(s_1) \cdots p(s_k).$$

If I knew the probabilities $p(w_1),\dots,p(w_n)$ (the distribution Alice is using), it'd be easy to compute $P(x)$ using dynamic programming: for each prefix $x_{1..i}$ of $x$, I compute $P(x_{1..i})$.

But I have the inverse problem.  I am given $w_1,\dots,w_n$ and $x \in \Sigma^*$, and I want to find probabilities $p(w_1),\dots,p(w_n)$ that make $P(x)$ as large as possible.  How can I do that?  Is there any efficient algorithm for this?

I would be happy with a practical algorithm that works well enough in practice, or a heuristic that gives an approximate solution.

I haven't managed to come up with any reasonable algorithm.  In the special case where no word in $W$ is a prefix of any other word in $W$, then there is a unique decomposition of $x$ into a sequence of words from $W$, and it's easy to use maximum likelihood methods to compute the optimal probabilities: the probability $p(w)$ is just the number of times $w$ appears in this decomposition, divided by the number of words in the decomposition.  However, in general there might be exponentially many ways of decomposing $x$ into a sequence of words from $W$, so this strategy doesn't work in general.  Is there a better method?


texts: Finding the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time

texts:
I am looking for a solution for the following problem:

Find the size of a subset of top $N$ elements, where the minimum element is at least $N$, in linear time.

Consider the following sequence:
$$
3, 1, 6, 1, 5
$$
The answer here is $3$, with $6, 5, 3$ being in the set found. The value of $N$ is not a given - we're looking for the largest $N$.
So far, I came up with three solutions:

Sort the sequence and go from the top.
Use a modified version of quickselect.
Use a modified version of BST where elements bigger than the current $n$ are inserted, and elements smaller than the new $N$ are removed.

1 and 3 are more or less $n\log n$ (though I'd expect 3 to be faster), 2 is best case $n$, worst case $n^2$.
Our teacher told us it's possible to do it in a reliable $n$ time. What is the algorithm for the linear solution, if there's one?


texts: Decomposing an Algorithm into Local Transformations/Perturbations

texts:
Is it common to try to improve an algorithm by decomposing its action on a topological piece of data (e.g. graphs, geometric data) into a series of steps, each of which only makes a local change/perturbation in a confined neighborhood of the data while fixing the rest?

One benefit of this "breakdown" is improved conceptual understanding, and it also facilitates induction proofs (possibly based on invariants that are preserved by each step). Does this "decomposition" have a name in algorithm design? The idea might be similar to Divide and Conquer.

One might say that every individual step in an algorithm, like deleting an edge or labeling a vertex of a graph, is small enough to be considered "local", but I'm talking more about the "decomposition" in a higher-level description, like how truncating a polyhedron is local but sorting a list is not (even though at the lowest level, comparisons, insertions and deletions are local).

Examples of decomposing into local transformations

Augustin Cauchy's proof of his Rigidity Theorem relied on his "Arm Lemma" that opened up a convex planar chain by sequentially opening at each vertex. Although his proof was found to be wrong, he decomposed the opening algorithm into a series of "local opening moves", and he tried to prove that each local move preserved convexity of the chain. By induction, convexity would still hold after iterating over all vertices.
The pivot algorithm for self-avoiding walks (SAW) transforms a SAW into another by rotating or reflecting part of the original SAW. Markov Chain Monte Carlo can employ this transformation as a transition between SAW states to sample the space of SAWs.
As an application of the above, one technique of protein folding prediction is to force an amino acid chain into several known protein structures, choose the one with the lowest energy (due to intermolecular forces), then let the chosen structure "relax" into a configuation with lower energy. Relaxation involves the prescription of a few "local moves", where small parts of the chain can "wriggle around" (e.g. subchains pivoting around their ends), and random wriggles are allowed for a period of time to let the chain "stabilize". Modelling the chain as an SAW allows pivots to be used as a "wriggle".


texts: Find dominated or subsumed linear inequalities efficiently

texts:
Problem statement
Given a set of $N$ linear inequalities of the form $a_1x_1 + a_2x_2 + ... + a_Mx_M \geq RHS$, where $a_i$ and $RHS$ are integers. The inequality $A$ dominates or subsumes inequality $B$ if all its coefficients are less or equal and $RHS_A \geq RHS_B$. Most inequalities are sparse, i.e. most coefficients are zero. Usually, both $N > 1000$ and $M > 1000 $. I'm trying to identify dominating or subsuming inequalities efficiently.
What are quick ways to find
a) if an inequality is dominated by any other inequality, and
b) which inequalities are dominated by a given inequality?
(Monte-Carlo algorithms are fine, that only report correct results most of the time)
Proposed solutions in the literature
Eén, N. and Biere, A., 2005, June. Effective preprocessing in SAT through variable and clause elimination. In International conference on theory and applications of satisfiability testing (pp. 61-75). Springer, Berlin, Heidelberg. (chapter 4.2) discuss a variant of this problem in the context where all coefficients are binary, i.e. $a_i \in {0, 1}$. They propose occurrence lists, one per variable $x_i$, containing all inequalities with non-zero coefficients $a_i$. Additionally they use a hashing scheme, similar to Bloom filters, to quickly eliminate candidates. I don't see how to translate this to non-binary coefficients.
Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E. and Weninger, D., 2020. Presolve reductions in mixed integer programming. INFORMS Journal on Computing, 32(2), pp.473-506. (chapter 5.2) discuss a variant of the problem, but don't solve it. They first hash inequalities by indices of non-zero coefficients and the coefficient values. Additionally, they limit their search to a small subset of inequalities.
Schulz, S., 2013. Simple and efficient clause subsumption with feature vector indexing. In Automated Reasoning and Mathematics (pp. 45-67). Springer, Berlin, Heidelberg. describes Feature Vectors for clauses and a kd-tree-like data structure to query combinations of feature vectors.
Things I've tried

The trivial solution is to check all pairs of inequalities in $O(n^2)$. Unfortunately, that's too slow for my application where I have millions of inequalities.
I tried performing a random projection of the coefficients for every inequality, resulting in a projection $p_j$ for every inequality. An inequality $j$ can only dominate inequality $k$ if $p_j \leq p_k$. Thus we don't have to check all pairs. I repeat this process 10 times with multiple random projections, and use the random projection where I have to check the fewest pairs. In practice this is not effective, as most coefficients are zero - and it's unlikely that a random projection focusses exactly on the few non-zero elements. It doesn't help nearly enough.
Similarly I implemented Feature Vectors, but couldn't replicate the performance reported by Schulz.
AFAIK, multi-dimensional data structures break down in high-dimensional scenarios (curse of dimensionality). I'm not aware of indexing techniques that work for high-dimensional range queries.
I thought about Bloom filters, unsuccessfully.
I thought about randomized algorithms, unsuccessfully.

Do you have any other ideas?


texts: Why is the Halting problem decidable for Goto languages limited on the highest value of constants and variables?

texts:
This is taken from an old exam of my university that I am using to prepare myself for the coming exam:
Given is a language $\text{Goto}_{17}^c \subseteq \text{Goto}$. This language contains exactly those $\text{Goto}$ programs in which no constant is ever above $17$ nor any variable ever above $c$.
$Goto$ here describes the set of all programs written in the $Goto$ language made up of the following elements:
With variables $v_i \in \mathbb{N}$ and constants $c \in \mathbb{N}$
Assignment: $x_i := c, x_i := x_i \pm c$
Conditional Jump: if(Comparison) goto $L_i$
Haltcommand: halt
I am currently struggling with the formalization of a proof, but this is what I have come to so far, phrased very casually:
For any given program in this set we know that it is finite. A finite program contains a finite amount of variables and a finite amount of states, or lines to be in. As such, there is a finite amount of configurations in which this process can be. If we let this program run, we can keep a list of all configurations we have seen. That is, the combination of all used variable-values and the state of the program. If we let the program run, there must be one of two things that happens eventually:
The program halts. In this case, we return YES and have decided that it halts.
The program reaches a configuration that has been recorded before. As the language is deterministic, this means that we must have gone a full loop which will exactly repeat now.
No other case can exist as that would mean that we keep running forever on finite code without repeating a configuration. This means after every step, among our list of infinite steps, there is a new configuration. This would mean that there are infinite configurations, which is a contradiction.
Is this correct? Furthermore, how would a more formal proof look if it is? If not, how would a correct proof look?


texts: Computing a fractional matching of maximum product in a bipartite graph

texts:
Given a bipartite graph $(X\cup Y, E)$ with edge weights, it is easy to find a matching in which the product of weights is maximum: replace each edge weight with its logarithm, and find a matching in which the sum of weights is maximum.
Now, we would like to find a fractional matching which maximizes the product of values.
A fractional matching is an assignment of a fraction in $[0,1]$ to each edge, such that for every vertex, the sum of fractions of edges adjacent to it is at most $1$ (a matching is a special case of a fractional matching in which all fractions are in {0,1}).
The product of values is defined as follows:

For each vertex $x\in X$, the value of $x$ is the weighted mean of the weights of edges adjacent to $x$. I.e., if it is adjacent to $e_1, e_2, e_3$, their weights are $w_1,w_2,w_3$, and their fractions in the fractional matching are $f_1,f_2,f_3$ (where the sum $f_1+f_2+f_3\leq 1$), then $v(x) = w_1 f_1 + w_2 f_2 + w_3 f_3$.
We are looking for a fractional matching $f$ in which the product of values of vertices of $X$ is maximum.

Here, the trick of replacing weights with their logarithms does not work. Is there a different solution?


texts: Generate integer from 0 to 1 with equal probability

texts:
I am trying to get around this problem of my own making. I want to generate 0 or 1 with another function(gr0_4()) which generates random number from 0 to 4.

I am wondering if I can approach this way:

a). if gr0_4() = 0 or 1 then I will use 0

b). if gr0_4() = 2 or 3 then I will use 1

c). if gr0_4() = 4 I will repeat the a) and b) steps.

Is my understanding correct that the "a" and "b" step each has 50% probability of happening?

def gr0_1():
  while True:
    x = gr0_4()
      if x == 0 or x == 1:
        return 0
      elif x == 0 or x == 1:
        return 1

What if I want to use gr0_1() to create gr1_7() i.e. create number between 1 to 7 with equal probability?

Can I use below reasoning to create that function gr1_1().

As 7 consists of 3 bits. I can generate each bit with equal probability using gr0_1(). So I will call gr0_1() three times and based on that value I get, I will set/unset the corresponding bits to generate a number between 1 to 7 including the numbers 1 and 7. However I can get the number 0 but I don't want that so I will repeat the process again. Will the probability of each number generation between 1 to 7 will be 1/7 in that case also?

Some simple mathematical calculation will be nice to answer this. I tried to read up on rejection sampling but couldn't understand much.


texts: How did the first computer model display text?

texts:
I have a question ive not been able to explain, and I still cant find the answer looking through computer history. I want to know how the first letters were programmed into the first computer.

Let me explain more..

So when i research computer history they discuss the machines and how they work and when dos was invented, and I learned about how they used lightbulbs for an 8 bit calculator.. but then it just kind of skips my question in the timeline of it all and just say the next generation uses dos!

Well i understand how dos works.. but how to you program what each letter looks like... How did the computer know how to draw a T on the screen. Or a 1 or a 0? How did they saughter a circuit board and somehow get text to appear on a screen in characters we understand.. that blows my mind can anybody help?


texts: Closed form of recurrence with two inputs

texts:
This question comes from a relatively simple coding challenge at Codesignal, but represents an interesting CS/math puzzle. The question states:
"When a candle finishes burning it leaves a leftover. m leftovers can be combined to make a new candle, which, when burning down, will in turn leave another leftover.
You have c candles in your possession. What's the total number of candles you can burn, assuming that you create new candles as soon as you have enough leftovers?"
So the inputs are the number of starting candles and how many burned candles can be reused recursively to make new candles.
Now, I solved this with a while loop, and the loop itself just involves division and modulo math:
def candles(c, m):

    burned=c
    while c>=m:
        burned+=c//m
        c=(c%m)+c//m
    return burned

But many of the other solutions go straight to closed form (which is obviously better in terms of complexity). I tried to figure out how they were reaching this by writing out a recurrence relation, but I can't do it... Here's an example of an accepted solution:
return c + (c - 1) // (m - 1)
I was hoping someone could help me figure out what techniques are used to arrive at this solution.


texts: The best approach to search for closest object in hash map holding arraylist without changing data structure

texts:
Imagine the game handled server sided, don't think of a visual problem.

Given a game 2D map, with size of n * n.
The game contains objects (such as door, wall, a table).

Each tile position (x,y) can contain multiple objects, but this is not the catch of the question, it can even be limited to one.

The data structure for the game objects linked to the map is designed like this:

HashMap<Integer, ArrayList<GameObject>>

Where the Key integer represents X position of the object, and the value represents a list of all objects with the same X position, different Y position.

Now, I have a player location, I want to fetch a list of all 10 closest object to the player's position, within 100 tiles distance of the player.

My way of doing so:

Starting from player's position, and simply going x - 1 and x + 1 grabbing the objects lists limited to Z or until you have 10 closest objects collected, and then performing a position distance comparing search on each object. (Note, the objects lists are not sorted)

But this way is not stable, in my opinion, but I am not sure how can you solve this without changing the data stucture?


texts: Fitting different rectangles inside a rectangle

texts:
I have a fixed rectangle of size X x Y.
I also have a bunch of rectangles of different sizes.

I want to check if these rectangles can fit in the larger X x Y rectangles knowing that one can rotate any one of them by 90°.

Any great algorithm to do this ?

I know that some packing algorithm exists and several threads discuss it but it's not exact and it does not support rectangle rotation, therefore I cannot apply it to find a minimum rectangle and compare it afterwards to the given X x Y rectangle.


texts: Modify max value multiple times of a list

texts:
I have two lists say $A$ and $B$, each consisting of n positive integers. I make a list $C$ such that each element of $C$ i.e., $C_i=A_iB_i$ for each element $A_i \in A$ and $B_i \in B$.

Now I have to update the value of the maximum element of $C$ say $C_j$ by decreasing $B_j$ such that $B_j \geq 0$ and $C_j$'s updated value should be less than the second maximum element of $C$.

The above operation have to be applied $m$-times.

The approach I used was:

Build a Max Heap of list C
repeat $m$-times

update the value of max element of heap according to the given condition
Apply Max-Heapify

The above approach worked fine. So my question is "Is there any way to do the above task in a faster way than my approach?"


texts: How to sort a queue using a temporary stack?

texts:
Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack
We are allowed to make only two actions:

Action "x": Dequeue an element from the queue and push it to the stack.
Action "o": Pop an element from the stack and enqueue it in the queue.

In the above example, the following actions sort the queue in ascending order:
Actions: "xxoxooxxoo"
ex.

queue: 3, 14, 1, 20  stack:
x
queue: 14, 1, 20     stack: 3
x
queue: 1, 20         stack: 14, 3
o
queue: 1, 20, 14     stack: 3
x
queue: 20, 14        stack: 1, 3
o
queue: 20, 14, 1     stack: 3
o
queue: 20, 14, 1, 3  stack:
x
queue: 14, 1, 3      stack: 20
x
queue: 1, 3          stack: 14, 20
o
queue: 1, 3, 14      stack: 20
o
queue: 1, 3, 14, 20  stack:

and the queue is sorted.
Any idea how can I solve this problem with the minimum number of actions?
[EDIT]
Actually, it should be with a minimum number of steps, as there is a dummy solution:
You can just rotate the queue by actions: "xo" (move the first number to the end of the queue) and when you reach the largest number, push it to the stack. Repeat this process until the queue is empty. The stack now contains all the numbers with the top being the smallest number. So you just push them out one by one and you have a sorted queue.


texts: Number of times statement is executed in complex nested loop

texts:
I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:

int s = 0;
for(int k = n; k > 0; k /= 2)
{
  for(int l = k; l < n; l++)
  {
    s++; // statement
  }
}

I have been stuck with this problem for a while since I couldn't really get the correct formula whenever I compared the result of my formula to the output s.

I started by doing this:

$$T(n) = \sum_{k=1}^{\left\lfloor{\log_2(n)}\right\rfloor + 1}\sum_{l=k}^{n-1} 1$$

then eventually got this as a result:

$$T(n) = (1/2)(\left\lfloor{\log_2(n)}\right\rfloor + 1)(2n - \left\lfloor{\log_2(n)}\right\rfloor-2)$$

Does anyone know how to solve this kind of problem?

(This is a self-made problem btw since I kind of find analysis of algorithms fun)


texts: Does Quantitative Type Theory make the Prop universe obsolete?

texts: Coq (and other type theories such as Setoid Type Theory) have a Prop universe for propositions. As far as I understand this universe is needed to be sure that the propositions can be erased. In Quantitative Type Theory one can explicitly say which parameters are only used in types and can be erased. Does Quantitative Type Theory therefore make a separate Prop universe unnecessary?


texts: NLP Classification: rule-based approach providing high precision but low recall

texts:
In NLP, rule-based/linguistic approaches are usually said to provide relatively high precision but low recall compared to for example machine learning approaches. I think this is often true for almost any classification task in NLP. However, I couldn't find a paper which specifically examines this phenomena. Can someone please name one? Alternatively, I'd be interested in a paper which generally compares different approaches in NLP classification tasks.

I did quite some googling but all I found is a very vague statement in here: http://bmcbioinformatics.biomedcentral.com/articles/10.1186/1471-2105-15-285


texts:
In the book by Sangiorgi and Walker ("The $\pi$-calculus: A theory of Mobile Processes"), Subsection 3.2 is devoted to recursion. They state the following constraint (pages 132-133):

"The environment is finitary, in the sense that any process depends on only finitely many constant definitions. (Formally, the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$, is well-founded.)"

I do not understand how the two sentences are related. Right after there is an example with the definitions of $B_0$, $B_1$ and $B_2$: instances of $B_1$ and $B_0$ occur in the definition of $B_0$; instances of $B_2$ and $B_0$ occur in the definition of $B_1$; and an instance of $B_1$ occurs in the definition of $B_2$. Thus the environment is "finitary" in the sense that each one of the constants $B_0$, $B_1$ and $B_2$ only depends on three constant definitions. But how is "the transitive closure of the relation that relates two different constants $K$ and $K'$ if an instance of $K$ occurs in the definition of $K'$" well-founded? This transitive closure should relate any of the three constants $B_0$, $B_1$ and $B_2$ to any of these same constants and thus, if I consider the set $\{ B_0, B_1, B_2 \}$, I cannot find a minimal element.


texts: Myhill-Nerode - Prove irregularity for $\{a^{n^3}\}$

texts:
I need to prove that the following language is not regular by showing there are infinite pairwise  distinct equivalence classes:
$$
  L = \{a^{n^3} \mid n \geq 1\} \subseteq \{a\}^*
$$
Looking at a few examples, I intuitively noticed that for each $i \geq 1$ there is an equivalence class $[a^{i^3}] \neq [a^{j^3}]$ for $i \neq j$ because the number of  $a$'s we need to add increases exponentially with $i/j$. Thus for every $i$ we can add a suffix of $a$'s to reach the next higher power $(i+1)^3$ but the length of that suffix is different for every other power, so that each equivalence class only actually contains the representative itself.
Example:
$$
\begin{align*}
  &n = 1 \implies a \\
  &n = 2 \implies a^8 \\
  &n = 3 \implies a^{27} \\
  \vdots
\end{align*}
$$
Then
$$
\begin{align*}
& [a] = \{x \in \{a\}^* \mid a \; R_L \; x\} = a \\
& [a^8] = \{x \in \{a\}^* \mid a^8 \; R_L \; x\} = a^8 \\
\vdots
\end{align*}
$$
Consider $[a]$. For $z = a^7$ we get $az = aa^7 = a^8 \in L$, but starting from $i \geq 2$, we have that $a^{i^3}z \notin L$.
How can I write this down in a more formal/rigorous way?


texts:
Suppose that $S \in PCP(r(n),q(n))$, colclude that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$

The idea of a nondeterminstic simulation of the $V$ on input $x$ is simple, guess a proof, check every string $y$ of the length $2^r$, and this simulation should take nondeterministic time $2^r \cdot poly$ because $V$ works in time $poly$ and there are $2^r$ string to check.

In case of deterministic simulation the same intuition is applied, the maximum length of the proof is $2^r \cdot q$ with non-adaptive queries, hence $2^{2^rq}$ number of proofs  should be checked by deterministic emulation, therefore the total time is $2^{2^r \cdot q} \cdot poly$, not exactly what's required.

The problem is to show that $S \in NTIME(2^r \cdot poly) \cap DTIME(2^{2^r q+r} \cdot poly)$


texts:
Suppose we have $x$ apples and $y$ boxes. Each box can fit at most 3 apples, and we say that a box is half full iff the box contains $\leq$ 1 apple. If each apple has a (non-empty) list of boxes that it can be placed in, what is a polynomial time algorithm that places apples in boxes such that the number of half full containers is maximized?

My attempt

Sort apples in ascending order of the number of boxes that they can be placed into. For each apple, if there is an empty box that it can be placed into, then place the apple there. Otherwise, if there is a box with 2 apples in it that the current apple can be placed into, place the apple in that box. Otherwise, place the apple in a half full box. This algorithm clearly runs in polynomial time, but I don't think it is optimal, especially since I haven't specified how to break ties between boxes.


texts: 6-coloring of a tree in a distributed manner

texts:
I have some difficulties in understanding distributed algorithm for tree 6 - coloring in $O(\log^*n)$ time.

The full description can be found in following paper: Parallel Symmetry-Breaking in Sparse Graphs. Goldberg, Plotkin, Shannon.

In short, the idea is ...

Starting from the valid coloring given by the processor ID's, the procedure iteratively reduces the number of bits in the color descriptions by recoloring each nonroot node $v$ with the color obtained by concatenating the index of a bit in which $C_v$ differs from $C_{parent}(v)$ and the value of this bit. The root $r$  concatenates $0$ and $C_r[0]$ to form its new color.

The algorithm terminates after $O(\log^*n)$ iterations.

I don' have the intuitive understanding why it's actually terminates in $O(\log^*n)$ iterations. As it's mentioned in the paper on the final iteration there is the smallest index where two bit string differs is at most 3. So 0th bit and 1th bit could be the same and $2^2=4$, so this two bit will give us 4 colors + another 2 colors for different 3th bit, and in total 8 colors and not 6 like in the paper, and why we cannot proceed further with 2 bits, it's still possible to find different bits and separate them.

I would appreciate a little bit deeper analysis of the algorithm than in the paper.


texts:
I know that Euclid’s algorithm is the best algorithm for getting the GCD (great common divisor) of a list of positive integers.
But in practice you can code this algorithm in various ways. (In my case, I decided to use Java, but C/C++ may be another option).

I need to use the most efficient code possible in my program.

In recursive mode, you can write:

static long gcd (long a, long b){
    a = Math.abs(a); b = Math.abs(b);
    return (b==0) ? a : gcd(b, a%b);
  }

And in iterative mode, it looks like this:

static long gcd (long a, long b) {
  long r, i;
  while(b!=0){
    r = a % b;
    a = b;
    b = r;
  }
  return a;
}

There is also the Binary algorithm for the GCD, which may be coded simply like this:

int gcd (int a, int b)
{
    while(b) b ^= a ^= b ^= a %= b;
    return a;
}


texts: What's the difference between studying "Software Development", "Software Engineering", "Computer Science" and "Information Technology"?

texts: I really cannot understand the key-differences between those fields of study. Can please someone explain it in detail? If one graduates from a Master program of Computer Science, how does he differ from the one graduated from a Software Engineering program, or one from IT?


texts: Are there any resources or forums online for helping me understand TAOCP?

texts:
Context
I am doing an undergrad math project that involves exploring Donald Knuth's "TAOCP, Volume 4, fascicle 6: Satisfiability".
I am having trouble parsing some of this material.
Surely there are some online forums where different sections are unpacked or discussed or translated into Python?
I googled this but cannot find anything that helps me.
Question
What are some online resources to help people parse TAOCP?
Surely many people have read this work before me?


texts: Is logical address generated by CPU and MMU same if Physical and Virtual address space are same?

texts: The system has same physical and virtual address space i.e. 32-bit. Are the logical address generated by CPU and address generated by MMU same?


texts: substitution method on T(n) = T(floor(n/2)) + n recurrence

texts:
While studying recurrences and the methods for solving them, I'm get confused on the assumption made on the solution of the following problem.

Why we assumed that this inequality holds for all positive $m<n$, in particular for $m=\lfloor n/2\rfloor$? on what basis do we choose this $m$ and why do we need it. Appreciate your answers.
EDIT: Excerpt is from Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein


texts: "Balanced" vertex deletion on bipartite graphs

texts:
Given a bipartite graph $G = (X, Y, E)$ with $|X| = |Y|$, vertices from $X$ are to be deleted sequentially. As $d_x \le |X|$ vertices are deleted from $X$, let the total number of degree zero vertices of $Y$ be $d_y$. The goal is to seek a most "balanced" deletion, i.e., minimizing the maximum of $(d_x - d_y)$ for $d_x = 1, \ldots, |X|$.

For the setup, I would like to either find a polynomial time algorithm (seems less likely) for computing an optimal deletion sequence or show that the problem is hard (seems more likely). Does this problem map to some known problem(s)?


texts:
A knob is used to select one of three positions A, B, C.

The knob can never be turned from A to C, or from C to A, without spending at least one second in position B. The initial position of the knob can be any of A, B, C.

Give a regular expression for this language.

I tried starting from B, and ended up with:

BB*((AA*(BB*)*) u (CC*(BB*)*)*

But, it seems impossible to express all possible transitions.


texts: How to prove that $\{0^n 1^{5n} \mid n \ge 10000 \}$ is not a regular language?

texts:
I proved that $$ \{ 0^n 1^{5n} \mid n \geq 0 \}$$  is not a regular language using Pumping Lemma by following way.

Solve by contradiction that $ L = \{0^n 1^{5n} \mid n \geq 0 \}$ is regular language.

Let $0^p 1^{5p}$ be in L, where $p$ is the pumping length.
Now here if the language $L$ is regular language, $0^p 1^{5p}$ can be represented in the form $xyz$ where $|xy| \le p$ & $|y|\gt0$.
Thus, from step 2, we can say that $xy = 0^p$ and $y = 0^j$.
So, $xyz = (0^{p-j})(0^j)(1^{5p})$.
Now pumping the value of y to 2, $xyyz = (0^{p-j})(0^j)(0^j)(1^{5p}) = (0^{p+j})(1^{5p})$, which is surely not in $L$, thus not a regular language.

But how to prove for condition $\{0^n 1^{5n} \mid n \ge 10000 \}$ & for also $n \le 10000$, we can just prove that one of them is not regular and obviously by rules the complement will also be not regular.


texts: Show $B= \{z \mid (\exists x)\; P(x,z)\}$ is a recursive enumerable set

texts:
Let $B = \{z \mid (\exists x)\; P(x,z)\}$ and $P$ be a computable predicate. Show $B$ is a recursive enumerable set.

My attempt

As $P$ is a computable predicate then there is a program that computes it, therefore $B= \{z \mid (\exists x)(\exists t)\;\text{STP}^{(1)}(x,z,t)\} \Rightarrow B= \{z \mid \Phi(x)\downarrow\} = W_z$ and so $B$ is a recursive enumerable set.

Further info

$\text{STP}^{(n)} (x_1, \ldots, x_n, y,t)$ is a predicate that is true if the program number $y$ halts after $t$ or fewer steps on inputs $x_1, \ldots, x_n$.

Note: please note this is the first time I ever try to solve this kind of exercises, so even if I got everything wrong and nothing makes sense, every nudge in the right direction is really welcome.


texts: Correctness proof of the algoritm to generate permutations in lexicographic order

texts:
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

Find the largest index k such that a[k] < a[k + 1]. If no such index exists, the permutation is the last permutation.
Find the largest index l greater than k such that a[k] < a[l].
Swap the value of a[k] with that of a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

(from https://en.wikipedia.org/wiki/Permutation#Generation_in_lexicographic_order)

I would like to know a (possible formal) proof.