texts: Finding minimum possible cost of road network between cities with distance from capital condition

texts:
I have a graph G containing cities (vertices V) connected by distanced roads (weighted undirected edges E).
Characteristics of the graph:

Each city is connected to the rest of the graph

Each city has an index value where the index is equal to minimum number of roads you need to use to get to the capital from this city. Capital has index of 0. The cities connected right to the capital will have index of 1 and so on.

Some of the roads will be selected to be changed into highways, creating some sort of network.

I would like to find minimum possible cost of said network based on these requirements:

It is possible to travel from any city to capital
When travelling from any city to capital, the sequence of indexes of visited cities during travel is non-increasing
The highway network has to be minimum possible

What I did so far:
I understood this does require MST solution and so I am using Prim's algorithm, but that is solving only part of the problem (req. 1. and possibly 3.) and I need to add something to my MST algorithm to ensure the 2. requirement is fulfilled, and that is my only problem.
I think starting from the capital city might be the first step (and I do so in Prim's), but how to deal with the indexation based on actual road distance from capital city?
Examples:
In the picture 1 below, fig. a) shows incorrect solution using MST algorithm only – one of the possible MST with weight of 35.
Opposed to this, fig. b) shows one of the possible correct solutions with paths with weight of 120.


texts: Towers of Hanoi but with arbitrary initial and final configuration

texts:
Recently, I came across this problem, a variation of towers of hanoi.

Problem statement:

  Consider the folowing variation of the well know problem Towers of
  Hanoi:

  We are given $n$ towers and m disks of sizes $1,2,3,\dots,m$ stacked on some
  towers. Your objective is to transfer all the disks to the $k^{\text{th}}$ tower
  in as few moves as you can manage, but taking into account the
  following rules:

  moving only one disk at a time,
  never moving a larger disk one onto a
  smaller one,
  moving only between towers at distance at most $d$.

  (Limits in the original problem:
  $3 \le n \le 1000$ and $m \le 100$. Number of test cases $\le 1000$.
  You can assume that all the problems can be solved in not more than
  $20000$ moves.)

It's an interesting one. The classic towers of hanoi problem has one source, destination and temporary tower that is used to move the disks from source to destination. The problem pitched on that site basically has an initial and final configuration.

How does one approach this problem?


texts: does there exist for each program that produces a sequence, a program that returns true or false if a number is in the sequence?

texts:
let S be the set of all programs that take a natural number as input and return another natural as output. let M be the set of all programs that take a natural number as input and return true or false. In both cases for a program to be in S or M it must halt.

Consider programs P in S, I will say the integer n is "in" P if there is some integer m such that P(m)=n

Consider a program P in M, I will say the integer n is "in" P if P(n)=true

Consider 2 programs P1 in S and P2 in M. I will say P1 and P2 are equivalent if for each integer n in P1, n is also in P2 and for each integer n in P2, n is also in P1.

I believe I have managed to prove the following:
There doesn't exist a program P such that P takes as input a program in S and returns an equivalent program in M.

However what I'd actually like to know is if for each program in S there is an equivalent program in M.

I figure this question can be answered in one of two ways. An explicit function in S could be given such that it has no equivalent function in M (this would require a proof that there is no equivalent function in M). Or it must be proven that for each program in S there is an equivalent program in M.

If there is another way to resolve this question other than one of the two ways I mentioned above I'd be interested to hear it. Also if you feel that simply proving there is no function P such that P takes inputs from S and returns equivalent programs in M is sufficient, please give an argument as to why this is.

I have chosen not to include the proof I mentioned above as its not strictly essential to the question however you think it would be relavent let me know and I can include it.

If any clarifications need to be made let me know.

Also please note that I might have gotten the tags wrong, I'm fairly new to the CS stack exchange, if I should change them let me know.

Thanks


texts: I recently read the first question and answer in this homework solution https://cseweb.ucsd.edu/classes/sp08/cse105/hw2s.pdf However, I am not sure if for example, you have two accepting states originally, one in which you leave the accepting state if you read 1 and the other in which you do not leave the accepting state no matter the input then how would one unite the two states. Your help is appreciated.


texts: Proving NP is a subset of the union of exponential DTIME

texts:
I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c > 1$.

Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a polynomial-size certificate in polynomial time with a turing machine $M$. So then we enumerate all possible certificates of polynomial size. There are $2^l$ possible certificates for a certificate of length $l$. For a certificate of length up to $n^c$, there are $\sum_{l=0}^{n^c} 2^l = 2^{n^c + 1} - 1$ many certificates. Each certificate can be decided in polynomial time, so we get that each problem in $\mathsf{NP}$ can be done in $\mathsf{DTIME}(2^{n^c}n^c)$. What am I doing wrong?


texts: How well do multi objective optimization algorithms such NSGAii scale when there are many objectives (for example 10 or more)?

texts: What I'm trying to figure out is what happens when using a multi objective optimization algorithm such as NSGA-ii and instead of trying to find the usual 2/3 objectives, I use 10 or many more objectives?


texts: Are time complexity of followng codes equivalent?

texts:
Implemented is done in C++.

Supposing we have defined a class T with no restrictions and three functions cond, next and f returning bool, void and anything respectively, are

for(T k = T(); cond(); next())
    f();

and

{
T k = T();

while(cond()) {
    f();
    next();
}
}

So, I would like know that time complexity of the following algorithms are same?


texts: Relation Between Priority Queue, Heap, Tree

texts:
There are $2$ "basic"/"fundamental" data structures due to the way memory works:

array
linked list

Then there are ADT that we implement using those two, for example: stack, queue and more.

When we arrive to priority queue we first need to implement and ADT called heap which can be implement using:

array
tree (which is ADT) the can be implemented using both array and linked list

So we have

array/linked list $\subset$ tree $\subset$ priority queue?


texts: Can anyone give an example for worst case of quick sort if we employ median of three pivot selection?

texts:
If we employ quicksort by selecting the pivot as the median of three elements viz., the first element, the middle element and the last element, then when will the algorithm hit worst case? and also can anyone give an example including integers?

Thanks.

Note: I have searched online for quicksort's worst case, but all of them are referring to quicksort wherein the pivot is either the first element or the last element, but what I want is completely different.


texts:
You have two binary search trees A and B, each one is a complete binary tree containing $2^k-1$
nodes. The maximum value of the keys in the tree A is less than the minimum value of the keys
in tree B.

Propose an efficient algorithm for creating a single height-balanced binary search tree containing the key values of all the nodes in both the trees A and B.


texts: Returning m greatest elements from k sorted array

texts:
We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$.

How can we get the $m$ greatest elements in running time $O(k + m\lg k)$?

I have tried to use MIN-HEAP size of $k$ since we have $k$ arrays. I have to navigate through the ends of the $k$ array somehow. By extracting the min of heap and getting new element from respective array was my idea but it does not work. I could not figure out getting m greatest elements.


texts: Confluence to show equivalent terms have one common reduct

texts:
In lemma 30.3.9, Pierce states a confluence property for $F_{\omega}$:

  $S \to_* T \land S \to_* U \implies \exists V. T \to_* V \land U \to_* V$

He then states the following proposition:

  $S \leftrightarrow_* T \implies \exists U. S \to_* U \land T \to_* U$

However, he doesn´t use the above property to prove it. I remember this was the case for other books on term rewriting systems that I read. However, to me it looks very simple to prove using the confluence lemma.

From $S \leftrightarrow_* T$ one has $S \to_* T$ and $S \to_* T \to_* S$ thus by confluence $\exists U. S \to_* U \land T \to_* U$.

Why is this approach not correct?


texts: If P = NP, why wouldn't $\emptyset$ and $\Sigma^*$ be NP-complete?

texts:
Apparently, if ${\sf P}={\sf NP}$, all languages in ${\sf P}$ except for $\emptyset$ and $\Sigma^*$ would be ${\sf NP}$-complete.

Why these two languages in particular? Can't we reduce any other language in ${\sf P}$ to them by outputting them when accepting or not accepting?


texts: Prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular

texts:
We have to prove that the language represented having equal number of $0$'s and $1$'s and starting with a $0$ is not regular.

Attempt: We assume that the language is regular. Thus it would satisfy the pumping lemma. Assume the pumping length to be $p$. Let us take the string would be length $p+1$ as  $0 0^p 1^{p+1}$. Now we need to divide this string into three parts $xyz$ such that the pumping property does not hold. The pumping lemma restricts the size of $xy$ to be less than or equal to $p$. So the y part can comprise entirely of only $0$'s. If we pump the $y$ part we can end up with strings having more number of $0$'s than $1$'s. Is this correct with respect to the string that has been considered? What other strings can be used to show this?


texts: What is an example of a Monte-Carlo algorithm for finding a Hamiltonian path?

texts: I've recently been made aware that there exist Monte-Carlo algorithm(s?) for determining whether a Hamiltonian path exists in a graph. I am struggling to figure out how it would work. What is the random element?


texts: How can i solve a recursion equation with square root using recursion tree method?

texts:
$T(n) = \sqrt{2}T(\frac{n}{2}) + \sqrt{n}$

I am trying to solve this question by recursion tree method, do we have any way in which we can draw a recursion tree for this eqn.
I just don't want to use master or extended master theorem


texts:
A Naive Bayes predictor makes its predictions using this formula:

$$P(Y=y|X=x) = \alpha P(Y=y)\prod_i P(X_i=x_i|Y=y)$$

where $\alpha$ is a normalizing factor. This requires estimating the parameters $P(X_i=x_i|Y=y)$ from the data. If we do this with $k$-smoothing, then we get the estimate

