texts: Minimum total waiting time for arrivals/durations

texts:
I have come up with the following problem, and cannot seem to find an effective way of solving it:

  Consider $n$ clients arriving at a service point at time moments $\{a_i\}_{i=1}^n$ whose duration of service (by a single employee, let's say) is known
  to be $\{d_i\}_{i=1}^n$. Choose the turn of servicing them, such that
  the total sum of waiting times (i.e. if we consider $\{s_i\}_{i=1}^n$
  the start-of-service time for each client, then the total waiting time
  would be $\sum\limits_{i=1}^n\{s_i-a_i\}$) is minimized.

The only difference in this problem to the Interval Scheduling that has a greedy method of selecting the earliest finish time first, is that here all clients have to be serviced. (whereas in the Interval Scheduling, some intervals may not be selected)

Is there an efficient greedy algo for this problem? Or isn't there? Many obvious or less obvious approaches do not seem to work, example with this:

Client 1: arrival at 1, duration of 9
Client 2: arrival at 2, duration of 13
Client 3: arrival at 15, duration of $\epsilon$

The above example hints at choosing the smallest $a_i+d_i$ first, but I seem to be unable to prove this on an exchange argument... Is perhaps the problem NP-Complete?


texts: What is the intuitive logic behind the working of the Variable Entered K-Map (VEM)?

texts: In this site here they have just said how to minimize a function using VEM. But no intuitive logic behind the same has been stated, making it too mechanical. And I am very bad at memorizing things, so an intuitive logic behind the same would help me a lot to solve problems using this problems independently.


texts: Construct a context-free grammar for a given set of words

texts: I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense "natural" (e.g., the grammar doesn't produce all words in the alphabet). The algorithm is very simple,  it has something like 3--4 rules for grammar transformation attempted on each new word. Any help in finding it would be appreciated.


texts:
I tried finding real life applications for the Four Color Theorem (except for coloring maps) but couldn't find anything useful and well illustrated. For example I found this:

Graph coloring problems are widely applicable to the problem of scheduling.
Consider a university, where you are trying to schedule times for all of the final exams. Some students are taking more than one class, so you want to make sure they don't have two exams scheduled at the same time. However, you want your exam writing period to be as short as possible, to run as many exams concurrently as you can.
You can represent this as a graph coloring problem: construct a graph in which each class is a vertex, and there is an edge between vertices any time a two classes contain the same student. Your colors will represent different exam timeslots. The minimum number with which you can color that graph is the smallest number of timeslots you need to write all your exams.
source: jmite on cs.se.

However, I don't really get how it works! Also if you could give more examples related with graph theory and four color theorem


texts: CPU Scheduling - Round Robin order on ready queue

texts:
I am attempting the question below:

  Assume a set of processes $P_1, P_2, P_3$ and $P_4$ arrive at different times in the ready queue. The table below shows the burst time, the priority (smallest priority number implies highest priority) and arrival time for each of the processes.
  \begin{array}{|c|c|c|c|}
\hline
Process & Burst ~ time & Priority & Arrival ~ Time \\ \hline
P_1 & 8& 2& 0\\ \hline
P_2 & 2 & 3 & 1 \\ \hline
P_3 & 4 & 1 & 3 \\ \hline
P_4 & 6 & 2 & 5 \\ \hline
\end{array}
  Draw a Gant chart, illustrating the execution of the processes, to demonstrate each of the following algorithms.

  First-Come, First-Served (FCFS)
  Round Robin(RR) with time slice of 3 time units.

Problem I am having is that my answer is not matching what I am getting form the simulator here.

The problem might be with the way I am handling my ready Queue. My workings and answer is below. The simulator shows that after first time P3 appears in the chart that P4 should start. But P1 was pre-empted and still had more execution hence I put P1 in there. Where am I going wrong?

Ready Queue (as I was working it out):
P1,P2,P3,P1,P4,P3,P1,P4

GANT CHART:


texts: Minimum number of deleting palindromes to delete whole string

texts:
Let's say we have given array $A$ of size $n$. Our goal is to delete the whole array with minimum steps. In one step we can choose substring (consecutive elements from the string) and delete it only if it is a palindrome (if we can read it in the same way from the front and the back).

For example the array 1 1 5 9 5 1 can be deleted in two steps. Step 1: Delete substring 5, 9, 5. Then delete the remaining substring 1, 1, 1. We only need to return 2, the number of steps.

My idea is to use dynamic programming technique. Our state would be $DP[L][R]$ meaning the minimum number of steps to delete the substring in range $[L, R]$. However I can't really work the transitions, since there can be cases when our front element will merge with some element in the middle and with some elements in the back, so I don't know how to cover all transitions between different states.


texts: Acceptance behavior of L and NL with and without cycling

texts:
The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't enter the accepting state), so we could define that it rejects in this case (which would be consistent with NL). Or is cycling simply not allowed for L?

Does this makes any difference at all, i.e. would NL or L get weaker (in the sense that we can't prove that they still accept the same languages), if we would completely forbid cycling?


texts: Reference request: Category theory as it applies to type systems

texts:
I keep hearing about how one must learn category theory to truly understand programming language theory. So far, I've learned a good deal of PL without ever stepping foot into the realm of categories. However, I figured it was time to take the leap to see what I had been missing.

Unfortunately, none of the sources I can find seem to make any connections to type systems or programming. They say it's an introduction to category theory for computer scientists, but then veer off into general abstract nonsense (I say this lovingly) without giving any practical examples or applications.

I guess my question is actually two-fold:

Is category theory essential for understanding the "deep concepts" in PL?
What's a source that explains category theory from the viewpoint of practical applications to type systems and programming?

So far, the furthest I've gotten is to a vague conception of functors (which don't seem to be related to functors in ML, as far as I can tell). I'm dreading the abstraction I'll need to keep in my head to understand monads from a category-theoretic view.


texts: How powerful is a k-stack pushdown automaton with a unary stack alphabet?

texts:
I'm interested in pushdown automata with a unary stack alphabet: let's call them UPDA's.  Define a $k$-UPDA to be a pushdown automaton with $k$ stacks, each with a unary stack alphabet.

I've figured out that a $k$-UPDA is at least as powerful as a $(k-1)$-PDA (see proof at the end). This implies that a $k$-UPDA is equivalent in power to a Turing machine when $k \ge 3$ (as it is at least as powerful as a Turing machine when $k \ge 3$, as you can simulate a TM with a 2-PDA, and by the Church-Turing thesis, no more powerful).

A 1-UPDA is more powerful than a NFA/DFA, as a 1-UPDA can recognize, for instance, the language $\{0^n1^n:n \in \mathbb{N}\}$. But, at the same time I suspect (although I do not know) that a 1-UPDA is less powerful than a 1-PDA.

My questions are as follows:

What is the complexity class recognized by a 1-UPDA? Or at the very least, are there better bounds than "more powerful than a NFA/DFA and no more powerful than a 1-PDA"?
What is the complexity class recognized by a 2-UPDA? Or at the very least, are there better bounds than "at least as powerful than a 1-PDA and no more powerful than a 2-PDA"? In particular, is a 2-UPDA more powerful than a 1-PDA?
Is there a $k$ such that you can simulate a TM with a $k$-UPDA without exponential overhead?
Is there a standard name for a UPDA?

Proof that a $k$-UPDA can simulate a $(k-1)$-PDA: use one stack for scratch space. You emulate a stack alphabet of $m$ symbols with a unary number, base $m$. To push a number $x$ to a stack, you multiply the number of elements in the stack by $m$ and then push $x$ more symbols. (You also need to check for if the stack is empty, but that is simple enough.) To pop a number, you modulo the stack by $m$ for the number to pop, and divide the number of symbols in the stack by $m$.


texts: How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))?

texts:
following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.

I tried to derive it on paper.

Let T(n) = T($\sqrt{n}$) + c
$\implies$ T($n^{1/2}$)+2c
$\implies$ T($n^{1/4}$)+3c
$\implies$ T($n^{1/8}$)+4c
$\implies$ T($n^{1/16}$)+5c
.....upto n > 1

I noticed that the power of n becomes 1/2 times the last value.

How should I proceed from here on?
I need to derive that T(n) is O(log(log(n))).


texts: Changes in prefix/ASN (Autonomous System Number) pairs?

texts:
I am wondering if a pair prefix/AS may change often ?
I mean let's say we have a list with many given prefixes (e.g. 4.6.20.0/24) that are mapped to ASN (e.g. 10753), this list is built on a given date. The question is, should we expect that several prefixes are mapped to other ASN in a list built few days later ?

I am asking this question because I m using a tool (pyasn) to perform ip to ASN lookup with historical data. It is possible (using RIB file from RouteView) to create lists of prefixes/AS pairs every 2 or 3 hours. I wonder if it is necessary to be that precise since the creation of the list is relatively costly ?

I personally do not think these pairs are meant to be changed often, but I d like a confirmation, and if possible a link towards a document that I can cite as reference in my work ? I have searched during half an hour without success ...

Thank you all in advance :D


texts: If a language is contained in other langauge, is it of the same complexity?

texts:
If some language $L$ is in P, and some other language $K$ is contained in $L$, does that mean that $K$ is also in P?

Thanks :)


texts: Calculating the information density of an encoding system

texts:
How do I calculate the information density of an encoding system?

