texts: Why is the syntax of some programming languages very much not according to earlier conventions?

texts:
Looking at the syntax of the programming language C and others inspired by it, I cannot help but ask the question in the title. Mathematics, logic and other subjects have been existing for many ages and so have natural languages and all of their symbols. Still, instead of respecting these conventions fully, designers of languages such as C have gone against them, for example by using the very old &, used in logic and natural language to denote conjunction, for something totally different, or by using the well-known = and == in unexpected ways, or by using ! for negation. Why?

Even if there were constraints to work with, certainly a programming language designer and implementor could make the syntax much more readable, less cryptic, and still concise and more natural, respecting established conventions? After all, there have been examples of that (Wirthian programming languages). And they can certainly do it these days.

Furthermore, certainly subjects such as philosophy, logic, mathematics and natural languages are very much primary and very essential subjects without which there would not even exist any computer science and no programming language. The symbols there used are very much known by many or they are at least standard. Why then go against established principles?


texts:
I'm interested in the following variant of Travelling Salesman Problem sometimes called Partial TSP. I'm particulary interested in the euclidian version :

Input : A set $\{x_1,\dots,x_n\}\subset \mathbb{R}^2$ of $n$ points in the plane, and an integer $k\le n$.

Output : A tour of $k$ points $x_{i_1},\dots, x_{i_k}$

Minimize : The length of the tour.

Is there any PTAS for this problem, or APX-hardness results ? Does Arora's technique applies on this case ?


texts: Exact definition of average time complexity?

texts:
Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least.
Here is a definition that I feel comfortable with:
Consider a set $A$ of finite elements, with each $a\in A$ indicating individual input cases. There exists a function $T(a)\mapsto t\in\mathbb{N}$, i.e., running time for individual cases. Now we can define the average running time of input set to be simply
$$\overline{T}(A)=\frac{\sum\limits_{a\in A}T(a)}{\#A},$$
where $\#A$ denotes number of elements in $A$. For example, in QuickSort, we let $A_n=\{\text{array of $n$ unsorted integers}\}=\mathbb{Z}^n$.
But now we have to do an additional step. An integer can take on an infinite set of values, so we naturally consider the memory constraint and instead confine each integer $i$ to be $L\le i\le U$. Now $\#(A_n)=(U-L+1)^n$, and we have a clearly defined $T(\cdot)$, and we can try to figure out $\overline{T}(A_n)$, although this is a very tough combinatorics problem.
We can also consider $i$ to be a bounded real number, with the modification $\#(A_n)=\mu_{\text{Le}}(A_n)=(U-L)^n$, and
$$
\overline{T}(A_n)=\frac{1}{(U-L)^n}\int\limits_{a\in A_n}T(a)\,\mathrm{d}\mu_{\text{Le}}.
$$
What CS people did instead, is stating $T(a)
\le T(\text{head})+T(\text{tail})+cn$ for some $c$, then simply averaging $T(\text{head})$ and $T(\text{tail})$ for varying head or tail lengths. This is stating implicitly somehow varying head (or tail) lengths are "equally likely", with out even considering the constraint that makes $A_n$ finite. This is like saying you can pick an odd number from the set of all integers at "$50\%$ probability" without even bothering to define what this "probability" means!
So how is this average time complexity rigorously defined over an infinite, countable number of cases?
If average time complexity is dependent on a set of rules of translating clearly defined recursion to what is essentially an intuitive ad-hoc definition each time, how can we define average time complexity for arbitrary code?


texts: How does the Sutherland-Hodgman Algorithm work?

texts:
The following are the Pages-96 and Page-97 of the book Schaum's outline series of Computer Graphics.

The algorithm considers several things:

(1) Whether the polygon is Convex or Concave.

(2) Whether the polygon is positively or negatively oriented.

(3) And, finally, testing polygon edges against the edges of the clipping window.

Consider the WXYZ as the clipping rectangle in the following picture.

I have several questions:

(1) Do I need to test an edge AB against all of the edges of  wxyz or just wx?

(2) Suppose, I test  AB against  wx. According to the Page-97 of the book, I should be testing whether it is on the left or on the right side of the clipping edge. But,in this case, there are no lefts or rights. There are aboves and bellows. How can I determine whether it is inside or outside?

(3) How can I keep track of the Inside and Outside? For example, Consider the polygon edge BC. If I test it against ZW, it is on the Right side and Inside the Clipping Region. If I test it against YX, it is on the Left side and Inside the Clipping Region. It turns out to me that, it is actually not possible to find the position of a point with respect to the clipping region unless we consider the region at once and as a whole. Then why is the book testing points against one line at a time?

(4) Consider the edge DE. Is it going out or coming in?


texts: Reed Solomon - why the interest in original view decoders?

texts:
As seem in the history section of the Wiki Reed Solomon article:

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction#History

Efficient decoders for BCH / fixed generator polynomial based code words were developed back in 1969 - Berlekamp Massey decoder, and 1975 - Sugiyama extended Euclid decoder.

However, decoders based on Reed Solomon's original scheme of using variable polynomials based on the message, using a fixed set of values mapped by that polynomial to create a code word were developed years later, such as 1986 - Berlekamp Welch decoder, and 2002 Gao extended Euclid decoder.

The Berlekamp Welch decoder is the slowest since it uses Gaussian elimination which is O(n^3). Sugiyama and Gao decoders use extended Euclid algorithm, and both are O(n^2), but Gao is significantly slower, 3 to 16 times slower depending on N and K for a RS(N,K) code in my testing.

Other than research purposes, was there a reason for going back the original encoding scheme despite being relatively slower?

There is one slight advantage, the original scheme maximum code word size can be one element larger than the BCH scheme maximum code word size.


texts: Deamortizing a Las-Vegas randomized algorithm

texts:
Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound.

For example, assuming you need to find the median of an array once every $n$ operations of type $X$ (which does not change the array).

You could take a specific algorithm, such as the median of medians selection algorithm, which takes at most $c\cdot n$ time, and perform $c$ of its operations every time $X$ is performed.
This guarantees that the worst case run time of finding the median in each $X$ call is constant.

But now assume we'd like to use a randomized Las-Vegas algorithm (always correct, runtime is computed in expectation), such as computing the median by selection with random pivot.

Now we know that the algorithm is expected to take $c'\cdot n$ operations, but it might take more, or less.

How do you determine how many of the iterations you run every time $X$ is performed?
Can we say that by performing, say, $2c'$ operations every time we will finish computing the median with high probability?
Can we adaptively select how many operations of the selection algorithms to perform at each of $X_1,X_2\ldots X_n$ calls such that we will finish computing the median with probability $1$, but so that with high probability, the number of operations in each $X$ call is constant?


texts: Implementing SUM(i,j) and CHANGE(i,j) in O(log(n)) using a datastructure with O(n) space complexity

texts:
I have two operations:

$Sum(i,j)$ : Calculate $A[i]+A[i+1]+....+A[j]$

$Change(i,x)$: Set $A[i]=x$

I need to implement these operations in an appropriate data structure using $O(n)$ space ($n$ is the length of the input array $A$).

The $Sum(i,j)$ procedure needs to have a runtime complexity of $O(\log(n))$ and the $Change(i,x)$ procedure needs to have a runtime of $O(\log(n))$.

I thought about using a heap seeing as change-key in a heap is $O(\log(n))$, but I cant figure out how exactly to get the $Sum(i,j)$ procedure down to $O(\log(n))$. To me it seems you would need $O(n)$ time to do this. If anyone could nudge me in the right direction I would appreciate it.


texts: Massalin's Synthesis Quajects equivalent to ASM generating macros used in Game Oriented Assembly LISP?

texts:
Alexia Massalin's Dissertation on Synthesis was a Phd thesis on Operating Systems that contained a concept called 'Quajects' (see Chapter 4).

This is some additional commentary on the Phd Thesis.

Best I can work out - a Quaject is construct that generates Assembler customised for the function being used at the time. (Perhaps like a JIT).

The project that I've seen that came closest to this was Game Oriented Assembly LISP (GOAL), a framework used in Crash Bandicoot that used ASM-generating LISP macros to speed up the development iteration process and generate the production code.

Can we say that the Macros generating ASM in GOAL were quajects? (yes or no question - please explain why if yes, and reasons if no.)


texts:
Can GDB be run on itself? How or why not?
I see something about it http://www.math.utah.edu/docs/info/gdbint_3.html
But GDB might not be written in a language that it can debug?


texts: How do I generate all possible MSTs of a graph using any algorithm?

texts:
For an un-directed graph, how do I obtain all possible Minimum spanning trees?

A graph is created with set of Vertices V, and set of edges E.
In the below graph, we can see that there are two MSTs. I want to obtain all such MSTs (using any algorithm).

I have currently tried to solve this using Kruskal's algorithm. But the algorithm will only give one MST.

 procedure Kruskal(G)
 A = {} //Empty
 foreach v belongs to G.Vertex
   MAKE-SET(v)
 foreach (u, v) in G.E ordered by weight(u, v), increasing:
   if FIND-SET(u) ≠ FIND-SET(v):
     A = A ∪ {(u, v)}
     UNION(u, v)

 return A

Can I tweak the above algorithm to obtain desired solution, or is there any other algorithm to do so?


texts: Level-order traversal of a balanced tree, with no parent pointers in $\mathcal o(n)$ space

texts:
Assuming you have a balanced tree, without parent-pointers, with $n$ nodes, and a height $H = \mathcal O(\log n)$.

I know you can traverse the tree in level order in $\mathcal O(n)$ time using a queue. However, even in a balanced tree, the queue can grow to $\mathcal O(n)$ in size.

So the best I came up with is essentially to in/pre/post order traverse the tree in $H$ passes, one for each level in the tree, and simply filter the visits to the level for that pass. This gives an algorithm with $\mathcal O(n\cdot H ) = \mathcal O(n \log n)$ runtime and $\mathcal O(H) = \mathcal O(\log n)$ space.

The question is:

is there a algorithm for traversing a balanced tree without parent-pointers in linear-time, and logarithmic space?
Or at least, in $\mathcal o(n\log n)$ time and $\mathcal O(\log n)$ space (i.e a better result than my naive algorithm).
Or more generally, linear time, but sub-linear space?

Also, no cheating, you cannot alter the tree :)


texts: How is this the expected number of of probes in open-address hashing?

texts:
I am reading the "Introduction to Algorithms" by Thomas Cormen et al. Particularly the theorem which says that given an open-address hash table with load factor $\alpha = n/m < 1$, the expected number of probes in an unsuccessful search is at most $1/(1-\alpha)$, assuming uniform hashing.

In the proof they are assuming $p(i)$ to be the probability of exactly $i$ probes where we are finding all of the slots to be occupied. $i$ is $0,1,2,\dots$ so for $i > n$ we have $p(i) = 0$ since we can find $n$ slots already occupied. I have understood upto this point.

