texts: Two-dimensional Range Minimum Query under a constraint

texts:
So, I have trouble understanding and solving the following question:

You are given a 2D array. Design an algorithm that, given two coordinates (each with two indexes ofc), returns the minimum in the rectangle between those coordinates. You know that the number of lines in that rectangle (of each query) is greater than $\frac{n}{3}$. Preparation time should be $O(n^2)$ and query time should be $O(1)$.

Thanks in advance.


texts: How rule 110 would be proven to be universal if the tag system did not exist?

texts:
I was reading about Cellular Automata and I read in this question that
Matthew Cook proved that rule 110 is universal, and that his proof relied upon showing how rule 110 can simulate a tag system.  Is there another method or information that would still prove the universality of rule 110?  In other words, is there another way to to do that without considering tag systems, and if so, can you explain the proof or give a reference to it?


texts: Simulate a regular Turing Machine with one that cannot write blanks

texts: Consider a Turing machine that cannot write blanks. How does one show that such a machine can simulate a standard Turing machine?


texts:
I have $x$ uniform machines that are identical, except that each runs at a different speed; machine $j$ runs at speed $s_j$.  I have $n$ identical jobs.  Each machine can handle one job at a time.  The time to complete a job on machine $j$ will be $1/s_j$ seconds.

I want to prove that the optimal schedule that minimizes $C_\text{max}$ is in fact also an optimal schedule for minimizing $\sum_i C_i$.  Here, $C_i$ is the time when job $i$ completes (under that schedule); $\sum_i C_i$ is the sum of completion times of all jobs; and $C_\text{max} = \max_i C_i$ is the time when the last job completes.  In other words, I want to prove that, when minimizing $C_{max}$ with identical jobs, the optimal schedule is also the optimal schedule for minimizing $\sum C_i$.

How can I prove this?

Or, to put it another way, using the standard notation for scheduling problems, I want to prove that
$$
Q|p_i=1|C_{max} \quad \equiv \quad Q|p_i=1|\sum C_i.
$$


texts: Is the decision problem, for a Turing Machine are there any input strings rejected decidable?

texts:
Given a Turing Machine T, are there any input strings rejected by T. I need to decide whether this is decidable or recursively enumerable. I think it's undecidable, but I'm not sure how to prove it.
My initial approach would be to reduce the Halting Problem as either a string will 1)halt on final state i.e accepted or 2)halt on non-final state and go in a loop
Perhaps, there is another approach involving diagonalization where I can prove that the diagonalization language is finite - how do I do that?


texts: Understanding the basic concepts in memory organisation

texts:
(Before actually proceeding to the question, I want to confess that this is a homework question, please do consider it and help me in improving my understanding a bit more.)

I have recently started learning computer organisation and architecture. I have gained fair understanding for how caches are organised, how mapping between cache and main memory takes place (direct , fully and set-associative mapping), what is a page table(what are pages, blocks etc.), i can that say I have basic knowledge of segmentation , paging, virtual address and physical addresses.( at the basic level ofcourse).

Well I have come across this question:

  A computer has 46-bit virtual address ,32- bit physical address, and a three
     level page table organisation. The page table base-register stores the
     base address of the first level table(t1), which occupies exactly one
     page.Each entry of t1 stores the base address of the page of second level
     table t2. Each entry of t2 stores the base address of the page of the third
     level table t3. Each entry of t3 stores a page table entry (PTE).
     The PTE is 32 bit in size. The processor used in the computer has a 1MB
     16-way set associative virtually indexed physically tagged cache. The cache
     block size is 64 Bytes.

First of all I am facing difficulty in just imagining such type of a virtual computer. can any one help me by giving a simple steps on How to realize such a virtual computer on paper, or just how to understand what is given in the question. What is really asked? How would one represent a computer having a 46-bit virtual address and having three level page table?

  What is virtually indexed and physically tagged cache?

After reading what is given above, I feel that I just know the terms but I am unable to relate them together to solve problems. I will be glad If someone tries to explain how my thought process should be understand and apply these concepts practically to solve such types of problems.

Some questions based on the above paragraph:

What is the size of a page in KB in this computer?
What is the minimum number of page colours needed to guarantee that no
two synonyms map to different sets in the processor cache of this computer?

A good resource where such problems are actually taught to solve will a appreciated. Good articles and views are most welcome.


texts: Difference between dynamic loading and dynamic linking in the OS

texts:
First of all, I saw many answers of this topic in Quora, Stackoverflow, and this site. But, I couldn't definitely understand the difference between dynamic loading and dynamic linking.
What I understood until now is this.

Dynamic loading : system library or other routine is loaded during run-time and it is not supported by OS.
Dynamic linking : system library or other routine is linked during run-time and it is supported by OS.

What I'm confusing is the behaviour of this two concepts. I know that loading occurs after linking like below image. (from Operating System concepts 9th edition, Chapter 8 figure 8.3)

Then, my question is that does dynamic loading is occured after dynamic linking? If I'm wrong, what is the exact difference between two concepts?


texts: Find the shortest string that is not a sub-string of a set of strings

texts:
Alphabet: abc

Sample input:

abc
cba
aabbcc
aaabbbccc
caac

Sample good outputs: acb, cab, cac and others, since they are not substrings of any other, and because all strings of length 1 and 2 are present.

Sample bad outputs:

aab since it is a substring of 3)
aaaa because it is not minimal: we have other solutions with 3 characters only

Questions:

What are the best ways to solve it?
Does the problem have a well known coined name?
What is the complexity of the calculation in terms of the input size (number of strings N and maximum string length M)?
What is the average asymptotic size of the output considering random uniformly distributed inputs?

Related questions:

Algorithm Request: "Shortest non-existing substring over given alphabet" seems to be the case for a single input string. If we can find a trivial reduction we can close as a duplicate.

Applications:

for file uploads, browsers use the enctype='multipart/form-data' encoding. This encoding can send several files in a single HTTP request. Files are sent directly without character encoding, so to separate the files, the browser has to find a string that is not contained in any of the files. I'd like to know how that can be done optimally. See also: https://stackoverflow.com/questions/4526273/what-does-enctype-multipart-form-data-mean/28380690#28380690
apparently this has some interest for bioinformatics, although I know nothing about that domain: https://biology.stackexchange.com/questions/3064/shortest-strings-not-present-in-the-human-genome . There has been some discussion on that question, but the answers there are more heuristic than algorithmic.


texts:
I am reading an article on algorithms for parallel computing and came across the following sentence.  What do they mean by a swap-with-memory instruction?

  Our algorithm provides reasonable latency in the absence of contention, requires only a constant amount of space per lock, and requires no hardware support other than a swap-with-memory instruction.

J. M. Mellor-Crummey and M. L. Scott, Algorithms for Scalable Synchronization on Shared-Memory Multiprocessors. ACM Transactions on Computer Systems, 9(1):21–65, 1991. (PDF)


texts: Google Deep Dream has these understandings?

texts:
From both my own exploration of Google Deep Dream using Dreamify for IOS, and from Google Image results on the topic. I've come to 3 conclusions about the networks understanding of images that seem too common to be coincidences.

I would like to know if these are recognised as consequences of the approach, or otherwise to what degree thease properties are imagined while trying to understand the ambiguous high frequency images the Deep Dream algorithm often produces?

3 dimensional understanding of real and dreamt objects, including rotation, occlusion (close things covering distant things), reflections etc...
Understanding of how objects group and are arranged allowing deep dream to create believable landscapes, settlements and narrative and physical interactions, including between people.
Objects (including people) being thematically/stylistically designed to fit a scene.

For example:

https://photos.google.com/share/AF1QipNgj7mRqnzW5G2D7ty3Sqb_ZITjnBQZA23RH71691sSNVGBvUTVmdSCzb_3b360xQ?key=SHpzeTVRbHk4SHFhUmMtRXVPRGxuMGRnd2xrM1dn


texts: A string that takes a DFA from any state to a given state?

texts:
EDIT: as templatetypedef commented, this problem is to find out if a DFA has a synchronizing word (a.k.a. "reset sequence").

Given a finite state set $Q$, a finite alphabet $\Sigma$, and a transition function $\delta : Q \times \Sigma \rightarrow Q$, I want to find out if there is a state $q_f \in Q$ and a string $s \in \Sigma^*$ such that for every state $q_0 \in Q$ (including $q_f$), the DFA $\left( Q, \Sigma, \delta, q_0, \left\{ q_f \right\} \right)$ accepts $s$. ($q_0$ is the initial state; $q_f$ is the only accepting state.)

In other words, if you think of a string as a list of directions for navigating the DFA, I want to find out if there is a list of directions that takes you to the same state no matter where you started. (Knowing the existence is enough; I do not need to know the state or the string itself.)

I have tried this algorithm:

Reverse the transitions in $\delta$ to form an NFA.
Convert the NFA into a DFA where each state corresponds to a subset of the NFA's states.
For each state $q \in Q$, search the new DFA for a path from $\left\{ q \right\}$ to $Q$. (I just do a depth first search.)
Iff one of these searches is successful, then the answer to the question is "yes".

This algorithm is correct, but it runs in exponential time and space, and it takes too long to complete. (My input DFAs have tens of states.) Note that I do not actually construct a DFA from the NFA -- instead, I perform the search on the NFA and I remember which subsets of its states I have visited.

Is there a way to improve my algorithm? Are there other algorithms to solve this problem? (Or at least, algorithms that would be useful?) Are there any properties of automata and regular languages that I can take advantage of?


texts: Is it possible to compute -12 (decimal) in 4 bits binary

texts:
This is what I have so far

1 1 0 0

Switch values by 2s Complement

0 0 1 1
+     1

0 1 0 0


texts: Does a PDA immediately accept if at final state with empty stack?

texts:
If computation on a PDA reaches a final state with an empty stack, will it immediately accept, regardless of whether or not the input tape has ended. For example if I have a PDA to recognize the language of strings where $a^nb^n$, if it was fed the string "aaabbba", will it stop after seeing the last "b" if the stack were empty and it was in an accept state? Or would the PDA, need to specify a dead state from the final state for incorrect strings?

For example, this PDA would seem to accept "aaabbba":


texts: Intuitively I think the answer is no since I don't think every certificate can be checked in polynomial time but I don't know how to give a formal proof. Is the statement true? Why or why not?


texts: Creating Random Number Generator with range

texts:
I've been trying to create my own random number library(in java). I've searched for randomization and Blum Blum Shub algorithm looks good. It needs a start value, it is not actually random. So i get unix timestamp mod(10) for first value. Now i can generate random numbers. My question is; how can i modify my structure with range? I mean, i want to generate that numbers in a range. (I don't want to use java's another classes or functions) Any advices? Thanks in advance.

EDİT:I coded $\ x(n+1)= x(n)^2mod(M) \\$ formula and gived x(0) unix timestamp's last digit and M=191. So i get random numbers with Blum Blum Shub. But i want to get that numbers in a range. It is not about my code. It is about the formula and method actually.


texts: Parallel single source shortest path algorithm

texts:
Is there a deterministic parallel single-source shortest path algorithm (for graphs with non-negative edge-weights) that runs in sublinear time? The number of processors may depend on $n$ or $m$ (i.e., the number of vertices or edges) and the total work time may be worse than $O(m + n\log n)$.