$$\hat{P}(X_i=x_i|Y=y) = \frac{\#\{X_i=x_i,Y=y\} + k}{\#\{Y=y\}+n_ik}$$

where there are $n_i$ possible values for $X_i$. I'm fine with this. However, for the prior, we have

$$\hat{P}(Y=y) = \frac{\#\{Y=y\}}{N}$$

where there are $N$ examples in the data set. Why don't we also smooth the prior? Or rather, do we smooth the prior? If so, what smoothing parameter do we choose? It seems slightly silly to also choose $k$, since we're doing a different calculation. Is there a consensus? Or does it not matter too much?


texts:
Wikipedia lists the time complexity of addition as $n$, where $n$ is the number of bits.

Is this a rigid theoretical lower bound? Or is this just the complexity of the current fastest known algorithm. I want to know, because the complexity of addition, underscores all other arithmetic operations and all algorithms which use them.

Is it theoretically impossible, to get an addition algorithm that runs in $o(n)$? Or are we bound to linear complexity for addition.


texts: Strict-Binary Tree - Same Post-order & Pre-order sequences?

texts:
I'm going through some past exam papers for my course and I'm having trouble completing this one question.

It is as follows: "Draw a strict binary tree with seven nodes that has the same pre-order and post-order traversal sequence".

Is this actually possible? Wouldn't I need to visit the root node before anything else for both sequences, that isn't possible with post-order traversal in a strict binary tree right? Unless the tree consisted of a single node?

I assume I'm missing something obvious. Post-order = LRN, Pre-order = NLR.


texts: Why we write "Ignore the input " when describing an Enumerator?(Sipser Chapter 3)

texts:
The Theorem and its proof is given below:

But I am wondering why we write "Ignore the input " when describing an Enumerator? could anyone explain this for me please?


texts: Why can't linear bounded automata accept an empty string?

texts:
The linear bounded automata (LBA) is defined as follows:

  A linear bounded automata is a nondeterministic Turing machine $M=(Q,\Sigma,\Gamma,\delta,q_0,\square,F)$ (as in the definition of TM) with the restriction that $\Sigma$ must contain two symbols $[$ and $]$, such that $\delta(q_i,[)$ can contain only elements of the form $(q_j,[,R)$ and $\delta(q_i,])$ can contain only elements of the form $(q_j,],L)$

Informally this can be interpreted as follows:

  In linear bounded automata, we allow the Turing machine to use only that part of the tape occupied by the input. The input can be envisioned as bracketed by left end marker $[$ and right end marker $]$. The end markers cannot be rewritten, and RW head cannot move to the left of $[$ or to the right of $]$.

Now I read that context sensitive grammar imitates the function of LBA and is defined as follows:

  A grammar is CSG if all productions in context sensitive grammar takes form
  $$x\rightarrow y,$$
  where $x,y\in(V\cup T)^+$ and $|x|\leq|y|$

Now people say that CSG cannot contain lambda or empty production (which takes form: $x\rightarrow \lambda$) as it will make make it impossible to meet the requirement $|x|\leq|y|$ and this can be understood.

However, what I don't understand is how informal interpretation of the working of LBA given above explains why LBA cannot accept empty string (which is why CSG does not have lambda production). Can anyone explain?


texts: How does hardware interrupt work on a physical layer

texts:
I'm a newbie in computer science and would to understand how hardware interrupts work at the physical layer. I ask my question considering a specific example. When packet arrives at the network adapter, a hardware interrupt is raised. Wikipedia says that

  an interrupt is a signal to the processor emitted by hardware or software indicating
  an event that needs immediate attention.

I know that the OS will invoke a corresponding interrupt handler when
the interrupt's type is detected. But I don't understand how the CPU detects and distinguishes incoming interrupts.

First, why CPU does know that the interrupt is coming from the network adapter and not from some other device?

Second, where are interrupt handlers registered in the CPU? Are there specific areas of the CPU that contain addresses for handlers registered by the OS?


texts: Maximum-cardinality matching in unbalanced bipartite graphs

texts:
Let $G = (X+Y, E)$ be a bipartite graph, and suppose we want to find a maximum-cardinality matching in $G$.
The Hopcroft-Karp algorithm runs in time $O(|E|\sqrt{|V|})$, where here $|V| = |X|+|Y|$. So if the graph is unbalanced and $|X|<|Y|$, the run-time is $O(|E|\sqrt{|Y|})$.

Is there an algorithm that attains a better worst-case runtime complexity for the case of an unbalanced bipartite graph, where $|X| \in o(|Y|)$? In particular, if $|X|$ is constant, is it possible to get run-time $O(|E|)$?


texts: Construct PDA for $Σ^* -\{(a^nb) ^n, n>0\}$

texts:
I want to construct a PDA for $Σ^* -\{(a^nb) ^n, n>0\}$ where $Σ=\{a, b\}$. Here is my try:
I know that context-free languages are closed under union operation. Also I know how to make a PDA for union. So I tried to decompose the given language to some parts. For example, the language of the strings starting by $b$, the language of strings ending with $a$, the language of strings containing $bab$ as a substring.
I made a context-free grammar for these languages. Then I made PDAs based on each grammar and I combined them to get a PDA for the union of them.
But I know that the union of these languages does not cover all strings in the given language. Could you help me find what I'm missing and how to make a context-free grammar for that?


texts: Subset on boolean cube with largest sum of biases

texts:
On the boolean cube $\mathcal{B}=\{0,1\}^n$, we assign each vertex a value by $p:\mathcal{B}\rightarrow[0,1]$. Let
$$\tilde{p}_i=\sum_{x\in\mathcal{B}}(-1)^{x_i}p(x).$$
What is the value of $\max_p\sum_{i=1}^n|\tilde{p}_i|$?

Since the objective $\sum_{i=1}^n|\tilde{p}_i|$ is convex on $p$, we can safely assume that $p(x)$ is either $0$ or $1$. So $p$ represents a subset of $\mathcal{B}$, and $|\tilde{p}_i|$ indicates the 'bias' of this subset on the direction of $x_i$. That's where the title comes from, but you can also think of it as bounding the L1 sum of some specific Fourier coefficients.

I tried to solve it combinatorially: let $f(n,k)$ denote the maximum value when $p$ represents a subset of size $k$. By considering the size of the intersection with $\{x\in\mathcal{B}\mid x_n=0\}$, we have the following recursive relation:
$$f(n,k)=\max_{0\leq\ell\leq k} f(n-1,\ell)+f(n-1,k-\ell)+|k-2\ell|,$$
for all $0\leq k\leq 2^{n-1}$. And clearly $f(n,2^n-k)=f(n,k)$. I ran a program to compute the first several terms of $\max_k f(n,k)$, which is always $f(n,2^{n-1})$:
$$1,2,6,12,30,60,140,280,630,\cdots$$
It seems to be $n\cdot\binom{n-1}{\lfloor n/2\rfloor}$, and this value can indeed by achieved when the subset consists of those $x$ with Hamming weight at most $\lfloor n/2\rfloor$.

It would be great to have a formal proof of this observation. A direct proof via the properties of Fourier coefficients on the boolean cube would be even better. Thanks in advance.


texts: What is the computational complexity of k bit subset sum problem?

texts:
The k bit subset sum problem is:

Input:

$(S, k, b)$ where $S$ is multi set of positive integers encoded in binary (base 2), $k$ is also positive integer encoded in binary (base 2) and $b$ is bit (binary digit) so that always $b\in\{0,1\}$.

Output:

True if exists subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.

False if does not exist subset sum of $S$ whose $k$ bit (binary digit) equals to $b$.


texts: String Search - how to find the "most" accurate string?

texts:
Assume I have the following list of companies:

Apple
Big Apple
Google

Then I have this sample string:

  Big Apple is a company that is trying to be the next Google.

Given the list of companies and the sample string above, how can I find the list of companies in the sample string?

If I iterate through the list of companies and search for it in the sample string, I would find three matches: Apple (because "Apple" exist in "Big Apple"), Big Apple, and Google. In my scenario, I wouldn't want just Apple to match since Big Apple is a more accurate match.

I'm trying to implement the solution in PHP, but a general description/strategy on how to solve this would be helpful.


texts: Is the 3D-matching still NP-complete if all elements occur in exactly three triples?

texts:
The 3D-matching problem is known to be NP-complete even if all elements occur at most three times (see Garey&Johnson). My question: Is it also NP-complete if all elements occur in exactly three triples?
The 3D-matching is defined as follows: Let $W, X, Y$ be disjoint sets with $|W|=|X|=|Y| = q$. Let $M \subset W \times X \times Y$. Is there a subset $M^\prime \subset M$ with $|M^\prime| = q$ such that all elements are disjoint in each coordinate? That means, each element in $W,X$ and $Y$ occurs exactly once in $M^\prime$.
The bounded version means, that each element in $W,X$ and $Y$ occurs in at most three triples in $M$. My question asks for the case where each element occurs in exactly three triples in $M$.


texts: Pumping Lemma for regular language for $a^n$ where $n$ is even fails

texts:
$$L=\{a^n \mid \text{\(n\) is even}\}$$

This is regular but fails in the pumping Lemma.

Assuming $m=4$, $w=aaaaaa$, $|w|=6$ (even).
Let $w=xyz$,
$x=a$,
$y=aaa$.
We have $|y|>0$ and $|xy| \le m$.

Let $w_i=xy^iz$.
For $i=2$,
$w_2=xy^2z=aaaaaaaaa$.
$|w_2|=9$ therefore it is not regular.

Where am I going wrong?


texts:
Suppose we had a domain with two individuals, $x$ and $y$. Suppose we had two predicate symbols $p$ and $q$ and three constants $a$, $b$, and $c$. Suppose we had the knowledge base KB defined by:

  $p(X) \leftarrow q(X)$
  $q(a)$

  How many of these interpretations are models of KB?

So we know that in total there are 128 interpretations (Models and non-models).

Constants $a,b,c$ can have two different individuals $\{x,y\}$: $2^3 = 8$
There are two possible values $\{true,false\}$ each for: $\pi(p(x)), \pi(p(y))$: $2^2 = 4$
There are two possible values $\{true,false\}$ each for: $\pi(q(x)), \pi(q(y))$: $2^2 = 4$
$8 \cdot 4 \cdot 4 = 128$

But now we have to subtract all the interpretations that are not acceptable (no models) from 128. Supposedly the solution should be 24, but I cannot wrap my head around it.


texts: What is the space-complexity of a boolean first-order query?

texts:
I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant).
However, in the very specific case of word-structures, I have read that regular expressions captures Monadic Second Order Logics, and hence, first-order queries. Furthermore, regular expressions can be transformed into DFA, which can be further implemented in an algorithm whose memory consumption does not depend on the size of the input. Hence, if my argument is correct, at least in the very specific case of word-structures, the amount of memory consumed for a (space-efficient) first-order query solver should be constant.
Is the space-complexity of solving a boolean first-order query contant (w.r.t. data complexity) only for the case of word-structures? Or is this the general case?
I know that the data-complexity of a first-order query is AC^0, however, I do not know how to relate circuit complexity with space-complexity.


texts: How can I use nested loops to print out this triangle word pattern?

texts:
I'm trying to make a pattern that looks like this:

And am given this code to start:

import static java.lang.System.*;

class TriangleWord
{
private String word;

public TriangleWord()
{
    word = "";
}

public TriangleWord(String w)
{
    setWord(w);
}

public void setWord(String w)
{
    word = w;
}

public String toString()
{

}
}

There's also a runner involved. Please help!!


texts: I know the difference between deadlock prevention and avoidance. But i want to know the difference between deadlock avoidance and detection. ?


texts: Partial intersection of 10 sorted lists of integers

texts: Suppose I want to find the numbers that appear in at least 3 of the 10 sorted lists, is there an efficient way to do it apart from iterating over all 10 of them in parallel?


texts: Red-Black Tree deletion algorithm (CLRS, 3rd edition) : Deleting the root

texts:
I have been following the third edition of Introduction to Algorithms (by Cormen, Rivest, et al.), and have been studying the deletion algorithm for red-black trees. However, I am confounded at the moment while I am trying to delete a node from the tree.
The algorithm could be found at Page No. 324, third edition, Introduction to Algorithms,(CLRS).
Suppose I have a red-black tree as follows:

This RB TRee was constructed by inserting the number 1 to 7 in non-decreasing order (i.e. 1,2,3,4,5,6,7).
Suppose we wish to delete the root of the tree, node 2.
Then as per the delete algorithm, on page-324,
1. y = z (i.e. y = ROOT of the tree)
2. y-original-color = BLACK
3. z.left exists, skip lines 4-5
6. z.right exists, skip lines 7-8
9. Now y = tree-minimum(z-right), i.e. y is a pointer to 3
10. y-original color = BLACK
11. x = y.right (i.e. T.NIL only)
12. y's parent = pointer to 4, which is not z (i.e. ROOT), skip line 13
14. Else transplant y with y.right, i.e. left of '4' is T.NIL now
15. Lines 15-16 fix the new parent issue for the transplanting node
17. Line 17 transplants z (i.e. the ROOT) with the pointer y, i.e. 3 is the root now
18. Lines 18-21 fix the parent and left child issue for the new ROOT
21. as y-original-color is BLACK, call the RB-DELETE-FIXUP function for x

As x is T.NIL, this is passed as an argument for the RB-DELETE-FIXUP function.
However, there is an issue.

How can we claim the parent of this x, i.e. the T.NIL, for the purpose of finding its sibling?
Even if we claim that 4 be the parent of this x, and 6 be the sibling (as per the diagram), then the deletion falls under none of the categories mentioned in the book since 6 is a BLACK parent and both of its children are RED.

I have been following the algorithm and have been quite confounded by this case. Maybe there is a misinterpretation on my end regarding following the algorithm. Any help in this regard would be appreciated.


texts: How to create DFA from regular expression without using NFA?

texts:
Objective is to create DFA from a regular expression and using "Regular exp>NFA>DFA conversion" is not an option. How should one go about doing that?

I asked this question to our professor but he told me that we can use intuition and kindly refused to provide any explanation. So I wanted to ask you.

"Regular exp>NFA>DFA conversion" is not an option because such a conversion takes a lot of time to convert a rather complex regular expression. For example, for a certain regex "regex>NFA>DFA" takes 1 hour for a human being. I need to convert regex to DFA in less than 30 minutes.


texts: Is the power of a regular language regular? Is the root of a regular language regular?

texts:
If $A$ is a regular set, then:

$L_1=\{x\mid\exists n \geq0, \exists y \in A: y=x^n\}$,

$L_2=\{x\mid \exists n \geq0, \exists y\in A: x=y^n\}$.

Which one of them is regular?

My reasoning is since in $L_2$ we can have uncountable $x$ from even one value of $y\ (y^0, y^1, y^2,...),\ L_2$ cannot be regular. But that thinking seems wrong.


texts: How hash-table and hash-map are different?

texts:
In the context of CS, how the hash-table and hash-map are different?

I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are somewhat confusing.

As far as I understand,

hash table → stores keys only → Swift Set.
hash map → stores key/value pairs → Swift Dictionary.

But, Wikipedia is talking hash-table is same thing with hash-map. Here I could not find any help.

Is this formal or widely accepted CS term? Am I understanding correctly? If I'm wrong, please correct me. Thanks.

I know industry uses their own terms that can be different, and I am asking about academia because I believe terms are more consistent in academia. If it's not, I just would abandon to learn academic terms.


texts: What subfields in computer sciences may one study without learning Object Oriented Programming?

texts:
What subfields in computer sciences may one study without learning Object Oriented Programming or is there some kind of degree in Computer Science without the OOP knowledge requirement?
Is there a language without OOP?
Does one need to know OOP to simulate a CPU?
I wanted to earn a CS degree without ever learning OOP. Is there a name for that?
My guess what that Computer science without OOP is simply applied Statistics or Machine Learning using SKlearn and packages.


texts:
Is this language Context Free?

$L=\{a^{n+3} b^{2m} \mid n \neq m \}$

I think that I could split the languages into $L_1$ and $L_2$ with the conditions $n<m$ and $n>m$, provide 2 CF grammars and then to make the union. But I don't know how to put the condition $n<m$ to the grammar or how to think about the conditions. Thank you!


texts: How can I do a subtraction on unary numbers terminated in X on turing machine?

texts:
For example, if I have 11X1111X as input, the result should be X. For another example, input: 1111XX -> 1111X. I am a complete beginner and all my tries so far failed to meet the expectation.
This was my latest try:


texts: Deduplication: how to implement content-defined chunking?

texts:
I'm writing deduplication program that implements content-defined chunking. Just now i know 3 algorithms to do it (hashing a fixed-size window and selecting hashes < maxuint/N, hashing an order-1 bounded window, and local maxima chunking). Are you know other algorithms or ideas to improve these ones? My goal is to get best compression for a given average chunk size.

A few deduplication-related links:
http://en.wikipedia.org/wiki/Data_deduplication
http://encode.ru/threads/1726-Deduplication-X-Files


texts: How can I debug my pseudocode algorithm?

texts:
The algorithms for the problem I am working on become more and more complex as I try to improve their performance. They already span several pages with cases and sub-cases, and will probably become even longer. I am worried that there might be mistakes that are difficult to notice.

As a programmer, I am used to writing detailed test-cases to test my programs, but the algorithm is written in pseudo-code (it is not easy to implement). What ways can you recommend for testing the algorithm?


texts: What is the minimum pumping length of the following languages?

texts:
How to determine the minimum pumping length of union of two languages?  How do I proceed after determining the individual pumping lengths?

0*1+0+1* U 10*1 - Here the minimum pumping length of the first expression is 1 and of the second is 2. I am  stuck here ! Now what do I do?
001 U 0*1* : The min PL of first expression is 4 and of the second is 1 , now what's the overall minimum PL?


texts: Extract Max for a max-heap in $\log n + \log\log n$ comparisons

texts:
Given a max heap with extract-max operation.

The basic version takes $2 \log n$ comparisons.
How can I make the running time just $\log n + \log\log n$ comparisons?
How about $\log n + \log\log\log n $ comparisons?

I thought of putting $-\infty$ on the heap root but not really sure what to do with it as it can go anywhere.

To be more precise, I'm only counting comparisons between array item values. I'm reading CLRS Chapter 6 (MAX-HEAPIFY and HEAP-EXTRACT-MAX).


texts: An algorithm for effecient resource redistribution

texts:
For those who think visually, say I've got 5 warehouses with a current stock level of # of fish, and a target level for each.  How do I achieve the new target levels in as few truck shipments as possible?

Or given an array A{250, 150, 45, 205, 350}, how can it be transformed to {200, 200, 150, 320, 130} in as few transfers as possible?  Moving 50 from A[0] to A[1] would be an efficient first move.
I'm sure I could muddle through this and come up with something, but I'm also sure this problem has already been solved by people smarter than me.  And it's important to me that it be correct and as efficient as possible.  This is a little outside my normal work, and I'm not sure how to search for something like this (I couldn't find anything).
Thanks much!

Update:
An initial thought ... find the warehouse with the biggest deficit, then find the one with the biggest (or closest matching?) surplus, do the shipment, then repeat.  Seems like that would work, but I'm not sure if there's a more elegant or efficient solution.  I'll add an answer once I've got the code working.


texts: Euler Circuit with least deviation from input

texts:
So given an undirected graph stored in form adjacency list using vector<int> adj[], I have to print the Euler Cicuit. Every edge is given as follows a bmeaning an edge from a to b.

But the problem is I have to follow the given order of input of vertices connected by an edge and change the order whenever it is compulsory.

For eg- input:

a b
c b
c a

Now for the cycle it has to be from b c. But if it was

a b
b c
c d
d b
b e
e a

There are multiple answers but I want the answer which deviates least from input. So the answer will be same as input.

How can I do this ? I found that Hierholzer's algorithm can be used to print the euler circuit. But the order will not be as I want.


texts: Converting Recursion into Into Iteration

texts:
While reading Code Complete second edition, I came across this line:

  You can do anything with stacks and iteration that you can do with
  recursion.

Is this true? or there are functions, that must be implemented recursively, and can't be done otherwise ?


texts: Method for measuring the 'similarity' between FSA grammars?

texts:
I'm working with a pattern matching algorithm that generates an acyclic finite state automaton that accepts a given text string and all its substrings. The FSA algorithm is being run on a symbolic representation of a music stream (e.g., MIDI data). The music stream has been preprocessed to divide each song into unlabeled 'segments'. An FSA is generated for each segment in each song: if I have $n$ songs, each divided into $y$ segments, I will have $n \cdot y$ separate FSAs.

I would like to compare each segment's FSA with the other FSAs in my corpus. The ultimate goal would be to do clustering within a similarity space and come up with 'classes' of segments according to how similar their construction metrics are. Thus, of particular interest are the grammars that each FSA defines (corresponding roughly certain components of the musical content in the segment). Are there techniques that might be good for comparing something like this? KL-divergence comes to mind (e.g., using it compare the distribution over strings associated with a given FSA), although there may be better/more efficient techniques?

Also, apologies if this question is either (1) trivially easy or (2) indicative of some deeper misunderstanding or (3) answered elsewhere. I'm a real nub, folks!


texts:
I'm trying to find the best algorithm for converting an “ordinary” linked list into an “ideal" skip list.

The definition of an “ideal skip list” is that in the first level we'll have all the elements, half of them in the next level, a quarter of them in the level after that, and so on.

I'm thinking about a $\mathcal{O}(n)$ run-time algorithm involving throwing a coin for each node in the original linked-list, to determine for any given node whether it should be placed in a higher or lower level, and create a duplicate node for the current node at a higher level. This algorithm should work in $\mathcal{O}(n)$; is there any better algorithm?


texts: Computation Complexity books for a mathematician

texts:
I recently attented to some computational complexity talks (or complexity theory, I am not sure which is the correct name) and I fell in love with it. I would like to find some books, online courses... in general resources of any kind to self-study this (securely) wonderfull subject.
My backgrund is pure mathematics with emphasys in discrete mathematics (graph theorey, crypto, coding thoery, combinatorics...), with no background in computer science. I am not sure if the last one is mandatory.


texts: Even distribution of weighted sums across a period of time

texts:
I want to automatically&optimally split and distribute a number in several buckets as evenly as possible across a period of time.
Example:

5000 across 12 months, in 6 buckets, with weights 15%, 20%, 15%, 10%, 30%, 10%, and a minimum of 100 per month per bucket; that is ~416 per month across buckets

Rules:

This is the catch: there has to be a minimum in each bucket (100 in our example; obviously, if this is zero, then the solution is very easy aka just an average)
Amount in each bucket doesn't have to be a whole number
Weights must be respected
Each bucket may skip a month of two, just so the sum per month across buckets adds up to 416

An example of my manual effort

Generalization and nice-to-haves

Configurable number of buckets & number of periods
Configurable minimum amount per bucket per month

References

Distribute value evenly across a number of cells


texts: Need a polynomial time reduction from 3SAT to INDEPENDENT-SET

texts:
In order to show that a problem is NP hard one must provide a reduction from a known NP hard problem to this problem.
My question is how to reduce 3SAT to INDEPENDENT-SET?

3SAT is a satisfiable 3 literals in a clause Boolean conjunctive normal formula.
INDEPENDENT-SET is a set of vertices in a graph, no two of which are adjacent.
I do know how to reduce 3SAT to a Clique, would that help?


texts: Conditions for bipartite graph to be planar with no edges going around the vertices

texts:
A bipartite graph is planar iff it has no $K_{3, 3}$ or $K_5$ minors.

I am looking for a necessary or/and sufficient conditions to allow planar drawings with no edges "going around" sets of vertices. These are drawings satisfying:

All vertices of one part are drawn on a single vertical line. Vertices of the other part are drawn on a parallel verticle line.
Edges do not intersect except at vertices.
Edges are all in the infinite strip between the two vertical lines in point 1.

For example, all drawings here except the bottom right are non-examples. The bottom-left graph can be re-drawn to satisfy the conditions by swapping the positions of Q and R. The tops two graphs cannot be redrawn to satisfy the conditions.

The top two graphs are the only obstructions I could find. My questions are:

Does this problem have a name?
Any other obstructions that I missed?
Any hints on how I can prove that these two obstructions (along with anything I missed), as minors of course, are necessary and sufficient.

Note that this is not the same as being outer-planar, $K_{2, 2}$ is outer-planar (can be drawn as a square) but it cannot be drawn to satisfy the conditions I mention above.


texts: Major Field Test Sample Questions (need further clarification)

texts:
I have several questions that do no make sense for me.

First Question:
A stack can be implemented with an array A[0..N-1] and a variable pos. The push and pop operations are defined by the following code.

push (x)
  A[pos] <- x
  pos <- pos – 1
end push

pop ( )
  pos <- pos + 1
  return A[pos]
end pop

Which of the the following will initialize an empty stack with capacity N for this implementation?

a)pos <- -1

b)pos <- 0