This question came up as I was reading several papers about encoding data in DNA (I think I have gone through just about every major paper on encoding data in DNA after Church's). All of them mention the information density of their encoding system, which I understand to be given in units along the lines of bits or bytes per nucleotide.

From looking around on the internet and asking around in the hbar (the Physics chat) I understand the absolute basics: that one creates a model that gives the probability distribution over the possible messages in your system (say, English, or ASCII) and then from there calculate the average information density of a message using that distribution.

Unfortunately, as a complete beginner, I don't know how to do any of those things. I'd like to understand that process and in the end be able to do my own calculations. Any resources would be helpful, of course, but I was advised to ask this question here.

Tl;dr: how do you calculate the information density of a system?


texts: Extracting Randomness from Mouse Acceleration

texts:
I'm working on trying to make an "entropy pool" that will be fed as input into an RNG (as in, ex, Fortuna). In order to do so, I need to take various collected data and extract as much entropy as possible to turn it into unpredictable bits. I've read many papers about extracting randomness, but I haven't understood how to apply it to real-world data sources.

For example, as one entropy source, I'd like to use the position of the mouse cursor. After some simple experimentation, it seems like using the acceleration of the cursor (resulting in two streams of X acceleration and Y acceleration) is the best representation to use in that it reduces the sample range significantly. Running several min-entropy estimators on the acceleration data (separately for X and Y axis data), I get estimates of at worst 0.75 bits/sample of entropy (ignoring that the two streams are correlated). Beyond that, I'm not sure how to apply any published randomness extractor to this data.

Part of my problem stems from the fact that most entropy extractors talk about entropy rate, which I'm not sure how to calculate in this case. My samples are 8 bits each (signed byte), so that could make the entropy rate 0.75/8 ~= 0.09, which is far too low for most extractors. Another problem is that I have two correlated streams, and I can't remember any extractors that deal with that kind of input.

Any guidance or references on how to extract entropy from this data using any published randomness extractor would be greatly appreciated. I'm very interested in using a "real" randomness extractor and not the common "just hash it" approach.

I have a custom design that I can detail if desired. It essentially computes symbol statistics from the entire test capture (5 million samples) and uses range encoding to encode each symbol using those statistics. It results in about 1.5 bits/sample of output for each stream, and I'm not sure how well founded the idea is.

Edit: One of my end goals is to have a very large state RNG, suitable for being able to shuffle 200 card decks into every possible combination. 200! is ~1246 bits, so (for ex) using a typical PRNG-oriented implementation of AES-256-CTR would not suffice because it has too small a state to store that much entropy.

Also, as for using cryptographic hash functions, some of the early papers on extractors indicate that almost all functions are good extractors for high-entropy data, but I haven't seen any information about using them to reduce low-entropy data to shorter higher-entropy data (keep the entropy level, but reduce the total number of bits). If this is a mathematically valid use, I'd really like to see papers about it.


texts: What does apostrophe-like symbol in the superscript mean?

texts:
It's hard to look up the meaning of a symbol if you don't know what it is called in the context that it is written.

That apostrophe-type symbol in the sequence notation - what is that?


texts: Can any non-halting Turing Machines with blank tape input print out any irrational number?

texts:
The fact that square root of 2, pi etc are computable numbers only means they can be approximated to arbitrary nth decimal, so these TM that approximate them do not count since they halt after printing out the nth digits. I would appreciate a definitive answer and reasoning.
If the answer is NO, which I suspect, is the following statement equivalent?
Any TM with blank tape input can only print rational numbers, assuming its alphabets are coded in integers.


texts: Why does RAID-5 require an additional disk for parity blocks?

texts:
I know that RAID-5 consists of block-level striping across multiple disks, but using an additional parity-check block on each disk .. and that at least two disks are required for striping.

And it's obvious that each parity block is specific to each disk it belongs to (and so there is no need for allocating an additional disk).

Image from Wikipedia.

However I've been unable to understand why in fact there is an additional disk required for parity checks, as I found on this article:

  The minimum number of disks in a RAID 5 set is three (two for data and
  one for parity).

Any idea?


texts: Proof that AND-OR graph decision problem is NP-hard

texts:
Given an directed acyclic AND-OR graph, where each non-terminal nodes are labelled as either AND or OR. The terminal nodes are the nodes which have no outgoing edges. Children of a node are the vertices all the outgoing edges of the node points to.

A solution graph for a node $S$ on an AND-OR graph $G$ is defined as a subgraph $G'$ which satisfies the following

(1) $S\in G'$

(2) If $v\in G'$ and $v$ is an AND node, then all of $v$'s children in $G$ are in $G'$

(3) If $v\in G'$ and $v$ is an OR ndoe, then at least one of $v$'s children in $G$ also belongs to $G'$

I want to show the following decision problem is NP hard:

Instance: An AND-OR graph $G$, a node $S$ in $G$ and a number $k$.

Question: Does there exist a solution graph for $S$ in $G$ which contains $\leq k$ nodes?

I am thinking about reducing some well known NP-hard problem to this problem. However, I am not sure which problem is the most suitable to pick. Please enlighten me! Thank you!


texts:
I'm trying to prove $EXP \subset E^E$ (strictly).

I believe I need to construct my own $A \in E^E$ and show that $A \notin EXP$, but I cannot think of a smart way of doing that.

Thanks.


texts: Algorithm to identify if a string of numbers is a lottery sequence

texts:
Suppose that a valid lottery ticket consists of a sequence of 7 numbers drawn from the set $\{1,2,\ldots,59\}$. Given a string like "$12345678$", I want to efficiently print all the lottery sequences using every digit in the input string.

In the example above, a couple of possible sequences are:
${1,2,3,4,56,7,8}$ or ${1,2,3,45,6,7,8}$ which both satisfy lottery number conditions.

I thought of a combinatorial solution like this:

Let $n$ be the number of characters in the input string. If $n<7$ or $n>14$ then there is no solution possible. For valid input strings of length $n$, where $n\in [7,14]$, the problem reduces to the following:

In a string of length $n$ there are $n-1$ locations to put a comma. We have to put $6$ commas in $n - 1$ spaces such that no two consecutive spaces are empty (Otherwise, a number will be consist of three digits or be greater than $59$). This simply means arrange six ones like this:

  111111

and then put $n-7$ $0$'s (representing emptiness) in the 7 slots. So, for example, if the input string is of length $8$ ("$12345678$") then we have to put $8-7 = 1$ zero in $7$ slots. So there are $7$ places where a zero can go and the strings generated are:

  0111111, 1011111, 1101111, 1110111, 1111011, 1111101, 1111110

which correspond to $\{12,3,4,5,6,7,8\}$, $\{1,23,4,5,6,7,8\}$ etc.

So the problem reduces to computing $\binom{7}{k}$ and for each arrangement like above, put the corresponding commas in the appropriate place in the input string. So $0111111$ maps to $12,3,4,5,6,7,8$ (the space between 1 and 2 is left empty while the commans occupy the remaining 6 slots).

Is this algorithm a bad choice or can I do better?


texts: How to interpret this formal language definition?

texts:
I am asked to construct a PDA to accept the language:

$\qquad \{w \in \{0, 1\}^* : \#_{0}(w) \ge \#_{1}(w)\}$

I am wondering how to interpret the $\#$ symbols and everything. Could someone please explain what exactly this means and how to construct it?


texts:
I'm taking an introductory course in AI and we've been given the assignment to solve a puzzle using different search algorithms on a state space (BFS, DFS etc). I understand the theory and everything, but I'm not sure what information I should store in the nodes of the tree.

Assume that I have a matrix to represent the game board. Should each node in the tree contain the entire board? For example, in the case of 19x19 Go, would each node consist a matrix of size 19x19 (the problem I'm trying to solve is a 1 player game, and not Go or chess or anything like that, however)? If this is the case, even with pruning, it sounds to me like this would take up an insane amount of space. For example, at depth 1, a state space of the game of Go would have 19*19 nodes each containing a 19*19 matrix (correct me if I'm wrong here). At the same time, I can't find a better option.

What is the general approach to storing these kinds of states?

Any help is greatly appreciated.
Please let me know if the question is in any way unclear.


texts: I need to test my understanding of the difference between the data model and database schema. According to my understanding, the data model is a description of how the data will be stored and the relationships between the data. While the schema is very similar to a database model and according to the book  "Database Management systems   " by Raghu and Johannes " A description of data in terms of a data model is called schema"  and it's a template of how the data will be stored. Is that right?


texts: How do I find the max and min value of an array in 3n/2−2 comparisons?

texts:
So I'm using this method to find the min and max value of an array simultaneously where I split the array into n/2 and n/2 parts. I then keep splitting each part until I have either a pair of numbers or a single number.

What I'm trying to do now is the same thing but I'm trying to come up with a method that will always use 3n/2−2 comparisons. The method above doesn't use 3n/2−2 comparisons each time. So I just want to visualize how this is done on an array before I start to programming the method.


texts: Topological sort where some nodes can't come in between two other nodes

texts:
I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node X or node Y. In other words, Y < X OR Z < Y.
I've thought about several approaches to this, but can't find a solution. Maybe I can turn every NonBetween relation into "regular edges" and then do a standard topological sort?
Have you heard of any similar problem or solution to this?


texts:
According to this Quora post,

  It refers to two things: A systems bottleneck, in that the bandwidth
  between Central Processing Units and Random-Access Memory is much
  lower than the speed at which a typical CPU can process data
  internally. The 'intellectual bottleneck' in that programmers at the
  time spent a lot of time thinking about code optimisation to stop
  'lots of words' being pushed back and forth between CPU and RAM.

But according to my class lecture, it is the problem that "Generic implementation of single, common instruction and data hierarchy makes it impossible to access data and instructions at the same time. This is traditionally called von Neumann bottleneck."

Which one is correct?


texts: Making a CFG for a^i b^j c^k such that i+k < 3j

texts:
I have the language $L = \{ a^ib^jc^k \mid i + k < 3j \}$, however I am struggling to convert it to a CFG.

I have thought about solving this for a long time but but this still hasn't gotten me very far

Any help would be appreciated Thanks


texts: Looking for an example of proving space upper bounds for computing functions on a DTM

texts:
Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of the input string.

This to my mind looks like a work that can be done using only a linear amount of space on the work tape. All you really need to do is just have a counter to count the length of the input string in one pass and then you know what $\vert x \vert$ is and then squaring it is a constant time process and then just output those many $0$s.

Is my intutiion correct? How is one supposed to formally prove such a space-bound on the working of a (deterministic Turing Machine) DTM? Can someone kindly show how to write this up formally?


texts: White-space and comment by lexical analyzer

texts: Lexical Analyzer mostly deletes comments and white-spaces. One example where I think Lexical Analyzer might not be discarding white-spaces is in Python language, as indentation has a important role in python. But I can't think of practical example where comments are/should be kept by Lexical Analyzer? Is there any such example you can think of?


texts: Can a computer game can run on a boot mode without the aid of os?

texts: I meant that that the game programmer can just add its own code to the game to manipulate its own low level function as the operating system does provide in a common executables,and load it into the boot mode using its own bootstrap


texts: Worst case for linear-time k'th smallest element algorithm?

texts:
There's an algorithm for finding the k'th smallest element in an unsorted array similar to quickselect:

  kthSmallest(arr[0..n-1], k)
  1) Divide arr[] into ⌈n/5⌉ groups where size of each group is 5
     except possibly the last group which may have less than 5 elements.

  2) Sort the above created ⌈n/5⌉ groups and find median
     of all groups. Create an auxiliary array 'median[]' and store medians
     of all ⌈n/5⌉ groups in this median array.

  // Recursively call this method to find median of median[0..⌈n/5⌉-1]
  3) medOfMed = kthSmallest(median[0..⌈n/5⌉-1], ⌈n/10⌉)

  4) Partition arr[] around medOfMed and obtain its position.
       pos = partition(arr, n, medOfMed)

  5) If pos == k return medOfMed
  6) If pos > k return kthSmallest(arr[l..pos-1], k)
  7) If pos < k return kthSmallest(arr[pos+1..r], k-pos+l-1)