The most suitable algorithm I found is the one of Han, Pan, Reif in the paper "Efficient Parallel Algorithms for Computing All Pair Shortest Paths in Directed Graphs". They present an algorithm for the all pair shortest path problem that runs in $O(\log n \log\log n)$ time in the CRCW model (concurrent read, concurrent write; that's okay for my scenario) and uses $O(n^3/(\log \log n \log^{7/6} n))$ processors.

Although the running time is perfect, I wonder if the number of processors or the total work time can be improved when restricting to the single-source shortest path problem. However, I didn't find anything comparable. There are many non-deterministic algorithms running on random graphs and many variations of the Dijkstra algorithm with linear running time.


texts: Simplifying an upper O-bound in two variables

texts:
I have an algorithm that depends on two input sizes n and m. The complexity breaks down to the following equation:

$\frac{nm - 1}{n-1} = O(?)$

Is Big-O of the Formula $O(mn)$ or $O(m)$ because $n$ cancels out? Thank you in advance!

PS: I know that if $O(m)$ is the upper bound $O(mn)$ is an upper bound too, I want to find the tightest.


texts: What's an example of an unsatisfiable 3-CNF formula?

texts:
I'm trying to wrap my head around an NP-completeness proof which seem to revolve around SAT/3CNF-SAT.

Maybe it's the late hour but I'm afraid I can't think of a 3CNF formula that cannot be satisfied (I'm probably missing something obvious).

Can you give me an example for such formula?


texts: How can I find the Myhill-Nerode classes for the language A?

texts:
I have the following task (no homework).

  Find all equivalence classes of the Myhill-Nerode relation of the language $$ \mathrm{A} \triangleq\{w \in \Sigma^{*} | w\text{ does not end with }01\}\,. $$

Because I have no Idea how I to find does classes -I know the theory, but I can't use it -.
So I build a DFA (what i should not do):

Now I know there has to be 3 different classes (because the DFA is minimized), but again, I have no idea how to find them.
I hope you can help me a little bit, because I write a test paper in 5 weeks and this will be a big Troublemaker.


texts: Why is the Mean Time To Failure of multiple disks calculated via division and not multiplication?

texts:
I am reading about disk redudancy.
I read the following:

  Suppose that the mean time to failure of a disk is 100,000 hours. Then
  the mean time to failure of some disk in an array of 100 disks will be
  100,000/100 = 1000 hours

I don't understand this. Why isn't it 100,000^100 instead?
Then the same textbook says in the next paragraph concerning 2 mirrored disks:

  If the mean time to failure of a single disk is 100,000 hours and the
  mean time to repair is 10 hours then the mean time to data loss is
  (100,000^2)/2*100

Now here it multiplies for the 2 disks but before the MTTF was divided.

Can anyone please help me figure out how we calculate this.
In case it matters the text book is Database Concepts from Silberschatz 4th edition paragraph 11.3.1 (Improvement of reliability via redundancy) page 403


texts:
I have a matrix $P \in M_n(\mathbb N)$, where

$$ P =
\begin{bmatrix}
0 &  P_{12}  & \ldots & P_{1n}\\
P_{21}  &  0 & \ldots & P_{2n}\\
\vdots & \vdots & \ddots & \vdots\\
P_{n1}  &   P_{n2}    & \ldots & 0
\end{bmatrix}$$

with $P_{ii} = 0$ for all $i \in \{1,2,\dots,n\}$. I need to find matrices $A, B \in M_n(\mathbb N)$ that satisfy $A + B = P$ and that satisfy the following constraints

$$\forall i\in [\![ 1,n]\!] \sum_{k=1}^{n} A_{ik} = \sum_{k=1}^{n} A_{ki}$$

such that $\sum_{i=1}^{n} \sum_{k=1}^{n} A_{ik}$ is maximized.

I need to implement an algorithm to solve this problem. On my input data I have approximately: $ n = 16 $  and  $ \sum_{i=1}^{n}\sum_{k=1}^{n} P_{ik} = 60000 $  so the brute-force approach is out of question.
I don't know what could be a good approximation algorithm so my current approach is to reduce the problem to a binary integer programming problem and then apply Branch-and-Cut but I have serious doubt on it effectiveness for this specific problem.

Finding the optimal solution in polynomial time would be perfect (not sure if it's possible), but I can satisfy myself with a good approximation algorithm. Not having a strong background in CS I'm a bit confused, help would be greatly appreciated !


texts: Time complexity of finding duplicates across multiple lists using hashing

texts: If I have m lists with n elements each, how would I go about finding duplicates in them (i.e. an element is in more than one of the lists)? My idea is to use hashing on the elements inside the list, which involves a O(1) hashing call on each of the elements and checking for collisions inside the buckets. However, on top of that, I would like to know which lists do not have any collisions with other lists (i.e. for each list, I would like to know with which other lists the intersection of their elements will be null). I am just wondering if another level of hashing is required, or perhaps using some other algorithms and data structures. Thanks.


texts: Possibility of using loops instead of traps

texts:
Draw DFA for the language of all strings starting with $a$ and ending with $b$.
Now what I have done is

Here I used q3 as a trap.
But could I do this instead?

I have not used trap in the 2nd solution and used a self loop instead.


texts: I need a hint for writing a context-free grammar for the language $L=\{1^k0^{2k}:k\in \mathbb N\}$. I'm starting to doubt that it can be done for general $k$.


texts: Comparison Procedure in Robinson's Unification Algorithm

texts:
I'm studying the Principal Type (PT) Algorithm in Basic Simple Type Theory by J. Roger Hindley.
One step to find the PT of a term is the Unification of types. The Robinson's Unification Algorithm uses a comparison procedure like as follow:

Comparison Procedure

Given a pair $(u, v)$ of types, write $u$ and $v$ as symbol-strings, say

$u \equiv s_1 ... s_m$ and $v \equiv t_1 ... t_n$ $(m, n >1)$

where each o f $s_1,... , s_m$, $t_1, ... , t_n$ is an occurrence of a parenthesis, arrow or
variable.

If $u \equiv v$, state that $u \equiv v$ and stop.

If $u \not \equiv v$,  choose the least $p < \min(m, n)$ such that $s_p \not \equiv t_p$;
 it is not hard
to show that one of $s_p$, $t_p$, must be a variable and the other must be a left
parenthesis or a different variable. Further, $s_p$ can be shown to be the leftmost
symbol of a unique subtype $u^*$ of $u$. (If $s_p$ is a variable, $u^* \equiv s_p$.) Similarly
$t_p$ is the leftmost symbol of a unique subtype $v^*$ of $v$. Choose one of $u^*, v^*$ that is a variable and call it $a$. (If both are variables, choose the one
that is first in the sequence given in Definition 2A1.) Then call the remaining
member of $(u^*, v^*)$ $\alpha$; the pair $(a, \alpha)$ is called the disagreement pair for
$(u, v)$.

My issue is with the Note bellow:

3D5.1 Note To prove that $p$ exists in the case that $u \not \equiv v$ in the comparison
procedure we must show that it is not possible to have

$t_1 ... t_n \equiv s_1....s_m t_{m + 1} ... t_n$

with $n > m$. This is left as a (rather dull) exercise for the reader.

I disagree with this note. I can image, say, $u \equiv a \rightarrow b$ and $v \equiv a  \rightarrow b  \rightarrow c$, where no $p$ is possible.

Maybe I'm missing something!
How $p$ is always possible?

As asked, the definition of types is given as follow:

2A1 Definition (Types) An infinite sequence of type-variables is assumed to be given,
distinct from the term-variables. Types are linguistic expressions defined thus:

i.   each type-variable is a type (called an atom);

ii. if $\delta$ and $\rho$ are types then $(\delta \rightarrow \rho)$ is a type (called composite type).

2A1.1 Notation  Type-variables are denoted by "a", "b", "c", "d", "e", "f", "g", with
or without number-subscripts, and distinct letters denote distinct variables unless
otherwise stated.

Arbitrary types are denoted by lower-case Greek letters except $\lambda$.

Parentheses will often (but not always) be omitted from types, and the reader
should restore omitted ones in such a way that, for example,

$\rho \rightarrow \sigma \rightarrow \tau \equiv (\rho \rightarrow (\sigma \rightarrow \tau))$

This restoration rule is called association to the right.


texts: If a problem $A$ is poly-time reducible to a problem $B$ ($A <_\mathrm{p} B$), and $B$ can be solved in time $O(n\log n)$, can $A$ also be solved in time $O(n\log n)$?


texts: finding third functional dependency and its candidate keys

texts:
i'm solving a multi part question regarding candidate keys and functional dependencies.

now i've already found 2 dependencies(the canonical covering of the functional dependencies contains only 3 dependencies) in the previous parts of the question:  $D\to BE, CE \to AD$ ($R=A,B,C,D,E$, R is in BCNF). how can i find the third and last one? i need to find in order to figure the candidate keys

(didn't post the previous part of the questin because they're irrelavant, just posted what i found and all the needed information from the question).

thank you very much for your help!


texts:
I'm confused on the definition of undecidable languages.

Definition: For an undecidable language, there is no Turing Machine which accepts the language and makes a decision for every input string w.

Can you say a language that isn't recognizable as undecidable?

If given a language like

$L = \{\langle M \rangle \mid M$ is a turing machine with more than 50 states i.e. $|Q| > 50 \}$

I have to give an undecidable language T such that $T \subseteq L$.

A language that is a subset I think would be

$L_2 = \{\langle M \rangle \mid M$ is a turing machine with more than 60 states i.e. $|Q| > 60 \}$
because if $\langle M \rangle \in L_2$, then $\langle M \rangle \in L$. Hence, $L_2 \subseteq L$

But I'm confused on the undecidable part. How do I justify if this language is undecidable or if it even is?


texts:
Let TOT be the set of all Turing Machines that halt
on all inputs.
Find a computable set B of ordered triples such that:

TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B]

This definition means that TOT is a set of all Turing machines e such that they halt on all inputs. The "for all" x denotes all inputs to that machine, and "there exists" a y denotes that e halts under y steps.
x consists of 0s and 1s, y and e are Natural numbers too ( e denotes Turing machine $T_e$ if we were to number all our turing machines)

EDIT: SOLVED


texts: In flow networks, may source/sink have incoming/outgoing edges?

texts:
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?

Flow-networks are always pictures with no edges entering source, and no edges leaving sink.

I've tried to search the web for an answer, but did not come across an answer i fully understand. Also, I've yet to see a flow network pictured with these edges from source/sink.

Could I transform an undirected graph into a flow-network ? This network will have edges going into source and edges leaving sink ?? This hypothesis is the reason for my question.


texts: I have an acyclic edge-weighted graph and have used Dijkstra's Algorithm with topological sort to find any shortest path to every other node from a root $s$. This is performed in time proportional to $V + E$, where $V$ is the number of vertices and $E$ the number of edges. I have $V= N^2$ vertices in my graph. Now suppose I remove $N$ vertices (for now lets assume at random, in reality there is a pattern). If I want to find shortest paths for my new graph, is there any information from the first computation that I can cache to speed things up?


texts: an appropriate data-structure to represent a family of sets (Which supports exactly MAKE-SET(x), UNION(S1,S2), REPORT(S))