c)pos <- 1

d)pos <- N - 1

e)pos <- N

I have zero idea for this question and I dont understand what is being asked

Second Question: Consider the following recursive function

int Fun ( int n )
if ( n == 4 )
  return 2
 else
  return 2 * Fun ( n + 1 )
 end if
end Fun

What is the value returned by the function call Fun(2)?

a)2

b)4

c)8

d)16

e)24

The answer is C but I got 6 cox this is how I did it, because n is 2 and it not 4 so it return 2 * (2+1) which is equal to 6

Third Question: Following is a definition of a widget and a declaration of an array A that contains 10 widgets. The size of a byte, short, int, and long are 1,2,4 and 8 bytes, respectively. Alignment is restricted so that an n-byte field must be located at an address divisible by n. Th fields in a struct are not rearranged padding is used to ensure alignment. All widgets in A must have the same size

struct widget
  short s
  byte b
  long l
  int i
end widget

widget A[10]

Assuming that A is located at a memory address divisible by 8, what is the total size of A, in bytes?

a)150

b)160

c)200

d)240

e)320

The answer is D but I dont understand why is it D and not C.


texts: How to apply the pumping lemma to this CF string?

texts:
I am struggling understanding how to apply to pumping lemma to a CF string.

I've got this string:

$$ a^{n}b^{n}c^{m} $$