The algorithm assumes that there are no repeated values.

I think that the worst case is when medOfMed is as big or as small as possible, so that it divides as unevenly as possible (although I don't know what the array would look like in that case). My idea for this was to make the medians of each subarray of five elements in a way so that when they're joined together it's as big (or small) as possible. For example: ((-10000, -1000, 1, 2, 3), (-50000, -2000, -100, 4, 5))

My classmate says that to achieve worst case results you can just fill the array with scales of length five that are increasing and has "average" values for the median and values above it, for example (-1000,-500,1,2,3) because then when it is time to sort by the median of medians you can get a number that is above the others.

I think he's wrong because at the end his median will always have to divide in groups of 2.

Who is right (if any)? Is there some other way to achieve worst case time? How can I prove this with time complexity?


texts:
I have to simplify A+C'+B'CD but I don't see how.

I had to deduce the expression starting from a logic diagram in which two AND gates were used for the B'CD part. Seeing the diagram all I can think of is to use one AND gate instead of two, but I don't see how the actual boolean expression can be simplified.


texts:
The Stable Roommates Problem matches 2n participants into n sets of roommates based off of each participant's list of preferences. I was wondering if there was a variant of this problem where the number of roommates is different. For example, matching 10n participants into n sets. Thanks for the help.

Edit: The Hospital Resident problem is also similar to this. Each hospital can take a certain number of residents. The problem is the residents list their preferences by hospital instead of other residents.


texts:
When applying the pumping lemma to $L = \{ 0^n \mid n>0\}$ I do the following:

$S = 0^p$
$x = \varepsilon$
$y = 0^p$
$z = \varepsilon$

so $S = xyz = (\varepsilon)0^p(\varepsilon)$

For $x y^i z$ if i choose $i = 0$ (pumping down)
i get $S = \varepsilon$, which is not an element of $L$.

Therefore according to the pumping lemma this language is not regular.
But since I am able to draw a DFA for $L$, I know it is regular.

I would like to know what rules I am violating by trying to apply the pumping lemma to $L$ in this manner.


texts: Problem with Understanding "correlated attributes into a set of values of uncorrelated attributes" in PCA

texts:
I am studying PCA. I have a problem in understanding the following concept:

What is meant by transforming "correlated attributes into a set of values of uncorrelated attributes" in Principal Component Analysis?

  Principal Component Analysis (PCA) is a mathematical procedure that uses an orthogonal transformation to convert a set of observations of possibly correlated attributes into a set of values of uncorrelated attributes called principal components.

as discussed in the article Weight by PCA (emphasis mine)?


texts:
I'm trying to solve this from The Algorithm Design Manual:

  6-23. Arbitrage is the use of discrepancies in currency-exchange rates to make a profit. For example, there may be a small window of time during which 1 U.S. dollar buys 0.75 British pounds, 1 British pound buys 2 Australian dollars, and 1 Australian dollar buys 0.70 U.S. dollars. At such a time, a smart trader can trade one U.S. dollar and end up with 0.75×2×0.7=1.05 U.S. dollars---a profit of 5%. Suppose that there are n currencies c1,...,cn and an n×n table R of exchange rates, such that one unit of currency ci buys R[i,j] units of currency cj. Devise and analyze an algorithm to determine the maximum value of R[c1,ci1]⋅R[ci1,ci2]⋯R[cik−1,cik]⋅R[cik,c1] Hint: think all-pairs shortest path.

My understanding is this is asking to find the longest simple cycle (LSC) on a directed weighted (complete?) graph. There is a reduction from longest simple path to LSC, so this would be NP-hard. It seems strange that the problem gives a hint, so maybe it's asking something else?.


texts: Is deciding if there is a set that is intersected with some given sets and that has at most one common element with other given sets NP-complete?

texts:
Given 2 collections of ﬁnite sets $A_1,A_2,\ldots,A_m$ and $B_1,B_2,\ldots,B_n$, is there a set $T$ such that: $\left|T \cap A_j\right|\ge 1$, for $j = 1,2,\ldots,m$ and $\left|T \cap B_i\right|\le 1$, for $i= 1,2,\ldots,n$?

I tried doing this problem by considering it as a decision problem (pi).
Please suggest me if you have an approach.


texts: Why system calls via interrupts are slow and thus we have SYSENTER/SYSEXIT instructions?

texts: As far as I understand we got SYSENTER/SYSEXIT instructions because system calls via interrupts were slow (right? I might be wrong though). Therefore my question is why system calls via interrupts are slow? And how do we optimize them via SYSENTER/SYSEXIT instructions? Thank you


texts: Understanding the proof of "DFS of undirected graph $G$, yields either tree edge or back edge" better with graph for each statement in proof

texts:
I was going through the edge classification section by $\text{DFS}$ algorithm on an undirected graph from the text Introduction to Algorithms by Cormen et. al. where I came across the following proof. I was having a little difficulty in understanding the steps of the proof and hence I made an attempt to understand it fully by accompanying each statement in the proof with a possible graph of the situation.

Theorem 22.10 : In a depth-first search of an un-directed graph $G$, every edge of $G$ is either a tree edge or a back edge.

Proof:

Let $(u , v)$ be an arbitrary edge of $G$, and suppose without loss of generality that $d[u] < d[v]$. Then, $v$ must be discovered and finished before we finish $u$ (while $u$ is gray), since $v$ is on $u$'s adjacency list.

If the edge $(u, v)$ is explored first in the direction from $u$ to $v$ , then $v$ is undiscovered (white) until that time.

 Figure 1 : Situation in point 2. DFS starts from 'u', 'u' is grayed and DFS then looks along the red arrow to 'v'

Otherwise we would have explored this edge already in the direction from $v$ to $u$. Thus, $(u, v)$ becomes a tree edge.

 Figure 2 : Situation in point 3. DFS starts from 'u', 'u' is grayed, then discoveres 'w' and 'w' is grayed and then again discovers 'v' DFS then looks along the red arrow to 'u' , the green pointer explains the rest

If $(u, v)$ is explored first in the direction from $v$ to $u$, then $(u, v)$ is a back edge, since $u$ is still gray at the time the edge is first explored.

 Figure 3 : Situation in point 4. DFS starts from 'u', 'u' is grayed, then discoveres 'w' and 'w' is grayed and then again discovers 'v' DFS then looks along the red arrow to 'u' , 'u' is already grayed so the edge becomes a back edge, indicated by the green pointer
■

Could anyone confirm if I am on the right track or if not please rectify me.
[My question might seem similar to this or this but neither of them seemed to help me]


texts: How does the momentum term for backpropagation algorithm work?

texts:
When updating the weights of a neural network using the backpropagation algorithm with a momentum term, should the learning rate be applied to the momentum term as well?

Most of the information I could find about using momentum have the equations looking something like this:

$W_{i}' = W_{i} - \alpha \Delta W_i + \mu \Delta W_{i-1}$

where $\alpha$ is the learning rate, and $\mu$ is the momentum term.

if the $\mu$ term is larger than the $\alpha$ term then in the next iteration the $\Delta W$ from the previous iteration will have a greater influence on the weight than the current one.

Is this the purpose of the momentum term? or should the equation look more like this?

$W_{i}' = W_{i} - \alpha( \Delta W_i + \mu \Delta W_{i-1})$

ie. scaling everything by the learning rate?


texts: proving that local sequence alignment can be done in linear space

texts:
according to the Smith-Waterman setup, I have 2 string sequences S and T, and I want to identify their respective subsequences $\alpha$ and $\beta$ whose global alignment have maximum score over all pairs of subsequences. As usual, the scoring system is a substitution matrix and a gap-scoring scheme. However, I want to find $\alpha$ and $\beta$ with linear space.

I know how to find the terminating point $(i^*, j^*)$ of the subsequences - I'm doing DP (dynamic programming) from the top-left, while throwing away negative scores.  The values in each row can be computed in a
row wise fashion and the algorithm must store values for only two rows at a time = linear space. I'll maintain the best score I saw and call it opt, and the indexes of opt would be $(i^*, j^*)$.

But now how do I find the starting point $(i', j')$? I thought about doing DP starting from $(i^*, j^*)$ going to the top-left corner, and stop when I reach the opt score from before. But how do I prove that I'll find a point with the opt score?

once I prove that, I just use Hirschberg from $(i^*, j^*)$ to $(i', j')$ and I'm done.

Thanks!


texts:
Let $\mathrm{MIN}_{\mathrm{DFA}}$ collection of all the codings of DFAs such that they are minimal regarding their states number. I mean if $\langle A \rangle \in \mathrm{MIN}_{\mathrm{DFA}}$ then for every other DFA $B$ with less states than $A$, $L(A)\ne L(B)$ holds. I'm trying to figure out how come that $\mathrm{MIN}_{\mathrm{DFA}} \in R$? How come it is decidable?

What is about this kind of DFAs that is easy to decide?


texts:
Consider the following inequalities:

$\sum_j a_{ij}x_{ij}=1 \;\;\; i=1,...,n$

$\sum_i a_{ij}x_{ij} \le y_i \;\;\; j=1,...,n$

$x_{ij} \ge 0 \;\;\; i,j=1,...,n$

$y_i \in \{0,1,2\} \,\,\,\, i=1,...,n$

$a_{ij}$ are 0-1 coefficient
$x_{ij}$ are unknowns.
$y_i$ are integral unknowns. Each $y_i$ can only take on integer value $0,1,2$.

Let $\textbf{y}$ be the vector of $(y_1,...,y_n)$. I want to count how many different $\textbf{y}$'s (if two $\textbf{y}$'s differ in at least one $i$ then they are different) such the above problem is feasible (there exists at least one $\textbf{x}$ satiesfies above inequalities)?