Then it says that expected number of probes in an unsuccessful search is
$$1 + \sum_{i=0}^\infty i\,p(i)\,.$$
How is it so?

If there is any confusion to the question please comment. I hope I have explained the question properly. Any help would be appreciated. Thanks in advance.


texts: TCP Connection Termination - FIN, FIN ACK, ACK

texts:
I've been reading that to terminate a TCP connection 3 handshakes are required: FIN, FIN ACK, and ACK. However, when closing a connection, Wireshark displays FIN ACK, FIN ACK, ACK; it never displays FIN by itself.

However, when establishing a connection Wireshark clearly displays the three handshakes: SYN, SIN ACK, ACK.

So I'm kinda confused why when closing the connection the three handshakes aren't displayed like that.


texts: Are there are satisfying explanations for why genetic algorithms work?

texts:
The following commentator writes:

Having studied this extensively back when they were called Genetic Algorithms, I would like to offer a few insights.
One of the biggest reasons they fell out of favor for more "mathematical" approaches was that no one could really explain why exactly they worked. It makes sense on the surface that "survival of the fittest" and doing something akin to multiple stochastic gradient descents would work, but no one has really been able to produce a mathematical proof as to why.
Since other folks are producing good examples of "explainable AI", I don't know how Genetic Algorithms/programming could be made 'explainable' as to why they achieved an optimal solution other than hand-waving to how evolution works in nature.

Steven Wolfram has published the book A New Kind of Science, in which he posits that mathematical proofs aren't relevant to this approach, and the algorithm is itself the science. Many considered this unsatisfactory.
We know that Cellular Automaton rule 110 is Turing complete. (And phenomenal things have been done with Conway's Game of Life).
My question is: Are there satisfying explanations for why genetic algorithms work?


texts:
I'm both interested in practical and theoretical aspects of the problem. How do you store linguistic data. Suppose you have stemmed, parsed, tagged and, perhaps even did some preliminary analysis, such as clustering by topics, how then do you store this information for reuse?

I've been looking at knowledge representation formats, but, and maybe because I was doing it on my own, without guidance, two aspects strike me as odd:

The technology is very immature (and most things I could find relevant to the subject seem to be abandoned in the last century).
Even then, there weren't real storage engines. The closest I could get was a triplestore. While, maybe at the basis level this is an interesting idea, there seem to be no tools or techniques which build on top of it.

To make this question more concrete, consider this chain: there are relations out there in the real world, certain aspects of them are captured by relational algebra; SQL language builds on top of relational algebra, adding new concepts such as tables, triggers etc.

Similarly, out there in the world there are phrases people say or write to each other, there are several theories which try to capture the underlying principles of the structure of those phrases (for example, dependency parsing or constituency parsing). If the later is in some sense equivalent to relational algebra, what would be the equivalent of SQL-enabled databases for linguistic data?


texts: What qualifies the structural relation in the pi calculus as a congruence?

texts:
In the pi calculus, there is an equivalence relation between terms that are structurally equivalent and should "act the same", which is usually described as structural congruence rules. For example, the reduction rules are usually described modulo the structural congruence.

My question is: in the context of a calculus, what exactly turns a relation as such into a congruence? Let's say I'm working with some process calculus, what would I need to prove in order to say that a similar equivalence relation is, in fact, a congruence?


texts:
I'm learning about monads, I understood why they are useful, I understood in general what bind, join, return do.

I also looked at basic usage examples for the basic reader / writer / state / list / maybe monads.

Still, being a beginner, I still don't feel I have a grip on what the "run" function means in general. It does not seem to have a generic signature like the above functions, and I don't get it if it's definable / makes sense for all monads.


texts:
Please tell me how I should apply minimax algorithm to the array
$$ 15, 12, 14, 16, 11, 13$$
and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)


texts: How to extract parent, child and grandchild from a treeview fomatted string?

texts:
I have a long string that contains data formatted in the following way:

var str = "parent /n /t child /n /t child /n /t /t grandchild /n parent";

If you print this out you get a tree structure like directories. I am trying to figure out a way/algorithm to individually extract every parent and child and children of the aforementioned and store them in an array for each of them so that I can access them later for other useful purposes. I was thinking of using a regular expression to extract the substrings since there is some sort of pattern but I am not an expert in that field and do not know if it is worth the time. Any other ways to approach this problem or is this the best way?

Notes:

A child is always preceded with \n\t

A child's child "" "" "" \n\t\t (possibly spaces between the literals)

If the string is searched the substrings that have been searched should be stored somehow for compiling the node later.


texts:
Rice-Shapiro theorem is:

  Let $Γ$ be a set of computable functions such that the set $R_Γ$ is recursively enumerable. We have $f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

If $Γ$ is singleton set, for example $Γ = \lbrace ϕ_{10}\rbrace$ then $R_Γ = \lbrace 10 \rbrace$ and is recursively enumerable, but $Γ$ does not satisfy:

$f ∈ Γ$ if and only if there exists a finite function $θ ∈ Γ$ such that $θ ⊆ f$.

Where I have made a mistake?


texts:
I have this problem to resolve in dynamic programming:

  An ice cream shop owner has 4 stores. To meet the demand in the summer he purchased 7 refrigerators for the ice cream. Because the stores are in different places, there are different points for selling the ice cream. It was estimated the profit (in monetary unit) that could be obtained in each store:

$$
\begin{array}{c|lcr}
N refrigerators & \text{store1} & \text{store2} & \text{store3} & \text{store4} \\
\hline
1 & 4 & 2 & 6 & 1 \\
2 & 6 & 6 & 12 & 4 \\
3 & 10 & 8 & 14 & 8 \\
4 & 12 & 10 & 18 & 16 \\
5 & 14 & 12 & 20 & 20 \\
6 & 16 & 16 & 22 & 21 \\
7 & 18 & 20 & 22 & 24
\end{array}
$$

The problem asks to find the working scheme that maximizes the financial return.

As dynamic programming aims to reuse the code I know that it is necessary to use a recursive function, but when analyzing the problem I assumed that my answer field is in a matrix where the lines are referring to the number of refrigerators and the columns the stores.

Then I assumed that $M(i, j)$ is my function that returns a monetary value, assuming that $i$ is the number of refrigerators, ranging from $1 \le i \le 7$, and $j$ is a particular store, ranging from $1 \le j \le 4$.

I also assumed that my function would have 4 calls of this same function $M(i, j)$, because there are 4 stores to divide 7 refrigerators:

The equation would be:

$$MAX  \{ M(i, 1) + M (i, 2) + M (i, 3) + M (i, 4)\}$$

Where $\sum_{i=1}^4 i \le 7$

As a base case of recursion I put this:

$$M(0, 1) + M (0, 2) + M (0, 3) + M (0, 4) = 0$$

But my problem is not knowing how to treat this problem recursively. Maybe I'm doing the wrong analysis, too. Every help is welcome.


texts: Tutorials/resources for building a toy SMT solver

texts:
I've built a rudimentary SAT Solver from scratch, and wanted to do the same with SMT solvers as well.
While I've found two toy SMT Solver implementations in Haskell and Ocaml, but no tutorials or examples, which is a stark contrast from all SAT Solver tutorials out there.
Is there a resource for building a toy SMT Solver from scratch?


texts: Looking for interesting unanswered questions within complexity theory for a project

texts:
I'm looking for interesting open questions in complexity theory that someone with an undergraduate degree in math and comp/sci could theoretically tackle. I have strong interest in the polynomial hierarchy, and the study of probabilistic classes like RP, co-RP, ZPP, BPP, and also their logarithmic counterparts. I also have some interest in quantum computing complexity theory, but I'm afraid my knowledge of quantum isn't that strong. (Only the basics from my modern physics class, which included some quantum). Important: must be new research or new expansion on previous research, a question that either hasn't been asked or hasn't been answered successfully that I might be able to say something interesting about, even if I don't ultimately solve it. I'm willing to learn any necessary programming languages/programs/methods/etc to the end of answering this question (or trying to)!

Note: this is for a senior year undergraduate thesis in math / comp sci.

Thanks for any suggestions!

Edit: An example might be to analyze the complexity of a particular problem that hasn't been (formally) analyzed yet but may yield interesting results.


texts: Why do we use DAG rather than trees to represent search space of a search problem?

texts:
I saw people use DAGs to represent the search space of a search problems like the travelling salesman problem. Why is this better than the tree representation? Is the reason to save memory space on the computer or can it reduce the computation time in some way?
I googled but I didn't find an answer, it would be great to have a simple explanation and a reference I can read as I would like to have a good understanding about why DAG approach is a better option.


texts: Can all programs with mutable state be refactored in programs without?

texts: Given the space A of all programs that could be possibly written in a given language and given the space B of all programs that could be possibly written in the same language but without any mutable state: can we be sure that with just B we can solve all the same problems we could solve with A ?


texts:
The $K$th Largest Subset problem is often given as an example of an NP-hard problem. However, the assumption is that $K$ is unconstrained, and can be as large as $2^n$. Clearly, if $K \le 3$ the solution in $O(n)$ time is trivial.

Are there any general results for time complexity of this problem for a given (and potentially small) $K$?


texts: Given $n$ unique items and an $m^{th}$ normalised value, compute $m^{th}$ permutation without factorial expansion

texts:
We know that the number of permutations possible for $n$ unique items is $n!$.
We can uniquely label each permutation with a number from $0$ to $(n!-1)$.
Suppose if $n=4$, the possible permutations with their labels are,
0:  1234
1:  1243
2:  1324
3:  1342
4:  1432
5:  1423
6:  2134
7:  2143
8:  2314
9:  2341
10: 2431
11: 2413
12: 3214
13: 3241
14: 3124
15: 3142
16: 3412
17: 3421
18: 4231
19: 4213
20: 4321
21: 4312
22: 4132
23: 4123

With any well defined labelling scheme, given a number $m, 0 \leq m < n!$, we can get back the permutation sequence. Further, these labels can be normalised to be between $0$ and $1$. The above labels can be transformed into,
0:       1234
0.0434:  1243
0.0869:  1324
0.1304:  1342
0.1739:  1432
0.2173:  1423
0.2608:  2134
0.3043:  2143
0.3478:  2314
0.3913:  2341
0.4347:  2431
0.4782:  2413
0.5217:  3214
0.5652:  3241
0.6086:  3124
0.6521:  3142
0.6956:  3412
0.7391:  3421
0.7826:  4231
0.8260:  4213
0.8695:  4321
0.9130:  4312
0.9565:  4132
1:       4123

Now, given $n$ and $m^{th}$ normalised label, can we get the $m^{th}$ permutation while avoiding the expansion of $n!$ ?
For example, in the above set of permutations, if we were given the $m^{th}$ normalised label to be $0.9$, is it possible to get the closest sequence 4312 as the answer without computing $4!$ ?
Math SE crosspost