I would like to understand the steps to apply the pumpuing lemma for this particular string and hence for any other.

At the moment I  have tried to decompose the string to $u,v,w,x,y$ with a trial and error approach but I can't figure out what is the procedure to retrive the result systematically.

I know that pumping lemma is condition neccessary but not sufficient to assert that a string belgons to CF, but I would like to understand how to apply the pumpuing lemma to this particular string.


texts: How to prove that the subset sum problem is polynomially reducible to the knapsack problem

texts:
I want to prove that the subset sum problem is polynomially reducible to the Knapsack problem. Overall I want to show that Knapsack is NP-complete.
There are two parts to showing knapsack is NP-complete

knapsack is in NP
If I show that the subset sum problem is polynomially reducible to the knapsack.
Then since subset sum problem is known to be NP-hard. Knapsack is NP-Hard

Both 1) and 2) imply that Knapsack is NP-Complete

Is trivial as given any sequence of items we can verify the sum of their value
and weights in linear time. So the knapsack is in NP. Correct me If I am wrong here.

How do I approach 2)? I am not sure how to phrase the polynomial conversion
from the subset sum problem to the knapsack.


texts: vector hashing function having collisions for permutations

texts:
let's consider vectors in space dim=3 and values {0,1,2,...,99} on each dimension I would like to create hash function but with special trait: collisions only for permutations on input

$\forall_{x, y \in N^3} (y = permutation(x) <=> hash(x) == hash(y))$

is it even possible but without sorting? if so please attach example :)

one idea is to sort these values and then just create a key like $x_1*10e4 + x_2*10e2 + x_3$, for higher dimensions sorting would slow down solving a bit, so is it possible without sorting?


texts: Why do floating point values have infinity?

texts: Why do floating point values have infinity instead of just a higher exponent?


texts:
I was doing some complexity theory exercices and I came over this one:

$AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$

Is $AlwaysHalt$ recursively enumerable?

I would say YES and construct the following TM that accepts this language:

Enumerate all $x \in \{0,1\}^*$ starting with length 1 and then increasing the length in every iteration and try the current $x$ with our TM $M$. We only care about those machines $M$ that halt with all words (we do not care if we do not halt, it would only mean that $R(M)$ is not in our language) so each $x$ will halt  eventually. There is only countably many words $x \in \{0,1\}$ so we can do that.

However, I am not sure if this is a correct proof? Can I enumerate all words from and infinite (but countable) language to  show that a TM behaves in some way on every single one of them?


texts: Can constraint satisfaction problems be solved with Prolog?

texts:
Is "party attendance" type of problems solvable in Prolog? For example:

  Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came.
  Whom is needs to be persuaded to attend the party in order to ensure that all her invitees attend?

I have tried to express this in GNU Prolog:

attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP).
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC).
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

I'm experiencing stack overflow (no pun), and have no knowledge of prolog evaluation, this is why I'm asking.

Generally speaking, this problem can be cast into Boolean CNF satisfaction formula (with 6 boolean variables). Therefore, does the prolog perspective have any merit?


texts: Is Vertex Cover of size $k >100$ polynomial time solvable?

texts:
I know that when we want to find out if Vertex Cover of size $k$ when $k
\leq C$, belongs to P or not (when $C$ is some constant), we actually
can find algorithm with polynomial time complexity (in the algorithm we
iterate over subsets $V'$ such that $|V'|=C$).  But what about $k \geq
C$?
I personally think it's not in P because $k$ can be as most in size
$|V|$, and therefore the time complexity is exponential, but I'm not
sure if I'm right (maybe it's unknown?)


texts: Find a $\log_2(|V|)$ long cycle where each node is of different color

texts:
Here's a question from an algorithms exam by Prof. Noga Alon that I just can't wrap my head around.

Let $G=(V,E)$ be a directed graph where $|V|=n$. Let $k=\lfloor \log_2(n)\rfloor$. Each node in the graph is in one of $k$ colors. Give an efficient algorithm to determine if there exists a simple cycle of length $k$ in the graph where each node has a different color.

I really don't know where to start with this. I thought about breaking the graph into subsets of nodes of each color and having multiple copies of each subsets in order to force a color change with every edge we traverse but I couldn't get this to work. Any hint is appreciated!


texts: Counting tokens in compilers, lexical analyser

texts:
Let's start with the question.  Say I have a C language statements follows

it 458cat 2.01 = 96.87abc a.2 ;