You can think of an $n$ by $n$ matrix $A$ with each entry equals to $a_{ij}x_{ij}$. Each row sum must be 1 and each column sum must be less than or equal to $y_i$. You can also think the problem as a bipartite graph $G=(V_1 \cup V_2 ,E)$ with incidence matrix $[a_{ij}]$. The problem is feasible if there is a special matching such as all nodes in $V_1$ are matched exactly once and all nodes in $V_2$ are matched at most $y_i$ times. (if $x_{ij}$ are restricted to binary, which I don't care)

Is this counting problem #P-complete?

edit:
This problem is a special case of my another question
Complexity class of maximum flow problem with random arc capacity
which no one has answered yet. If anyone has relevant reference for the original question too I'll appreciate it.

To clarify the problem a little bit more, the problem has

INPUT: $a_{ij}$

OUTPUT: Number of different $\textbf{y}$'s that above inequalities are satisfied.

I am not an expert in complexity theory, but I tried to dig around the problem of counting the number of matchings in a bipartite graph, which is closely related to #P. I have no success because there is a gap between the number of matchings and the number of different $\textbf{y}$'s. Different matchings can correspond to the same $\textbf{y}$ (and of course the same matching can be satisfied by different $\textbf{y}$'s).


texts: How exactly MOV AX will load data from RAM?

texts:
Somewhere on Internet I read  : Whenever word size is greater than memory cell size, then there is a need for accessing multiple memory cell
Example:
for 16 bit processor:
MOV AX [2000]
 To transfer memory content, we need to transfer 16 bit data , so we need to access 2 memory cells
M[2000 H]
&
M[2001 H]
But I didnt get this. Why 2 cells ?
I interpreted as follows:
1) 8 bit binary code will be fetched which decoded as MOV AX.
2) From next memory location , (00 H ) will be fetched as memory is byte addressable.
3) From next memory location , (20 H ) will be fetched.
4) In IR register it is treated as ( 2000 H ) and data at (2000 H) memory location is       fetched and moved to AX register.
So why to access M[2001 H] memory location ??


texts: Does a function that belongs to θ(n) belong to O(n^2)?

texts:
My understanding is that the answer is yes. To be θ(n) implies O(n), which itself implies O(n^2).

In other words, a function that is tightly bounded by n is trivially upper-bounded by n^2 as well.

The TA of my class tells me that I'm wrong, that a function that is tightly bounded by n cannot be upper-bounded by anything other than n. Which doesn't sound right to me, as O(n) is but a subset of O(n^2).


texts: Why $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$ does not holds for the class of Recursively Enumerable Languages?

texts:
"The class of Recursively Enumerable Languages is closed under Union,
  and Intersection but they are not closed under Complement."

I know why they are not closed under Complement & why they are closed under Union & Intersection but for other classes of languages we use a reasoning for closures based on the De'Morgan Law:

  $A \cap B = \widehat{\widehat{A}\cup \widehat{B}}$

That is,
If some language class is closed under any two of the three operations namely, Union, Intersection & Complement then it must be closed under the third.
So what's wrong with the class of Recursively Enumerable Languages?
are not they sets?
Or am I using implication incorrectly?


texts: Upper bound on the average-case runtime of shell sort

texts:
I found that shell sort with the gaps of Fibonacci sequence has the lower bound complexity $\Omega(N \log N)$ in average cases.
I want to know the upper bound complexity in average cases, so I write
some of code to test it. It seems to be $O(N\log N)$ but how to prove it?

Here is the lower bound of average cases analysis:

According to this, for increment sequence $h_1,\dots,h_p$, it will have the lower bound of average case

$\Omega(N\sum_{k=1}^{p}\frac{h_{k-1}}{h_k})$ where $h_0 = N$

Then, the shell sort with the Fibonacci increment sequence will be