texts:
I need to represent a family F of sets with some appropriate datastructure. The datastructure needs to support the procedures MAKE-SET(x), DISJOINT-UNION(A,B) and REPORT(A). I dont have a problem with implementing the procedures themselves. Its pretty straightforward if you follow the idea introduced in the chapter on disjoint-set data-structures in Introductions to Algorithms (CLRS for short). My problem is, in this book there is an added procedure Find(x), that, given any member of F, finds the set it belongs to by returning a representative of its set. But i am not meant to implement this procedure. So how exactly am i supposed to represent the family F? I figure we need some way of representing this collection seeing as otherwise what we have is just loose and unassociated sets. What do i do?

if it serves any interest here is the original problem statement:

  We are interested in maintaining a family of sets of  integers F = S1, …, Sk under the following operations:

  •  MAKE-SET(x ): add the set {x} til F

  •   REPORT(Si ): report (ex. print) all elements in Si.

  •   UNION(Si , Sj ): add the set Si ∪ Sj to F . delete Si og Sj from F.

  •  DISJOINT-UNION(S1, S2): Like UNION except it is assumed Si and Sj are
      disjoint, meaning., Si and Sj do no share any elements. If Si and Sj are not
      disjoint the result of the operation is not defined.

  4.1. Come up with a datastructure, which supports MAKE-SET and DISJOINT-UNION in
       O(1) time and REPORT(Si ) in  Θ(|Si|) time.
       Hint: use an appropriate list datastructure


texts: Star-free decomposition of regular language given by regular expression

texts:
I was wondering: is there an algorithm to decompose any regular expression, provided it doesn't use complementation, into one or more regular expressions which don't use Kleene star (only catenation and union).

Right now I'm reading On the Decomposition of Finite Languages by A. Mateescu, A. Salomaa and S. Yu, but this paper doesn't seem to discuss this problem, but that's where I get the idea.


texts: tightest upper bound on binary search tree insertion?

texts:
The upper bound on the runtime of binary search tree insertion algorithm is O(n) which is if it is not balanced
What will be the tighter upper bound on this,will it become O(logn)
I have read that tighter upper and lower bounds are often equivalent to the Theta notation.


texts:
First - I've seen and thoroughly read all the similar questions. None of them solves my problem. I've read them all, and seen lectures and asked my Prof but no one was able to answer. They all at most give a mathematical answer, but can't give a real example.

In CLRS 3ed pg 155 we have "The running time of MAX-HEAPIFY on a subtree of size n rooted at a given node i is the $\Theta(1)$ time to fix up the relationships among the elements $A[i]$, $A[LEFT(i)]$ , and $A[RIGHT(i)]$, plus the time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i (assuming that the recursive call occurs). The children’s subtrees each have size at most $2n/3$ - $\textbf{the worst case occurs when the bottom level of the tree is exactly half full}$ — and therefore we can describe the running time of MAX-HEAPIFY by the recurrence $T(n) \leq T(2n/3) + \Theta(1)$.

I understand why the maximum nodes a subtree can have is around $2n/3$. I have two questions:

1) We're dealing with a heap - a  "binary tree that is completely
filled on all levels except possibly the lowest, which is filled from the
left up to a point" (CLRS pg 151). For a given n, there's only one legal tree structure - we can't "make" its bottom level exactly half full. So what does it mean to say the worst run-time for n is when the bottom level is exactly full? If you mean that the worst-case happens when n is such that the bottom-level is half-filled, then it's worse in comparison to what? trees of other sizes? obviously different sizes have different run-times!

2) I understand why when there's a height difference it'll take another MaxHeapify call, but why does the bottom level have to be full? Can you give me an example of two trees of height larger than 1, where in one its bottom level is half-full, and in the other it's almost half-full (missing just one leaf from being half-full) and there's a worse run-time in the first one?


texts: Pumping lemma with multiple of prime number + a constant

texts:
Given the language
$$L = \big\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\} $$
show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be userful the pumping lemma of the language of prime numbers, you can find it here.

A counterexample must be a string $z \in L$ whose length $|z|$ is greater than a generic h such that for any the decompositions $uvwxy=z$ with $|v|+|x|\ge 1$ and $|vwx|<h$ exists an i such that $uv^iwx^iy \not\in L$. Generally we have to find a contraddiction of $|v|+|x|\ge 1$ or $|vwx|<h$.

There are five possible decompositions of the string. The only required case is the one with $v$ completely in the first part of the string and $x$ completely in the second part.

Now follows some failed attempts:

This one was posted as answer I deleted because incorrect. I took as string $z = 0^{2h}10^{5h}$ which is in the language for $m = 2h$ and $k = h$. The problem here is that $m$ is prime, so $m = 2h \iff h = 1$ which means $h$ is not a generic length anymore. Here it follows the incorrect attempt:

   $$ uv^iwx^iy = 0^{2h + |v|(i-1)} 1 0^{5h + |x|(i-1)} = 0^{m} 1 0^{2m+k} \in L $$
 The equation has solution iff has solution the system
 $$ \begin{cases} 2h + |v|(i-1) = m, m \text{ prime} \\ 5h + |x|(i-1) = 2m + k \\ \end{cases} $$
 For $i = h + 1$ we have $$ 2h + h|v| = h(|v| + 2) = m $$ But $m$ cannot be prime because it's a moltiplication of two terms $h$ and $(|v| + 2)$. Contraddiction!

We need to choose $m$ as something like $h$ or $ah + b$ in order to avoid this issue.
I took as string $z = 0^h 1 0^{2h+1}$ which is in the language for $m = h, k = 1$. We have
$$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{2h + 1 + |x|(i-1)} $$ We have to solve the system
$$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\
    2h + 1 + |x|(i-1) = 2m + k\end{cases} $$

Trying with $i = h + 1$ does not work: the first equation becomes

  $$ h + h|v| = h(1 + |v|) = m \text{ prime} \iff |v| = 0$$
  so the second equation results in
  $$ 2h + 1 + h|x| = 2h + k \Rightarrow |x| = \frac{k-1}{h} $$
  so the string results in $0^{m} 1 0^{2m+k} \in L$ with $m = h$, $k = h + 1$ from the decomposition with
  $$ |v| = 0 \qquad |x| = \frac{(h+1) - 1}{h} = 1$$

Trying with $i = 0$ leads to

  $$ \begin{cases} h - |v| = m \\ 2h + 1 - |x| = 2m + k \end{cases}$$
  which results in
  \begin{align*} 2h + 1 - |x| &= 2h - 2|v| + k \\ 2|v| - |x| &= k - 1 \end{align*}
  which results in as many string $\in L$ as you want (for example $k = 3, |x| = 0, |v| = 1$ gives $0^{h-|v|} 1 0^{2h-2|v|+1} = 0^{h-1} 1 0^{2h-1} \in L$)

I took the string $z = 0^{h} 1 0^{3h}$ which is in the language for $m = h, k = h$. We have
$$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{3h + |x|(i-1)} $$
We have to solve the system
$$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\
    3h + |x|(i-1) = 2m + k\end{cases} $$

Trying with $i = h + 1$ we have

  $$ h = m \qquad |v| = 0 \qquad 3h + h|x| = 2h + k$$
  which results in $ |x| = \frac{k}{h} - 1$; then we can take $k = 3h$ so $|x| = 2$, and the result is the string $0^{h} 1 0^{4h} \in L$

As you can see, I can't find a combination of string and $i$ that generates a contraddiction. How would you proceed?


texts: Multilayer perceptron memory requirements

texts:
How much memory do we need to train a multilayer perceptron?

I've started to figure this out myself, but I'm stuck.

I have one-layer MLP. Each training example is a vector of 100 real numbers in float32. There are 1000 training examples. The hidden layer is 50 units. The output layer is 10 units.

Karpathy's excellent blog gives me a starting point.

Weights and biases from input to hidden: (100 x 50) + 50 = 5050

Weights and biases from hidden to output: (50 x 10) + 10 = 510

Total = 5560 parameters

To store the parameters, I'll need (5560x4)/(1024^2) = 0.019 MB

I have minibatches of size 100, so I need to read 100 examples at a time into memory:

(100 x 100)x4/(1024^2) = 0.038 MB

I think I'll also need to store:

the gradients of the activations
the gradients with respect to the weights (?)
the step cache (since I'm using momentum)

I'm using rmsprop as the optimizer.

Do I need to store the gradients of the activations AND the gradients of the weights? How much memory do these require? How about the step cache? Am I missing anything?


texts: Error Detection Distance of Residue Codes

texts:
Given a residue code representing a number N with the tuple (N, R(N))where R(N) equals N mod A.

What is the error detection distance of a certain check base A? In other words, how many bits can be flipped but still detect an error?

Edit:
I would think the minimum distance is 2 for any base. Consider a base A > 2. If N equals 1, R(N) also equals 1. If we now look for for N+1 = 2, R(N) equals 2. The Hamming distance between those residue tuples is HD((1, 1), (2, 2)) = 2, which cannot be better.


texts: Knapsack-like problem oriented on contiguous selection

texts:
Problem inputs is an ordered array $A = [a_1, a_2, \ldots, a_n]$ with $\text{weight}(a_i) = w_i$.
We define a $subgroup$ of $A$, denoted by $B$, whose elements' indices are continuous in integer. For example, if $A = [a_1, a_2, a_3, a_4, a_5]$, then $[a_2,a_3, a_4]$ is a subgroup of $A$, while $[a_1, a_3, a_4]$ is not. And we say a $subset$ of $A$ is a collection of non-overlapping subgroups of $A$.
Our goal is to find a subset $\mathcal{S}$ with $k$ elements in $A$, such that total weight $\displaystyle\sum_{s \in \mathcal{S}}\text{weight}(s)$ is maximized, while the number of subgroups is less than a given $m$. For example, suppose the corresponding weights of elements in $A$, $[8,1,6,2,7]$ and $k=3$, $m=2$, then the optimal is $\{[a_1], [a_4, a_5]\}$.


texts: Creating a binomial heap from an array in Θ(n) time

texts:
I'm studying binomial heaps. A book tells me that insertion of a node to a binomial heap take $\Theta(\log n)$ time. So given an array of $n$ elements it would take $\Theta(n \log n)$ time to convert it to a binomial heap.

Does anyone know a method that can convert an array of numbers to a binomial heap in $\Theta(n)$ time? Wikipedia claims that insertion takes $O(1)$ amortized time but I need to refer to the worst case.


texts:
Lately, I saw an NP-complete proof that involves creating an instance of a problem using $\infty$. Is this a polynomial-time reduction?

More precisely, let a problem $\Pi$ has an instance $I=(n, A, v)$ where $A$ is a matrix of size $n\times n$, $A=[a_{ij}]$, and $v$ is positive.

The proof that $\Pi$ is NP-complete works by reducing the independent set problem (an instance is a graph $G=(V,E)$ and an integer $k$) to $\Pi$ as follows: $n=|V|,v=k$ and

$$a_{ij} = \begin{cases}
\infty \text{ if } \{i,j\}\in E\\
0, \text{ otherwise }
\end{cases}.$$
Also, $G$ has an independent set of size $k\iff\Pi$ has a value $v= k$.

I do not see how one can set $a_{ij}$ to $\infty$.


texts:
I recently read that it is possible to have arrays which need not be initialized, i.e. it is possible to use them without having to spend any time trying to set each member to the default value. i.e. you can start using the array as if it has been initialized by the default value without having to initialize it. (Sorry, I don't remember where I read this).

For example as to why that can be surprising:

Say you are trying to model a  worst case $\mathcal{O}(1)$ hashtable (for each of insert/delete/search) of integers in the range $[1, n^2]$.

You can allocate an array of size $n^2$ bits and use individual bits to represent the existence of an integer in the hashtable. Note: allocating memory is considered $\mathcal{O}(1)$ time.

Now, if you did not have to initialize this array at all, any sequence of say $n$ operations on this hashtable is now worst case $\mathcal{O}(n)$.

So in effect, you have a "perfect" hash implementation, which for a sequence of $n$ operations uses $\Theta(n^2)$ space, but runs in $\mathcal{O}(n)$ time!

Normally one would expect your runtime to be at least as bad as your space usage!

Note: The example above might be used for an implementation of a sparse set or sparse matrix, so it is not only of theoretical interest, I suppose.

So the question is:

  How is it possible to have an array like data-structure which allows us to skip the initialization step?


texts: Find the 'best' longest common subsequence

texts:
I am writing a program that computes and displays diffs. I implemented Meyers algorithm that computes the LCS between 2 subsequences (seq1 and seq2); its output is one of the possible LCS and a partition of seq1 and seq2, one projection of which is lcs.

I want to improve it so that the LCS displayed minimizes the number of breaks; to do so, I implemented a function f(lcs, seq):

seq is a sequence of characters
lcs is a subsequence of seq
the output is a partition of seq p0, p1, p2, ... pn such as

either p0 + p2 +  or p1 + p3 + ... is lcs
and n is minimal

I did so using some sort of BFS, at each step finding the next element non-covered in lcs in seq and greedily expanding the common part.

The resulting algorithm is quite slow: on a typical input, ~3x slower that the Myers algorithm which seems to compute something way more complex.  See code here: https://github.com/mookid/diffr/blob/c9ed7746193fd9833ddce1237d6e5005e91deaf4/diffr-lib/src/best_projection.rs

Am I missing a better algorithm?


texts: If $NTime(2^n) \subseteq DTime(n^n) $, then what can you conclude about $DSpace(n^n)$?

texts:
Assume $NTime(2^n)\subseteq DTime(n^n)$, what can you conclude about $DSpace(n^n)$?
I don't know if this is the correct approach, but here was my attempt at an answer:

Let $A \in DSpace(n^n) $ and define language $B= \{
<x,0^{log(|x|^{|x|}) - |x|}> : x \in A  \} $.  Define a machine $M_B$
that receives input $y$, checks it's of the form  $y= <x, 0^{log(|x|^{|x|}) - |x|}> $, and if so simulates the $DSpace(n^n)$
machine on $x$. Then $M_B$ decides B in
$DSpace(|x|^{|x|})=DSpace(2^{|y|})$, and so by assumption there exists a
machine $M'_B$ that decides $B$ in $DTime(n^n)$.
Now we can define a machine $M'_A$ that receives input $x$, builds $y= <x,0^{log(|x|^{|x|}) - |x|}> $, and calls $M'_B$. Then for input length $n$, $M'_B$ runs in time $O(log(n^n))+O((n \cdot log(n))^{n \cdot
 log(n)}) = O((n \cdot log(n))^{n \cdot log(n)})$. Since $n \cdot log(n) = O(n^2)$, we can say that $M'_B$ runs in $O((n^2)^{n^2})=O(n^{n^2})$. Thus, we can say that $NTime(n^n) \subseteq DTime(n^{n^2}).$

I still have trouble when using the padding argument in various questions (e.g., "if $NTime/NSpace(f) \subseteq DTime/DSpace(g)... $), so I don't know if I made a mistake or if there are stronger claims that can be made.
Also, correct me if I'm wrong, but is it true that if we have $NTime(n) \subseteq DTime(n^c)$ for some constant $c$, then $P=NP$? If so, then does the same conclusion hold if we have $NTime(f(n)) \subseteq DTime(n^c)$ for some function $f(n)>n?$


texts:
Let $ C $ be a reed solomon code with length $6$, dimension $2$ and distance $5$.
Suppose that we are over $\mathbb{F}_7$ and we have the genrator polynomial $g(x)=(x- \alpha)(x- \alpha^2) (x- \alpha^3) (x- \alpha^4)$, where $\alpha=3 \in \mathbb{F}_7 $.
We get the word $r(x)=x^5+6x+4$ and we want to find the word that was sent.

I found the syndrome:$ S(z)=2z^4+4z^3+6z^2+6z$.

We are looking for the error locator polynomial, that is defined as follows:

$$ \sigma(z):= \prod_{j=0}^{l-1} (1- \alpha^{i_j} z) $$

for $ e(x)=x^{i_0}+ x^{i_1}+ \dots+ x^{i_{l-1}}$.

The degree of $\sigma(z)$ is equal to the number of errors that are done.

The code can correct till $ \lfloor \frac{d-1}{2}\rfloor=2 $ errors.

So $ \sigma(z)=(1- \alpha^j z)(1- \alpha^k z)$.

It holds that $ z^5=(2^4+4z^3+6z^2+6z)(4z+6)+(z^3+3z^2-z) \Rightarrow z^3+3z^2-z=(1-4 z) S(z) \mod{z^5}$.

So $w(z)=z^3+3z^2-z$ and $\sigma(z)=1-4z $, where $ w(z)= \sum_{i \in E} e_i \alpha^i  \prod_{j \in E \setminus{\{ i\}}}(1- \alpha^j z)$.

$E=\{0 \leq i \leq n-1 | e_i \neq 0 \} $.

Since we have found that  $ \sigma(z)=1-4 z$,it means that there is one error.

But then  $w(z) $ is of the form $ e_j \alpha^j z $.

But I have found that $w(z)=z^3+3z^2-z $.

What have I done wrong?


texts: Minimum spanning tree such that one edge can be minimised

texts:
During a computer coding exam, I have encountered such a problem.

Given a list of vertexes and edges between the vertexes,and a positive number, D, what is the minimum spanning tree between the vertexes such that the sum of the lengths of the edges is minimal, provided that you may subtract any one edge of your choice in the tree by the positive number D and reduce the weight of that edge to max(0, weight-D)?

I know that Kruskal's and Prim's algorithm can all be used to solve the first part of the problem, the minimum spanning tree, and I can do it. However, I have been struggling hard for the second part, as I don't know how to minimise the weight of the tree given the number D.


texts: Practicality of compressing data with hashing algorithms

texts:
I want to compress the string 0cc175b9c0f1b6a831c399e269772661. I can do so by storing the string a, and, when decompressing, using a as input for the MD5 hash algorithm to get the original string.

I realize it's impossible to represent $2^{128}$ possible strings with inputs less than 128 bits long, even if MD5 had no collisions. However, a percentage of 128 bit strings could still be compressed using this concept.

Maybe another hash algorithm could be made with this application in mind. It does not need to be secure, irreversible, or computationally difficult. It just needs to represent the largest number of output strings given a string who's length is smaller than the output.

Multiple hashing algorithms could be used to increase the number of possible strings that could be compressed.

Is this idea practical? Could this idea be applied to compress large chunks of arbitrary data such as a file?


texts:
I was calculating the time complexity of the following recurrence relation given that T(1) = 1 :

T(n) = 2T(n/2) + Logn

I was calculating the value and this is where I reached:

T(n) = logn + 2log(n/2) + 4log(n/4) + 8log(n/8) + .....+ 1

I have tried solving this by opening log but I'm unable to reach O(n). I don't want any other method like substitution or root tree to be used. I want to use simple maths and reach O(n), please let me know if you have a clue about it.


texts: How to get expected running time of hash table?

texts:
If I have a hash table of 1000 slots, and I have an array of n numbers. I want to check if there are any repeats in the array of n numbers. The best way to do this that I can think of is storing it in the hash table and use a hash function which assumes simple uniform hashing assumption. Then before every insert you just check all elements in the chain. This makes less collisions and makes the average length of a chain $\alpha = \frac{n}{m} = \frac{n}{1000}$.

I am trying to get the expected running time of this, but from what I understand, you are doing an insert operation up to $n$ times. The average running time of a search for a linked list is $\Theta(1+\alpha)$. Doesn't this make the expected running time $O(n+n\alpha) = O(n+\frac{n^2}{1000}) = O(n^2)$? This seems too much. Am I making a mistake here?


texts: Embedding a general planar graph into a grid

texts:
I have here a little problem with my homework, and would appreciate some direction.

I am attempting for some time now to show that every planar graph is embeddable into a grid (As large as needs be).

I tried to make this argument inductively in many ways, but I am afraid that I don't see any good way to do that so far. My main problem is that while the subgraph may be embeddable in a grid, it might not still be possible to connect the relevant nodes to the nodes added in the inductive stage after the reorganization.

While writing this down, I thought of another possible solution which might solve it - observing the embedding to the plain as an embedding in the Cartesian plane, and moving every node to a "very close" point whose both coordinates are rational. Taking the greatest common denominator of all the coordinates, I believe that I'll find myself in a (huge) grid as required.


texts:
Suppose we have a datastructure that is a list containing elements that are either a leaf or another layer of the datastructure (recursively defined). What would we call this? It isn't a tree, since it has variable number of leaves and branches on each node. It isn't a forest, since it doesn't consist of a list of trees. I'm not exactly sure what to call it.

For context, the specific structure I'm designing is used as part of a compiler. The language is indentation structured, so blocks of code are grouped by their indentation level.

I have an Indentation_______, which is a list of nodes where the node is either a statement in the program, or a new Indentation_______ containing the next nested indentation level.

Any ideas?


texts: No polynomial time approximation algorithm better than $n^{1 − ε}$

texts:
What does this sentence mean?

For all $ε > 0$, it is NP-hard to approximate MAX CLIQUE to within $n^{1 − ε}$.

Is the fact that complexity of approximation depends on $\epsilon$ hidden in the statement? I mean, if not, I guess we can make $\epsilon$ arbitrarily small, (like $\epsilon = 0.9999$), and get a very good approximation. So, I guess as we make $\epsilon$ smaller, the complexity should go remarkably higher. Right? In which order?


texts: in function declarations, what advantages are there to having the type of the parameter specified after the parameter name?

texts:
For typed languages, what advantages/disadvantages are there to specifying the parameter type after the parameter name?

For languages like C and Java, the type comes first:

void myfunc(TypeA param1, TypeB param2);

For other languages like Scala, Rust, etc, the type comes after the parameter name:

fn myfunc(param1: TypeA, param2: TypeB) {}

What advantages are there to this approach?   I could see in languages where specifying a type is optional (or inferred) and can be left off, but at least for Rust types have to be specified in a function's parameter list.


texts: How to prove the union of languages recognized by a set of turing-recognizable Turing machines is also turing-recognizable?

texts:
Let $G = \{\langle M_1\rangle, \langle M_2\rangle, \langle M_3\rangle,\cdots\}$ be an infinite turing recognizable language, whose members are descriptions of turing machines.

How can one prove that the union of all the languages recognized by the turing machines in $G$, $L(M_1) \cup L(M_2) \cup L(M_3)\cup\cdots $ is turing recognizable?

I tried to prove it by building an enumerator for the language, using the fact that since $G$ is turing recognizable it can be produced by one.

E' =
1. Initialize steps counter i=0
2. Run E, the enumerator of G, number of steps equal to i.
3. For every turing machine description M produced by E:
   3.1 for every input word corresponding to 0 up to i according to lexicographic order do:
      3.1.1 Run M on the current input.
      3.1.2 print if M accepts.
4. increase i by 1, and go back to step 2.

Is this a correct approach? Running the enumerator for a limited amount of steps would produce the same words over and over again. Is this not a problem when creating an enumerator? Is $E'$ valid and producing the language as needed? If not, what should be changed?


texts: How does this unsigned subtraction work?

texts:
Modern computers don't have circuits dedicated for subtraction. They do it by using the method of complements.

All is well when the 2 operands are signed 2's complement numbers. The result of addition will be another 2's complement which, when interpreted as a 2's complement number, will give the correct result provided that there's no overflow.

Now consider a 4 bit number. The unsigned range is 0 <-> 15. Signed range is -8 <-> 7.

What happens when I do 15u - 14u? The first thought which comes is "Do the 2's complement of 14 and do 15 + (-14)". But then, -14 is not in the range of a 4 bit number.

But if I do it anyway (Flip all bits and add 1):

   1111
 + 0010
------------
1  0001  =  0001 (4 bits)

It works. But 0010 is not even a negative 2's complement number. It is just 2. However, 0010 is the additive inverse of 14 for 4 bits. Is it a coincidence?

Question: Why does it work? And is this even the actual way it's happening?


texts: What is the exact definition of a dictionary in the concept of linear algebra and computer science?

texts:
I am reading this paper for my master thesis and trying to understand every concept in it. The following sentence confuses me as to what is the exact definition of a dictionary in this concept except for the fact that it holds the atoms as its columns?

  Recall we refer to the columns of the matrix $A$ as atoms that are later used as building blocks in the construction of $b$. Such a matrix that holds the atoms as its columnsis referred to as a dictionary[...].


texts: Is this benchmark sufficient to consider my algorithm as an efficient matrix multiplication algorithm?

texts:
I built a matrix multiplication algorithm and now I need some thoughts about following benchmark.
C++ chrono:: high resolution clock Time(micro second)

(Dim)256--> (Naive algo ) 296807, (My algo) 187479
(Dim)512--> (Naive algo) 2249495, (My algo) 1359046
(Dim)1024-->(Naive algo) 27930970, (My algo) 12309645

FYI, I have no knowledge about strassen matrix multiplication algorithm and how to utilize a github project.Therefore,I stole some benchmark from a github account for sake of some comparisons with strassen matrix mulplication algorithm.Those are as below.
C++ chrono:: high resolution clock Time(micro second)

(Dim)256-->(Naive algo) 260281,(Strassen algo) 216970
(Dim)512--> (Naive algo) 2122299, (Strassen algo) 1580466
(Dim)1024-->(Naive algo) 2algorithm?Strassen algo) 14696774