-my question is how many tokens are there in the above statements. Secondly does white space like tabs, newline, makes a token or not?
If you are interested in my solution then  proceed on your own risk. Firstly I think in lexical analyser there is no such thing as white space so after removal of that the above statement would look catastrophic so, I have not taking that approach.
Now we see 'it' as an identifier similarly, '458' as integer, 'cat' as identifier, (please not that I may have mistaken here which i don't know that is '458cat' may be invalid identifier so the lexical analyser may report an error, but I don't know will that happen or not. you may argue that what I have written is wrong because  if it was true then the identifier like '678hello' will be a valid identifier but since its not then iam wrong. But take a different approach like if all white space between '468   abc' being vanished (this is what lexical analyser does first) then it would like '468abc' . Initially in case of  468 abc we were taking 468 as integer and abc as valid identifier but after  white space removal things are changed so what I think is it will be reported in syntax analyser  but I don't know that am I right), similarly, '2.01' as real integers, '=' as operator, '96.87' as real number, 'abc' as identifier, 'a ' as identifier, .2 as real number and ' ; ' as special symbol.
I most certainly know that iam not right but if you could correct where I was  wrong it will be helpful


texts: Need an adaptive algorithm for participant subgroups that balances repeated pairings

texts:
I want to build a utility that helps manage small groups of participants. It is an acting class setting.
For each exercise, the facilitator will usually have some number of participants get up to do a scene. Two is the most common, but sometimes 1 or 3 or 4. More than 4 is not common.
I want the utility to have a list of participants and then the facilitator can just ask it for a specified number of people. E.g. 2.
The utility should do a good job of balancing combinations. For example, let's say there are 5 participants, A, B, C, D, E. If A and B work together, then ideally they should have also worked with C, D, and E before working together again.
I know how to manage this well if it's always just pairs. You can create, in advance an ordered list of all the pairings.
But once you add the possibility of other changeable group sizes, I don't know how to manage it.
My starting point is to keep track of how often each participant has worked with every other participant. So, I could look at A and know how often she has worked with B, C, D, and E, and then if A is due to get up, pair her with the person/people she has worked least often with.
The problem with this, is that it can lead to situations where the last remaining unmatched pair have already worked together.
As a simple counter-example: Say I have 6 participants - A - F. In the first lot of exercises, these are the pairs. AB CD EF. Then next round, I might (if not thinking) do AC, then BD, but now I'm left with E and F again. This is not ideal, and is what I need the algorithm to avoid.
I think part of the solution should be that everyone should get a roughly even number of turns. So, at any given point, we have a group of participants who have had fewer turns that the others, and we need to balance them out so that they don't work with people they've worked with (where possible) or at least with the people they've worked with least, and it needs to anticipate the possible remaining combinations and avoid duplication there too. Part of the complexity is that you don't know in advance what group sizes will be used for the remaining groups.
Does this type of algorithm / problem set have a specific name? Are there known algorithms for solving it?
(As an extra complication, there is the possibility of a participant having to leave unexpectedly, or an extra participant who arrives late, but that might be for later)
This is my first time asking here, so I hope I've posted this appropriately. Thanks for your patience and assistance!


texts: Given a directed graph and a vertex v, find all cycles that go through v?

texts:
Given a set of uniquely numbered items that each has three attributes id, from and two in the following format,

{id, from, to}

we would like to find all cycles that a particular item participates in.

For example, given the following items

{id:1,  from:h, to:l},
{id:2,  from:b, to:e},
{id:3,  from:p, to:q},
{id:4,  from:e, to:h},
{id:5,  from:e, to:g},
{id:6,  from:l, to:m},
{id:7,  from:m, to:k},
{id:8,  from:k, to:i},
{id:9,  from:g, to:i},
{id:10, from:i, to:b},

we can construct a directed graph

Each item is connected or related to another by the from and to attributes and there can be items that are not related to any others (for example the item with id = 3 in the example above).

The input is the id of an arbitrary item within the array and the output of the algorithm is the list of cycles that each item participates in. For example, based on the image above, examples of the expected output are:

Given the id = 7, the expected result is:

An array containing this single array (or its equivalent circular linked list).
That is, the items connected by the blue line.
If the items in the inner array are rotated by N, it's ok.

output = [
    [
        {id:7,  from:m, to:k},
        {id:8,  from:k, to:i},
        {id:10, from:i, to:b},
        {id:2,  from:b, to:e},
        {id:4,  from:e, to:h},
        {id:1,  from:h, to:l},
        {id:6,  from:l, to:m}
    ]
]

Given the id = 2, the expected result is:

An array containing two arrays (or their equivalent circular linked list).
That is, the two collections of items connected by the red and the blue line.
If the items in the inner arrays are rotated by N, it's ok.

output = [
    [
        {id:2,  from:b, to:e},
        {id:5,  from:e, to:g},
        {id:9,  from:g, to:i},
        {id:10, from:i, to:b}
    ],
    [
        {id:2,  from:b, to:e},
        {id:4,  from:e, to:h},
        {id:1,  from:h, to:l},
        {id:6,  from:l, to:m},
        {id:7,  from:m, to:k},
        {id:8,  from:k, to:i},
        {id:10, from:i, to:b}
    ]
]

So, the questions is what could be the possible algorithm and data structure to resolve this problem? It's ok to have whatever time/space complexity. Optimizations can be performed later.


texts: Understanding hashtable performance in the worst-case

texts:
Under assumption that the hash function is uniform, we have worst-case performance for the search operation in a separate-chaining (e.g. java.util.HashMap) hashtable $O(\log n)$. Why? I cannot really understand this. If we have a uniformly-distributed hash values it should be the case that each hash bucket contains approximately the same number of elements.

Therefore, if we have load-factor (buckets_number/elements_number) say $0.5$, we guarantee the constant-time performance for search operations $O(2)$.


texts: Generating finite automata from regular expression

texts:
Right now I am trying to learn how to work with automata and regular grammar, and I encountered the following exercise:

$(1^*01)11$

I found the following solution, but I am not really sure if it's right.

What I didn't understand it's from where exactly I should continue after I close the parenthesis or start a new one (let's say the expression was $11(1^*01)$ . When I start the parenthesis and I have A ->1B -> 1C, do I continue the automata after the C or I return to A?

Thank you.


texts: Example of a non-regular language that is a subset of a regular language?

texts: How can this be? I don't think it is actually possible for a non-regular language to be a subset of a regular language. What examples are there where this is true?


texts: Does "output" always imply halting in computability?

texts:
$L = \{P : P(n)$ outputs $n^2$ for all $n \in N  \}$

In questions of this nature, are we supposed to assume that "outputs" means "halts and outputs"? In modern programming languages, I can certainly "output" using a print statement and then have the program go into a loop after that.


texts: how does the program change the clock speed of the processor?

texts:
bios is a program that checks all devices and starts the bootloader.
but how does the CPU sync with the motherboard if the CPU clock settings are stored in the BIOS?

Does the BIOS have CPU clock frequency settings?
how does the BIOS adjust the clock speed of the processor if it's just a program?
does the BIOS synchronize the internal clock of the processor with the external clock on the motherboard?
does the processor first start on the external clock, and after synchronization - on its own internal clock frequency?
does the change in the CPU clock speed mean its own internal clock due to heating problems (throttling)?
How can the operating system change the clock speed of the processor? does it really change the cpu settings or put some limits on the task scheduler? (Are Linux and Windows the same with this?)

I am completely confused about how the processor actually syncs at startup and sets the clock speed?
please explain me.
answer as processor clock = base clock * multiplier. I do not understand


texts: Sampling a uniform distribution of fixed size strings containing no forbidden substrings

texts:
Given a list of "forbidden" words (substrings), an alphabet, and a desired output string length, how would I efficiently sample output strings containing no forbidden word?

For short output strings with few forbidden words, I would use simple rejection sampling. Pick a string (uniformly) with the specified alphabet and length, return that string if it contains no element of the forbidden list, try again otherwise.

If I use that algorithm for output lengths several times larger than the typical forbidden word, then the probability of rejection will be higher. (Most words are 2 or 3 characters long.)

Assume the requested output length is too long to enumerate and store every possible value. My alphabet size would be 16 to 36 characters, but solutions to large alphabets would be interesting to  think about. (In which case I would call these things random sentences, forbidden n-grams, and dictionary words.)

My forbidden word list will have one hundred to one thousand strings. I would like to avoid solutions requiring expensive precomputation or lots of memory.

My first idea was to try to build a random string incrementally, in contrast to the all-or-nothing approach of straightforward rejection sampling. I doubt that my algorithm produces each possible output with equal probability.

The algorithm idea follows:

Initialize a char buffer long enough to fit outlen characters.
Pick a random letter of the alphabet and append it to the buffer.
If the buffer ends with a forbidden word of length k, then remove the  last k letters from the char buffer and go to 2.
Otherwise, go to 2 if the buffer has less than outlen characters.
Return the contents of the buffer if it is full.

Step 3 serves to rewind the algorithm, returning the char buffer to a previous legal state.

I understand that clearing the whole buffer in step 3 definitely would produce uniform output just like the straightforward rejection sampling method. However, the average number of rejections before the first valid output is generated will be the same.

I've gotten stuck trying to determine if my proposed algorithm is uniform. I have had no luck finding alternative algorithms either. I haven't yet looked at how this algorithm's performance would compare to basic rejection sampling.


texts: Approximating longest path on graphs with average degree n/2

texts: I have a graph with average degree $n/2$. How I can find an approximation algorithm for the longest path problem with factor $1/4$?


texts: 2-dimensional ranking of multiple arrays

texts:
Given a fixed dimension $d$, say $d=2$ we want the following:
Input: $A_1\ldots A_m$: $m$ arrays of length $n$ of integers
Each input array $A_i$ must be a permutation of the numbers $1..n$, so in each array each number from $1$ to $n$ appears exactly once.
Output: For each tuple (pairs in the case $d=2$; triplets in the case of $d=3$ etc. In this example we'll use pairs) of numbers $(1,1),(1,2)\dots(n,n)$, we want a count for in how many input arrays the first number of the tuple is also the first to appear in the array (among the numbers of that tuple). The order in which the other numbers of the tuple appear in an array doesn't matter, as long as they come later than the first number of the tuple.

Question: Can this be done quicker than $O(mn^d)$ in the worst case?

Upper and lower bounds
The output is represented as a $d$-dimensional array of length $n$. Therefore a lower bound for the runtime complexity is $O(n^d)$.
The naive approach is to create $m$ mappings from each number to its index for each input array. Then for all $n^d$ tuples, walk through the $m$ mappings, yielding a runtime complexity upper bound of $O(dmn^d)$ and since $d$ is a constant this is $O(mn^d)$.
Examples
A = (1,2,3,4),        Output =  1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4),     =>       1 | 4 4 4 4
    (1,2,3,4)               2 | 0 4 4 4
                            3 | 0 0 4 4
    d=2, m=4, n=4           4 | 0 0 0 4

=======================================

A = (4,3,2,1),         Output = 1 2 3 4
    (1,2,3,4),                  -------
    (1,2,3,4)      =>       1 | 3 2 2 2
                            2 | 1 3 2 2
    d=2, m=3, n=4           3 | 1 1 3 2
                            4 | 1 1 1 3

Application
While writing poker analysis software, I'm particularly interested in the case $d=3, m\approx 1250, n\approx 1250$. I estimate that the naive $O(mn^d)$ solution takes multiple hours but less than a day when using native Java arrays (no hashmaps etc) on a single thread.
$d$ stands for the number of players that are still active during a poker hand. Normal poker software handles the case $d=2$. Some high-end software handles the case $d=3$.
I'm interested in the case $d=2$, but then the naive approach is already quick enough in most situations. I'm mainly interested in the case $d=3$. I'm less (but still) interested in the case $d=4$ which is probably unfeasible and even less interested in greater values. I'm not interested in $d>10$. A poker table has 10 players max. The values of $m$ and $n$ do not increase/decrease with $d$.


texts: Proving $\lceil \lg n \rceil -1 = \lfloor \lg n \rfloor$

texts:
I recently came across the question:
Show that there are at most $\lceil n / 2^{h + 1} \rceil$ nodes of height hh in any nn-element heap.
I looked for some solutions and found this one:
Binary heap: prove that number of nodes of height h is not bigger than $\lceil \frac{n}{2^{h+1}} \rceil$
But I got confused with the answer which used the expression:
$$\lceil{\log_2n}\rceil-1$$
as the height of the tree.
But, I am confused because I have earlier proved that the height of the tree is:
$$\lfloor \lg n \rfloor$$
Even if I consider both are the same it could only be true if $\lg n$ returns a decimal value instead of an integer.
For example, consider an example of taking $n=4$ the example would fail as:
$$\lfloor \lg n \rfloor \le \lg n \le  \lceil \lg n  \rceil$$
Please help.
Thank you.


texts: Showing that the pumping lemma cannot prove that some language is not regular

texts:
I have this language $ L = a^* \cup \left \{ a^mb^n|m>n\geq 0  \right \}^* $ I have to prove that this language is not regular but still satisfies the pumping lemma for regular languages (Since the pumping lemma is a necessary but not sufficient condition for a language to be regular).
First I made the leap that $L$ is equivalent to $L' = \left \{ a^mb^n|m>n\geq 0  \right \}^*$ since this language already contains $a^*$(I hope it's correct).
My question is: to prove that the pumping lemma holds is sufficient to prove that exists a word in this language that satisfies the lemma or that must hold for all words in the language?   For example in this case we could consider the word $aaa$ it's easy to say how this word satisfies the pumping lemma because $aa^ia \in L' \space \forall i \geq 0$.
This means that proving the pumping lemma holds for a language is easy (must find an instance in whitch it holds) but proving it doesn't hold is harder (must prove that it doesn't hold for all instances of the language).


texts: If we could use electrons as information storage, how would we model a database?

texts:
It's not completely incredible that electrons are accessible information storage units. So let's say there is a breakthrough and we suddenly have read/write access to every electron on the planet. They may each have a few GB of storage, and the "metadata" that keeps their integrity is negligible in size (and immutable, to avoid a nuclear disaster). Lets also assume that the communication between electrons are made at the speed of photons.

The question is now, how would we model a database on this? What differences would it have compared to the DB:s of today? What similarities? Would the possibilities for concepts like ACID increase?