$\Omega(N(\frac{N}{F_n} + \sum_{i=2}^{n}\frac{F_n}{F_{n-1}}) = \Omega(N\log N)$ where $F_n$ is the Fibonacci sequence below $N$


texts: Algorithm of Communication with Failures

texts:
I am interested in Distributed Algorithms especially in communication in network with failures.

I look for the proof of the following randomized algorithm of communication in network with failures. For me it seems like very general result in the communication, nevertheless I haven’t found the proof yet.

Algorithm: Initially only vertex $v_0$ has the message, at the end of the algorithm every vertex of the network should have the message.

On every round every vertex that has the message choice the neighbour randomly and sends it the message.

Assumptions: only $f$ failures might happen on the edges between the vertices.
$T = O(\log n)$ - time complexity and the entire network will know the message with high probability, when $f<n/3$, where n - number of vertices.

I will appreciate for link or reference to the paper.


texts: How to efficiently organize based on rule?

texts:
I am searching for an optimized way of doing the have the following scenario. With two classes: Wrapper and Child. My goal is to organize the child objects inside the Wrapper class based on some rules.

Scenario

class Wrapper {
    int id;
    List<Child> children;
}

class Child {
    int id;
    int score;
}

Child mainChild;

There are N objects of type Wrapper with also M children inside each.
Each Wrapper has an id used for the sorting.
In one of the Wrapper objects there's one child which is equal to the mainChild.
All children in all Wrappers have a score which says if a child (except child which is equal to the main child) belongs together with the main child. (They should be in the same wrapper).
A child is only allowed to go to an existing wrapper if it is above the score (which means they belong together. If it is bellow, it should either stay in the wrapper or go to a new one (while trying to maintain the rules bellow)
New wrappers are allowed to be created.

The goal is to have the main child in the same Wrapper with all the children (from any Wrapper) that have a score above X (let's say 2). And all bellow keep separated or separate from main child.

Rules

The two rules of the sorting are: the wrappers with lower ids should be preferred to survive instead of creating new wrappers. Reduce to the minimum the amount of moves of children between wrappers. The survivorship of the wrappers with lower ids have priority over quantity of moves.

Examples

For easier illustration here is a scenario:

  Example 1: in this case the optimal arrangement maintains wrapper 1 and 2 while doing the minimum amount of moves.

  Example 2: in this example it would be possible to move main child and children 4 and 5 to a new wrapper, but this would go against the minimum amount of moves rule. So instead we move main to wrapper 2 and child 3 to a new wrapper.

  Example 3: the minimum amount of moves would be to move main child and child 1 to wrapper 2, but this would go against the rule that the wrapper with lower ids should survive. Which has priority over amount of moves.


texts: Randomized and Deterministic Communication Complexity of a function

texts:
I have a problem I'm trying to answer for my homework. The question is:

Let $p$ be a prime number and let $GF(p)$ denote the finite field of size $p$. Suppose that A has input $x∈GF(p)$ encoded with $⌈log2p⌉$ bits and B has input $y∈GF(p)$ encoded with $⌈log2p⌉$ bits. Let $f:GF(p)×GF(p)→\{0,1\}$ be the function defined as
$$
f(x,y)=
\begin{cases}
0& \text{if}& x+y+xy=0\\
1& \text{if}& x+y+xy≠0
\end{cases}
$$
for all $x,y∈GF(p)$. Show that the randomized communication complexity of $f$ is $O(log\text{ } log\text{ } p)$ bits. Can you prove a lower bound on the deterministic communication complexity of $f$?

I've been thinking about using a random element $r∈GF(p)$ and make A calculate $f$ using $x$ and $r$ and sending the answer $r$ to B, but this doesn't seem to work as there are no general trend using such an protocol. For example that when A and B get the same answer, the function is $0$ or if they get different answers, the function is $1$.

Anyone have any idea how this protocol can look like? For example what kind of random input should be used?


texts: Is this problem hard? Finding all the subsets of size k from a sequence of n numbers

texts:
I want to know the hardness of finding all subsets of size k from a sequence of n numbers. There is an algorithm based on recursion: Print all possible combinations of r elements in a given array of size n.

However, I am not sure whether this can be done in polynomial time or not.


texts: How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$

texts:
Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove :

  If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$.

The previous similar theorem was

  If $\textsf{NP} \subseteq \textsf{P/poly}$ then $\textsf{PH}=\Sigma_2^p$.

The second theorem was easy to prove  as $\textsf{NP}=\Sigma_1^p$. But $\textsf{EXP}$ does not have such characteristic. How do I prove the first theorem. Any hints?


texts:
This is very unclear to me. I understand what the left quotient is, however, can someone explain this:

A={0,101}
B=01,10,001}

then how is A\B={1,01}

I mean where are these strings extracted from? I dont see them in A. How can I appeand 01 to anything is B to get something in B?


texts: Upper bound on $k$-sized frequent subsets

texts:
In the market-basket analysis problem, suppose the set of items $I$ has size $10^6$, the number of transactions $T$ is $10^9$, and each transaction $t \in T$ contains at most $10$ distinct items. Compute upper bounds for $F_1$ and $F_2$, the number of frequent itemsets of size $1$ and $2$, respectively, for a support value of $0.1\%$.

Since support is 0.1%, each item has to be in at least $10^6$ many transactions to be frequent.
There are $10^9$ transactions so there can be at most $10^3$ many size 1 frequent subsets.
Now $\text{CANDIDATE-GEN}(F_0)$ can produce up to $|F_0|^2$ many 2-sized subsets. Now I am confused how to make this bound even tighter.
In general, if I wish to find $k$-sized frequent subsets, do I have to find all $1,2,\ldots,k-1$-sized subsets, or is there a direct way?


texts: Pushdown automaton for complement of { ww | ... }

texts:
I want to be able to describe the idea behind the pushdown automaton (no tables or diagrams).

So, I already know that $L = \{ ww \mid w \text{ in } (0,1)^*\}$ is not context free. Since CFL are not closed under complement its complement $L'$ is a CFL.
I also read somewhere that any odd word is part of $L'$ (what about even length words?). So a pushdown automaton description could be: read one letter and put into stack, then read next letter and remove previous letter from stack. Do this until the end. If one letter is left in the stack at the end then word is odd length thus accept, else reject?


texts: O(n) Palindromic Substring: Why is O(n^2) needed here?

texts:
I have been doing dynamic programming problems, and I came across a palindromic substring question.  I answered it quickly, and found an $O(n)$ dynamic programming solution, but when I check the actual solution, I find that I should be getting an $O(n^2)$ result.

Can someone explain where I am going wrong/how this is not correct?

The problem reads: given string $x_1,x_2,\ldots,x_n$, find the longest palindromic substring.

I write:

$$
T(i) = \text{max length palindromic substring ending at position }i\text{ in string }X
$$

Then I write down the following subproblem (where $j$ is intended to be the letter right before the beginning of the palindrome ending at position $i$):

$$
\begin{align}
\text{IF  }x_i = x_j, \text{ where } &j = i - T(i-1)-1:\\
T(i) &= T(i - 1) + 2;\\
\text{ELSE IF} x_i = x_{i-1} \\
T(i) &= 2;\\
\text{ELSE } T(i) &=1;
\end{align}
$$

As far as I can tell, this is correct.  In order to recover the palindrome, I record it in linked lists or whatever, and calculate the argmax of $T$.

Where am I going wrong?


texts: Data + data schema needs dependent types to be type-checked statically?

texts:
I will set this question in a very practical way. Let's say we have a web-form data received as JSON at the backend together with the schema (for instance, some version of JSON schema), something like: {"data": {...}, "schema": {...}}. An important thing is, that backend can validate the data according to the type definition, given in the schema.
Is my intuition right, that we can't really have static type checking in many widely used statically typed programming languages for the data+schema structure, because in a sense data are given with their type definition representation?
Of course, we can have some approximate type checking, for example, that schema has valid structure and JSON type is valid, but we can't really statically type-check the data according to the schema.
Is the above understanding correct? And if it's correct, would it be also correct to say, that we need a static type-system with dependent types to be able to fully type-check the form data? Or are there other (less powerful than dependent types), which can make it possible the described type-check?
Please, note, that web form and JSON and it's schema is just an example. It can be XML+schema or any other equally powerful data format, so this question is actually very general. (If there is some good scientific term for defining types in the runtime data as opposed to code, please let me know.)


texts: Proof for This Greedy Strategy for Equalizing An Array

texts:
Recently the following problem was posed in a private coding competition at my workplace:

  An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

In discussion forums it was suggested to repeatedly find the difference of the smallest and largest elements and then greedily increment all but the largest element by this amount. An implementation using this strategy passed all test cases. However I'm unable to see how this strategy will indeed result in the smallest number of steps.


texts: A pretrained model for mathematical equations characters detection

texts: I am working on a project to convert equations to LaTeX code. After segmenting out the characters, I got stuck on the detection part and was looking for some pre-trained model that could detect characters of the equation for later conversion to LaTeX. Is there any such pre-trained model available on the internet that could be used in Python to identify characters. If not then can somebody share some source to find a dataset to train such kind of model in Keras? I was able to find one on GitHub but It doesn't detect symbols accurately.


texts: return a key of a node with maximum value within a range of keys in B+ tree

texts:
I've been asked a question about B+ Tree.

The question is: Suppose we have object of the following type:

class Obj {
private:
    int value;
    int key;
public:
    Obj(int uniq_key , int value)
}

and I am creating a Generic B+ tree which will sort objects in it leafs nodes by keys and not by values. (The keys are unique values aren't)
Now I want to return the key of a node containes Maximum value within a range of keys.
For Example:

If I have the following objects inserted in my B+ tree:

Obj a(1,10) , Obj(2,5) , Obj(3,0)

Then by calling this method I will get a return value : 1

I thought of having an extra rank tree with the same data stored in it and a pointer from a leaf node in the B+ tree to it's equivalent node in the rank tree but I think that there is a solution involves adding extra data in the nodes in the B+ tree which can solve this issue.

p.s.   I don't know if this post is duplicated - I couldn't find anything else answering this kind of question.

Thank you,
Michael


texts: Why does CLRS refer to the disk parts as pages rather than blocks?

texts:
I recently decided to review the B-tree chapter (chapter 18, p 486 in 3ed) in Introduction Algorithms, and found that they call pages what I always referred to as blocks or clusters:

In order to amortize the time spent waiting for mechanical movements,
disks access not just one item but several at a time. Information is
divided into a number of equal-sized pages of bits that appear
consecutively within tracks, and each disk read or write is of one or
more entire pages. For a typical disk, a page might be $2^{11}$ to $2^{14}$
bytes in length. Once the read/write head is positioned correctly and
the disk has rotated to the beginning of the desired page, reading or
writing a magnetic disk is entirely electronic (aside from the
rotation of the disk), and the disk can quickly read or write large
amounts of data.

I always thought that pages are related to the virtual memory, although including swapping with the disk access. When the talk goes into the discussion of the filesystems in general, then I thought the information is divided into blocks rather than pages. Is he talking about virtual memory here? If I restate the whole paragraph in terms of blocks, would it be still correct, except for the provided sizes of the blocks?


texts: Regular Expression to Context-Free Grammar

texts: Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?


texts: What is the connection between data structures and data types?

texts:
I have read some books and wikipedia, which seem to give not completely consistent definitions and notations. I try to understand the concepts, regardless of what they are called. Here are what I have figured (please correct me) and would like to ask :

a (abstract) data type is a set $D$ of values, together with some
operations on it (each $n$-ary operation is a mapping $D^n \to D$).
E.g. The set of all the integers with arithmetic operations on it forms a data type.
A data structure seems to be a data type. Or are they the same
concept? What is the formal definition of a data structure?
I have some difficulty in understanding if a "container-like construct" is a data structure or data type, or the set of all of them is. What I mean by a "container-like construct", is some set of values, but with some relation(s) on the set, e.g. a queue, a graph, a stack, an array, a map, .....

E.g., a queue is a set of values in it, with some ordering on the values according to which value was added earlier than which. Is a queue with a fixed size and fixed elements, as a set of values in it,  a data type or a data structure?  Or do all the queues form a data
type or a data structure? Are adding and removing elements from a
queue, which obviously create new queues, viewed as operations on the set of all the queues?

Similarly, a graph is a set of vertices and has relation between the vertices being the edges. Is a graph with fixed vertices and edges a data type or a
data structure, or is the set of all the graphs a data type or a
data structure? Are transformations from a graph to another different graph  considered to be operations on the set of all the graphs? Is searching for a vertex in a graph considered to be an operation on that single graph?


texts: Finding continuous line consisted of points surrounding points of different color

texts:
I have a problem with creating an algorithm that would find continuous line consised of points of one color (say blue) that surrounds points of different color (say red).

This problem occurs in "Dots" game.

At first I tought that simple BFS would suffice (I can treat two dimensional table of ints that represents map of points as an undirected mesh graph), but unfortunately there's too many edge cases to take care of, like those showed here.

How can I approach this?
Thank you for help.


texts:
I had a question for my paper last week and i tried solving but failed.

Given n people, any two are either friends or enemies, and friendship and enmity are mutual. I want to distribute hats to them, in such a way that any 2 friends possess a hat of the same color but no two enemies possess a hat of the same color. Each person can receive multiple hats. What is the minimum number of colors required to always guarantee that I can do this ?

Topic was about intro to graph theory.
It will be very helpful if anyone can provide a solution for this.
Thank you :)


texts: ground terms in logic and $\lambda$-calculus?

texts:
What are the differences of ground terms in first-order logic and higher-order logic?

I found on the Wikipedia: "In mathematical logic, a ground term of a formal system is a term that does not contain any free variables."

That mentioned "free variable" is the same thing with free variables of $\lambda$-terms?

I know the closed terms and open terms $\lambda$-calculus. How can we connect closed terms of $\lambda$-calculus with ground terms of logic?

I am bit confused between these concepts, could anyone explain?


texts: How can recursion tree split a problem into smaller pieces that do not add up?

texts:
If I have a recurrence equation:
$$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$
It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at the leaves is 1 or less. The first part that does not make sense to me is how can you split a problem of size n into 3 problems of size n/4. To me it seems that there are now 3 problems of size n/4, but where is the remaining 1/4 of n? Who is solving that?
Also, the number of leaves is
$$n^{\big(\frac{loga}{logb}\big)}$$
Assuming n=1000, it can be calculated that there are 235 leaves. So 235 problems of size 1 are solved, how are the rest of 765 solved?
I have a feeling that I have misunderstood some principle, but I do not know what exactly.


texts: NP-complete language as a result of xoring two PTIME languages

texts:
We define xor operation on languages $L,M\subseteq \{0,1\}^*$:
  $$L\oplus M = \{u\oplus v :|u|=|v|, u\in L, v\in M\}$$   $\oplus$ is
  defined as xor on postions, for example:  $001\oplus 100=101$   Show
  that there exist  languages $L,M\in PTIME$ such that $L\oplus M\in
 NP complete$

It is hard to me. I have been thinking a lot about it. My intuition is:

Write the problem as equations system and reduce 3-SAT to it. But, I am not sure if it is ok and, if yes, how to solve it.


texts: Efficiently populate a look-up table for a function over a range of arguments

texts:
I am minimizing a scalar function $f$ which takes a $n$-dimensional vector input and outputs a scalar value.  I have code that given an input $x$ will compute the output of $f(x)$ (a scalar), its Jacobian (a $n$-dim vector), and its Hessian (a $n \times n$ matrix).  In my application, $n \approx 10$.  Unfortunately, evaluating the function $f$ takes too long for many points. I'd like to build a surrogate model $\hat{f}$ instead that I can use for minimization.

I've been thinking of a scheme based on precomputing $f$ at a regularly spaced grid of inputs, and then $\hat{f}(x)$ would perform linear interpolation based on the grid points nearest to $x$.  However, this requires regular sampling and might be inaccurate due to the use of linear interpolation.

I'm hoping there is a more intelligent method for this? Perhaps with automatic refinement of inputs sampled or a more sophisticated interpolation scheme?

Technically, the output contains the Jacobian and Hessian but I need those with decent fidelity, so I would either need a higher order representation of the scalar function (with added sampling frequency) or I need to approximate the Jacobian and Hessian too.


texts:
CNF H = {<ø>|ø is a satisfiable cnf-formula where each clause contains any number of
literals, but at most one negated literal}

I want to show that CNF H is in P, but I'm having some trouble finding an algorithm. My first idea was to check for each clause c in P if that clause contained at most one negated literal. If no clause contains more than one negated literal, accept, if not, reject.

The problem with this idea is if there is a clause with only one literal, and this literal is negated. Than the clause would be false, and therefore ø is false. How do I write an algorithm that also covers this case?


texts: Testing two distributions, both accept null hypothesis

texts:
I have a sample that is collected to verify the accuracy of a new random number generator.
Applying the goodness of fit test to check if this sample comes from the Standard Normal Distribution and Uniform Distribution, I found out that both of these accept null hypothesis although they are contradicting to each other.
Is it theoretically possible? Why?


texts: Deterministic approximation algorithm for MAX k-CUT

texts:
I've been trying to solve this problem for two days. This problem is from Vazirani's book Approximation Algorithms (pg 23).

  Given an undirected graph $G = (V,E)$ with nonnegative edge costs, and an integer $k$, find a partition of $V$ into sets $S_1,\dots, S_k$ so that the total cost of edges running between these sets is maximized.
  Give a greedy algorithm for this problem that achieves a factor of $(1−\frac{1}{k})$. Is the analysis of your algorithm tight?

I am trying to solve it using local search as following. Initially I create $k$ empty partitions $V_1, \dots, V_k$, then divide vertices arbitrarily into $k$ parts and put each part into the partitions, so that initially each partition $V_i$ has $\frac{|V|}{k}$ vertices.

My local move runs over each partition $V_i$ and for each vertex $v \in V_i$ puts $v$ into another partition and then checks the sum of the weights of crossing edges between each partition $V_i$ and $V_j$. If this move improves (increases) the sum of the weights of the cut then we continue the local search, otherwise we reached the local maximum.

But I am not able to prove that this guarantees $OPT(1-\frac{1}{k})$.
I suspect that my approach is not correct which does not result in $(1-\frac{1}{k})$-approximation. So far I could obtain the following inequality
$$opt \geq (k-1)\sum{w(e)}, \text{  where } e \text{ are all noncrossing edges and } opt \text{ is the local maximum}$$

Could someone give me a right direction, or help prove that this approach indeed yields $(1-\frac{1}{k})$-approximation?


texts: Finding C-convex holes in a planar point set

texts:
I am looking for an efficient algorithm to find convex holes in a given point set.
The problem is

  Given $n$ points in the Euclidan plane, and a constant $c$, determine how many empty convex polygons $P_1, \dots, P_k$ there are, such that for each $i = 1,\dots,k$; $P_i$ has exactly $c$ vertices from the given point set.

Although there are some papers that considers finding possibly non convex holes [1] [2] [3], and some others that show existence of such holes [4] [5], I could not find a paper that describes an algorithm to find them.

Obviously, a naive algorithm that runs in $\mathcal{O}(n^c)$ comes to mind, where each $c$-subset is traversed. However, I would like to know whether there exists a more efficient algorithm.


texts: Is there an algorithm that can find a solution that solves the most number of equations in a linear system of equations?

texts:
My apologies if this question makes no sense. I am trying to find an algorithm that can solve a linear system of equations. Unlike most problems like this, this algorithm does not need to find a solution set that solves the entire set of equations. It only needs to solve the MOST number of these equations. For example, if a given linear system has $n$ equations, then the solution set returned by the algorithm should "fit" the most possible number of equations in the system.

Example: if there are $N$ linear equations in a system $S$ of linear equations, then the algorithm should return a solution set that solves $m$ linear equations in $S$, where $m\le N$.

Based on what I have researched, none of the algorithms I know of will do this. Hopefully I am just missing something and I can get pointed into the right direction. Thanks.

Also, I forgot to add in that the given system of equations will have 10,000-1,000,000 variables, with x being Sparse. Is there a mod 2 algorithm or something similar to it that works on very large matricies?


texts: Can there be an oracle that solves its own halting problem?

texts:
Since the same contradiction from the Turing machine is still there, we allow the oracle not always return an exact value, and say it solves the halting problem if the probability of returning "HALT" equals to the one that the program halt.

If not possible, can it solve a weaker halting problem?


texts: Does this algorithm on a circular linked list ever terminate?

texts:
Suppose we have a circular linked list that has nodes $1$ to $n$. L is a pointer that points to node 1 (with label $1$). Note i has a link to i+1 and we have a link from node n to node 1 because the list is circular.

Now we have following pesudo-code:

Int SO(LIST *L) {

  While ( L->Next != L ) {
    L->Next = L->Next->Next;
    L = L->Next;
  }

  return L->Data;
}

The question is: what is the output for $n=729$ and $n=2200$ what is the output of the above code.

My solution: I check the pesudo-code. My idea is this code has a problem and  L and L->Next never become equal so an infinite loop occurs. Is this correct?


texts: Message receipt verification in a cluster

texts:
At my current project I had a network problem come up for which I could not find a solution. In a peer-to-peer network I needed to send an action to all peers, and each peer was to act on it only if it could verify that all other peers would also act on it.

That is, given a network of peers $P = { P_1, ..., P_n }$. We wish to send, from some source peer $P_s$ a message to all other peers. This message contains an action which must be performed. The peer should perform this action if and only if every other peer will perform the action. That is, it performs the action if it can verify that all other peers will also have receipt of the action and can perform the same verification.

The problem is subject to these conditions:

There is no implicit message delivery guarantee: if $P_x$ sends a message to $P_y$ there is no way for $P_x$ to know if $P_y$ gets the message. (Of course $P_y$ can send a receipt, but that receipt is subject to the same constraint)
Additional messages with any payload may be created.
There is no total ordering on the messages received by peers. Messages can arrive in a different time-order than which they were sent. This time-order may be unique per peer. Two messages sent in order from $P_x$ to $P_y$ are very unlikely to arrive out of order.
Messages can arrive at any point in the future (so not only are they not ordered, they can be indefintely delayed). A message cannot inherently be detected as lost. Most messages will be delivered quickly, or truly lost.
Each peer has a synchronized clock. It is accurate enough in the domain of scheduling an action and to approximately measure transmission delays. It is however not accurate enough to establish a total ordering on messages using timestamps.

I was not able to find a solution. I'm interested in a guarantee and not simply a high probability of being correct (which can be done simply be repeatedly sending confirmations from peer to peer and rejections upon any likely loss.) My stumbling block is the inability to verify that any particular message actually arrived. So even if $P_x$ determines there is an erorr, there is no guaranteed way to tell the other peers about it.

A negative confirmation is also acceptable. I have a suspicion that a guarantee cannot actually be achieved, only an arbitrarily high probability.


texts: How to write regular expression excluding certain pattern aba from albhabet set {a,b}?

texts:
Often we are asked to write regular expression for the set of words that contain a certain string pattern, like $aba$. But what about the opposite?
Is there any generic way to write a regular expression for the set of all words that do not contain a certain pattern?


texts:
Consider the function
$$
f(n) = 2n^2 |\sin(\pi \cdot n/2)|.
$$
Which of the following classes does $f(n)$ belong to?
$$ O(n^2), \Omega(n^2), \Theta(n^2), \omega(n^2), o(n^2). $$

I'm working in this and so far I have been trying to use different methods but always get to a dead end.


texts: what is a disagreement set in nominal unification?

texts:
In unification, for example set $s=\{ f(a,Y),f(X,d) \}$ has a disagreement set $\{ (a,X),(Y,d) \}$, since these two elements does not match on their fields. simply speaking that is a set disagreement set and in unification finds terms for $X$ and $Y$ to make disagreement disappear, so unifies.

I got a question about nominal unification.

source: nominal unification

Definition 2.5. The disagreement set of two  permutations $\pi$ and ${\pi}^{'}$ is the set of atoms $ds(\pi,\pi^{'})=\{a|\pi.a  \neq \pi^{'}.a \}.$

It gives an example. here it is

$\{a \#X,c \#X\} \vdash (a\,c)(a\,b).X \approx (b\,c).X$

saying the disagreement of the permutations $(a \,c)(a\,b)$ and $(b\,c)$ is $\{a,c\}$.

I don't get how that disagreement set is obtained.

can anyone explain to me?

Thanks in advance


texts: Why are there two different `until` ($\cup$) semantics in Timed Computation Tree Logic?

texts:
Background:
In the book of Principles of Model Checking (Christel Baier and Joost-Peter Katoen, MIT Press, 2007), Section 9.2, page 701, the semantics of the until modality is defined over some time-divergent path $\pi \in s_0 \Rightarrow^{d_0} s_1 \Rightarrow^{d_1} \cdots \Rightarrow^{d_{i-1}} s_i \Rightarrow^{d_i} \cdots$ as follows:

(We can skip the formal definition at your first reading.)
$\pi \models \Phi \cup^{J} \Psi \iff$
$\exists i \ge 0. s_i + d \models \Psi \textrm{ for some } d \in [0,d_i] \textrm{ with } \sum_{k=0}^{i-1}d_k + d \in J \textrm{ and }$
$\forall j \le i. s_j + d' \models \Phi \lor \Psi \textrm{ for any } d' \in [0,d_j] \textrm{ with } \sum_{k=0}^{j-1} d_k + d' \le \sum_{k=0}^{i-1} d_k + d$.

  Intuitively, time-divergent path $\pi \in s_0 \Rightarrow^{d_0} s_1 \Rightarrow^{d_1} \cdots \Rightarrow^{d_{i-1}} s_i \Rightarrow^{d_i} \cdots$ satisfies $\Phi \cup^{J} \Psi$ whenever at some time point in $J$, a state is reached satisfying $\Psi$ and at all previous time instants $\Phi \lor \Psi$ holds.

However, in the book of Model Checking by E.M. Clarke (Section 16.3, Page 256), the semantics of the until modality is given as follows:

  $s \models E[\Phi \cup_{[a,b]} \Psi]$ if and only if there exists a path $\pi = s_0 s_1 s_2 \cdots$ starting at $s = s_0$ and some $i$ such that $a \le i \le b$ and $s_i \models \Psi$ and for all $j < i, s_j \models \Phi$.

As indicated, the second definition is stricter than the first one in that it does not allow the case of $\lnot \Phi \land \Psi$ before reaching a state satisfying $\Psi$.

Questions:

Why are there two different until ($\cup$) semantics in Timed Computation Tree Logic (TCTL)?
Which one is more official?


texts:
What will be the context-free grammar of $B= A_1.A_2 $
when $A_1 = \{0^n1^n|n\geq 0\}$
$A_2 = \{1^n0^n|n \geq 0\}$
Also verify using a string.
if  the Grammar for
$A_1$: $S_1 \rightarrow 0S_11 | \varepsilon$
$A_2$: $S_2 \rightarrow 1S_20 | \varepsilon$
I am stuck with the value of $S \rightarrow$ ?


texts: Mutex implementation on top of a minimalistic preemptive scheduler

texts:
In this question, I'm implementing some synchronization primitives in the standard library of an operating system. Specifically, I want to implement mutexes and condition variables. This is on top of a microkernel with a preemptive scheduler (a thread has no way to prevent the scheduler from preempting it). I'm exploring how minimalistic the system can get while remaining powerful and efficient enough for my needs.

From the hardware, I get a basic atomic primitive such as compare-and-swap or load-link/store-conditional. You can assume that the word size for these instructions is large enough to store a pointer or a thread identifier. Furthermore all threads see the same memory.

From the kernel, I get three primitives:

sleep(): suspend the current thread until a thread has called wake(t) where t is the current thread. If the current thread's wake-up flag is already set then sleep() returns immediately. Returning from sleep clears the wake-up flag.
wake(t): wake thread t if it's asleep. If t isn't asleep then its wake-up flag is set and t's next call to sleep will return immediately. Note that non-participating threads may call wake — as far as the locking mechanism is concerned, it's thus possible for a thread's wake flag to become set non-deterministically.
yield(): give all other threads that are not asleep a chance to run.

How can I implement a mutex and condition variable API on top of these primitives?

lock(m): if m is taken, sleep until it is free. Mark m as taken.
unlock(m): mark m as free. If some other thread is waiting for it to become free, that thread is woken up.
wait(c, m): wait for the event c to happen. If c has already happened, don't block. When wait returns, it atomically locks the mutex m. When a thread notices c, the event is cleared.
signal(c): signal an event on the condition c. This wakes up one thread that's waiting on c.

A good solution must avoid starvation: if a thread tries to lock a mutex, it must eventually get it provided that every thread that acquires it releases it eventually. Preferably, threads should obtain the lock on a first-come, first-served basis. (To give a counter-example, a last-come, first-served system would be bad because one thread could hog the mutex if it keeps acquiring it immediately after releasing it.)

A solution is better if it avoids scheduling a thread that ends up doing no useful work. For example, systematically waking up all threads when something happens is not good enough.

What is an efficient algorithm for implementing mutexes and synchronization variables? (Note that I am not asking how to implement a spinlock! A spinlock is probably involved, but I expect answers to this question to explain how to set up wait queues and not just handwave that part.) Efficiency may vary based on the amount of contention; the kind of systems I work on tend to have low contention in practice (but must not overly drain the battery when there is contention).

(I expect answers to explain the algorithm in sufficient detail that a programmer could understand it, but a reference would be appreciated as well.)


texts:
I'm working on a project compiling various versions of the Bible into a dataset. For the most part versions separate verses discreetly. In some versions, however, verses are combined. Instead of verse 16, the marker will say 16-18. I wonder if, given I have a lot of other versions that separate them discretely, I can train an NLP model to separate those combined verses into discrete verses. I'm fairly new at deep learning, having done a few toy projects. I wonder how to think about this problem? What kind of problem is it? I think it might be similar to auto-punctuation problems and it seems the options there are seq2seq and classifier. This makes more sense to me as a classification problem, but maybe my inexperience is what drives me that direction. Can people suggest ways to think about this problem and resources I might use?
In answer to questions in the comment, I am dealing only with text, not images. An example might be like this:
Genesis 2, New Revised Standard Version:

5 when no plant of the field was yet in the earth and no herb of the field had yet sprung up—for the Lord God had not caused it to rain upon the earth, and there was no one to till the ground; 6 but a stream would rise from the earth, and water the whole face of the ground— 7 then the Lord God formed man from the dust of the ground, and breathed into his nostrils the breath of life; and the man became a living being.

Genesis 2, The message version:

5-7 At the time God made Earth and Heaven, before any grasses or shrubs had sprouted from the ground—God hadn’t yet sent rain on Earth, nor was there anyone around to work the ground (the whole Earth was watered by underground springs)—God formed Man out of dirt from the ground and blew into his nostrils the breath of life. The Man came alive—a living soul!

The goal then would be to divide the message version into discrete verses in the way that the NRSV is. Certainly, a part of the guide would be that a verse always ends in some kind of punctuation, though while necessary it is not sufficient to assign a distinct verse.


texts: An efficient method to compute a minimum set of sets that form the union of these sets?

texts:
Let's say we have a set of sets:

$$\mathfrak S = \lbrace S_1, S_2, ... , S_n\rbrace$$

And the union of the all the sets in this set:

$$\mathfrak U = \bigcup\limits_{i=1}^{n} S_{i}$$

And so there is at least one minimum set of sets that is identical to this union:

$$(\mathfrak M \subseteq  \mathfrak S) = \mathfrak U$$

What is the most efficient known method of computing $\mathfrak M$ ?


texts:
In popular literature, complexities are usually used in a very imprecise manner, often to describe the runtime performance of an algorithm and denoted with "$O$". My question is about these Landau symbols.

Take Quicksort for example, which is often cited as being $O(n^2)$ in the worst case, but $O(n \log(n))$ in the best one. To my understanding though, it is also $O(n^2)$ in the best case, since $n\log(n)$ is asymptotically bounded from above by $n^2$.

My question now is: is there a notion of a "least upper bound" complexity when using Landau symbols? When I call an algorithm $O(n^2)$, does this mean that $n^2$ is the slowest growing function that still bounds the runtime from above, or is this just a moral imperative?

(Similar issues of course apply to other Landau symbols, such as lower bounds.)


texts: Simulating DFA operations on non-regular languages with finite final state set

texts:
A language I'm investigating is not regular since the minimal DFA for the language grows depending on input string size. However, while the number of non-final states increases, the final states are the same small strictly finite core which include the initial state.

Another question looks superficially similar, hinting that what I'm looking for might be an interpretation of this language as a generalization of a prefix-code in order to ignore the infinite non-final states.

Are there methods to treat this 'pseudo-regular' language as regular (or any other language class with efficient algorithms) for purposes of intersection and path finding from the small final state set back to the inital state, thus sidestepping the issue that the complete DFA is not finite in size?


texts: Given a set of n balls with different weights and a scale that compares two balls

texts:
Write an algorithm to determine if there's a set of > n/4 balls of the same weight. The algorithm cannot exceed O(n log n) time.

One way I was thinking about this was using divide and conquer. My original algorithm was as follows:

findSet(S) #S is the set of n balls
    If |S| = 1, return the lone ball
    If |S| = 2 or 3, return any ball
    Divide S up into 4 subsets of equal length, run findSet on each
    If no run returns a ball, return nothing
    If a single test returns a ball, weigh the ball against all other balls
      in S. If we generate a set of balls > n/4, return the ball

    If >=2 tests return balls, let B denote the set of these balls.
    For each ball b in B, weight b against all elements in B.
      If we generate a set of balls > n/4, return the corresponding b.

I think the algorithm is O(n) because the recurrence would be T(n) = 4T(n/4) + n which can be reduced to O(n log4 n). However, I'm pretty sure this algorithm is incorrect. Primarily, I'm not sure if the base cases will ensure we choose a ball b that is > n/4 in the original set.


texts: What is the time complexity of the below algorithm?

texts:
Below I have two algorithms for finding the maximum 2 numbers from an array of numbers of size>=2. n=Size of the array

Algorithm 1:-
1. Loop through the array, find the index of max number. (n comparisons)
2. Swap the last position number with the number present at the index of the max number.
3. Loop through the array excluding the last element, and find the max number. (n-1 comparisons)
4. Swap the last but one position number with the index of 2nd largest number.
5. The max two numbers are now in pos n and n-1.
So the time complexity of the above program is always (n + n-1) ~ 2n.

2nd Algorithm (In python3), a=array

def max_pairwise(a):
    n = len(a)
    max1 = 0
    max2 = 0
    for i in range(0, n):
        if a[i] > max1:
            max2 = max1
            max1 = a[i]
        elif a[i] > max2:
            max2 = a[i]
    return max1, max2

I know that 2nd algorithm is better than the 1st algorithm as inside of the loop we sometimes make 1 comparison(when the array element is greater than the max1 number) and sometimes 2 comparisons(when the array element is less than the max1 number).
So the time complexity has to be between n to 2n comparisons, but how to do I calculate the exact time complexity of the 2nd algorithm?


texts: tool to insert nodes in a tree with queries

texts:
I have a tree where each node has a type. Multiple nodes can have the same type.
I want to insert new nodes in this tree at some specific positions specified by queries,
such as :

Insert the node next to the lowest and left most child of type 1
Insert the node as child of root after the last child of root of type 2
etc..

Is there an existing query-like language that does that ?
I found this (used for biology), and this, which are usefull for selecting
nodes, not inserting, and don't seem to be used a lot.


texts: Algorithm to find what points are the nearest to other points

texts:
I have two lists:

Location list, it contains point of interest
People list, it contains coordinates of every person. One single person could be in the list multiple times, depending from the log time. Someone who is out for a walk will result in two different locations in two different hours.

I would find out what people where near every point of interest.

I could approach the problem with brute force: external loop check for every point of interest the entire people list finding out who was there.

I would obviously avoid brute force. I thought about Nearest Neighbour, for sure multiple people will be in the same spot so I could look for a point of interest in the cluster.

Solutions?


texts: Does it make sense to say Big Theta of 1? Or should we just use Big O?

texts:
Does saying $f(x) = \Theta(1)$ provide any extra information over saying $f(x) = O(1)$?

Intuitively, nothing grows more slowly than a constant, so there should be no extra information in specifying Big Theta over Big O in this case.


texts:
Is incremental compilation ever done based on the AST? That is, the compiler would just regenerate code for the parts of the AST that have changed.

I know that many compilers do incremental compilation on a file-basis, but I don't know about on an AST-basis.


texts: Construction of the complement of universal Turing machine - where is the catch?

texts: This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?


texts: Fastest Algorithm for finding All Pairs Shortest Paths on Sparse Non-Negative Graph

texts: As discussed here Johnson's Algorithm can be used to solve the APSP-Problem in $O(V^2\log V + VE)$ in stead of $O(V^3)$ for Floyd-Warshall. However, Johnsons Algorithm does quite a bit of work for the case that some weights are negative. Is there a faster way to compute this given that all weights are positive?


texts: Enumerating all the walks in a graph between a start vertex and a terminal vertex?

texts: I was reading something about the concept of walks in a graph b/w a start vertex and a terminating vertex in a graph and then suddenly a problem struck me, is there any algorithm or a method that can be used to enumerate all the distinct walks from a start vertex to a terminal vertex in a graph, if so can you all point me to some relevant links to study this problem and what are some applications of solving this problem?


texts: Using a neural network to identify patterns in strings

texts:
I am currently doing a research on data sensing and I came across the following concept. The requirement for me is to identify different data types using neural networks. Please note that I don't want to use regular expressions for this since it is suggested by most when I explain what i want to do. The neural network should learn to identify the string data structure instead of running rules against it.

The requirement in examples is:

If input string is "123.456" => output is "floating point number"
If input string is "test@example.com" => output is "email"

My first approach was to train a multi-layer neural network using different features pre-engineered as the input

ex: 123.456
I input the no. of numeric characters and no. of periods to the network

So far I was able to obtain some accuracy for 2 data types (around 60%). The issue with this approach is that it disregard the order of characters when I provide the input as such.
ex: it disregard that 123 comes before the first '.' and 456 comes after that

So I now thinks of using convolution networks for the process. As per my understanding (please correct me if wrong), convolution networks are primarily tasked with recognizing image patterns given that they were built using the brain anatomy. Hence the best way of input for the network is an image. Thus, I thought of converting the text string to an image and feed it to a convolution network so that I might identify it with considerable context. (like where comes which pattern)

Before digging into this path I want to know if this is possible path or not. Please let me know of your ideas.

Please note that my knowledge on NN are limited and I haven't done enough research on the path.

Thank You


texts: In a distributed system is it possible for both parties to simultaneously agree a message exchange was made?

texts:
Given that the two generals problema is unsolvable, which means that both parties involved cannot agree that both know something, i ask something simpler.  Is it possible for both parties to agree that a message Exchange occurred? In other words, is it possible for both parties to agree that a "conversation" occurred?

For instance, if A and B communicate with messages Mx

A -M1 -> B
A <-M2 - B
A -M3 -> B

At this point B knows that a message Exchange occurred, but can he be sure that A also knows so?

Thanks in advance


texts:
I'm working on an example which says that a string x is obtained from a string w by deleting symbols if it is possible
to remove zero or more symbols from w so that just the string x remains. For example, the
following strings can all be obtained from 0110 by deleting symbols:

λ, 0, 1, 00, 01, 10, 11, 010, 011, 110, and 0110.

Let Σ = {0, 1} and let A ⊆ Σ
∗ be an arbitrarily chosen regular language.

Define
B = {x ∈ Σ
∗
| there exists a string w ∈ A such that x is obtained from w by deleting symbols}.

In words, a string is in B if you can obtain that string by first choosing a string from A and
then deleting zero or more symbols from that chosen string. Prove that B is regular.

I'm not able to prove it. Any help would be appreciated.


texts: How to order the functions based on complexity $2^n$ vs $n^{\log n}$?

texts:
How to order the functions $2^n$ vs $n^{\log n}$ based on their complexity?

I found this question in a programming website (InterviewBit). But the answer given there, $n^{\log n}, 2^n$, does not seem convincing.

The graph of the two functions also indicates that $n^{\log n}$ is more complex than $2^n$.

I also tried substituting a couple of large value for $n$ like $10^{10}$ or $10^{10000}$. They all seem to indicate that $n^{\log n}$ is more complex than $2^n$.

Is $n^{\log n}$ greater than $2^n$?
Assuming 1 is true, how to prove it without using graphs?


texts: Operating System: About user thread and kernel thread?

texts:
Is that a "thread" consists of both "user thread" and "kernel thread" as two parts?

And when I create a "thread", is that I create a "user thread" and another "kernel thread" is created "in the background" by OS also?

I'm confused because of the second picture.

The book I'm reading is "Operating System Concepts, 9th ed., SILBERSCHATZ", and it's at page 169. Thanks a lot


texts: Prove the equivalence between a CFG and a Context free language

texts:
I have to prove that the language $L=\{a^ib^j:2i=3j+1\}$ and the CFG G with the following rewrite rules:

$S\rightarrow a^2Tb$

$T\rightarrow a^3Tb^2 |\epsilon$

are equivalent to each other.

I'm going to prove this by saying $L(G)\subseteq L$ and $L \subseteq L(G)$. I was able to prove the first one. I should be able to prove the second one with induction on the length on a word $w$. But how can I do that? The induction basis should start at length 3, because the smallest word $w \in L$ is $aab$. But the second word has a length of 8. This means the stepsize in the induction proof is 5. I've never done an inductive proof with a stepsize different from 1. How can I do something like this as it's not possible to state in the induction step that "We assume that the theorem holds for $|w|=n$, now we are going to proof that it holds for $|w|=n+5$"?

UPDATE:
I think I found a solution to my own question:

Inductionbasis: Suppose $|w|=3$. Then $w$ must be $aab$ because that's the only word of length 3 that satisfies the requirements for the language L. But $aab$ is also an element of $L(G)$. The basis is OK.

Induction hypothesis: Assume that the theorem holds for all words $w`$ with length $|w`|=3+5n$. We are now going to proof that the theorem also holds for all words $w$ with length $|w|=3+5(n+1)$.

$w$  must be of the form $\alpha a^3b^2 \beta$ to be an element of $L$. Now consider the word $z=\alpha \beta$ with length $|z|=3+5n$. Then, by induction, we know that $z \in L \implies z \in L(G)$. Because $z \in L(G)$ it must hold that $z$ is of the form $a^nb^m$ with $2n=3m+1$. If we add the 3 $a$'s and 2 $b$'s from $w$ to this equation, we find that $2(n+3)=3(m+2)+1$. The following applies to this equation:

$2(n+3)=3(m+2)+1$

$\iff 2n+6=3m+6+1$

$\iff 2n+6=3m+1+6$

$\iff 2n+6=2n+6$

Thus, $w$ also satisfies $L(G)$. QED

Is this proof correct?


texts: How to find a path that connects all the dots in the matrix?

texts:
I have a matrix that consists of 0, 1, 2.

0 - dot.
1 - block.
2 - start dot (initial position in the path).

I have to create a path from the start dot, that

connects all the dots in the matrix and
visits each dot ONE time
doesn't visit blocks

In other words, create a Hamiltonian path in a matrix.
A pic below exhaustively shows what I want.


texts:
I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int i I use instead 2i+1). Let's denote the box representation as $[[\cdot]]$, then I was able to make the following deductions. Consider x the number to be the shifted value and y the shift value (read the following to understand the whole process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]-1}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]]-1 \, \frac{[[y]]}{2}}\big] + 1$

Here we can use $\frac{[[x]]-1}{2}$ or $\frac{[[x]]}{2}$ because $[[x]]$ always ends with a one however in the last step we remove the division by two and for $[[x]]$ we have to keep $-1$ but not for $[[y]]$. Please note that this translation is meant for left shifts where the bit structure of $x$ is important, namely if we have $x_1 x_2 x_3 1$ the last bit will be actually used in contrast with the right shift case.

The following is the version for the right shift (again read what follows to understand the process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x-1]]}{2} \, \frac{[[y-1]]}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]] \, \frac{[[y]]}{2}}\big] + 1$