I don't know specs of github user's computer.I assume it's better than mine after observing both execution times of naive matrix multiplication algorithm.(quoted from https://github.com/rangelak/Strassen-Matrix-Multiplication)
Specs of my computer
Processor core i7 6th gen(2.60 GHz)
Ram 8gb
What do you think about my algorithm after observing above mentioned band what can I expect after comparing my algorithm with strassen matrix multiplication algorithm?


texts: Formal way to model or describe distributed systems architecture

texts:
I've been tasked to create the systems architecture for a distributed system.

One approach to designing this system is to pick systems architecture patterns, and then evaluate different technologies that implement those architectural patterns.

For example, a particular architecture might call for a message bus, and given that, I could choose between various off-the-shelf open source or commercial projects that implement a message bus.

While this approach yields a nice white-board diagram, and a high-level understanding of how the system will work, some drawbacks are:

its difficult to gauge the performance of the system as a whole without fully implementing it
its difficult to determine how well each pattern / implementation will mesh with the other components
because of that, choosing between patterns tends to be gut feelings similar to "Kafka is cool, I used it on project X and it did really well"
there are no hard guarantees about the performance of the system as a whole (consistency, availability, etc)

Is there a formal approach to modeling distributed systems?  Ideally one that provides a way to abstract patterns, and provide analytic tools for making predictions about the behavior of the system?


texts: Finding a subset of triplets of digits 0-9 such that each digit occurs 40 times in each position in the triplets

texts:
I am trying to generate a list of digit triplets to specify stimuli in an auditory (speech-in-noise) perception experiment. Each triplet has to have three different digits (i.e., no repetition within triplets). I have recordings of digits 0-9, recorded in each triplet position (i.e., I have 30 digits, 0 in 1st position, 0 in 2nd position, 0 in 3rd position, 1 in 1st position, 1 in 2nd position, etc...). This is for a homogenization task, i.e., a task for figuring out the signal to noise ratio (SNR) for each digit in each position so that the level of individual digits can be adjusted upward or downward to make them equally intelligible at a fixed noise level.

In the homogenization task, stimuli will be presented at 10 SNRs, and I want each digit in each position to be presented four times at each SNR, but in different triplets. Hence, I want 4 x 10 x 10 triplets total. (The four repetitions is somewhat arbitrary, but it's based on previous work, and 400 trials works out nicely with respect to the amount of time listeners will spend doing the task.)

There are 720 total triplets. I use Python, so it's easy to get the full list with:

all_triplets = list(itertools.permutations(np.arange(10),3))

I'm finding it very difficult to get a subset of 400 of the 720 possible triplets such that each digit occurs in each position exactly 40 times. That is, I want 400 triplets such that

np.sum(triplets[:,c]==d) == 40

is True for all c in [0,1,2] and all d in [0,1,2,3,4,5,6,7,8,9], and with triplets a 400 x 3 numpy array containing the subset.

I think that such subsets exist, but I am not sure, since I haven't buckled down to try to work out the math (I may not have the ability to do so even if I do buckle down, and I definitely don't have the time to do so, regardless). I can't figure out how to construct any such subsets from scratch (I wrote some aggressively mediocre code to do this that kind of works sometimes) or to select the right elements from the full set (assuming there are some).

I wrote some less mediocre code to sample randomly from the full subset and score each subset based on how much it deviates from the 40-of-each-digit criterion, and I found a subset with these tallies (rows are triplet position, columns are digits):

[[43, 41, 39, 40, 37, 40, 42, 42, 37, 39],
 [43, 41, 39, 38, 41, 39, 44, 38, 40, 37],
 [43, 38, 40, 38, 38, 41, 42, 44, 39, 37]]

Of course, randomly sampling from approximately 1.92e+213 total subsets of size 400 from the 720 total set of triplets isn't terribly efficient.

So, is there a solution to this problem? A commenter on reddit's intuition is that this problem is NP-complete, but I don't know enough about the relevant math or computer science to have particularly strong intuitions about this possibility. Should I just be happy with the best solution I stumbled on?


texts: Why are kernel methods with RBFs effective for handwritten digits (letters) classification?

texts:
The question emerged while reading Ch. 3 of Rasmussen & Williams http://www.gaussianprocess.org/gpml/. In the end of this chapter, the authors gave results for the problem of handwritten digits classification (16x16 greyscale pictures); features are 256 pixel intensities + bias. I was surprised that in such a high-dimensional problem, 'metric' methods, like Gaussian processes with squared exponential kernel, or SVM with the same kernel, behave quite nice.

Also, I heard sometimes that SVM is good for [essentially bag-of-word] text classification. Why aren't they suffering from the curse of dimensionality?


texts: Simulating multi-tape turing machines by single-tape TM

texts:
In "Computational Complexity: A modern approach", Arora and Barak proof the following Claim:

  Define a single-tape Turing machine to be a TM that has only one read-write tape, that is used a input, work, and output tape. For every $f: \{0,1\}^* \rightarrow \{0,1\}$ and time-constructible $T: \mathbb{N} \rightarrow \mathbb{N}$, if $f$ is computable in time $T(n)$ by a TM $M$ using $k$ tapes, then it is computable in time $5kT(n)^2$ by a single-tape TM $\hat{M}$.

The proof roughly goes like this, from my understanding:

-> We encode the $k$ tapes of $M$ on a single tape, using locations $i,k+i,2k+i$ for the $k$-th tape.

-> For each character $a$ in M's alphabet, we define another character $\hat{a}$ in $\hat{M}$'s alphabet. For each of M's tapes, the $\hat{a}$ character indicates the current position of that respective tape (for $M$) in $M's$ encoding.

-> For each state transition of $M$, $\hat{M}$  then perform two sweeps: One left-to-right, where $\hat{M}$ finds the positions of $M$ at the respective working tapes and one right-to-left where $\hat{M}$ updates its tape encoding according to state transition function of $M$.

Its not clear to me how the first step exactly works. Arora and Barak write:
"First it sweeps the tape in the left-to-right direction and records to its register the $k$ symbols that are marked by $\hat{a}$". As far as I understand, registers correspond to states in the TM $M'$. What is exactly is meant by recording the symbols to its register?


texts: How may an algorithm always color optimally connected bipartite graphs?

texts:
Let's consider a greedy algorithm for the coloration problem called the Dsatur algorithm, designed by Daniel Brélaz in 1979 at the EPFL, Switzerland.. This algorithm is based on an order of vertices which we can obtain from considering the saturation degree of each vertex $v$ from $G$. The saturation  degree of a vertex $v$ , which we can write as $DSAT(v)$, is the number of color, the number of different colors used in $v$ neighborhood. The idea is to color  first the vertices with a saturation degree high enough to avoid using too many colors.

Data : an undirected (*non-orienté*) connected graph $G=(V,E)$.
Output : all vertices of $G$ colored.

SORT the vertices by decreasing order of degrees.
COLOR a vertex of maximum degree with color 1.
While it exists vertices not colored do
  CHOOSEa vertex $v$ with max DSAT
  COLOR $v$ with the smallest possible color
  UPDATE DSAT for all neighbors of v

How to show that DATSUR Algorithm always  color optimally connected bipartite graphs ?

My attempt

I think I have to prove it by the absurd :

As far as it is a conected graph it can't be colored by one color solely.
If there were three colors returned by the algorithm Dsatur, taht would mean that a vertex would return $Dsatur(v)= 2$ (it exists two neighbors with two different colors). Which is impossible. But why ?

That would mean that it gives three kind of different colors... But I don't know how to show why this is impossible... Can you help me ?


texts: Why are diploid (dominant/recessive) genes not used widely in genetic algorithms?

texts:
In most implementations of genetic algorithms, the focus is on crossover and mutation. But somehow, most of them leave out diploid (dominant/recessive) nature of genes. As far as my (limited) understanding goes dominant/recessive nature of genes is a very important factor in deciding the actual characteristics of an organism.

So my question is why is the diploid nature of genes left out of genetic algorithms in most implementation?

Is it because:

it doesn't provide much benefit
it adds unnecessary complexity to an otherwise simple algorithm
it's difficult to implement

Or something else entirely?


texts: Why is the set of all regular expressions classified as context-free, instead of regular?

texts: As I understand regular languages can be closed under concatenation, so can I concatenate the set of all regular expressions to classify them as regular?


texts: Closure properties between 2 languages of different types

texts:
Whenever said - The intersection between a Context Free Language and a Regular Language is always Context Free, what is the best logical way to confirm the statement?
I have this Chomsky hierarchy in mind that I refer whenever closure properties between Type-m and Type-n languages are asked but sometimes I come up with a wrong result.
How do you people logically solve it? What is the best simplest way?