texts: What is a non-ambiguous CFG for generating the set of natural numbers?

texts:
I'm trying to write a non-ambiguous context-free grammar that can generate the set of natural numbers, including the 0. My current solution is the following grammar:

$\mathcal{G}: S \rightarrow 0\ |\ ...\ |\ 9\ |\ 1S\ |\ ...\ |\ 9S$

From what I understand, there is not an algorithm to determine whether my guess is correct, thus only I—or you—can convince myself it is (or it is not, of course).


texts: Confused about adding numbers in fixed-point

texts:
So I'm performing some operations with fractional numbers in a 16-bit FIXED-POINT processor.
I have to add the numbers $\ x=-7.1$, represented in $\ Q_{12}$, and  $\ y=0.75$, represent in $\ Q_{15}$. So to perform this I know I first need to shift $\ y$ to $\ Q_{12}$, add up the numbers and shift again to $\ Q_{11}$.
First I represent the numbers in the respective notation in binary. The MSB is the sign bit.
So $\ x=1111.000110011010$ and $\ y=0.110000000000000$. Ok now I represent $\ y$ in $\ Q_{12}$, $\ y=0000.110000000000$. I know the binary point is just in our mind and the processor treats this numbers as integers.
Ok then we add up the numbers and get $\ x+y=1111.110110011010$. Finally convert this to $\ Q_{11}$, $\ x+y=11111.11011001101$.
However if I performed the operation in decimal I would get $\ x+y=-6.35$, and representing it in $\ Q_{11}$, $\ x+y=10110.01011001101$.
What is going on here? Why is the result different? Am I missing something?


texts: Best case "skew height" of an arbitrary tree

texts:
Given an arbitrary binary tree on $n$ nodes, choose an assignment $A$ from each parent to one of its children (the "favored child" as it were). We define the skew height of the tree as $H_A(\mathsf{nil})=0$ and $H_A(\mathsf{node}\;a\;b)=\max(H_A(a), H_A(b)+1)$ if $A(\mathsf{node}\;a\;b)=a$ is the favored child and symmetrically $\max(H_A(a)+1, H_A(b))$ if $b$ is favored.
The question is: For a fixed tree $T$, what is the minimum skew height over all assignments? I would like to get an asymptotic bound on $f(n)=\max_{|T|=n}\min_AH_A(T)$.
Other variations on this problem I am interested in are when the trees are not binary (but there is still one favored child and all others add one to the height), and when there is sharing (i.e. it is a dag), which doesn't affect the height computation but allows for much wider "trees" while staying under the $n$ node bound.
The obvious bounds are $f(n)=\Omega(\log n)$ and $f(n)=O(n)$. My guess is that $f(n)=\Theta(\log n)$ for binary trees, and $f(n)=\Theta(\sqrt n)$ for dags (with some kind of grid graph as counterexample).


texts:
Computational complexity asks the following question: Given a problem $P$, what is the time-cost of the lowest time-cost machine $M^*$ that solves $P$?

But this misses a certain aspect of the complexity of $P$, namely the complexity of finding $M^*$ in the space of machines. The problem of finding $M^*$ can be seen as an instance in the meta-problem of finding for some problem $P$ in a class class $\mathcal P$, a machine, or the optimal machine (according to some criterion) that solves $P$".

  The meta-problem $\mathcal P$ is: Given a problem $P\in \mathcal P$, find a (Turing) machine that solves $P$, optimized for some resource constraints $C(P)$.

We could turn the set of problems $\mathcal P$ into a single problem $\tilde {\mathcal P}$, where the specification of which $P\in \mathcal P$ we want to solve, is defined within the information describing the instances of $\tilde {\mathcal P}$. However, an efficient machine $\tilde M$ that solves $\tilde {\mathcal P}$, can not necessarily be used to solve the meta-problem $\mathcal P$, since $\tilde M$ might not make use of specific possible optimizations for problems $P\in \mathcal P$. For example. the solution to some specific problem $P_i\in \mathcal P$ might be simply to always output $0$, in which case the solution to $\mathcal P$ for instance $P_i$, is a $C(1)$ complexity machine $M_i$ that ignores input and outputs $0$. But $\tilde M$ might instead do all kinds of complex computations, that still are below the worst-case bound for all problems in $\mathcal P$, but don't make use of this specific feature of the instance $P_i$.

Hence it may be that some problem $P$ has very low computational-complexity, but high "meta-complexity" (i.e. for problems in the class of problems $\mathcal P$ that $P$ is a part of, it is hard to find an efficient algorithm).

Is there a theory akin to this type of "meta-complexity"?


texts: Do Kruskal's and Prim's algorithms yield the same minimum spanning tree?

texts: Assuming the edges are undirected, have unique weight, and no negative paths, do these algorithms produce the same Minimum Spanning Trees?


texts:
I need some help with the following question.

SHIP LOADING: Given items of weights $x_1,\dots,x_n$, ships of weight
capacity $B$, can the items be loaded onto $C$ or fewer ships? (All
numbers are positive integers, given in binary.)
Show that SHIP LOADING is NP-complete. (Hint: reduce from SUBSET SUM,
but go through a restricted version where the target $b$ is half the
total.)

My questions are:

Do you have any idea or hint about how to approach to prove that
this problem is a NP problem?

What does it mean by the target $b$ is half the total. Then, is the
sum of the indices $a_1,\dots,a_n$ equal to $b/2$?


texts:
So I am studying this great book, and Chapter $3.1$ is about registers.

Quoting from this book / chapter:

  A register is a storage device that can "store" or "remember" a value
  over time, implementing the classical storage behaviour $out(t) = out(t-1)$.

What is mean by:

  the classical storage behaviour $out(t) = out(t-1)$ ?

If $out(2) = out(1)$ and $out(1) = out(0)$ how are we ever going to store a value?


texts: Why Is Alloy not an Answer Set Programming system?

texts:
Alloy's front page doesn't mention ASP, but the description sounds like ASP (finding solutions consistent with a logical spec).  And Alloy isn't listed in the Wikipedia ASP article.  Yet ASP systems and Alloy both seem to built on top of SAT solvers.  So how do they differ?

[edit: Would it be fair to say, for example, that Alloy is ASP extended with a pile of useful built-in abstractions that make it more useful for writing and checking specs?  Or are there things that Alloy can do that ASP cannot?]


texts:
In the modal logic K does □ distribution over →?

For example, would the following be correct?

□(p → q) ≡ □p → □q


texts: Finite state automaton for the reverse of the language, and multiple starting states

texts:
I am studying about Finite State Automaton, and I found that the when reversing a language (i.e., transforming $L$ to $L^R$), I have to add new start state. Why is that?

Also, can a Finite State Automaton have more than one starting state?


texts: Is this a correct way to show that a problem is coNP-complete?

texts:
Let $A$ be a problem that I want to show it is coNP-complete.
I know I could just show its  complement $\bar{A}$ is NP-complete
 or that $\bar{A}$ is in NP and for some coNP-complete problem $Q$, show that $Q$ can be Karp-reduced to $A$.

But I wonder if the following steps are sufficient to show that A is coNP-complete?

   Show that $A$ is in $coNP$ by showing that its complement is in NP
   Choose one coNP-complete problem $Q$ and Cook-reduce it to $A$.

Does the coNP-complete class still be distinguishable (under the assumption $P\neq NP$) from the NP-complete class? since it seems that any coNP-complete problem is Turing-polynomially equivalent to any other NP-Complete problem.


texts: Constructing orthogonal latin square Parker/Knuth method

texts:
I'm working through Knuth; The Art of Computer Programming, Vol. 4 Fascicle 0 and I'm having a little trouble making sense of the method Knuth describes for computing an orthogonal latin square.

The text of Knuth's explanation is available in this PDF, starting on page 16 (pp 6) and continuing to the next page: http://www.cs.utsa.edu/~wagner/knuth/fasc0a.pdf

The square he uses in his example is this one:

0 1 2 3 4 5 6 7 8 9
1 8 3 2 5 4 7 6 9 0
2 9 5 6 3 0 8 4 7 1
3 7 0 9 8 6 1 5 2 4
4 6 7 5 2 9 0 8 1 3
5 0 9 4 7 8 3 1 6 2
6 5 4 7 1 3 2 9 0 8
7 4 1 8 0 2 9 3 5 6
8 3 6 0 9 1 5 2 4 7
9 2 8 1 6 7 4 0 3 5

and its orthogonal mate is this one:

0 2 8 5 9 4 7 3 6 1
1 7 4 9 3 6 5 0 2 8
2 5 6 4 8 7 0 1 9 3
3 6 9 0 4 5 8 2 1 7
4 8 1 7 5 3 6 9 0 2
5 1 7 8 0 2 9 4 3 6
6 9 0 2 7 1 3 8 4 5
7 3 5 1 2 0 4 6 8 9
8 0 2 3 6 9 1 7 5 4
9 4 3 6 1 8 2 5 7 0

I've checked it, and it is indeed orthogonal. I just can't figure out how he produced it from the instructions he gave.

The general procedure he describes is to calculate all the transversals and then find a set of those that are disjoint, and that makes an orthogonal square. A transversal is a sequence of ten values, one from each column that are each also in a separate row, and that have no repeated values. For example, 0859734216 is one transversal of the 808 in the original square.

I've worked out how to calculate the transversals and I come up with the exact same number Knuth describes of each starting number, so I feel confident about that part.

It seems the problem I'm having is how to combine those to make the orthogonal mate. The way I interpret his instructions is that you find one of the 808 that starts with 0 and that's the first row, then find one that starts with 1 and that's the second row. If you can find such a row for each of the ten values such that each column has exactly one of each value, that's a latin square orthogonal to the original. (The transversals already only have one of each value.)

Where his description doesn't square with the example orthogonal is that one can see by inspection the first row of the orthogonal square is not a transversal of the original square. In fact, none of the first five rows are; I stopped checking after that :)

So I must be getting something wrong.

I've worked out an algorithm for finding a disjoint set of transversals and it does indeed produce only a single solution, as Knuth claims, and it is a latin square (kind of by definition) but it neither matches this solution nor is the resulting matrix orthogonal to the first.

Does someone understand the Parker method well enough to point out where I've gone wrong in the procedure?

Note: I originally submitted this question on the Mathematics site, but got no takers; I'm submitting it here thinking this might be the more appropriate site.


texts: Constraint on Universal set of hash functions

texts:
I was reading hashing from CLRS. In it author says:

  Let $\mathscr{H}$ be a finite collection of hash functions that map a given universe $U$ of keys into the range ${0,1,...,m-1}$. Such a collection is said to be universal if for each pair of distinct keys $k,l\in U$, the number of hash functions $h\in\mathscr{H}$ for which $h(k)= h(l)$ is at most $|\mathscr{H}|/m$.

So basically in universal set of hash functions, the number of hash functions a finite collection of hash functions is said to be universal if number of hash functions $h$ for which $h(k)=h(l)$ is at most $\frac{\text{number of hash functions}}{\text{size of hash table}}=\frac{|\mathscr{H}|}{m}$