Here the point is that the last bit is no longer useful and can be ignored.

I wonder if me scheme is correct and efficient in the sense that it may exist other procedure that is more efficient than mine. I would appreaciate as well that you clarify the intuitive ideas I gave for my procedure (if it is correct) reelaborating my assertions with possibly more accurate ones. Also I would appreciate ideas that suggest how to mix this two implementations.


texts: proving an automaton language for the language over $\{a,b\}^{*}$ : $w\in L$ if $aa$ is not an infix of $w$ ($aa$ doesn't appear in $w$)

texts:
I built the next automaton:

I have problem to prove $L = L(q_0)\cup L(q_1)$, (when $L(q)$ denotes words $w$ such that $\hat{\delta}(q_0,w) = q$ at a given DFA) because semantically $L(q_0)$ is the language of words over $\{a,b\}^*$ which don't start with $a$, and $L(q_1)$ is the language of words which start with $a$  (by the way, one could also say $L(q_0)$ are the words which don't end in $a$ and $L(q_1)$ are the words which end with $a$).I failed to understand why  $L(q_0)\cup L(q_1) = L$.

My second question, Is it "valid" to prove that $L(q_2) = L^c$, generally speaking, does it valid to prove $\bigcup_{q\in F^c} L(q) = L^c$ in order to prove $L(A)= L$ ? (when $F$ is the set of finite states of an automaton A)