texts:
In DFA/NFA the automaton halts when it finishes reading the string.

In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or does it have to pop them?

Or maybe does the behavior depend on whether the PDA is deterministic or not?

Here's an example to demonstrate where the ambiguity is.

It's a dumb example and it can be done with a DFA but just for demonstration.

This PDA should accept anything but the string aa.

It starts by inserting a $ to mark the bottom of the stack. Then it inserts 2 as. Then when it receives an a it pops one from a stack. It can do that twice.

Now at this point suppose that the input string was indeed aa, and that the machine reached state x and popped the two as. Now the stack has only $ in it.

Does it have to go to the next state (y) because there's a $ on top of the stack?
Or by non-determinism can it be either in x or in y?

If the latter is true then this is a wrong PDA for this language. It would accept everything.


texts: Having trouble understanding a proof of Mahaney’s theorem

texts:
I am reading a blog post of Lance Fortnow, which includes a proof of Mahaney's theorem.

I am not sure why $a’$ cannot be in between $w_i$ and $w_j$ in Case 1, and also why $a’$ cannot be in between $w_0$ and $w_1$ in Case 2.

Can anyone give me some explanation?


texts: In Amortized Analysis, can we chose how big $n$ is?

texts:
Suppose I want to show by contradiction that the amortized cost of a data structure with some operations cannot be less then $\Theta(k)$. I assume for the sake of contradiction that it is possible. Can I then choose an $n$, large enough, and a special sequence of operations and show that they take $\Theta(nk)$ and conclude that the amortized cost has to be at least $\Theta(k)$? Or does my counter example must be for any chosen size of $n$ sequences?

In other words, I want to show that for any large $n$ that satisfies $\frac{n}{2}>2^k-1$, the counter example works. Is this sufficient?

Edit: To show what I mean here is an example:
I have a binary counter that supports the option INCREMENT and DECREMENT. It starts at all zeros at the start. I wanna show that the ammortized cost cannot be less than $\Theta(k)$.

So I assume the opposite. And I first do $2^k$ increment operations so that I have [1(k-1 zeros)] as the binary counter. Then I do $m$ DEC INC operations in succession where each of them will take $\Theta(k)$.

here we have $n=2^k+m$. Choosing $m=2^k$, we get $n=2^{k+1}$ so $m=\Theta(n)$. So we get total amount of work $\geq km=k\Theta(n)=\Theta(nk)$ so the amortized time is $\Omega(k)$.

However, the above argument only holds if $n\geq 2^{k+1}$, does this constitute a proof?


texts: Operating System: Redundancy of implement a monitor using semaphores in my textbook?

texts:
Why the part highlighted the following picture is need? I've been trying to follow to logic flow of it as follow:
Imaging a Situation:
Two processes enter/call F, first A, second B:
Process A: mutex(value: 1 -> 0) enter the body of F, then calls x.wait(), so mutex(value: 0 -> 1) but this process into waiting state because x_sem(value: 0 -> -1) and now count(value: 0 -> 1).
Process B: mutex(value: 1 -> 0) also enter the body of F, then calls x.signal(), so since count > 0 pass, next_count(value: 0 -> 1). Now, only at this moment next_count > 0 will pass, but Process B still holding the mutex.

So why the part I highlighted is needed?
The book I'm reading is "Operating System Concepts, 9th ed., pages 229~230."


texts: Decision tree complexity of deciding whether array is "zigzag"

texts:
I am currently studying for a test on data structures.

I have to find the lower and upper bounds for the following problem:

  Input: an array with $n$ numbers.

  Output: boolean answer for the question if there exist $1\le i\le j\le n$ so that:

  All the elements in the array between $1$ and $i$ are in ascending order.
  All the elements in the array between $i$ and $j$ are in descending order.
  All the elements in the array between $j$ and $n$ are in ascending order.
  We call this type of array a zigzag array.

I have these ideas: in general, in order to find an upper bound I am looking for an efficient algorithm. For lower bound I am using the decision tree model. For example: in order to find the lower bound for comparison sort algorithms of $n$ numbers, we have $n!$ leaves on the binary decision tree, so we have $n!$ different possibilities for sorting $n$ numbers, which results in an $Ω(n \log n)$ lower bound.

For upper bound I am thinking about just moving from the first element step by step and finding if the array is a zigzag or not, so upper bound is $O(n)$

Lower bond: I don't know how many different possibilities of zigzag arrays of length $n$ we have, so i don't know how so solve it. If one of you has a different method of finding the lower bound I will be happy to know.


texts: prove that $BPP(\alpha(n), \beta(n)) = BPP$

texts:
prove that for every $0 \le \alpha(n), \beta(n) \le1 \; s.t.$ there exists $c \in \Bbb{N} \;s.t \;\alpha(n)+\beta(n) \le 1- \frac{1}{n^c}$ then $BPP(\alpha(n), \beta(n)) = BPP$.

I tried to show that by running k times we can get the error to be exponentially small using the chernoff inequality, for $0\le\delta\le1$
$$p(\sum_{i=1}^{n} X_i \gt (1+\delta)pn) \le e^{-\delta^2pn} $$

If we run the algorithm k times, and accept only if we accepted at least $\frac{a(n)+b(n)}{2} k$ times.

then we should set $\delta = \frac{\alpha(n) + \beta(n)}{2\alpha(n)} -1$

But then I get stuck because it doesnt necessarily hold that $0 \le\delta \le 1$


texts: What is the order of this traversal method?

texts:
Please see below pseudo-code for finding the max-height of a b-tree

maxDepth()
1. If tree is empty then return 0
2. Else
     (a) Get the max depth of left subtree recursively  i.e.,
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e.,
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,
                             max depth of right subtree)
                             + 1
     (d) Return max_depth

My guess is that this is post-order traversal.

Because we are calculating the height of the left tree and then the right tree and in the end, we find the max(left_tree_height, right_tree_height) to figure out the max height of the root node.


texts: Idea behind $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?

texts:
$\mathsf{3SAT}$ in $n$ variables is an $\mathsf{NP}$ complete problem.

Augment input to $\mathsf{3SAT}$ with constants $\{a_i\}_{i=1}^{n^c}$ where each constant $|a_i|<n^e$ to get an artificial problem ${\mathsf{3SAT}}_{aug}$. There is a direct reduction from $\mathsf{3SAT}$ to ${\mathsf{3SAT}}_{aug}$.

Assume that $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$ where suppose there exists $n^c$ constants for a fixed $c$ that will help solve any $n$-variate $\mathsf{3SAT}$ instance in $n^d$ time for a fixed $d$, however finding those constants offline takes exponential amount of time.

Since by hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$, we have constants that help solve $\mathsf{3SAT}$ in poly time, let augmented input to ${\mathsf{3SAT}}_{aug}$ contain constants that help solve ${\mathsf{3SAT}}_{aug}$ in poly time.

${\mathsf{3SAT}}_{aug}$ is $\mathsf{NP}-\mathsf{complete}$: $\mbox{  }$ Since $\mathsf{3SAT}$ reduces to ${\mathsf{3SAT}}_{aug}$, ${\mathsf{3SAT}}_{aug}$ problem remain $\mathsf{NP}-\mathsf{complete}$.

${\mathsf{3SAT}}_{aug}$ is in $\mathsf{P}$: $\mbox{  }$ Follows from hypothesis of $\mathsf{NP}\subseteq \mathsf{P}/\mathsf{Poly}$.

So why then is still $\mathsf{NP}\subseteq\mathsf{P}/\mathsf{Poly}\implies\mathsf{P}=\mathsf{NP}$ not true?


texts:
I'm reading this book Cracking Coding Interview. In this book author is speaking about BST representation of Hash Tables.

I googled a lot for BST Representation of Hash Table. Code in C++ but didn't find any link or example. Can someone help me with the implementation. I'm really confused how to represend Key-Value pairs on BST. And what if there are collisions etc.

All, I found was comparison b/w BST and HasTables:

https://stackoverflow.com/questions/22996474/why-implement-a-hashtable-with-a-binary-search-tree
https://www.geeksforgeeks.org/advantages-of-bst-over-hash-table/


texts:
Let $L$ be the languague which contains all satisfiable formulas which do not have the or symbol $\lor $.
Or more precise $$L=\{\phi | \phi \text{ is a satisfable formula which is only using the junctors $\lor$ and $\neg$ }\}$$
Is $L$ NP-Complete  ? I think it is NP-Complete. I can at least show that is in NP. A nondeterministic polynomial time machine can guess an assignment to a given formula φ and if the
assignment satisfies φ it can simply check if the formula is using $\lor$ . If no, accept. If yes, reject.
Next I would need to make a polynomial time reduction from a $NPC$ problem to $L$. I think $3-SAT$ would be a good starting point. But I dont know how to convert a satisfable 3-CNF formula into a satisfable OR free formula.


texts: Reinforcement learning with 0 rewards and costs

texts:
Suppose we have a hallway environment, i.e, $N$ nodes from left to right, and we can either move left or right. Moving left at the leftmost node does nothing and reaching the right most node gives you a $+1$ reward and terminates the game. But every other action has $0$ cost or reward.
I'm curious to know how reinforcement learning works in this case, because based on what I know it shouldn't.
Consider a trajectory $\tau = (o_0, a_0, \cdots o_H, a_H)$ sequence of observations and actions up till horizon $H$. Then the gradient by the gradient policy theorem looks like $g = \sum_{h = 1}^H [\sum_{t = h}^H\text{Reward at step t}]g_\pi(a_h|\tau_h)$ where $g_\pi(a_h|\tau_h)$ is the gradient of the log probability of choosing action $a_h$ given the trajectory up till step $h$, $\tau_h$.
But if Reward = 0 at every step, and we only get a reward of $1$ at termination, doesn't this simply become: $\sum_{h = 1}^H1\cdot g_\pi(a_h|\tau_h)$? And this is a bad thing since when we do gradient update to the params this weighs us towards the action of moving left as well, and obviously we want our policy to tell us to go right. So it seems the gradient signals the wrong directions to move in (in policy space).
So how would the typical policy gradient update technique work here? Am I wrong or does it not work?
More questions: How is this affected by $N$ the number of nodes? My intuition is that it shouldn't be (after all, $N$ doesn't even appear in the equation above). But I'm not sure.


texts: Computing snapshot of Turing machine from previous snapshots in logarithmic space?

texts:
To prove that $P \subseteq P_{\ poly}$ [see book by Arora and Barak, chapter 6, page no 105]

Proof : Let $M$ be an oblivious TM and running time is $T(n)$, let $x \in \{0,1\}^* $ be some input for $M$ and define the transcript of $M$'s execution on $x$ to be the sequence $z_1,z_2,..z_{T(n)}$ of snapshots (the machine's state and symbol read by all heads) of the execution at each step in time.