However next the author says:

  In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$.

I didnt get the last part "$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$". How $|\mathscr{H}|=$[$h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$]


texts:
AFAIK, a hierarchy of type universe(Type^0: Type^1: Type^2: ...) was introduced to avoid inconsistency caused by Type: Type.

But some functional language(e.g. Idris) also allows subtyping of these type universes(x: Type^n then also x: Type^n+1). From my understanding, this is not mandatory to solve the inconsistency. So it leads me to guess there should be some advantages from this redundant subtyping rule.

When is cumulative type universes useful?


texts: Relation between Russellian type theory and type systems

texts:
I recently realized that there is some sort of relation between Russellian type theory and type systems, as found e.g. in Haskell. Actually, some of the notation for types in Haskell seems to have precursors in type theory. But, IMHO, Russell motivation in 1908 was to avoid Russell's paradox, and I am not sure how that is related to type systems in computer science.

Is Russell's paradox in one form or another something that we would have to worry about, for example, if we didn't have a good type system in a given language?


texts: Using existential quantifier within implication

texts:
I had used an existential quantifier within an implication, as below:

$$\exists ~ \sigma_{opt}~~~ \wedge~~~ n \in R^{+}~  ,~0<n<1 \rightarrow ~~ \sigma_{opt} = n$$

I've, recently, found that it is illegal to do that and just universal quantifier could be used in this situation. Could anybody explain the reason?


texts: What does the halting problem mean for a Babbage machine?

texts:
I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example).

The way I imagine that is there is no finite method (i.e. algorithm) which would examine the Babbage machine, possibly by testing it, but most probably by dismantling it like a watch and concludes that it indeed computes logarithms.

Would that be a correct way of thinking the halting problem on the Babbage machine?


texts: printf("%d",~5); prints out -6 why is that?

texts: I was reading the book "Computer systems: A programmer's perspective" and saw that the operator, "~", is a NOT operator. When I use it to NOT positive integers, it returns the negative of the original number plus one. Why does that happen?


texts:
I am designing a 4-bit comparator with a look ahead unit using a bit slice approach. I have to break the propagation of the Logical expressions for (A<B)i and (A>B)i. The main question is, could I use the following to simplify the boolean expressions.. The i is a subscript meaning the ith bit. The i-1 is a subscript meaning the bit before the ith bit.

(A<B)i = ~Ai*Bi + ~Ai*(A<B)i-1 + Bi*(A<B)i-1

Could I Take ~Ai common from the first two expressions leaving me with

~Ai*(Bi + (A<B)i-1) + Bi(A<B)i-1

Let's call  Bi + (A<B)i-1) = Q

And let's call ~Ai = P

I'm left with P*Q + Q

Using the boolean law that Q + Q*P = Q

Can I simplify the expression to just

(A<B)i = Bi + (A<B)i-1


texts:
Let $q$ be a prime number and let $\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$; I need to prove that the family $\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \mathbb{Z}_q^3}$ is 3-wise independent, where $h_s$ is defined as:

$$h_s(x):=h_{s_0,s_1,s_2}(x):=s_0 + s_1 x + s_2 x^2 \bmod q$$

How could I do it? My intuition would be proving that it is 1-wise independent and use the property $$x_1,\dots,x_t \in \mathcal{X}, \quad y_1,\dots,y_t \in \mathcal{Y}, \quad \Pr[h_s(x_1)=y_1 \wedge \dots\wedge h_s(x_t)=y_t \mid s \leftarrow _\$ \mathcal{S}]=\frac{1}{|\mathcal{Y}|^t},$$ but I'm not sure how to do that.


texts: Is there an Interval Tree which supports O(1) dynamic space requirements for queries?

texts:
I observed that all the interval tree implementations I am able to come up with are required to utilize a stack (or a-like) to answer queries (report any overlapping interval with a key).

In general when visiting a node in an (common) interval tree you are required to visit multiple child nodes and check for results there and recurse.
This requires you to (dynamically) allocate memory upon lookup.

In contrast, f.e. consider a simple binary search tree. You can easily unroll the recursion because you will only ever visit a single child node.

Is it possible to achieve a similar algorithm for intervals?
To clarify I would like to know whether there exists an interval tree which supports finding any overlapping interval in constant required space.


texts:
The randomized selection algorithm is the following:

Input: An array $A$ of $n$ (distinct, for simplicity) numbers and a number $k\in [n]$

Output: The the "rank $k$ element" of $A$ (i.e., the one in position $k$ if $A$ was sorted)

Method:

If there is one element in $A$, return it
Select an element $p$ (the "pivot") uniformly at random
Compute the sets $L = \{a\in A : a < p\}$ and $R = \{a\in A : a > p\}$
If $|L| \ge k$, return the rank $k$ element of $L$.
Otherwise, return the rank $k - |L|$ element of $R$

I was asked the following question:

  Suppose that $k=n/2$, so you are looking for the median, and let $\alpha\in (1/2,1)$
  be a constant.  What is the probability that, at the first recursive call, the
  set containing the median has size at most $\alpha n$?

I was told that the answer is $2\alpha - 1$, with the justification "The pivot selected should lie between $1−\alpha$ and $\alpha$ times the original array"

Why? As $\alpha \in (0.5, 1)$, whatever element is chosen as pivot is either larger or smaller than more than half the original elements. The median always lies in the larger subarray, because the elements in the partitioned subarray are always less than the pivot.

If the pivot lies in the first half of the original array (less than half of them), the median will surely be in the second larger half, because once the median is found, it must be in the middle position of the array, and everything before the pivot is smaller as stated above.

If the pivot lies in the second half of the original array (more than half of the elements), the median will surely first larger half, for the same reason, everything before the pivot is considered smaller.

Example:

3 4 5 8 7 9 2 1 6 10

The median is 5.

Supposed the chosen pivot is 2. So after the first iteration, it becomes:

1 2 ....bigger part....

Only 1 and 2 are swapped after the first iteration. Number 5 (the median) is still in the first greater half (accroding to the pivot 2). The point is, median always lies on greater half, how can it have a chance to stay in a smaller subarray?


texts:
i have the following regular grammar :
$$S \rightarrow aS | cS | bQ_1$$
$$Q_1 \rightarrow bQ_2$$
$$Q_2 \rightarrow aQ_3 | cQ_3 | bQ_1$$
$$Q_3 \rightarrow aQ_4 | cQ_4$$
$$Q_4 \rightarrow \varepsilon$$

The question is to transform that into a linear grammar with less nonterminals than the regular grammar and my idea was:
$$S \rightarrow aSa | cSc | aSc | cSa | bQ_1a | bQ_1c$$
$$Q_1 \rightarrow b$$

and the rest i don't know. Could you help me to solve this problem?


texts:
So I get this through the math behind the SVM (Support Vector Machine), and I get this formula
$$(w^T)(x_1-x_2) = 2.$$
We then divide both side with norm of $w$ then we get the new formula
$$ \frac{w^T}{\|w\|}(x_1-x_2) = \frac2{\|w\|}. $$
Why do we divide by the norm of $w$ in both sides?


texts: How do I continue learning programming, beyond the basics?