texts:
So propositional logic (PL) is efficiently (in P) decidable because I can convert formulas to an equisatisifiable CNF-formula, negate and convert (efficiently, by De Morgans laws) to DNF. I can then efficiently see if this formula is satisfiable. If it is satisfiable then my original formula was not a theorem. PL is however not super expressive.

On the other hand some more expressive logics like tarski's theory of real closed fields is decidable but in an absolutely absurd amount of time.

Somewhere in between is certain modal logics like GL and K that have PSPACE-complete decidability.

In the middle I know about practically efficiently decidable logics like those handled by SMT solvers. But these are not formally efficient decision procedures. No matter how good they become I can always find some pathological case.

Are the more expressive logics that are formally efficiently decidable? To put it in bullets are there any logics that have the following properties:

Decision procedure for membership in set of theorems is efficent
More expressive than PL (but not nearly as expressive as Tarski's logic)
Not just practical but formally efficient


texts: Prove or disprove if $L_{1}$ is undecidable and $L_{2}$ is finite language then $L_{1} \cup L_{2}$ is undecidable

texts:
I tried to prove by contradiction.

$L_{1}$ is undecidable and $L_{2}$ is finite language then $\overline{L_{1}}\cap \overline{L_{2}}$ is decidable.
$$L_{1} = \overline{HALT_{TM}} = \big\{ \langle M, w \rangle \mid M \text{ is TM and }M \text{ doesn't halt on input } w \big\}$$
$$L_{2}=\emptyset$$
then,
$$\overline L_{1}={HALT_{TM}}=\big\{ \langle M, w \rangle \mid M\text{ is TM and }M\text{ halts on input }w \big\}$$
$$\overline L_{2}=\Sigma^{*}$$
The intersection, $\overline{L_{1}}\cap \overline{L_{2}}$ is $\overline L_{1}={HALT_{TM}}$ is decidable and this is the contradiction.

Is it true?

Thanks.


texts: Path on an edge-colored DAG using exactly $k$ colors

texts:
I have the following problem:

  Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
   does there exist a path from $s$ to $t$ using exactly $k$ distinct colors?

Can anyone provide pointers to the complexity of this problem?  More specific, is it $\mathsf{NP}$-complete or in $\mathsf{P}$?


texts: What is the advantage of heaps over sorted arrays?

texts:
I'm fairly new to heaps and am trying to wrap my head around why min and max heaps are represented as trees when a sorted array appears to both provide min / max properties by default.

And a follow up: what is the advantage of dealing with the complexity of inserting into a heap given an algorithm like quick sort handles sorting very well?

Context: I'm working through CLRS / MIT 6.006 in python and have only seen integer representations of leaf values. Is this more applicable in a language like C where each leaf contains a struct that can't easily be sorted?


texts:
Two algorithms to solve a particular problem can have theur efficiency compared using the $O$ and $o$ notation. However, this is very crude method, and tells us no information on how more effective one is than the other.

Is there a yard stick that can be applied to ALL algorithms, with ALL time complexities, that can be used to evaluate the efficiency of two algorithms?

I actually developed a method for this, but it applies only to polynomial algorithms.

MY METHOD.

  Suppose we want to compare two algorithms for accomplishing a task $f_i(n), g_i(n)$. $f_i(n) = o\left(g_i(n)\right)$
  A simple way to compare $f_i$ and $g_i$, is to find their ratio $r_i(n)$
  $$r_i(n) = \frac{g_i(n)}{f_i(n))}$$
  Express $r_i(n)$ as a polynomial of ,$n$.
  $$r_i(n) = n^{k}, \{k: k \in \Bbb R\}$$
  $$m = \lceil{k}\rceil$$

  $R_i(n) = m^{th}$ derivative of $r_i(n)$.
  It follows that $R(n)$ is a constant.

My method works nicely for polynomial algorithms, but is completely useless for other time complexities. Is there a more effective yardstick? One that applies to all complexities?