We can encode each such snapshot $z_i$ by a constant-sized binary string, and furthermore, we can compute the string $z_i$ based on input $x$, the previous snapshot $z_{i-1}$ and snapshot $z_{i_1},z_{i_2},\cdots ,z_{i_k}$, where $z_{i_j}$ denotes the last step that $M$ 's jth head was in the same position as it is in the ith step.

The composition of all these constant-sized circuits gives rise to circuit that computes from the input $x$ the snapshot $z_{T(n)}$. This requires polynomial space, but I want to do this whole computation in logarithmic space.

My question : How to compute snapshot $z_i$ of Turing machine $M$ from previous snapshots using logarithmic space?


texts: If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover?

texts:
I was reading the following paper on Robustness and Generalization (and covering numbers)and I was reading their example 1:

which didn't quite make sense to me. The reason it didn't make sense is that intuitively it seems to me that each region $X_i$ could have the label either +1 or -1, so it seems to me that the partition of Z should be exponential:
$$2^{\frac{K}{2}}$$
because it region can have either label +1 or -1. However, instead it seems to be that instead if 2 times the epsilon cover of the other set X, which seems puzzling. Any ideas why?

Ok for background definition:
Epsilon cover means the smallest set size that can $\epsilon$ cover some target set T. i.e.:
$$ N(\epsilon,T,\rho) = \min \{ |\hat T | \mid T \subset \cup_{\hat t \in \hat T} B(\hat t; \epsilon, \rho ) \}$$
where $B(\hat t; \epsilon, \rho ) = \{ x \mid \rho(\hat t, x) \leq \epsilon \}$ is the epsilon ball around $\hat t$.
Ab algorithm $A_s(x)$ has a margin $\gamma$ if every point in the input space around it would be classified the same way. i.e. as the paper wrote:
$$ A_{s}(x) = A_s(s_{j | x}) ; \forall x: \| x - s_{j|x}\|_2 < \gamma $$
for more definition the paper has them pretty much on the page and the page before Example 1 I am referencing.


texts: Order of growth: substitution of monotonically increasing functions

texts:
One strategy for ordering the growth of functions involves substitutions when comparing functions using the limit as $n$ goes to infinity comparing two equations using the following rule.