texts:
DISCLAIMER: I understand that I might not be posting in the right part of StackExchange, or this question might have been asked before (I haven't found it). If this offends anybody, I apologize.

I'm 15 and a sophomore in High School. I have an interest in Computer Science in general. The thing is, I've learned a few languages here and there, but I just don't know how to keep learning on a regular basis. What I mean by this is that yeah, I can make a calculator with java, or some really basic scripts with python, but the fact of the matter is that I don't know what to do after that. Making a script that can count the words in a book seems so pointless.

What can I do to learn a programming language, practice it, and have an overall mastery of it? Anybody can learn how to do basic things like I've done, but what can I do so that at the end of some time, I can look back and say "yeah, I'm a real programmer now." I know that sounds cheesy, but help me out here.


texts: Algorithm for executing a command against a million hosts

texts:
Consider the following problem: you are given a set of one million machines (hosts), and you would like to have the ability to execute at will an arbitrary command against the whole set; for the moment, let us suppose you want to run one command at a time. How to do that efficiently?

Is also desirable to have the ability to query at any moment the progress (status of execution on each host), as well as to consult afterwards the outcome of each individual execution (both exit code and stdout/stderr); hence, the outcome must be persisted somewhere.

Ideally, if you could deliver instantaneously the command at all the hosts, and coordinate them to start at the same time, you would have an ideal time of the command duration (assuming command takes same time on every host). Thus, I presume that a big part of the problem is how to deliver as fast as possible the command to all the hosts; the problem may get more elaborated if we add the quality of being fault-tolerant (that is, to ensure that the execution does take place on all available hosts even if some of the auxiliary machines used for the delivery fail or have issues).

If I execute a dummy echo command using ssh on an intranet I have access to (after having automated the authentication with keys); the time for getting back a response is at best 0.25 secs. Thus, running one million times ssh against each one of the hosts does not sound promising if done serially (it would take almost 3 days to finish the execution serially on this environment).

Even if we could deliver the command within a few milli-seconds to each machine using a custom protocol other than ssh, doing the delivery from a single source may not be the best approach. I suppose that the problem may benefit from some parallel/distributed algorithms, as well as network/graph theory. It would also be nice to avoid using a centralized approach too, if one does not want to rely on the availability of a fixed set of machines for doing the delivery (which ideally should be a subset of the one million hosts, so we do not need additional infrastructure machines).

Is there an standard name for this kind of problem? Any known algorithms or approaches?


texts: How do I prove no algorithm exists for a given problem?

texts:
Is there a general framework for showing that a problem has no algorithm? For example, to show that two problems are equally as hard to each other, we use reduction.

One example of where this was done, is Hilbert's 10th problem


texts: Etymology of time and space "complexity"

texts:
The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. This question is concerned with the language used to describe them.

Colloquially, one would probably not say that insertion sort is more "complex" than radix sort.

Is the origin and rationale of this word choice known? If so, what is it?


texts:
A producer wants to arrange couples of boys and girls for a dance.
There are n boys arranged in a row [A1...An] in some certain order and n girls arranged in a different row [B1...Bn], also in some certain order.
Only a couple in which there is a boy and a girl with exactly the same height can dance.
The height of every boy and girl is known.  The producer needs to find the maximum number of couples that can dance (There might be people who can't dance).

Show an algorithm for the general case.
Show an algorithm, in which you can't change the order of the boys and the girls. In other words: If there is a couple (Ai,Bj) then there can't be (Ak,Bp) (so that k > i, p < j or k < i, p > j)

Analyze the complexity in every case.

What I know is that the solution to 1 is sorting the array in $O(nlogn)$.
My idea in approaching 2 is that it's like LCS in a static table, only with numbers and not chars, which takes $O(n^2)$.

Can 2 be done in better complexity that $O(n^2)$?


texts: I am learning this topic and there is a concept that LSB ( bit ) of MSB ( byte ) should be set to 1 for multicasting . But why we need to do so as multicast address is unique so why can't we assign any multicast address which is not present in that network.


texts: Prim's algorithm on graph with weights of only $1$ and $2$ on each edge

texts:
I have this version of  Prim's algorithm

Prim$(G=(V,E),s\in V,w)\\
1.\ d(s)\leftarrow  0;\forall u \neq s:d(u)\leftarrow \infty\quad \color{red}{O(|V|)}\\
2.\ \forall u \in V:p(u)\leftarrow \text{null}\quad \color{red}{O(|V|)}\\
3.\ s\leftarrow \emptyset,T\leftarrow \emptyset\quad \color{red}{O(1)}\\
4.\ Q \leftarrow \text{Makeheap}(V)\quad \color{red}{O(|V|)}\\
5.\ \text{while}\ Q\neq \emptyset\\
6.\qquad u\leftarrow Q.\text{ExtractMin()}\quad \color{red}{O(\log(|V|))}\\
7.\qquad S\leftarrow S\cup\{u\},\ T\leftarrow T\cup\{(u,p(u))\}\quad \color{red}{O(1)}\\
8.\qquad \text{for each}\ (u,z)\in E,z\in Q\\
9.\qquad\qquad \text{if}\ d(z)>w(u,z)\ \text{then}\\
10.\qquad\qquad\qquad Q.\text{Remove}(z);Q.\text{Insert}(z,w(u,z))\quad \color{red}{O(\log(|V|))}\\
11.\qquad\qquad\qquad d(z)\leftarrow w(u,z),\ p(z)\leftarrow \quad \color{red}{O(1)}\\
12.\ \text{return }T$

Total time: $O(|E|\log(|V|))$

Given a weighted, connected, simple undirected graph $G$ with weights of only $1$ and $2$ on each edge, why in this case the running time of the algorithm is $O(|E|+|V|\log(|V|))$?

I really not understand why the running time is not the same in this case, any help?


texts: How to go about proving an algorithm correct?

texts:
The algorithm (called as rmax(1,n)) finds the maximum of a list of numbers contained in an array S[1..n].

rmax(x, y)
// return maximum in S[x..y]
if y − x ≤ 1
then return maximum(S[x], S[y])
else max1 ← rmax(x, [x+y]/2)
     max2 ← rmax([x+y]/2 + 1, y)
     return maximum(max1, max2)

How would I go about arguing that the algorithm is correct?


texts: How to lexically list sentences in peano arithmetic?

texts:
I am working on building a toy automated theorem prover,

What I want to do is to efficiently generate sentences in peano arithmetic, that I can attempt to verify as True/False/requires-more-resources in a higher model of logic.

My first task I want to work on is to build a tool that can list out statements in PA

So my current idea was to build a compiler that can recognize, if a sentence is a well formed sentence in PA, and then brute force all possible strings in lexical order,

$$\forall, \forall \exists , \forall x, \forall |, ... (\forall x|\exists y...), ...  $$

And have the compiler recognize if this is a sentence or not, but the problem is that it will end up spending a lot of time shifting through junk.

Since most permutations of character simply aren't meaningful at all,

Is there a more efficient way for me to list out sentences? perhaps a way to compute the first $n$ sentences in $O(n^2)$ time and $O(n^2)$ space (that would have to be asymptotically optimal).

Even better is if this procedure can be a start stop procedure, that is it can be given a most recently generated sentence $T_n$, and automatically form that point on, start generating additional sentences $T_{n+1}, ... $


texts: Which algorithms have runtime recurrences like $T(n) = \sqrt{n}\,T(\sqrt{n}) + O(n)$?

texts:
The algorithms using the "divide and conquer" (wiki) design strategy often have the time complexity of the form $T(n) = aT(n/b) + f(n)$, where $n$ is the problem size. Classic examples are binary search ($T(n) = T(n/2) + O(1)$) and merge sort ($T(n) = 2T(n/2) + O(n)$).

  Do you know any algorithms (probably using "divide and conquer") that have the time complexity of the form $T(n) = \sqrt{n} \cdot T(\sqrt{n}) + O(n)$?


texts: Splitting a set of points in the plane evenly and sorting it

texts:
Input: A set of points P(x,y). There are two versions of it - Px, sorted by x and Py, sorted by y.

Output: The two even halves of Px, sorted by y.

The trick here is that it has to work in linear time, otherwise, it's rather useless. What I've come up with so far is finding the midpoint of Px, let's call it Px[mid] and then iterating over Py, checking if each point's x coordinate is bigger than Px[mid] and then assigning it to the appropriate half.

Example:

Px = [(1,7),(2,3),(3,1),(4,-2)]
Py = [(4,-2),(3,1),(2,3),(1,7)]
Px[midpoint] = (2,3)
Ly = [(2,3),(1,7)]
Ry = [(4,-2),(3,1)]

This works quite well, if you account for points with equal x coordinates and compare said points by y instead (and vice versa), which sorts them in a way that avoids potential surprises. Where it fails is the following case:

Px = [(1,7),(2,-3),(2,-3),(4,-2)]
Py = [(2,-3),(2,-3),(4,-2),(1,7)]
midpoint = 2
P[midpoint] = (2,-3)
Ly = [(2,-3),(2,-3),(1,7)]
Ry = [(4,-2)]

I can't seem to think of a way to exclude non-distinct points from the left half, when they're equal to the midpoint. Again, keep in mind that this has to work in linear time, so I can't just split Px into two halves and search for points which might belong to it for the odd case.


texts: Word-hyphenation algorithm for monospaced fonts

texts: I have seen a few standard hyphenation algorithms for non-monospaced fonts, where you are free to squeeze and separate words and letters, but I haven't seen any related to monospaced fonts specifically. Wondering if there are any good resources on the topic. Such as how to best properties to use when hyphenating a monospaced word, etc.


texts: Why is the class of recursively enumerable languages not closed under complementation?

texts:
I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed under complementation?

Explanation also says,

  This fails because $M$ only needs to halt if $w \in L(M)$ - doesn't have to say "no".

What does it mean?


texts: Arithmetic on signed 12-bit octal number stored in sign magnitude form

texts:
What is 4365 − 3412 when these values represent signed 12-bit
octal numbers stored in sign-magnitude format? The result should be written in
octal. Show your work.

Octal to binary:

4365: 100 011 110 101
3412: 011 100 001 010

By recognising the role of the sign bit, we can
represent positive and negative 64-bit numbers in terms of the bit value times a
power of 2. The binary number x, where xi means the ith bit, represents the number:

(x11 * -2^11) + (x10 * 2^10) + (x9 * 2^9) + ... + (x1 * 2^1) + (x0 * 2^0)

I have used the formula given above to convert the value of octal 4365 in decimal:

(1 * -2^11) + (1 * 2^7) + 2^6 + 2^5 + 2^4 + 2^2 + 2^0 = -2048 + 245 = -1803

Similarly, the value of octal 3412 in decimal is 1802.
Having obtained the two values in decimal, I subtract (-1803 - 1802), obtaining the result -3605.
Binary representation of 3605 is 111 000 010 101.
Converting it back to octal gives 7025.

This answer is wrong. It should be octal 7777 or decimal -3777.
The concept is not clear to me. Where am I going wrong?


texts: Priority queue with unique elements and sublinear time merge?

texts:
Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.

I am looking for a priority queue that merges in (expected|average|amortized|worst-case) sub-linear time, but also has the following properties:

Elements are unique
peek and pop should work in (expected|average|amortized|worst-case) sub-linear time

Is this impossible?


texts: existence of a permutation that satisfies order-constraints

texts:
I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.

For example, suppose we have a set (1, 2, 3, 4, 5) and a number of constraints:

1 should be before 2
2 should be before 4
4 should be before 1

(which is of course infeasible).

Is there a simple algorithm for checking the feasibility of order-constraints? (that does not rely on lp-solvers)?

I do not have anything against Lp-solving, but i suspect that simpler algorithms are available.


texts:
I need to generate flip graphs on around 10 points (more would be nice).  Specifically, I would like flip graphs on subsets of the integer lattice, so the coordinates of each point are integers.  Is there any software for this?  If not, what language would be best to build something simple?
Thanks!


texts: How does a transition function behave in a FSM when an input is not recognized (i.e. the input is not contained in the alphabet)?

texts:
In Sipser's Introduction to the Theory of Computation, the provided proof for the union operation being closed for regular languages has a step for the transition function that I find a bit lacking.
Assuming that $M_1=(Q_1, \Sigma, \delta_1, q_1, F_1)$ and $M_2=(Q_2, \Sigma, \delta_2, q_2, F_2)$  are two different FSMs for languages $L_1$ and $L_2$. With $M=(Q, \Sigma, \delta, q_0, F)$ being the FSM for $L = L_1 \cup L_2$ (the regular languages for the FSMs).  The step for the constructed transition function, $\delta$, states that for each $(r_1,r_2) \in Q$ and each $a \in \Sigma$, let $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$. This is working with the assumption that the input alphabet, $\Sigma$, is the same for $M_1$ and $M_2$.
I am confused on how $\delta((r_1,r_2),a)=(\delta_1(r_1,a),\delta_2(r_2,a))$ behaves for a combined alphabet $\Sigma = \Sigma_1 \cup \Sigma_2$, specifically if $a \in \Sigma_1$ and $a \notin \Sigma_2$? What would the output of $\delta_2(r_2,a)$ be and how would this transition work in the FSMs $M_2$ and $M$?


texts: Prove that my NP-complete problem is strong

texts:
I have two problems, one of which is solved using dynamic programming. I showed that it is NP-complete (a knapsack variant), therefore having this dynamic programming solution says that this one is weakly NP-complete. Right?

Then, in the second problem I have added a new dimension to the problem which makes is more complicated. It is still NP-complete and I assume that this one is strongly NP-complete.

Is there a way to prove that it is 'strongly' NP-complete?

Update:

I can show that the second problem needs to solve $2^n$ instances of the first problem, where $n$ is the size of problem.


texts: How can there be undecidable languages in P/1?

texts:
I didn't understand some things about $ P/POLY$ class, and I will be thankful if you could help me.
as I learned in class,
a turing machine M accepts language L with advice $ {a_n} $ if
$\qquad\displaystyle M(x, a_{|x|}  ) = 1 \iff x \in L$.

Does it mean that M with the advice decides L (halts on every input)?
or recognizes L? (accept every x in L but may not halt on x that is not in L)

Generally, if a language L is in P it means that there is polynomial time machine that decides it right? I feel like it really confused me.
then we defined:
$ P/POLY $ = union of (DTIME($n^{k_1}),  n^{k_2})$ on every $k_1,k_2$ in $N$ .
we proved in class that there is a unary language which is undecidable,
and that every unary language is in $P/1$.
that means that there is language in $P/1$ which is undecidable.

I don't understand it because $P/1$ is in $ P/POLY $ . as I understand by the definition, there is poly time machine that decides it.. so what do I get wrong?