texts: Splicing squares on a Turing Machine finite tape

texts:
Trying to explain a problem, I thought of a variant of Turing
Machines. It is unlikely to be new, but I do not recall ever seing it
before, and I wonder whether it has been used or has a name. The idea
is that the TM uses a "linked list" rather than a tape, so that the
head can splice a new symbol position between two existing ones (one
could also think of removing some, but I had no use for it :). Of
course, that requires having a new item in the description of a
transition to specify whether a new square should be spliced in, on the left or on the right of the head (both are needed).

The final point is that it does start with a finite tape. I did not
give all the details, but I do not think the rest matters much.

I have not done any proof, but I conjecture its computing power is
that of usual TM :) .

As I said I thought of it as a convenient way of explaining some other
problem. Then it hit me that, while TM are finitely defined, they are
stuck with their infinite tape from the very beginning. It never
bothered me very much, until some physicist started explaining that TM
are not realistic because of their infinite tape (which I only saw as
a convenient mathematical shorthand). I could fight that technically
in various ways. But this splicing idea should just do away with such
silly objections using no mathematics at all.

So my question is: where has this model, or some similar one, been considered before,  by whom and under what name?


texts: Problem with update in Dynamic Bayesian Networks

texts:
Consider the following Bayesian network:

I want to impose constraints that state that a node can only be true (1) if at least one of its parents are true (1). So, for node $C$, the constraint takes the form $P(C=1|A=0,B=0) = 0$.

Now I want to take into account time. So it seems like the logical thing to do is to construct a dynamic Bayesian network from the above structure, as follows:

So, the update for a given node, say $C$ to updated value $C'$ obeys the following probability $P(C'=1|A,B,C)$. The leaf nodes, say $A$, obeys the update $P(A'=1|A)$.

Issue: I'm a little bit confused on how to ensure that the constraints I wish to impose are held after the variables are updated. For example, let $P(A'=1|A=1) = 1-\alpha$ and $P(B'=1|B=1) = 1-\beta$, where $\alpha,\beta>0$. This allows for the possibility of the realized values of both $A'$ and $B'$ becoming false (0), where $C'$ could be true, violating the constraint stated earlier.

Question: How do I ensure that the constraints are maintained after the variables are updated? Under the current set up, it does not seem like the dynamic Bayesian network shown above is capable of doing this.

Idea: Does the update need to be performed starting from the leaf nodes? That is, update $A'$ and $B'$ first, then once their values have been realized, update $C'$, and so on, down the DAG? Is this the standard way of doing this?

Update: Would the following representation allow for the constraints to be represented?

Update #2: Does anyone have any ideas? I'm really stumped on this.


texts:
I am thinking about the worst-case space complexity of an algorithm.

Obviously, if $f \in O(nm)$ then $f \in O(n+nm)$. But is the converse true?

$O(m)+O(nm) = O(m+nm) = O(m(1+n)) = O(m)O(1+n) = O(m)O(n) = O(nm)$

If that were true then $O(n+nm) = O(m+nm)$


texts: Maximum space consumption of stack and queue for DFS and BFS

texts:
I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS.

Since BFS and DFS while traveling graphs have node discovery control (no loops), we can analyze the problem by thinking in terms of trees instead of graphs, where your starting node is taken as root, as usual.

I've started by assuming that the resulting traveling is a complete tree (all leafs have same depth), with height $h$, $n$ nodes, and thus all nodes having degree $d$ (except leafs).

Of course, since the tree is complete, $n$ can be calculated from $h$ and $d$:

$$n = \frac{1 - d^{h + 1}}{1 - d}$$

Under this asumption, the worst case scenario for DFS is when you are in the deepest non-leaf node of the first branch of the tree: since each time you pop a node, you insert all of its children, for each level, you have $D - 1$ pending nodes in the stack, except in the last non-leaf, where all of its children are inserted.

If you, instead of being in the first branch, were in another one, you would have some branch with less than $d - 1$ pending children in the stack, and thus you have less nodes in the stack.

So the maximum memory consumption of DFS for a complete graph with homogeneus degree is ($ms$ stands for maximum space):

$$ms = h * (d - 1) + 1$$

This last + 1 represent the extra child for the last non-leaf node. For instance, for a tree with $d = 4$ and $h = 20$ nodes, a DFS's stack would require as maximum:

$$ms_{DFS} = 20 * 3 + 1 = 81\ nodes$$

Taking into account that this graph would have $n = 1.4660155e^{12}$ nodes, this is a more than admisible amount. That's the adventage of logarithmic space complexity ($h = \lfloor log_d((d-1)n)\rfloor$).

However, for BFS, which have exponential space complexity, the worst case scenario is when you have all leafs pending to be discovered, while having discovered every other node, so your queue contains all leafs (so have the full last-level pending to be discovered but nothing else):

$$ms_{BFS} = d^h\ nodes$$

which, from our example, equals $1.0995116e^{12}$.

My problem now is relaxing the restriction of the graph to be complete, so $d$ is not an homogeneus degree anymore, but an average degree instead (which can contain now decimals), and the tree can have any disbalance, even being a list. Consequently, the number of nodes is free, so it's not attach to d and h as before.

If $d$ is an average degree and $n$ any amount of nodes, I've tried to model somehow an upper bound of space consumption by first modelling a complete tree with an homogeneus $\lfloor d\rfloor$ degree, and then adding children to the last leaf until getting $d$ (I assume that the resulting number of nodes should equal $n$, but I'm not sure on that either; I've even tried to calculate, given some $d$ and $n$, a lower and upper bound for the height of the tree).

Since $d$ is an average, if some node has more than $d$ children is because some other node has less than $d$ children, and thus the idea was to find the worst case scenario for DFS and BFS by removing children from one node and moving the cut branch as child of another node or, in general, finding somehow the closest upper bound as possible of memory consumption, but I couldn't find a way.

The thing is that, if you apply this height increase repeatedly by moving sibling branches to deepest levels, you would probably end up having a lot parent or sibling paths consisting of just lists, which would be removed from the stack/queue very quickly, and thus there must be some tree state where you cannot make the space consumption worst than that. I assume though that the "worst tree" can be different from DFS and BFS though.

Is making this upper bound (or even exact amount) calculation even possible? Or the worst case scenario is just the balanced one?


texts: What is minimum cost perfect matching problem for general graph?

texts:
It does make sense when we talk about perfect matching in bipartite graphs because there are two sets of points, for example, one set may be jobs and other set may contain different machines. But when we talk about minimum cost perfect matching in general graphs, it is not making any sense for me, what are the nodes and edge cost representing, If you can give some real-life example depicting minimum cost perfect matching in general graphs. It will be very helpful to me.

Also, I need a precise definition of the minimum cost perfect matching problem. Thank You.


texts: What are some problems in the class P which we used to think were in the class of NP?

texts: I was recently watching a video on the classes of P and NP, in which it was claimed that there have been 'several' problems that were presumed to be in the class of NP, which have since been shown to be in the class of P. Unfortunately, no examples of such problems were given. Could anyone verify this statement by providing an example of such a problem?


texts: Are there any problems in complexity class EXP that are not in NP?

texts: I cannot conceive of any problem that can be solved in exponential time, but cannot be checked in polynomial time.


texts: Is there an algorithm to generate all permutations of a multiset through swaps?

texts:
I am currently working on a project where I have to perform a computation over all possible permutations of a multiset $S$. In my setting, each multiset is a list of small positive integers such as $S = [1, 1, 3, 4]$ with between 2 to 10 elements and at least 1 duplicate.

I am wondering if there is an algorithm to generate distinct permutations of S by swapping two elements at a time? I am open to any algorithm, though ideally I am hoping to find an iterative procedure.

Example: Given $S = [1,1,3,4]$, the algorithm would output $12 = 4!/(2!1!1!)$ distinct permutations $P_1, P_2,\ldots, P_{12}.$ The permutations would be distinct in the sense that $P_t \neq P_{t'}$ for all $t,t'$. Given a permutation $P_t$ where $t < 12$, the algorithm would produce the next permutation $P_{t+1}$ would be by swapping the elements of $P_t$ at locations $i$ and $j$. Thus:

$\begin{align}
P_{t+1}[i] &= P_t[j]\\
P_{t+1}[j] &= P_t[i]\\
P_{t+1}[k] &= P_t[k] \quad \textrm{for}~k \neq i,j
\end{align}
$

Note that we do note need for there to exist a "swap" that would transform the last permutation $P_{12}$ into the first permutation $P_1$. In this sense, the problem is easier because the permutations would not need to form a Hamiltonian path.

I also did a bit of background research and discovered the following facts that might help:

It seems as if there is a result that shows that it is impossible to generate the permutations of a multiset through adjacent swaps (see e.g., p.2 of this paper). However, I am not sure if this result holds when we are allowed to perform non-adjacent swaps.
The FXT library has several implementations of algorithms for multiset permutation. This algorithm seems to fit the bill (see
code
and sample
output).
I am hesitant about using it since I have not seen it mentioned
in a paper or textbook and I'm not familiar with C++ syntax. If someone could confirm that it works and explain it, that would also be an acceptable solution.


texts: Show that language generated by grammar is regular

texts:
We have grammar with nonterminals $ X_1,...X_n$ terminals $V_t$ and rewriting rules of form:

$X_i  \rightarrow a \in V_t   $

$X_i \rightarrow X_jX_k, \  i \ge j  , \ i > k  $

How can I show that language generated by this grammar is regular?

I don't think this is duplicate question, because:

I don't have concrete language, but set of nonterminals and set of terminals
I have to show, that for every possible combination of terminals and nonterminals I get only language which is regular

If I had been given particular language, I could prove it by giving DFA, showing that rules are only of linear type,etc....


texts: Computing/sketching essential bit content of a binary source

texts:
I'm given the Bernoulli distribution of a biased coin toss with probability distribution $P_X = \{0.2, 0.8\}$ over the alphabet $\mathcal{A}_X=\{0,1\}$.

I want to sketch the normalized essential bit content $\frac1N H_\delta(X^N)$ as a function of $\delta$ for $N=1000$, where:

$X^N = \{X_1, X_2,\dots,X_N\}$ is the outcome of $N$ independent repetitions of tossing the coin
$H_\delta(X^N)=\log_2 |S_\delta|$, with $S_\delta$ being the smallest $\delta$-sufficient subset of $\mathcal{A}_X^N$
the $\delta$-sufficient subset is chosen such that $P(x\in S_\delta)\geq 1-\delta$

To be able to sketch the function I have to compute $H_\delta(X^N)$ for different values of $|S_\delta|$. So I computed the mean $\mu$ and standard deviation $\sigma$ of $X^N$ and approximated the binomial distribution with a standard normal distribution to find the number of elements in $S_\delta$ ($s$ is the number of $0$'s):

$$P(-\alpha \leq \frac{s-\mu}{\sigma} \leq \alpha)\geq1-\delta$$

To find the the critical value $\alpha$, I rewrote the equation as follows to find $\alpha$:

$$P(\frac{s-\mu}{\sigma} \leq \alpha)\geq1-\frac{\delta}{2}$$
After determining $\alpha$ for a fixed $\delta$, $|S_\delta| = \sigma\cdot\alpha\cdot2$.

When plotting this for different values of $\delta$ I get the correct "flipped" sigmoidal shape. However, the values for $\frac{1}{N}H_\delta$ are about $150$ times too small compared to the solution.

It seems like I'm missing something. Can someone point out where my calculation is wrong?

Disclaimer: I'm working through David MacKay's book (Information Theory, Inference, and Learning Algorithms) by myself, I'm not asking for help with solving course homework. The exercise in question is 4.15.


texts:
I was reading the Modular Multiplication page on wikipedia...and could not understand the algorithm to compute $a \cdot b \pmod{m}$.

uint64_t mul_mod(uint64_t a, uint64_t b, uint64_t m)
{
  long double x;
  uint64_t c;
  int64_t r;
  if (a >= m) a %= m;
  if (b >= m) b %= m;
  x = a;
  c = x * b / m;
  r = (int64_t)(a * b - c * m) % (int64_t)m;
  return r < 0 ? r + m : r;
}

I get that:

$$ a \cdot b \pmod{m} \equiv ((a \mod{m}) \cdot (b \mod{m})) \mod{m}$$

the step I didn't get is c=x*b/mand later doing r = (int64_t)(a * b - c * m) % (int64_t)m; what is that for?

The article says:

  by employing the trick that, by hardware, floating-point
  multiplication results in the most significant bits of the product
  kept, while integer multiplication results in the least significant
  bits kept

I can't see how this is related !!!


texts: Paths in a graph with two kinds of costs

texts:
A weighted graph $G= (V, E, W_1, W_2)$ has two cost functions $W_1, W_2 : E \rightarrow \mathbb{R}$. Each edge $e$ has two costs $W_1(e)$ and $W_2(e)$. We may think the costs as representing different resources, such as time and fuel. Similarly, a path $p =e_1, e_2, \dots e_n$ has two costs,

$$W_1(p) = \sum_i W_1(e_i) \qquad \text{and} \qquad W_2(p) = \sum_i W_2(e_i) \qquad$$

Consider the following decision problem: given two nodes $u, v \in V$ and two constants $c_1, c_2$, does there exist a path $p$ from $u$ to $v$ such that $W_1(p) \le c_1$ and $W_2(p) \le c_2$?

Is it NP complete or is a polynomial algorithm known to exist?


texts:
Ternary heap is like a binary tree, just every node can have up to $3$ sons and not $2$.

I try to bound the number of nodes in the heap, $n$, using the height of the heap $h$.

The solutions get to:

$$
3^h < n < 3^{h+1}
$$

Yet, I get to:

$$
\frac{3^h}{2} < n < \frac{3^{h+1}}{2}
$$

In short, what I do is:

$$
\sum_{i = 0}^{h - 1}3^i = \frac{3^h-1}{2}
$$

For all the nodes in all levels except for the last level, because all the levels are full.

If the last level is full:

$$
\frac{3^h - 1}{2} + 3^h
$$

If the last level has only $1$ node, we get:

$$
\frac{3^h - 1}{2} + 1
$$

From here I conclude what I showed at the beginning.

Why the solutions get to something else?


texts: Find a 3-colouring using the 3-colourability decision problem

texts: I was learning about NP problems. I read that for many problems, like Clique, we can easily convert its decision problem to derive a solution of search problem. (For Clique problem, you only need to enumerate the vertices of $G$ and delete any vertex that if your decision function tells you is not in the clique) But for 3-COLOR problem, I have no idea of how to link decision problem to search problem. Can anybody help me?


texts: What does it mean to take a union of a transition function with a starting state?

texts:
$$
\delta(q,a) = \begin{cases}
\delta_1(q,a) & q \notin F_1 \text{ or } a \neq \lambda \\
\delta_1(q,a) \cup \{q_1\} & q \in F_1 \text{ and } a = \lambda.
\end{cases}
$$

Look at the second line of the function definition. It's a transition function. $q_1$ is the starting state. What does that union mean here? Union of the function range with $\{q_1\}$?


texts:
Graph isomorphism solver Nauty has two main procedures, individualization and refinement, to get to a discrete partition. During refinement procedure, we take some cell of the current partition and attempt to further split the partition on more cells. What I found is that depending on the order of which you select cells during refinement, you can get different equitable partitions (at least up to the permutation of cells in the equitable partition). I guess this corresponds to the quote from Practical Graph Isomorphism II:

It is well known that for every colouring π there is a coarsest equitable colouring π' such that π' < π, and that π' is unique up to the order of its cells.

An example of this would be Example 7.7 (page 257), where selecting {1,3,7} instead of {2,4,5,6} will result in a permuted equitable partition

And more importantly these 2 equitable partitions can give 2 different certificates, so it is important to select the right order on the cells to get minimal among possible equitable partitions.

So my question is how does nauty ensure that during refinement it will find the “right” equitable partition and not lose the equitable partition that would potentially lead to the minimal certificate? In order words, among all (a) coarsest partitions how does it make sure to select the coarsest partition (because it selects just one equitable partition)?


texts: Hardness of finding all Control Flow Paths of a function

texts:
I have a control flow of function F, I want to know all control flows of this functions.
I.e.,
function F {
   A;
   if B {
     B;
   }
   C;
}

would have the control flows {[ABC],[AC]}. My intuition tells me that the complexity/amount of different control flows is $O(2^m)$ with $m$ being the amount of branches. However, I am unable to find a definitive answer/literature describing the problem and its complexity in detail.
What is the complexity of calculating all possible control flows trough a function?


texts: How are basic feasible solutions in linear programming related to vertices in its corresponding polytope?

texts:
In Section 2.3.3 "Polytopes and LP" of the book "Combinatorial Optimization: Algorithms and Complexity" by Christos H. Papadimitriou, Theorem 2.4 establishes the relation between bfs's (basic feasible solutions) of LP and vertices in polytope (for developing the simplex algorithm). However, I have difficulty in understanding its proof.

Consider an LP instance $Ax = b, x \ge 0$ where, $A$ is an $m \times n$ matrix, $x = (x_1, \ldots, x_n)$ is an $n$ (column) vector, and $b = (b_1, \ldots, b_m)$ is an $m$ (column) vector.

By convention (if I understand it correctly; Page 38 for the discussion), we can assume that the left hand sides of the LP instance is of the form with $A = [H|I]$ in the figure.

Let $P \subseteq R^{n-m}$ be the convex polytope corresponding to the feasible set of the LP instance:
$$x_j \ge 0, \quad j = 1, \ldots, n-m$$
$$b_i - \sum_{j=1}^{n-m} h_{ij} x_j \ge 0, \quad i = n-m+1, \ldots, n$$

Theorem 2.4 (Page 39) states that

  $(c) \Rightarrow (a):$ If $y = (y_1, \ldots, y_n)$ is a bfs (basic feasible solution) of $Ax = b, x \ge 0$, then $\hat{y} = (y_1, \ldots, y_{n-m})$ is a vertex of $P$.

The proof (Page 40) goes as follows:

$y = (y_1, \ldots, y_n)$ is a bfs

$\Rightarrow^{1}$ there exists a cost vector $c$ such that $y$ is the unique vector $x \in R^{n}$ satisfying $c'x \le c'y; \quad Ax = b; \quad x \ge 0$ ($c'$ is the transpose of $c$).

$\Rightarrow^{2}$ $\hat{y} = (y_1, \ldots, y_{n-m})$ is the unique point in $R^{n-m}$ satisfying $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$, where
$$d_i = c_i - \sum_{j=1}^{m} h_{n-m+j,i}c_{n-m+j} \qquad i = 1, \ldots, n-m$$

$\Rightarrow^{3}$ $\hat{y}$ is a vertex of $P$, with supporting hyperplane defined by $d' \hat{x} = d' \hat{y}$

Questions:

  In step $\Rightarrow^{2}$: How $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$ (in particular, the $d_i$ values) is obtained?
  In step $\Rightarrow^{3}$: Why does $d' \hat{x} \le d' \hat{y}, \hat{x} \in P$ imply that $\hat{y}$ is a vertex of $P$? Should a vertex in $P \subseteq R^{n-m}$ be defined by at least $n-m$ hyperplanes?
  Consider the following LP instance in Example 2.4 (Page 40; note that $A$ is of the form of $[H|I]$):
  $A = \begin{bmatrix} 1 &1 &1 &1 &0 &0 &0 \\ 1 &0 &0 &0 &1 &0 &0 \\ 0 &0 &1 &0 &0 &1 &0 \\ 0 &3 &1 &0 &0 &0 &1 \end{bmatrix}$ , $x \in R^{7} \ge 0, b = (4,2,3,6)$.
  Consider the base $\mathcal{B} = \{ A_1, A_2, A_4, A_6 \}$ ($A_i$ denotes the $i$-th column of $A$), its corresponding bfs is $y = \mathcal{B}^{-1}b = (2,2,0,0,0,3,0)$. According to Theorem 2.4, $\hat{y} = (2,2,0)$ is a vertex of the polytope $P$ corresponding to the feasible set of LP.
  How to obtain this result following the steps in the proof above?


texts:
Given a 7 tuple push down automaton
M = (K, Σ, Γ, Δ, s, F) where K = {p, q, r}, Σ = {a, b, c}, Γ = {a}, s = p, and F = {r}, with the transitions
((p, b, ε), (q, ε)), ((q, a, e,), (p, a)), ((p, c, a), (r, ε)), ((r, c, a), (r, ε))
This is my diagram:

How can I account for the last element of the stack? Some other examples saw had something like ε, ε -> $ in the first state to second, and then ε, $ -> ε for the final.


texts:
Are data and return addresses both pushed on the same stack space?
If yes, couldn't this piece of code cause problems:

CALL r1 //the PC is now the contents of register 1, return address is pushed on the stack.
POP r2  //pop the top of the stack and put the data in register 2.
RET     //return from subroutine

The POP instruction would delete the return address of the subroutine so the RET instruction will return to the wrong location.


texts:
I have seen two different Peterson’s Solution to mutual exclusion, one is from Modern Operating Systems:

#define FALSE 0
#define TRUE 1
#define N 2

int turn;
int interested[N];

void enter_region(int process)
{
    int other;
    other = 1 - process;
    intersted[process] = TRUE;
    turn = process;
    while(turn == process && interested[other] == TRUE);
}

void leave_region(int process)
{
    interested[process] = FALSE;
}

The other is from Operating System Concepts:

while (true) {
    flag[i] = true;
    turn = j;
    while (flag[j] && turn == j)
        ;
        /* critical section */
    flag[i] = false;
        /*remainder section */
}

But they are different. The first one set turn to itself, while the second one set turn to the other. The following while condition also has the same difference. After googling around, I think the second one is right, but not sure.


texts: Complexity of linear programming with restricted quadratic constraints

texts:
A problem instance is a linear program with the following kind of quadratic inequalities allowed: For some of the variables $x_i$, there is a variable $s_i$ (intuitively for approximating $x_i^2$, and distinct from all the $x_j$) and positive constants $l_i,r_i$, such that the following constraints are also included:

$l_i ≤ x_i ≤ r_i$  (confined to boxes; this is the case for every variable in my application)

$l_i x_i ≤ s_i ≤ r_i x_i$  (minor improvement over $l_i^2 ≤ s_i ≤ r_i^2$)

$s_i ≥ x_i^2$  (the approximation is tightly constrained from below, only)

Only the third line is quadratic. I include the first two lines in case they make the problem more tractable.

Is this a convex optimization problem? Can it be formulated as a semidefinite program? I see that the regions confining the values of $x_i^2$ are convex, but I doubt that implies the solution space as a whole is. [edit: I was wrong; according to @Vincenzo it is indeed that simple.]

The reason I suspect it might be efficiently solvable is that it seems it can be approximated well (provided the intervals $[l_i,r_i]$ are small, which they will be in my case) with increasing numbers of linear constraints over the same variables. In particular, each $s_i ≥ x_i^2$ is replaced by some $k$ linear constraints defined by

$s_i ≥$ line tangent to $x_i^2$ at the point $x_i = a_1$

...

$s_i ≥$ line tangent to $x_i^2$ at the point $x_i = a_k$

where each $a_t$ is a constant in $[l_i,r_i]$.

Optional question: In case the set of infeasible such problems is coNP-hard, is there nonetheless some method that is said to work well in practice?


texts: How to schedule different elements in a 24h range?

texts:
Given the following conditions:

An element has:

A time range, for example: 9:00 to 18:00.
A repeat time, for example: every 5 minutes.

Then a device recieves some elements and has to schedule them in a 0-24h range.

The device has a minimum separation time between elements, for example: 3 minutes (schedules must be separated with at least 3 minutes).

However, an element can be immediately followed by another, but it's not desirable. Let's say there's a max elements per time. Usually 2 or 3.

Two elements cannot be scheduled at the same time.
The repeat time of the schedules can be reduced or incremented if there's no other way to fulfill the separation time requirement, but it's not desirable.

How should the problem be pointed out? Or is there any place I can find information on how similar situations are resolved?

An example:

One single element:
  time range: 9:00 to 18:00
  time repeat: 5 min

Separation time of the device: 3 min

Result: 9:00, 9:05, ..., 17:55

Another example:

ELEMENT A:
  time range: 9:00 to 18:00
  time repeat: 5 min

ELEMENT B:
  time range: 9:00 to 18:00
  time repeat: 7 min

Separation time of the device: 3 min

Result:
A -> 9:00, 9:06,  9:10, 9:15, 9:21, 9:25, 9:30
B ->    9:03,     9:10,   9:18,     9:25,   9:33

Thank you very much.


texts: How to obtain a trilateration ordering in a graph?

texts:
In a sensor network graph $G = (V,E)$
$V = \{1,2,...,n\}$ is the set of sensors and the edge $(i,j)$ denotes that sensor $i$ and sensor $j$ are inside each other's sensing range. The weight of that edge denotes the Euclidean distance between the corresponding sensors.
The problem is in 2D.

Our goal is to fix the positions of three sensors and find the positions of the remaining.
Starting from 3 nodes (seed nodes), we first start the localization by finding a common adjacent of those 3 nodes.
Determining the position of a fourth node using three already localized node is called trilateration.

We expand the localization using trilateration. We have a localized node set, and each time we search for three nodes from that set that has a common unlocalized adjacent.

When we find such node, it does not mean it is localizable.

A trilateration ordering is: starting from three nodes, the list of vertices  denoted by $a \rightarrow i, j, k$ so that when followed, the localization process is completed unless there can be no improvement.

For instance:
$1 \rightarrow 5, 6, 7$
$2 \rightarrow 5, 6, 7$
$4 \rightarrow 5, 6, 7$
$8 \rightarrow 1, 2, 4$

Is a trilateration ordering.

My question is:

How to obtain such ordering, starting from three seeds, without checking the same node triplet twice and without skipping any node triplet.


texts: Difficulty in understanding the proof of the lemma : "Matroids exhibit the optimal-substructure property"

texts:
I was going through the text "Introduction to Algorithms" by Cormen et. al. where I came across a lemma in which I could not understand a vital step in the proof. Before going into the lemma I give a brief description of the possible prerequisites for the lemma.

Let $M=(S,\ell)$ be a weighted matroid where $S$ is the ground set and $\ell$ is the family of subsets of $S$ called the independent subsets of $S$. Let $w:S\rightarrow\mathbb{R}$ be the corresponding weight function ($w$ is strictly positive).
Let us have an algorithm which finds an optimal subset of $M$ using greedy method as:

$\text{G}{\scriptstyle{\text{REEDY}}}(M,w):$
$1\quad A\leftarrow\phi$
$2\quad \text{sort $S[M]$ into monotonically decreasing order by weight $w$}$
$3\quad \text{for each $x\in S[M]$, taken in monotonically decreasing order by weight $w(x)$}$
$4\quad\quad \text{do if $A\cup\{x\} \in \ell[M]$}$
$5\quad\quad\quad\text{then $A\leftarrow A\cup \{x\}$}$
$6\quad \text{return $A$}$

I was having a problem in understanding a step in the proof of the lemma below.

Lemma: (Matroids exhibit the optimal-substructure property)
Let $x$ be the first element of $S$ chosen by $\text{G}{\scriptstyle{\text{REEDY}}}$ for the weighted matroid $M = (S, \ell)$. The remaining problem of finding a maximum-weight independent subset containing $x$ reduces to finding a maximum-weight independent subset of the weighted matroid $M' = (S', \ell')$, where
$S' = \{y\in S:\{x,y\}\in \ell\}$ ,
$\ell' = \{В \subseteq S - \{x\} : В \cup \{x\} \in \ell\}$ ,
and the weight function for $M'$ is the weight function for $M$, restricted to $S'$. (We call $M'$ the contraction of $M$ by the element $x$.)

Proof:

If $A$ is any maximum-weight independent subset of $M$ containing $x$, then $A' = A - \{x\}$ is an independent subset of $M'$.

Conversely, any independent subset $A'$ of $M'$ yields an independent subset $A = A'\cup\{x\}$ of $M$.

We have in both cases $w(A) = w(A') + w(x)$.

Since we have in both cases that $w(A) = w(A') + w(x)$, a maximum-weight solution in $M$ containing $x$ yields a maximum-weight solution in $M'$, and vice versa. ■

I could understand $(1),(2),(3)$. But I could not get how the line $(4)$ was arrived in the proof from $(1),(2),(3)$, especially the part in bold-italics. Could anyone please make it clear to me?


texts: How is conditional jump implemented in the CPU?

texts:
After reading the question I'm still not sure how CPU does branching.
I understand that we have an instruction counter which points to the current instruction. And after performing conditional jump it either stays the same (increments as usual) or increases (jumps) and points to another branch, that's clear.
The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.
So how does the conditional jump work on the lowest level?


texts: Are there any garbage collectors that take into account paging?

texts:
Garbage collections have to visit all objects that are alive, so as to find the memory that can be reclaimed.  (Having many generations’ just delays this a bit)

All things being equal, it is clearly better to first visit the object that are already paged into RAM, before paging other block in and therefore paging out some object.

Anther possibility is that when the OS wishes to take a page of ram away from the process, the GC is first asked if it has a page that can be given up without needing to be paged out.   The GC may  be mostly done with moving objects from a page, so can clear that page within the time limit the OS has for needing a page.

Yet, I cannot recall any garbage collector that integrates with the OS paging system that drive the order the GC works in.


texts: I don't see why the array[1..3, 1...2] is faster to index than array[1...2, 1...3]?

texts:
In my programming concept class we learned that for the array type it's faster to index  in memory if the length of an element is = $2^n$. This case make us only need to offset instead of actually doing multiplication.

We also learned about the representation of multivariable arrays with row major. It was then said that the array[1...3, 1...2] is faster to index compared to array[1...2, 1...3] because we have the length of an element being = $2^n$. I don't understand why you can determine this?


texts: Correct mapping "update" notation for computer science papers

texts:
A nice easy one.

I'm interested to know the most standard and accepted way to denote the update of a mapping in the context of a theoretical computer science paper.

By example, suppose we have a mapping $m$:

$$
m = \{1 \mapsto 2, 2 \mapsto 3, 3 \mapsto 4\}
$$

Now suppose we wish to mutate the $m$ such that $~m(1) = 666$. How would this be best denoted?

Off the top of my head, I have seen this denoted as $m \leftarrow m \circ \{1 \mapsto 666\}$ or even $m \leftarrow m[1 \mapsto 666]$. How would you do it?

Cheers


texts: How can a stack-based VM be Turing-Complete?

texts:
I was trying to implement a stack-based Virtual Machine (e.g. like JVM or some early version of Lua) for some benchmarks in order to test its performance against a Register-based VM.

I originally implemented it as having a global stack for all values and an array of instructions, where for the sake of simplicity, no functions are implemented, but only goto statements that jump occationally in between the array of instructions, in order to operate on the stack. All instructions are decoded in a linear fashion, and then loaded into an array, which in turn gets fed into the gigantic switch, looping itself while directing instructions to different operations. The values contained in the instructions are decoded seperately within the switch, and then get stored into the global stack, when needed.

Later on, I heard that in order to be Turing-equivalent, the stack machine must have at least two stacks. So the question I'm asking here, is 1) is my original design Turing-equivalent? 2) If not, how to revise the design so that it would be Turing-equivalent?

The reason for the stack VM to be Turing equivalent is that then its speed and efficiency can be compared to another Turing-equivalent custom-made Register machine. Please correct me on this if it does not :)

Thanks!


texts:
How we can prove that the relation: $R= \left\{0,1\right\}^*\times \left\{0,1\right\}^* \in FP$
I understand that we need to find a polytime algorithm to decide whether $(x,y) \in R$ since $(x,y)\in R= \left\{0,1\right\}^*\times \left\{0,1\right\}^*$
How can we find this? And this is enough to prove that $R \in FP$?


texts: Is it possible to support .(any symbol) or \d, \w, \W in DFA

texts:
Is it possible to build DFA that support \d, \w, .(any symbol)?
I understand that we can add each symbol from [0-9] as a separate edge for some of the symbols, but what about the others? for example .(any symbol)? or \S (not white space)?

In other words, can we build equivalent DFA for this NFA

(1) ---a----> (2)
 |
 |
 .(any symbol)
 |
 \/
 (3)


texts:
Let's say we have millions of strings (each of them < 100 characters):

alpha
allo
blah
hello world
orlando
...

I know how a binary search tree or a trie can help to do "prefix search" (example: find all strings that match al*, i.e. beginning  with al).

Which data structure / algorithm could be used to search patterns inside a word (i.e. not necessarily at the beginning or end), that wouldn't need to do an inefficient O(n) traversal of all the millions of strings?

Example: the pattern orl should match "hello world" as well as "orlando"

Notes:

is that called "infix search"?
I'm looking for something working on strings even without meaning (the pattern qys should allow to find the string uyiuqysidi among millions of other strings), on DNA (pattern ATTG found in GGATCATTGAAGG), on sequences (subsequence 1, 4, 8 found in sequence 7, 2, 1, 4, 8, 19, 32), etc.


texts: How multiprocessing is done in Single Core Systems?

texts: Can we do multiprocessing on single core system ? I thought that single core means that ONLY one process/thread can execute at any time. For multiple processes , there can be concurrent execution to appear as they are executing Simultaneously.


texts: Turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols

texts:
I need to build a turing machine that decides $A=\{0^{2^n} | n \ge 0 \}$ with an alphabet of two symbols - $\{0, \_ \}$.
I'm aware of the known TM that decides this language with three symbols $\{0, x, \_\}$ but I am not able to come up with one that does it with just two.
Any advice would be highly appreciated