$$
\lim_{n\to\infty}\frac{f(n)}{g(n)} =
\left\{ \begin{array}{cc}
0, & f(n) \in O(g(n))  \\\
\infty, & f(n) \in \Omega(g(n))  \\\
c\neq 0, & f(n) \in \Theta(g(n))  \end{array} \right.
$$

Using a substitution was a new strategy to me, and it was explicitly used with logarithms because they are monotonically increasing. For example:

$$
\lim_{n\to\infty}\frac{lg(n)^{lg(n)}}{2^{lg(n)}} = \lim_{k\to\infty}\frac{k^k}{2^k}
$$

Obviously, this is a much easier problem to solve, and is much easier to prove in this form. The only two cases this was useful on the assignment I was working on was with logarithms, as in the case above, and iterated logarithms.

Are there other useful substitutions like this, or is there a broader implication of these monotonically increasing functions outside the realm of comparing order of growth? A big pet peeve is learning about a math concept in practice before in principle, because I don't feel like I understand the big picture. What realm of mathematics does this fall into?


texts: Underlying codes for Niederreiter cryptosystems

texts:
Niederreiter cryptosystem is usually described by a parity check matrix $H$ over $\mathbb{F}_{2^n}$.

The minimum distance $d$ is given by

$d := min\lbrace k \text{ such that there are $k$ linearly dependant columns in $H$}\rbrace$

Encryption in this case is done by encoding messages $m$ of weight less than $d/2$.

Now keeping Niederreiter systems in mind, my question is, since $m$ is over $\mathbb{F}_2$, it makes sense to consider linearly dependence over $\mathbb{F}_2$ rather than $\mathbb{F}_{2^n}$. In other words, is it okay to consider code as a code over $F_{2}$ with alphabet extension or do we  have to consider it as codes over $\mathbb{F}_{2^n}$.


texts: RSA Decryption from Simple Public Key Values

texts:
I'm a little stuck trying to figure out how to decrypt some messages and could use some hints as to what I may be doing wrong.

I was given a series of integer values that make up my cipher text. Here are just a few of them:

6584 15650 16198 11003

I was given the following public key b = 3001 n = 18209

So to encrypt a message M, you would use the formula:

C = M^3001 mod 18209

I understand to encrypt, I need to find a 'd' value that satisfies:

bd = 1 mod 18209

3001d = 1 mod 18209

Any hints on a technique or algorithm to help me find a suitable value for 'd'?


texts: How can i implement this data structure?

texts:
Does anyone have an idea about the idea of implementing a data structure so that - the following things will happen?

The structure should save the amount of money that n people have, each person has for example a "cell" that contains the amount of money he has.

And then, how can you implement this data structure so that for example you can implement the getMostM(m) function - which returns the names of the m people with the most money (sorted in descending order).
Complexity for this function: Time: O(m)
Complexity of Location: O (n)

There are a total of $n$ people.


texts:
In an unweighted graph, we can find Multiple Source Shortest Paths using the Breadth-First Search algorithm by setting the distance of all starting vertices to zero and pushing them into the queue at the beginning of the algorithm.

However, I'm wondering if we can use the same technique to solve Multiple Source Shortest Paths in a weighted graph using Dijkstra's algorithm (for non-negative weight edges) and Bellman-Ford algorithm (when negative weight edges are allowed, and of course there is no queue here).

If I'm right, we can think in this situation as there are edges with weight equal to zero between any source and all other sources in the graph.

So, can we use this technique in a weighted graph? And why?


texts: How do you convert an NP problem which runs in O(f(x)) time in a SAT instance with O(f(x)*log(f(x))) variables in O(f(x)*log(f(x)))

texts: I looked at the Cook's theorem at Wikipedia which presents a way to convert any NP problem to SAT but it seems to require O(f(x)^3) variables. Is it possible to remove some of the checks in the conversion so to make it O(f(x)*log(f(x))) in variables and time?


texts: Successive Shortest Paths vs Ford–Fulkerson

texts: Can someone explain how exactly Successive Shortest Paths (SSP) is a generalization of the Ford–Fulkerson algorithm? I've found this stated in a few papers and websites as well as the Wikipedia page for the Minimum-cost flow problem. But none of them go any further than that statement or explain how exactly they differ. Any help would be greatly appreciated. Thanks.


texts: What are the differences between Earliest Deadline First (EDF) and Earliest Due Date (EDD)?

texts:
From my understanding, the EDF (Earliest Deadline First) rule is essentially an iterative "version" of the EDD (Earliest Due Date) rule, which allows for preemption. At every point in time, EDF looks at all the processes present and sorts them into the processes with the earliest deadlines first and the latest deadlines the last.
This means that if at time t1 we only have a process P1 with deadline d1 running, and no other processes; then P1 will run. But if at t2 we have a new process P2 with deadline d2 (such that d1 > d2), then P1 will be interrupted and P2 will be executed. Once P2 is finished, if only P1 is present then it is executed otherwise the deadlines of P1 and the next process are compared and the one with the earliest deadline is executed.
Is this the only difference or any there any more?


texts:
I want to ask, consider we want to compute the slope of x-direction of the following step

.

The slope for it would be

$m =\frac{0}{m_2 - m_1} =\frac{0}{5 - 2}$ which is 0.

But the derivate for image in x-direction computed with (something like, some symbols aren't existed in my phone so lets just say $\frac{df}{dx}$)

$\frac{df}{dx} = f(x+1) - f(x)$

It's computed under the consideration of next pixel $f(x+1)$ minus current pixel $f(x)$.

Is there any interpretation that I'm missing, shouldn't it be 0, in both cases?


texts: Sample applications based on First Order Logic

texts:
I often hear about benefits of FOL, but I wonder what are some of its real world applications?

Could someone please provide samples/case studies of applications of FOL that address real world challenges?
What are typical tools / programming languages used in developing such applications?

Note: If this is not the correct forum for this question, please let me know which forum is the best. Many thanks in advance.


texts: Relationship between Deterministic Finite Automata languages

texts:
What this "⊃" superset means? What do I need to prove here. Can someone, please, explain in English?
Do I need to do a cross product?
Plus, in textbooks and online I only see "∩" "∪" these kinda symbols.  What this symbols "⊃" means?

Let M = (K, Σ, δ, s, F) be a deterministic finite automaton. Let M' =
(K, Σ, δ, s, F') be a similar deterministic finite automaton where F is
a proper
subset of F'. For each of the following provide an example to show that
the
relationship between L(M) and L(M') is possible or explain why the
relationship
is not possible.

The problem to prove: L(M) ⊃ L(M')


texts: What problem cannot be solved by a short program?

texts:
BACKGROUND:

Recently I tried to solve a certain difficult problem that gets as input an array of $n$ numbers. For $n=3$, the only solution I could find was to have a different treatment for each of the $n!=6$ orderings of the 3 numbers. I.e., there is one solution for the case $A>B>C$, another solution for $A>C>B$, etc. (the case $A>C=B$ can be solved by any one of these two solutions).

Thinking of the case $n=4$, it seems that the only way is, again, to consider all $n!=24$ different orderings and develop a different solution for each case. While the solution in each particular case is fast, the program itself would be very large. So the runtime complexity of the problem is small, but the "development time" complexity or the "program size" complexity is very large.

This prompted me to try and prove that my problem cannot be solved by a short program. So I looked for references for similar proofs.

The first concept that I found is Kolmogorov complexity; however, the information I found about this topic is very general and includes mostly existence results.

QUESTION:

Can you describe a specific, real-life problem $P$, such that any program solving $P$ on an input array of size $n$ must have a size of at least $\Omega(f(n))$, where $f(n)$ is some increasing function of $n$?

Since the answer obviously depends on the selection of programming language, assume that we program in Java, or in a Turing machine - whichever is more comfortable for you.

Every undecidable problem trivially satisfies this requirement because it has no solution at all. So I am looking for a decidable language.


texts: Variation of the dining philosophers: is the standard solution still valid?

texts:
I have a problem that is almost equal to the standard one of the dining philosophers, but has a quirk: while a philosopher thinks, he still holds the fork on his left.

If after the period of thinking (which isn't infinite), I release the fork on the left and then apply the normal solution (that is, acquire forks in the order of their priority), then would this solution be correct for this problem?


texts:
As part of an object tracking application, I am trying to solve a node-disjoint k-shortest path problem. My graph is (for now) k-partite. I have a single source and single sink. My edges are initially negative-positive but made non-negative by transformation.

This paper provides (in appendix) a solution but the explanation is quite evasive. They are making references to a book that I do not have: Disjoint paths in a network, J.W. Suurballe

My approach would simply consist in:

Input: Graph g
for i in range(1,K+1):
    p[i] = dijkstra(g)
    g.remove_edges(p[i].edges)
    g.remove_nodes(p[i].nodes)

I also wonder what's the added value of doing node-splitting (fig. 3 of this) compared to my own approach.

Questions:

Could you provide some exhaustive paper on node-disjoint k-shortest path? (other than the book I mentioned since it's not available at my university).
Can you explain the added-value of node-splitting w.r.t. my naive approach?
Any insight into the notions of the node-disjoint KSP algorithm of the first paper would be appreciated (augmenting, interlacing, signed-path,...)
Any general advice and comments on node-disjoint KSP are welcome.


texts: Dijkstra function for navigation for disadvantaged

texts:
Is there a way we can write a function for Dijkstra to determine which node to enqueue and which to discard. This is for a navigation solution for people with disabilities where path to stairs may be shorter but not preferable to wheelchair bound individuals. The navigation solution should also support all individuals and only give a path discarding stairs if the specified user group is someone who is wheelchair bound etc. So basically i am attempting to write a function that checks if user group = wheelchair bound then removes the shortest path to stairs and gives the path to the nearest elevator.
I am pretty new to this so any assistance would be very much appreciated. My apologies for being unclear previously.


texts: Find the minimum edge size, L, that would allow the construction of a tree whose edges connect all given 2-d points, but no edge exceeds length L

texts:
Given a set of points in the 2-d plane, find the minimum edge size, L,  that would allow the construction of a tree whose edges connect all given points, but no edge exceeds length L.

Here is an algorithm, which I think might work but seems slow:

Pick a random point
find the distance of its nearest neighbour, store the distance, d
your set of covered points, S, now has 2 points in it
find the nearest neighbour point (which is not in S) to any points in S and compute its distance to a point in S, e. Add this new point to S.
d = max(d,e)
repeat steps 4 and 5 until all points have been added to S. now d is the required distance L.

I need help determining if this is correct and if so, the time complexity. Also can the algorithm be made faster (it will be run over a lots of data)?


texts: Iterating over a union of sets denoted by bitmasks

texts:
Consider the set $\mathbb{B}^n$ of all $n$-digit binary numbers. Let us define a bitmask as a tuple $M=(m_0,\ldots,m_{n-1})$, where $m_i\in \{0,1,*\}$.
Such bitmask denotes a set $S \subset \mathbb{B}^n$ containing all numbers with digits $b_0...b_{n-1}$ such that $\forall i \in [0, n-1]: m_i \neq * \Rightarrow b_i=m_i$.

For example the bitmask 1*0* would denote the set $\{1000, 1001, 1100, 1101\}$.

Given a set of $k$ such bitmasks $\{M_i: i \in [0, k-1]\}$, how to efficiently iterate over the union of the corresponding sets of binary numbers in lexicographical order? By efficiently I mean doing some pre-processing in polynomial time and then computing each next number in $O(n)$ amortized time and also using a polynomial amount of memory.


texts: How does normalised floating point binary work with two's complement?

texts:
I'm doing AQA a-level computer science, and the specification for which states that:

Exam questions on floating point numbers will
use a format in which both the normalised mantissa and
exponent are represented using two's
complement

(despite this not being the IEEE standard). I can't find much information online about how a system would work with a mantissa that is both normalised and in two's complement. This is because I would guess that the mantissa has to represent a value between -1 and 1; however if we do this, then the same numbers can be expressed in multiple ways so I would not consider it normalised, for example:

1.0110 * 2^(3) = (-1 + 1/4 + 1/8) * 2^(3) = -5

and

1.1011 * 2^(4) = (-1 + 1/2 + 1/8 + 1/16) * 2^(4) = -5

From the A-level Paper 2 June 2017 question 11, it seems that

1 . 0 0 0 0 0 0 0   |   0 0 1 0

is considered a negative normalised value but

1 . 1 0 0 1 1 1 0   |   1 0 0 0

isn't. Any enlightenment would be much appreciated.

EDIT:

The comment below explains the answer. For the value to count as "normalised", the absolute value of the mantissa must be between 1/2 and 1 which prevents double counting. This corresponds to the first two digits of the mantissa being 1.0 or 0.1 (so you could save on bits if you were actually implementing this).


texts:
I'm looking for a tree data structure that allows to keep the tree balanced in high (minimum high as possible).

I mean, suppose a tree where:

each node has a parameter k that is the maximum number of sons that can be attached to him, $0≤k≤N$
all the operations will be about insert and delete (no search): it's just just important that every node know the son/s, I'm not interested at all in search (<0.1% of operations)

Would an adaption of RB-tree or AVL tree be a good idea for that task or there are better solutions (other data structures, other kind of tree, etc)?


texts: Relation between "undecidability of arithmetic" and "godel's incompleteness theorem"?

texts:
There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the symbols are interpreted in the standard way, is undecidable.

Godel's first incompleteness theorem states that there does not exist a set of axioms from which we can prove all true arithmetic statements: There does not exist a set of first order formula's $\Phi$ that is consistent and decidable, such that for any first order $(+,\cdot,0,1)$ sentence $\phi$, we have $\Phi\vdash\phi$ or $\Phi \vdash \neg \phi$. By the completeness theorem we could have instead written "$\Phi\models\phi$ or $\Phi \models\neg \phi$"

But since we can construct a first order proof system that is complete, in the sense that all valid sentences can be proven, doesn't this boil down to the same thing?

Isn't godel's incompleteness theorem simply an implication of the undecidability of arithmetic?


texts:
This is the PDA to accept strings with equal number of $a$'s and $b$'s. The $\epsilon$ transition in the first state is causing nondeterminism.
When we have input a with Z at the bottom of the stack, then at the beginning it can do $(a,Z/aZ)$ or $(\epsilon,Z/Z)$ and go to final state, so automaton has 2 choices which can lead to 2 different states.

How do I convert it to DPDA ? How do I remove that $\epsilon$ transition from first state to make the PDA deterministic?

Here, the stack symbol is $Z$ and the transition $(a,Z/aZ)$ means on seeing input $a$ with $Z$ at the top of the stack, push $aZ$.


texts: How to Determine Places, Transitions and Tokens in a Scenario when Modeling with Petri Nets?

texts:
When modeling a scenario with Petri nets how should I determine the places, transitions and tokens?

Example:

There are two exam assistants in an exam hall observing the exam. They stand in front of the exam hall. When a student has a question one of the assistants goes to him and answers his question while the other stays in front of hall. When the question is answered, the assistant goes back to the front of the hall.

By modeling this scenario it must be distinguished which assistant stays in front of hall. Then the Petri net must be expanded so that the assistants take turns answering the questions.

Here is my solution:

p0 represents the front of the exam hall. The two tokens represent the assistants and p1 is where the student seats. I also limited the capacity of p1 to one.

The given solution is however totaly different:

How should I generally think and how can I determine which part of a given scenario is represented by which part of the Petri net (places, transitions and tokens)?


texts: Fast checking Matrix multiplication in mod 10

texts:
I recently faced this problem in a programming contest: Given 3 square matrices N x N of size N up to 1000. All elements in 3 matrices are from 0 to 9. Check if matrix A x B equals to C, mod 10. In other words, return the result of expression (A x B) mod 10 == C.

For example:

$\qquad A = \begin{bmatrix}
 0 & 5 & 8 \\
 1 & 4 & 9 \\
 2 & 3 & 3
\end{bmatrix}\qquad
B = \begin{bmatrix}
 3 & 5 & 0 \\
 1 & 2 & 6 \\
 3 & 7 & 0
\end{bmatrix}\qquad
C = \begin{bmatrix}
 9 & 6 & 0 \\
 4 & 6 & 4 \\
 8 & 7 & 8
\end{bmatrix}$

return: TRUE

If

$\qquad C = \begin{bmatrix}
 1 & 6 & 0 \\
 4 & 6 & 4 \\
 8 & 7 & 8
\end{bmatrix}$

return: FALSE, since the element C(1, 1) must be 9.

Time limit is 1s, pretty strict. Please gives me some idea how to solve the problem efficiently; is it possible time $O(N^2)$?


texts: How can image processing neural networks be effectively trained?

texts:
I was just thinking about image processing neural networks and how to effectively train them in regard of the available dataset.

Let's say you'd want to build a neural network which can distinguish between pictures showing a cat or a dog. I do not have much experience in the field, but I think it would take a pretty big dataset until the network comes to an acceptable success rate.

How could a big enough dataset be acquired? You can't just automatically generate pictures showing a cat or a dog. This means a human would be needed to catagorize thousands and thousands of pictures before the data could be fed to the untrained neural network.

How is it done in practice? Are small datasets (say 100 pictures) ran over and over again? Or is there an completely different, more effective approach?


texts: What is $R_\min$ in this formulat for optimal buffer size?

texts:
I read a question from my recitation about optimal buffer size. As solution there is a furmula for calculating the optimal buffer size; I'm not sure about one of its parameters. The formula is

$\quad \operatorname{Buffer}_{\text{optimal}} =  \frac{\operatorname{Buffer}_{\text{current}}}{1-\frac{R_{\text{app}}}{R_{\min}}}$

Where

$\operatorname{Buffer}_{\text{optimal}}$ is the optimal buffer size we want to calculate.
$\operatorname{Buffer}_{\text{current}}$ is the current buffer size.
$R_{\text{app}}$ is the rate the application reads data from the buffer at.
$R_{\min}$ -- this is the one I'm not sure about.

The example problem is this:

  Alice connects to web server and downloads a file of 12KB size from
  the server. There is a router between them. The transmission rate
  between Alice and router is 400,000B/s and the transmission rate between
  router and server is 1MB/s. Buffer size in the router is 4KB, and buffer
  size in Alice is 3KB. The rate the application reads from Alice buffer with
  is 100KBps.

  Calculate the optimal buffer size for Alice as a fuction of router buffer
  size and free space at the buffer.

So as described in the solution, according to the above formula the solution is

$\qquad \operatorname{Buffer}_{\text{optimal}} = \frac{3*10^3}{1-\frac{10^5}{4*10^5}}$

So what $ R_{\min} $ could be  ?


texts:
This might seem very simple but it's been giving me lots of headaches.

For example if I run f(12345) the result is 5310135.

I understand why it would return 5310, the rest of 135 is what is giving me troubles. Sorry if the question sounds dumb, I am a newbie seeking for help:).

function f (integer n)
{
    print n%10;
    if (n!=0)
    {
        f(n/100);
        print n%10;
    }
}


texts:
I've been trying to investigate 3-SAT for variables appearing 3 times and so far I'm getting some mixed answers as to its complexity.

For example, https://people.maths.ox.ac.uk/scott/Papers/restricted3sat.pdf says

  instances of 3-SAT in which every variable occurs three times are
  always satisfiable (this is an immediate corollary of Hall’s Theorem),
  while it is NP-hard to decide the satisfiability of 3-SAT instances in
  which every variable occurs four times

so apparently when variables appear 3 times it's an easy problem (?).

But the following two references seem to say something else:

From here, http://www.csie.ntu.edu.tw/~lyuu/complexity/2008a/20080403.pdf,

  3sat is NP-complete for expressions in which each variable is
  restricted to appear at most three times, and each literal at most
  twice.

and http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.319.8796&rep=rep1&type=pdf Lemma 5:

  The  SAT-3  problem  is  NP-complete  even  when  each  variable
  appears  3  times.

So is this problem NP-complete for when variables appear 3 times or 4 times? I'm pretty confused.


texts: how to defend against DOS caused by SYN cookies?

texts: i have read about SYN cookies and i understood that they help to avoid DOS .. BUt my prof wants an answer as how SYN cookies can be used to cause DOS and how can it be avoided ? any help woul dbe really appreciated.. thanks in advance


texts: Turing machine for unary encoded quadratic numbers

texts:
I want to design a turing machine that accepts strings of the form $0^{n^2}$ where $n \geq 1$ and I want to give an implementation description for this. So I am thinking that the algorithm can go something like this: If we have $0^{1^2}$, we can just cross off that only $0$ and accept. If we have $0^{2^2}$, we can first scan and cross off two zeros and then scan again and cross off the last two zeros since there are four zeros total. And then for $0^{3^2}$, we have $9$ zeros, so in three scans we can just cross off three zeros.

So can anyone tell me if I have the right idea and how I can put this into an implementation description? What I can't think of is, how would it know though that it has just one zero, or 4, or 9, or 16 and so on?


texts: Are there any non-trivial functions in TC1? Apart from that are there functions which are known to be in NC2 but not in TC1?


texts: is it decidable whether a grammar in Chomsky normal form has useless rules?

texts:
Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without changing the language.
Note this is not the same as asking whether the grammar has the minimum possible number of rules to generate the language, since we can imagine two grammars with different number of rules, none of which are useless, generating the same language.
For the general case of an arbitrary context-free grammar (i.e. not necessarily in Chomsky normal form), it is definitely undecidable whether any of the rules are useless (proving this is given as problem 5.36b in Sipser 3rd edition). Of course, we cannot just use the general result as a "subroutine" here, since converting to Chomsky normal form drastically changes the rules (even if not the language).
A related question asks if grammars in Chomsky normal form can have useless rules, and the answer is clearly yes.


texts: Can lists be defined in a special way so that they contain things of different type?

texts:
In https://www.seas.harvard.edu/courses/cs152/2019sp/lectures/lec18-monads.pdf it is written that

A type $\tau$ list is the type of lists with elements of type $\tau$

Why must a list contain elements of the same type? Why can't it contain elements of different types?
Is there a way of defining a list polymorphically in the typed lambda calculus, so that it takes elements of any type?
Can we then use the List monad on lists, defined polymorphically?


texts: Disk scheduling algorithm - SCAN and C-SCAN

texts:
I'm studying several disk scheduling algorithms; however, I'm kinda confused with SCAN. I understand the concept, but I don't understand the example given in the book. I think that the author made a mistake, but I want to be sure.
The example is the following:

Description of SCAN: The disk arm starts at one end of the disk, and moves toward the other
end, servicing requests until it gets to the other end of the disk,
where the head movement is reversed and servicing continues.
Suppose that the cylinder range goes from 0 to 199 and you have the following queue:
98, 183, 37, 122, 14, 124, 65, 67
Head pointer: 53
As seen in the image, the total head movement is of 208 cylinders

I don't understand why 208 cylinders. If I understand correctly, the head will start at 53 and then move to 0 (that's 53 cylinders), then the head will move up and the last service requested is at 183 (that's another 183 cylinders). So the total head movement should be 53 + 183 = 236.
The book also has an image and description of C-SCAN:

C-SCAN moves the head from one end of the disk to the other, servicing requests
along the way. When the head reaches the other end, however, it immediately returns
to the beginning of the disk without servicing any requests on the return trip.
The C-SCAN scheduling algorithm essentially treats the cylinders as a circular
list that wraps around from the ﬁnal cylinder to the ﬁrst one.

Using the same example, with C-SCAN the cylinder would start at 53, then move up to 199 (146 cylinder movements), then go to 0 (199 movements), and then the last request would be at 37 (37 cylinder movements). The total cylinder movements would be 146+199+37=382. My question here is, do we also have to count the cylinders when the head goes back to 0 since it isn't servicing any requests?
Note: This information was extracted from Operating System Concepts with Java - 8th Edition by Silberschatz, Galvin, Gagne.
You can also find this part of the chapter here.


texts: How to decide the scope of the following lambda expression?

texts:
I am having a difficulty in deciding the scope of the left-most lambda in the following expression.

λx.x(λuv.v)(λab.a)(λcd.c)

I have learnt that we should put brackets in such a way that the scope of lambda will be maximum. So arrived at candidate- answer 1, below.

On the other hand, since the expression (λuv.v)(λab.a)(λcd.c) does not contain any x, if we put brackets as in answer 2, still we are not changing the scope, right?

But I know that these two answers are not equivalent. So which one is the correct one?

The two candidate answers are:

λx.(x(λuv.v)(λab.a)(λcd.c))
(λx.x)(λuv.v)(λab.a)(λcd.c)

I came up with this confusion through the tutorial: A Tutorial Introduction to the Lambda Calculus by Raul Rojas. There, in page 6, ~T is given as λx.x(λuv.v)(λab.a)(λcd.c). If we apply brackets as in my answer-1, we will not be able to evaluate ~T to F.


texts: Determining whether a relation is the "union" of two other relations

texts:
Given a relations $P$ and $Q$ on $S$, what are the most efficient algorithms to find whether the relation satisfy the constraints $P \cup Q = S \times S$ and $P \cap Q = \emptyset$?

If it helps, for my application the elements of $S$ are strings. Apologies if my question is not up to standard, this is my first question on Stack Exchange and it's been several years since I've done any formal math.


texts: Efficiently map different codes to rotation-different codes

texts:
Let $\mathbb{F}^n_2$ denote the set of $n$-bit 0-1 strings. How to construct an efficiently computable function $f:\mathbb{F}^n_2\to \mathbb{F}^m_2 (m>n)$ satisfying that $\forall u\neq v$,$f(u)\neq f(v)$ and $f(u)$ is not a circular rotation of $f(v)$?

$m$ is expected to be as small as possible.

Thank you very much for your kindness.


texts: Shortest path in weighted(positive or negative) undirected graph

texts:
I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different shortest paths, the algorithm should prefer the one with less edges on it. The time complexity of the algorithm is $O((|V|+|E|) \log |V|)$.

So, I tried:

My first thought was DFS/BFS (the $O(|V|+|E|)$ looks tempting), but (I believe) no modification of these two algorithms works on weighed graphs.
Then I thought about Dijkstra's algorithm - but that one doesn't work on graphs, which can have negative edges.
My last hope was Bellman-Ford algorithm, which could work I guess, but I have no idea, how to rewrite it for undirected graphs.

Any hint is appreciated.


texts: How is Eventual Consistency (EC) better than Strong Consistency (SC) when N = 3, R=W=2 when SC gives better consistency gurantee in same config?

texts:
In dynamo paper, it says that in production most of the users set N = 3, R = 2 and W = 2.

The common (N,R,W) configuration used by several instances of Dynamo is (3,2,2). These values are chosen to meet the necessary levels of performance, durability, consistency, and availability SLAs.

In most production system, N = 3 is good enough as more replicas of data will waste storage. Keeping W and R = 2 will mean that reads will always see the last write mostly.

Strongly consistent (SC) stores also can have N = 3 and R, W = 2 with writes going to one primary for ACID transactions and replicate to (W - 1) active secondary for committing.

Eventual Consistent (EC) stores gives multiple masters for scaling writes rather than one primary in strongly consistent db. However, read which is local in case of SC primary now require network hop to another Replica in EC case.

How is EC better than SC when N = 3, R=W=2 ?

I think that EC stores don't take any locks and wait for others replica confirmation to commit. Hence, they are simpler and faster.

Is this true ? What are the other factors that make EC better than SC when N = 3, R=W=2 ?

What are other production configuration of N, R, W for EC stores when they become better than SC in read world production systems ?


texts: What do we call a function that outputs 0 on half and 1 on the other half of all inputs?

texts: I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying this is the output is one half the time and zero half the time, on average. What is the scientific notation for describing this output scenario?


texts: Why is log(n/p) asymptotically less than log(n)/log(p)

texts:
I'm trying to figure out which is better asymptotic complexity, $O(\log{\frac{n}{p}})$ or $O\left(\frac{\log{n}}{\log{p}}\right)$. $p$ is the amount of parallelism (i.e. number of cores), and $n$ is the problem size. When I plot them in Grapher.app with any constant value for $p$, the first looks better:

But when I try to work out the math it doesn't seem right:

$$
O(\log{\frac{n}{p}}) = O(\log{n} - \log{p})
$$

$O\left(\frac{\log{n}}{\log{p}}\right)$ seems like a better bound than the above since it divides by $\log{p}$ instead of just subtracting it. What am I missing?


texts:
Given a planar graph (represented using adjacency lists) we want to find a set of vertices which are around one (random) face. We know that the graph contains at least one triangle.

How do we find such a face?


texts: What happens when the xor inBlock chaining returns false?

texts:
"With block cipher, each plaintext block is XOR-ed with the previous ciphertext block and then encrypted, this is known as block chaining. This prevents identical blocks of plaintext from producing the same ciphertext each time they are encrypted"

What happens inside the clause of the "XOR" statement, to make two equal plain text blocks encode into two different cipher text blocks?


texts:
I have encountered the term many times, in various CS education materials:

L2 CS162 (UC Berkeley):

  Memory-mapped I/O

L4 CS162 (UC Berkeley):

  Memory mapped files

L24 CS61 (UC Berkeley):

  “Memory mapped I/O”:  Device control/data  registers mapped to CPU
  address space

Even, after googling "mapping", I got the article
Map_(higher-order_function), but it wasn't very clear to me.
Even more, tried to understand the meaning in the context of bitmap by
reading the Wikipedia article:

  A bit array is a mapping from some domain (almost always a range of
  integers) to values in the set {0, 1}

I'm not sure, but in the context above it sounds to me about data
conversion.
Later after reading a CS book, I found only
this paragraph but it didn't explain the meaning of "mapping" for
me:

  Memory Mapping Linux (along with other forms of Unix) initializes the
  contents of a virtual memory area by associating it with an object on
  disk, a process known as memory mapping.

I got also MapReduce as a search result: where map is explained as "an idiom in parallel computing
where a simple operation is applied to all elements of a sequence,
potentially in parallel".

I'm still confused about the term. Can anyone explain what does "map" mean in the contexts I mentioned?


texts: Proving that co-finite languages can be decided in constant time

texts:
I am trying to show that given a co-finite language $A$, $A \in \text{TIME}(1)$.

If $A$ is co-finite, $A$ is regular, so $A \in \text{TIME}(n)$.

I'm not sure how to proceed from here. Any hints?


texts: What is the difference between saying there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time and $n^{2-o(1)}$ or $\Omega(n^2)$?

texts:
I have seen the formulations

there is no ϵ>0 such that a problem can be solved in $O(n^{2-\epsilon})$ time

a problem requires time $n^{2-o(1)}$

a problem requires time $\Omega(n^2)$

being used in the context of lower bounds but I am not sure as to whether there are relevant differences between these notations or if they are simply equivalent. Intuitively, it seems to me like at least the first and third one are while the second one excludes running times like $n^3$ that are included in the others. However, I have also encountered situations where the second one has been used in a similar way to the first one (i.e. the definitions of the Orthogonal Vectors Hypothesis here, p. 6 and here, p. 6) which suggests to me that they are also equivalent. So how do these notations relate to each other?


texts: Need to understand signals received vs sent

texts:
What is meant by in the following statement (from the paper titled "Implementing Lightweight Threads"):

  As in singlethreaded processes, the number of signals received by the
  process is less than or equal to the number sent.

Why is the number received less than or equal to the number sent. I don't have enough background in singlethreaded processes I guess.


texts: The set of all eventually periodic words is not Buchi Recognizable?

texts:
An $\omega$-word $s \in \Sigma^\omega$ is eventually periodic if it is of the form $s = uv^\omega$ for finite words $u, v \in \Sigma^*$.

I want to show that the set of all eventually periodic words is not buchi-recognizable.

I do not know how to proceed. My attempt was to find a part of the word and then pump it indefinitely to get something that is not in the language. However, pumping right away does not seem to work since that would give an eventually periodic string again.


texts: Efficient way to concatenate strings to find specific split up values

texts:
I'm working with a list of objects ("Section") that contains a string value among other fields. The strings in all of the sections can be concatenated to form the complete text. I am, however, wanting to implement a method that searches for a specific (given) value and returns the Section object(s) it found the value in. There are however two different scenarios as described below.

Value: restaurant

Scenario 1

"John went to the restaurant to pick " ✔
"up the food he ordered online before "
"he went to his mother's house."

Current behaviour: Found in Section 1

Desired behaviour: Found in Section 1

Scenario 2

"John went to the restaura"
"nt to pick up the food he ord"
"ered online before he went to his mother's house."

Current behaviour: Couldn't find the value

Desired behaviour: Found in list(Section 1, Section 2)

Scenario 1 is easily solved as the value is found completely in section 1. In the 2nd scenario, the value is never found as it is split up between sections. I have written an algorithm that tries to stitch these sections together. It appears to work when the given value is simple e.g., "car" or "boat". I'm having troubles with compound strings such as "the supermarket" or "a green flower". I wrote the code a couple of months ago and tried debugging it, but even I fail to understand my own code here.

I deliberately left my code out of this post as it has rough hardcoded rules and has extreme levels of code complexity. I'd like to rethink the algorithm without looking at the current one to refrain from blatantly copying sections of the existing code.

The code is written in Java in case anyone knows some handy Java functions that might help.


texts:
I need help on this exercise:
You are given an array of n elements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(n log n).

I find a solution but in O(n^2)... How can I apply D&C?


texts: Can PTAS $\epsilon$ parameter be dependent on the algorithm input?

texts:
Let A be a PTAS algorithm with time complexity $O\left(\frac{1}{\epsilon}\right)$.
Let $n$ be the input of the algorithm A.
From Wikipedia:

The running time of a PTAS is required to be polynomial in $n$ for every fixed $\epsilon$, but can be different for different $\epsilon$.

Can we define $\epsilon$ to be equal to $\frac{1}{n}$?
Thus, the time complexity of A would be $O(n)$, which is polynomial in $n$, but, can $\epsilon$ be dependent on $n$?


texts: What can be said in general about a homomorphism between two regular languages?

texts:
In other words: is a homomorphism always guaranteed to exist between two arbitrary regular languages? If not (which I suspect), are there only a finite number of classes of languages, for which we can find a homomorphisms? And if not that, are there maybe a finite number of families of homomorphisms which divide all regular languages into classes?

My motivation for asking this question is from taking an undergrad course in group theory, and wanting to see if the treatment of polynomials by group theory can be applied to regular languages.


texts: DFA Minimization: Finding all equivalence classes of $\mathsf{R_L}$ for language $011(0+1)^*011$

texts:
How do we find all equivalence classes of $\mathsf{R_L}$ for a language?

Say I'm trying to look for all equivalent classes for the regular language $\mathsf{L}$ is $011(0+1)^*011$.

Here's an example they give us in the book
http://books.google.com/books?id=VEHYzv0GHt8C&pg=PA73&lpg=PA73&dq=ding+du+example+2.51&source=bl&ots=P8gAls0z7f&sig=HIsMb7rcD3hKZHYzi8fYZsyrLQ8&hl=en&sa=X&ei=5N0nUfSoJ6We2gWOv4HYDQ&ved=0CDMQ6AEwAA

ps
The relation $\mathsf{R_L}$ is an equivalent relation.
$\mathsf{R_L}$ on $\Sigma^* as:$
$xRy$ iff $(\forall w)[xw \in \mathsf{L} \Leftrightarrow yw \in \mathsf{L}]$


texts: I'm trying to learn reduction. I have this problem called "even subset sum" that's very similar to subset sum. It's the same problem as as subset sum except that the only numbers allowed are even positive integers. I'm trying to show this problem is NP-hard by reducing the problem subset sum to it but I'm not sure where to start.


texts:
Why is $\log(n!)=\Theta(n\log n)$?

I tried:
$\log(n!) = \log1 + \dots + \log n \leq n \log n \Rightarrow \log(n!) = O(n \log n)$.

But how can we prove $\log(n!) = \Omega(n \log n)$ without Sterling's approximation?


texts: For a balanced binary search tree what is the worst case case time complexity for accessing all elements within a range of nodes?

texts:
I have this question which is asking for the worst case time complexity for a balanced binary search tree, assume the nodes are labeled as integers and we consider a range of [nodex, nodey], nodex<=nodey. And also given that the range has exactly  k nodes, k can be at most n ie. total number of nodes. The question asks what is the worst case time complexity of accessing all the
k nodes in given range. According to my knowledge of Time-Complexiy analysis It must be O(k*log(n)) since there are k elements and each element takes O(log(n)) time in worst case ( since the tree is balanced ) this seems very plausible, However the answer seems to be O(k + log(n)), what am I doing wrong?


texts: Compute 'permutation' like problem with modulo

texts:
Say, I have some permutation or combination formula like this,
$$\frac{n!}{(n-r)!r!},$$
and I want to $\bmod$ the result with some big prime ($10^9+7$ for example).

I already tried with modular operation and multiplicative inverse but failed (I don't quite understand them). Can someone give me some example in code so I can grasp the idea? (I prefer C).


texts: Does this algorithm traverse trees in logspace?

texts:
Does this algorithm traverse trees (correctly) in logspace?

Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree is a connected undirected graph with N-1 edges.

Define nextNeighbor(current, previous):

If current has a neighbor larger than previous, then return the smallest such neighbor.

Otherwise, return the smallest neighbor of current.

Initialize current to the vertex you want to traverse from.

Initialize previous to the largest neighbor of current. (Assume current has at least 1 neighbor.)

Repeatedly call nextNeighbor 2*(N-1) iterations (you'll walk each of the N-1 edges twice). For each iteration, update previous to current and current to the output of nextNeighbor.

Implementation:

Tests
Main function (treeTraverse)
nextNeighbor
largestNeighbor
forEachNeighbor
forEachEdge


texts:
In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the following properties:

the empty set is in $F$;
Each single element set is in $F$;
If $X, Y$ are in $F$, then $X \cup Y$ is in $F$;
If $X, Y$ are in $F$, then $XY$ is in $F$;
If $X$ is in $F$, then $X^*$ is in $F$.

In 4. $XY = \{xy \mid  x \in X \text{ and } y \in Y \}$, what is this product? concatenation product?

In the following link, there is a complete paper
http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1969-3RationalSetsCommutativeMonoids.pdf


texts: How to use PHOG and LPQ features for Emotion Recognition?

texts:
I have a database that consists of PHOG and LPQ features for each image. Now, I wish to train an SVM on these features for emotion recognition i.e SVM classifies the images on basis of emotion in the image.

Please provide a detailed procedure on how to use these features to train SVM.


texts: Complexity of finding a majority element

texts:
I was given a question that is stated that;

  Suppose you’re consulting for a bank that’s concerned about fraud
  detection, and they come to you with the following problem. They have
  a collection of n bank cards that they’ve confiscated, suspecting them
  of being used in fraud. Each bank card is a small plastic object,
  containing a magnetic stripe with some encrypted data, and it
  corresponds to a unique account in the bank. Each account can have
  many bank cards corresponding to it, and we’ll say that two bank cards
  are equivalent if they correspond to the same account. It’s very
  difficult to read the account number of a bank card directly, but the
  bank has 1 a high-tech ‘equivalence tester’ that takes two bank cards
  and, after performing some computations, determines whether they are
  equivalent. Their question is the following: among the collection of n
  cards, is there a set of more than n/2 of them that are all equivalent
  to one another? Assume that the only feasible operations you can do
  with the cards are to pick two of them and plug them into the
  equivalence tester. Show how to decide the answer to their question
  with only O(nlog n) invocations of the equivalence tester.

I proposed an algo for this problem that is like this;

  For the equivalent majority there must be majority of the equivalent
  cards on one side of the n cards if we divide them into two halves. So
  one of the two sides must return one card that has majority more than
  n/2 in whole list.

  Let’s say equivalentTest is the function that takes two bank cards
  and, after performing some computations, determines whether they are
  equivalent.

Function checkMajority(c, M)
    i = count = 0
    While i less than length of M:
        if (M[i] is not actual c) and (equivalentTest(M[i], c) == true) then:
            count ++
        Endif
    Endwhil
    If count is greater than half the length of M then:
        Return true
    Else
        Return false
    Endif

Function divide_and_find(M)
    If M.length = 1
        Return M[0]
    Else if M.length = 2
        If equivalentTest(M[0], M[1]) == true
            Return M[0] or M[1]
    Divide M
    M1 = assign first half
    M2 = assign second half
    c = divide_and_find(M1)
    if c is returned then
        found = checkMajority(c, M)
        If found = true then
            Return c
        Else
            c = divide_and_find(M2)
            found = checkMajority(c, M)
            If found = true then
                Return c
            Else
                Return ‘not found’
            Endif
        Endif
    Endif
    Return ‘not found’

According to my understanding,

  The algorithm complexity is O(nlogn) because we have used divide and
  conquer strategy. There would be (logn) steps and each step would take
  O(n) time for checking the majority. So the complexity would be
  O(nlogn)

But at the same time, I think it will take O(n*n).. that is big O of n square, In worst case scenario. Because then it will check n cards for n cards, to find duplicate cards.

Can any one help me out in resolving my confusion??


texts: We recently in computational complexity class dealt with approximation algorithms and I was wondering how one would prove a heuristic having a certain ratio in regards to the optimal version. Looking at some notes it seems that one has to relate the approximation to an intermediate algorithm, right?


texts: The Absolute Minimum Every Software Developer Absolutely, Positively Must Know about Computer Science (No Excuses!)

texts:
Yes, I borrowed the title form a famous joelonsoftware post for my question because I didn't exactly know how to ask this.

I'm a professional programmer for a few years now and although I followed informatics courses in school there was a lot of stuff missing from the curriculum, as I now know but wasn't aware then. For example I didn't do any compiler theory, algorithm analysis (the Big-O), have no idea what P-NP meant etc.

So I want to catch up now!

But the field of computer science is big. Really big! So from here my question: What's the absolute minimum every software developer absolutely, positively must know about computer science (no excuses!)?


texts: Algorithm for finding roots of a polynomial modulo prime powers

texts:
Given a polynomial $f$ with integer coefficients and a prime power $p^i$, I wish to find a root of $f$ modulo $p^i$, provided one exists, in polynomial or randomized polynomial time in the size of the input.

A simple idea would be to use Cantor-Zassenhaus' algorithm to find a root modulo $p$, and then lift it by Hensel's lemma. But then, this would work only when $f'$ isn't zero. Is there a way where we can get past this barrier?


texts: Finding the $k$th largest element in an evolving query data structure

texts:
Basically, the problem I am solving is this. Initially, the array $A$ is empty. Then I am given data to fill the array and at any time I have to make a query to print the $|A|/3$-th largest element inserted so far.

I was solving the problem with segment trees, but I am not able to make a little modification to the query function of the segment tree. The query function that I wrote returns the largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$:

int query(int Nodenumber,int t_begin,int t_end,int a_begin,int a_end)
{
    if (t_begin>=a_begin && t_end<=a_end)
        return Tree[Nodenumber];
    else
    {
        int mid=((t_begin+t_end)/2);
        int res = -1;

        if (mid>=a_begin && t_begin<=a_end)
            res = max(res,query(2*Nodenumber,t_begin,mid,a_begin,a_end));

        if (t_end>=a_begin && mid+1<=a_end)
            res = max(res,query(2*Nodenumber+1,mid+1,t_end,a_begin,a_end));

        return res;
    }
}

Note to make a query, I call the query function as query(1,0,N-1,QA,QB).

But I want to return the $|A|/3$-th largest element between indices $a_{\text{begin}}$ and $a_{\text{end}}$. So how should I modify the function to do this?

So updating, queries, updating, queries, updating, queries and so on are done randomly and several (upto $10^5$) times.

So, for solving the problem, did I pick the right data structure? I thought of using heaps, but that will be too slow, as I would have to pop $|A|/3$ elements from the top and reinsert them for every query.


texts: Maximum number of inversions that can be removed by swapping two elements?

texts:
I have come across a question that is a bit hard to understand due to its wording, I may havecome up with a possible solution, but I don't know if it's correct. Can you please help me? Thanks in advance!

Question

Suppose we exchange elements $a[i]$ and $a[j]$, where $j > i$, which are originally out of order.

For example, $a = [2,8,3,7,1,5,6]$ and we exchange the second and sixth elements, we have $[2,5,3,7,1,8,6]$.

The array has now fewer inversions. What is the maximum number of inversions that can be removed if we exchange $a[i]$ and $a[j]$?

My proposed answer

Take an array and sort it in reverse order. The first element would have the most inversions. We switch it with the last element and the number of inversions decrease drastically.

The maximum number of inversions would be $j-i+n-2$.

My concern

Since the question doesn't say anything about me being allowed to change the order of the array, I don't know if my proposed answer is the one they were aiming for.


texts: Is there a DFA with $k+2$ states which its reverse has $2^k$ states

texts:
I am trying to figure out if there exists a DFA $M$ with $k+2$ states (for every $k\in \mathbb{N}$ ) so that every automaton which accepts $L(M)^R$ has at least $2^k$ states.
I am trying to find an example of such a DFA, any help?


texts: Greedy and backtracking solutions to an arrangement problem with constraints

texts:
I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class mates but they all seemed to be confused. One gave me a sample answer of code doing it, whereas another one thought he wants some sort of graph with nodes/edges to represent the answer.

  1)
  A group of $n$ teenagers $T_1,\dots,T_n$ are to sit in a single row of $n$
  chairs watching a particularly boring comedy movie. Some
  teenagers quarrel with each other all the time. The problem is
  to devise a seating arrangement for the group in such a way
  that teenagers sat next to each other do not quarrel.

  a) Propose a solution to this problem using the Backtracking
  approach. Specify clearly the search space and any
  pruning conditions used. Show how your algorithm would
  work for 3 teenagers, $T_1,T_2,T_3$, assuming that the only
  quarrelling teenagers are $T_2$ and $T_3$.
  Note: stop the search after finding a solution. [12 marks]

  b) Propose a solution to this problem using the Greedy
  approach. Estimate the complexity of the resulting
  algorithm. [8 marks]

I've spent days going through my notes and reading up on greedy/backtracking but I still don't see how it fits with the question. Whenever I look up Backtracking/greedy approach questions the questions are nothing like how college asks them which makes me very confused...

We've covered dynamic programming, backtracking, greedy algorithms knapsack problem, first fit, next fit minimal spanning trees, Kruskal's algorithm, Prim's algorithm, divide and conquer $N$ queens problem for backtracking.


texts: Hardware implementation of direct mapped , set associative mapped and fully associative cache

texts:
I have consulted many textbooks (Morris Mano, H.P Hayes, Hamacher, William Stallings) but could not find a standard and clear hardware implementation of each of the models of cache organization. It is quite necessary for me to know the logic diagrams of how the comparators, multiplexers and the decoders are used to actually the bring the concept into action. Each textbooks explain the concepts only theoretically with an example, but the actual way the work is done in the hardware is not given. Moreover in few competitive examinations the latencies of  various building blocks like MUX, comparators are given and one is asked to find the hit latency. Now without the proper knowledge of the hardware logic diagram, it is quite difficult to answer such questions.
Could anyone explain me the hardware implementation of the each of the 3 types of cache organization. Does there exit a standard design for each of the following?


texts: Why do we need two variables for implementing kleene star operation on a language using context free grammars?

texts:
I have a Context-Free Grammar (CFG) G which has a S for generating a language L. Now to produce a grammar for L*, another variable T (which is not present in the variable set of G) is taken and the grammar is produced in the following way:
                                 G' = (V, A, T, P)

where,
  G'.V = G.V U {T} (V is the variable set)
  G'.A = G.A       (A is the alphabet here, I was't able to insert the symbol of capital sigma here)
  G'.T              is the starting variable
  G'.P = G.P U { T -> ST | NULL }   (P is a finite relation from V to (A U V)* )

My question is that why can't we use S-> SS | NULL instead of introducing T?
P.S. : This is my first question so apologies for incorrect formatting. Also I am new to Theory of Computation so a basic and simple explanation will help me more. Thank you.


texts:
I need to write a truth table for all possible unique Boolean functions with one input. However, I am confused regarding the word "unique".

I thought about writing down the truth table for a NOT, since it has just one input.


texts: Computing binomial coefficients and factorials modulo a composite number

texts: Does anyone know of a fast algorithm to compute factorials and/or binomial coefficients in general or modulo a composite number in particular (for composite moduli I am interested in the case where the factorization is not necessarily known)  I know that for primes and factorials we can apply Wilson's Theorem but I was wondering if there is also a fast method for composite numbers.  For binomial coefficients I was thinking of using recursion and the addition rule: $$\binom{n}{x} + \binom{n}{x+1} = \binom{n+1}{x+1}$$ somehow but I'm not sure really how to go about it.  Any suggessions?  Thanks.


texts:
Often I see a sentence like this while reading texts on Computational Complexity:

"For this special case of $\text{TSP}$" or

"This is a special case of $\text{SAT}$" or

"$k$-$\text{PARTITION}$ is the following special case of $\text{BIN PACKING}$" or

"$\text{SUBSET SUM}$ is a special case of $\text{KNAPSACK}$" ad nauseam.

What I find missing is the criterium to claim one problem is a special case of another.
What is the necessity of classifying one problem as a special case of another?  Does a special case always carry the complexity class as its  'unspecial' case?

Often this is simply stated with no proof of relation between these problems.

What requirements must be met for a problem to be a special case of another?

How can I prove a new Language for a problem is a special case of an already existing problem?


texts: Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer?

texts:
I'm creating a simple row buffer simulator to go along with a simple cache simulator in order to count hits and misses in the row buffer. Whenever a cache block isn't in the cache I want to go look for it in the row buffers of the main memory and record whether it is present of not.

How accurate would it be to have just one long "row buffer" struct containing all the data found in all the individual row buffers of each corresponding bank in each DRAM chip? Say that each chip has 8 banks, I would then have to create 8 of these extra long row buffers to simulate these chips. This idea is based on the understanding that all these chips work in unison, so that if I want to load the cache block at address 0, the row buffers of bank 0 in each chip would fill with data from addresses starting at address 0 in chip 0, and ending at address 0 + (length of row buffer * number of DRAM chips) in the last chip. It would assume a row interleaved address mapping (with consecutive rows in consecutive banks) for simplicity's sake.

Are there any major misunderstandings about how DRAM works that causes this to be a very bad way to model row buffer behavior or is this a reasonable simplification? I'd also like to underscore that simplicity is the main goal here.

EDIT added clarification on question posted in comments below:
I assume that all the row buffers for banks with ID, say, 0 work together in unison on the same read or write, with all of them containing data for that particular operation. Couldn't I model these 8 row buffers (if I have 8 DRAM chips) as just one very big row buffer? The total size of this combined row buffer would be the length of the normal row buffer*number of DRAM chips. So if I were to a model chips with 8 banks for example, I'd have 8 of these "combined" row buffers, one for each bank.


texts: what is the k-line-connected graph definition

texts: What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems on a 3-connected cubic planar graph and their applications" where it comes without definition. Unfortunately for me I couldn't get the definition from the context given in its authors' proofs.


texts:
I am looking answer for the question: Is every total, convergent function f: N → N is WHILE-computable?
In Wikipedia stand, "Every convergent function is computable." But I have no idea how to implement that to this question. How can I show or disprove this statement?
Thanks!


texts: If an algorithm for $SAT$ runs in $O(n^{\log n})$ time, and if $L$ belongs to $\mathsf{NP}$, is there an algorithm for $L$ that runs in $O(n^{\log n})$ time?