texts: Shouldn't complexity theory consider the time taken for different operations?

texts:
I have read the answer found here which considers the size of integers when doing comparisons and how that affects on the basic cost of comparison.

I am trying to understand why each basic operation takes $O(1)$ time.
For example branches in general are considered to run in $O(1)$ time when they usually don't.

In computer architecture branches are considered the most time-consuming and problematic part of the code and this is one of the reasons why a loop is unrolled by the compiler in order to reduce the amount of branches the processor needs to execute.

For example a simple branch (let's say if a>b) needs to do at least four things

Get a from memory (whether it is cache or RAM or on disk does not
matter; cache misses and hits are a different field of study).
Get b from memory
Evaluate the two and select the proper answer
Search in instruction memory a new value for the Program Counter
     depending on the result of the evaluation.

Now get the variables from RAM is something done everywhere. So let's not count that.
But since all modern processors load more than just one instruction from instruction memory (let's say for our case 100) so as to reduce instruction memory accesses and a branch usually leads to a different place in the instructions list (let's say if a>b call a method that swaps them), that would mean that branches take a lot more time than any other basic function.

Also in all modern processors multiplications and divisions take significantly much more time than additions and subtractions. Which is the reason why when multiplying or diving by numbers that are powers of two we should use logical bit shifting.

I know that in CS Theory and evaluating an algorithm we do not care. But in practice when implementing an algorithm the operations we use really effect the efficiency and complexity of our code.

So let's say we have three algorithms

$n$ additions
$n$ multiplications
$n$ branches

In Theory all three of these compute in time $n$ but in practice, 1 is faster than 2, which is faster than 3.


texts:
After a year hiatus from Computer Science courses in college, im back to hitting them hard for the next two years straight. In the next few weeks before classes start again I have been trying to refresh my memory on key concepts by writing and trying to explain them to people that have never gotten deeper into a computer than Word, or Excel, maybe even just Photoshop.

Right now i'm trying to explain Objects and Classes, using the cookie cutter is a class and a cookie is an object.

In trying to explain Objects I thought that starting with trying to describe a Cookie would be easy and I described it like so.

Dinosaur_Cookie_Name = "T-Rex"
Dinosaur_Cookie_Frosting_Colour = "Green"
Dinosaur_Cookie_Eaten = False

And then I was going to explain how these have no linking between them and that if you wanted to say that

my_cookie = Dinosaur_Cookie_Name

it doesn't necessarily mean that it's also green and uneaten.

So I was then going to explain that by making my_cookie a list, you could then iterate through the list to access properties and tada, a sort of rudimentary object. Afterwards would then be, tada here is what an object is.

That's where I froze. In the year since learning about Objects in my beginning C++ class I couldn't remember how I made the jump TO Objects.
I remember a little talk about name spaces and pointers but thats about it.

So do objects store properties in an array?
Would it be appropriate in teaching about Objects to have a middle step of a list, between non-associated variables and an object?


texts: I don't want to binarize a certain image through another program, I want to know how to binarize things myself. All I know is that there is something to do with a threshold and if it is above the threshold it is either 1 or 0 and the opposite if below. My images are using RGB but I can also use HSB or HSV. I just want the algorithm to do so . :)


texts: Is this relation in Boyce-Codd's Normal Form?

texts:
I thought I understood BCFN until I bumped into this example from my course slides.

A relation in a library database contains what books are currently borrowed by what users.
The relation contains the unique ID of the user, their name and the title of the book.
Different users might share the same name.
A book can only be borrowed by one user.
A user can have borrowed more than one book.

An example of this relation could be:

USER_ID
USER_NAME
BOOK_TITLE

U012
Charles
Hamlet

U034
Alex
Blue Moon

U491
Diane
Capital

U034
Alex
The Crow

U491
Diane
Economics 2

U012
Charles
Lost Girl

U034
Alex
Chess basics

U012
Charles
Greek History

U491
Diane
Red Mars

According to the slide, this relation is in Boyce-Codd's Normal Form,as:

all functional dependencies of the form $\alpha \rightarrow \beta $
are either trivial or satisfy that $\alpha$ is a super-key of the
relation

While it is my understanding that those are the requirements for BCNF, I don't think this relation satisfies them. In particular, the functional dependency USER_ID $\rightarrow$ USER_NAME is not trivial (as $\beta$ is not a subset of $\alpha$) and $\alpha$ is not a super-key (since by itself we cannot distinguish between entries representing different books borrowed by the same user).
Am I missing something?


texts: Shortest paths among two subsets of nodes

texts: Given a directed graph $G = (V, E)$ with all edge weights being non-negative and two disjoint subsets of nodes $S, T \subseteq V$, design an algorithm to find the shortest paths among $S$ and $T$, (formally, $\min\{d(s,t): s \in S, t \in T\}$) in $O(m \log n)$ time, where $|V| = n$ and $|E| = m$.


texts: Graph isomorphism and the automorphism group

texts:
A common approach to decide whether two given graphs are isomorphic is to compute the so-called canonical label (alternatively, canonical graph) of each graph and to check whether those match or not.

Tools such as Nauty compute the canonical graph via search trees that are pruned using some clever ideas that rely, among other, on graph automorphisms. Because of this, Nauty allows one to compute a generator of the graph automorphism group. However, as far as I understood the idea behind Nauty, the computation of the canonical graph does not require one to compute a generator of the graph automorphism group in general.

My question is therefore: is there a formal complexity-theoretical relation between GI and the computation of a generator set of the graph automorphism group?

Many thanks.


texts: Explanation of implementation of an algorithm for Dominating Set

texts:
I'm working on an application, in which users can use domination in graphs. I have already finished up with graph generation algorithm, I use lists to store vertices...
So, I have found a well developed, gorgeous implementation of the needed algorithm.

It is a bit complicated for me, I would like to ask for some description for code above. How is it working? I would like to get only a short summary.


texts: Are the non-regular languages closed under reverse, union, concatenation, etc?

texts: My question: do the non-regular languages have closure properties? For example, if the reverse of L is non-regular, then L is non-regular ? thank you :-)


texts: How to query and update ranges of arrays?

texts:
I have an array of size $N$ $(N \leq 10^5)$. I need to perform two types of operations on the array.

Decrease elements in range $[L,R]$ by $X$.
Count the number of negative elements in range $[L,R]$.

There are $10^5$ queries. All I can think about is using a segment tree with lazy propagation, but I believe there would be a better method. The segment tree method will probably time out because in case of alternate update/count queries, this will be close to linear.


texts: Maximum weighted matching for directed (non-bipartite) graphs

texts:
This post concerns mainly non-bipartite graphs.

Edmonds (1961) have proposed the Blossom algorithm to solve the maximum matching problem for undirected graphs. The best implementation of it is due to Micali and Vazirani (1980): $\mathcal O(|E|\sqrt{|V|})$ time. There is a version of the Blossom algorithm for weighted graphs (Kolmogorov, 2009), but still it concerns only undirected graphs.

Are you aware of any implementation of the Blossom algorithm for weighted directed graphs? I could not find one.


texts: CPU Cache is managed by which software component?

texts: CPU caches are used by exploiting temporal and spatial locality. My question is who is responsible for managing these caches? Is this Operating system that identifies a particular access pattern and then manages (i.e store the data in) cache, using low level OS function calls?


texts: Is there an official name for this tree merging algorithm?

texts:
Is there a standard name for an algorithm to handle this type of tree merge? Each node of the tree has a label. Nodes from the 2 trees should be combined if they have the same label, and their values should be totaled.
Example: tree1 and tree2 are merged to produce "output"
const tree1 = [
  {
    label: 'Parent A',
    value: 20,
    children: [
      {
        label: 'Child A',
        value: 100,
      }, {
        label: 'Child B',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 50,
    children: [
      {
        label: 'Child E',
        value: 200,
      },
    ],
  },
];

const tree2 = [
  {
    label: 'Parent A',
    value: 30,
    children: [
      {
        label: 'Child A',
        value: 75,
      }, {
        label: 'Child C',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 200,
    children: [
      {
        label: 'Child F',
        value: 100,
      },
    ],
  },
]

const output = [
  {
    label: 'Parent A',
    value: 50, // AMOUNTS SUMMED TOGETHER
    children: [
      {
        label: 'Child A',
        value: 175, // AMOUNTS SUMMED TOGETHER
      }, {
        label: 'Child B',
        value: 50,
      }, {
        label: 'Child C',
        value: 50,
      },
    ],
  },
  {
    label: 'Parent B',
    value: 250, // AMOUNTS SUMMED TOGETHER
    children: [
      {
        label: 'Child E',
        value: 200,
      },
      {
        label: 'Child F',
        value: 100,
      },
    ],
  },
];


texts: How do you find all integers in a sorted array of size n that appear n/k times, given that 0 < k < n, and in O(k log n) time?

texts:
This looks like a typical divide and conquer algorithm, but with a few tricky parts.

It looks like we want to do k operations and divide the array in half at each step because of the O(k log n) restriction, but I'm confused about the specifics. When I try to come up with the algorithm, I think about making k comparisons with varying elements that are ceil(n/k) apart, but I don't see how recursively doing anything like that with broken up halves of the array would do anything beneficial.

Given this sorted array:

A = [1, 2, 3, 4, 4, 4, 4, 5]

If k = 1, then we do one comparison between A[0] and A[7] and we're done.

If k = 2, we can't do much because there's no good way to make 2 meaningful comparisons. And if we're going to split it in half and check again to fulfill the log(n) time requirement, the 4's would get split up.

Any ideas?


texts: Dijkstra Partitioning Algorithm : Special Case

texts:
I have been exploring Dikstra partitioning Algorithm. Below are my given:

R = Red
W = White
B = Blue

I have this unpartitioned array.

| W | B  | R |  W  | R  | W | B |  W  |  W |

I want it partition in the format: R, W, B consecutively.

| R  |  ?  | W  |  B |
0     i     j    k    n

Given:

 i = 0
 j = n
 k = n
 n = number of elements

Below is my algorithm:

 while  (i < j)
 {
     case a[i]:
         R : i++;
         W : j--; swap(a[i], a[j]);
         B : j--; k--; swap(a[i], a[k]); swap(a[i], a[j]);
     end case
 }
 //Done Sorting

The output should be like this:

 |  R  | R  | W  |  W  |  W  |   W  |  W  |  B  |  B |

My question is:

Can I reduce the number of swaps? If yes, how?
Is the algorithm applicable if there are 4 colors to be partitioned?

Thank you. I really need to understand this concept.


texts: How to identify strongly confluent cellular automatas?

texts:
Lets represent a class of cellular automata as a finite, unidimensional bit array state : [Bit], plus a rewrite rule rule : (Bit,Bit,Bit) -> (Bit,Bit,Bit). Given any state of the system, a posterior state can be computed by taking any consecutive triple of bits (a,b,c) and replacing it by the result of rule(a,b,c).

Since rule is a map from 3 bits to 3 bits, there are (2^3) ^ (2^3) == 16777216 possible rules. Is it possible to identify if a specific rule is confluent?


texts:
Suppose I type in the website  www.youtube.com. The computer first asks a local domain name server (DNS) what the IP address of this website is. If it can't find it, it then asks the root server, etc. This is recursive querying.

How does DNS work if there is no recursive querying? Is the root server the only one that is used to find the IP address of the website?


texts: Are there any articles or software which can infer original shapes from overlapping shapes?

texts:
Given that some shapes overlap in an image, are there any papers or articles or code which can infer the original shapes from the overlapping?

I am thinking to apply some machine learning to this since I can generate overlapping shapes using code and use a neural network to try to work out the original shapes. Perhaps another way is just heuristic rules.


texts: In-place algorithm for interleaving an array

texts:
You are given an array of $2n$ elements

$$a_1, a_2, \dots, a_n, b_1, b_2, \dots b_n$$

The task is to interleave the array, using an in-place algorithm such that the resulting array looks like

$$b_1, a_1, b_2, a_2, \dots , b_n, a_n$$

If the in-place requirement wasn't there, we could easily create a new array and copy elements giving an $\mathcal{O}(n)$ time algorithm.

With the in-place requirement, a divide and conquer algorithm bumps up the algorithm to be $\theta(n \log n)$.

So the question is:

  Is there an $\mathcal{O}(n)$ time algorithm, which is also in-place?

(Note: You can assume the uniform cost WORD RAM model, so in-place translates to $\mathcal{O}(1)$ space restriction).


texts: How to efficiently flatten a hierarchical state machine?

texts:
David Harel's StateCharts introduces hierarchical states and history mechanism, which are really powerful when modeling complex system behaviour. But when doing model based testing we need a "flattened state machine", that is an equivalent state machine without any hierarchy.
By googling around I found this paper by Wasowski, but its a little bit too hard to understand.
Is there any existing algorithm for hierarchical state machine flattening?


texts: Add type checking/inference to my programming language

texts:
I am currently creating my own compiled programming language, and I have come to a point where I would like to start working on the type system and introduce some type checking. Ideally I would like to introduce type inference.

Right now I'm using the Visitor pattern to traverse the AST produced by the parser. I started implementing a pretty naive and ugly solution, but wasn't very happy with it. It seemed pretty hacky. Type checking that fits with this pattern would be great, but not critical.

I have looked into algorithms like the Hindley-Milner. I'm developing the programming language in Swift, so I found this GitHub gist that shows how it can be implemented, but opening the lid on this code immediately gets me to Lambda Calculus, which seems like a beast. I know Swift uses a variant of the Hindley-Milner type inference, so that would be incredibly sexy to implement, but it's way over my head at this point.

Since this is my first programming language, what's a good first attempt at a type system with type checking, possibly with type inference?


texts: Minimal colouring problem aproximation threshold

texts:
Given that 3-colouring and 4-colouring are NP-complete show that the
  aproximation threshold of the minimal colouring problem is greater or
  equal than $\frac{4}{3}$.

My current approach is to work by contradiction assuming there was such an algorithm that in polynomial time can produce a $\delta$-aproximation with $\delta < \frac{4}{3}$ using the fact that 3-colouring and 4-colouring are NP-complete. I didn't obtain much progress.

References

I just wanted to point out that this is an application of the "Gap technique" presented in the book "Complexity and Aproximation" of Auseillo et alii., I wasn't familiar with the notation they use so I couldn't understand how to fully apply the technique.


texts: Solving T(n) = 2*T(n-1)+4 witht the Master Theorem

texts:
I am wondering if there is a way to solve a recurrence time function with the master theorem if no $b$ exists. Like in this case.
$$ T(n) = 2\times T(n-1)+4$$


texts: Utilization Factor, periodic tasks and schedulability

texts:
We have 2 periodic tasks that start at the same moment in a monocore processor.
Why can happen that, even if the utilization factor is <= 1, the 2 periodic tasks are not schedulable ?

For example, in this picture the 2 tasks are schedulable, but if i increase the computation time of the first task of 1 ms, we've got that the utilization factor is 1, but the 2 task are no longer schedulable.


texts:
I am reading Automata and Computability by Dexter C. Kozen and I am in the first chapter entitled Strings and Sets.
If we have a set $A=\{ab,b\}$ do we get to assume that the null string $\epsilon$ is also a member of that set? If we have another set $B=\{\epsilon\}$, does $A\cap B = \{\epsilon\}$ or does $A∩B=\emptyset$?
On a related note, I am having trouble understanding the meaning of a little chunk in the textbook. What does "family of set indexed by another set $I$" mean? What does the set $I$ consist of here? I am very confused by the notation as well. Anything you can do to help me understand the excerpt below is appreciated.

Set concatenation distributes over union:
\begin{align}
A(B\cup C) &= AB \cup AC, \\
(A \cup B)C &= AC \cup BC.
\end{align}
In fact, concatenation distributes over the union of any family of sets.
If $\{B_i \mid i \in I \}$ is any family of sets indexed by another set $I$, finite or infinite, then
\begin{align}
A \bigl( \bigcup_{i \in I} B_i \bigr) &= \bigcup_{i \in I} AB_i, \\ \bigl( \bigcup_{i \in I} B_i \bigr) A &= \bigcup_{i \in I} B_iA.
\end{align}
Here $\bigcup_{i \in I} B_i$  denotes the union of all the sets $B_i$ for $i \in I$. An element $x$ is in this union iff it is in one of the $B_i$.


texts:
Is it theoretically exist a computer that never affected by computer virus?

just wonder if there could be a revolution on the computer?


texts: Complexity of finding a subset of vertices within distance k of each other, given a set of vertices

texts:
I am trying to understand an algorithm  presented in Using Stable Communities for Maximizing Modularity by S. Srinivasan and S. Bhowmick, along with its complexity results. (The complete algorithm is presented on page 7, in pseudocode.)
As I understand it, the idea of the algorithm is to identify densely connected communities (basically, subgraphs) in a graph, such that any subset of vertices in the community has more connections (that is, edges pointing to another vertex) inside the community than to any other community in the graph.
Below I've cited the part of the algorithm I'm having trouble with:
For all vertices v_i in network N that are not in any stable community
    Create a subset S of v_i and its neighbors
        For each neighbor n_j
            ...
            Identify y_j, the subset of external neighbors
            which are all within distance k of each other

I take "external neighbors" to mean the neighbours of $n_j$ that aren't in $S$, and where the distance between them is also never measured through $S$ (as otherwise, they would never be more than two hops apart—through $n_j$).
The authors state the following about the complexity of this part:

...the average degree of a vertex is $d$...
...the complexity for computing $y_j$ for all possible values of $k$ is $O(d^3)$.

On the next page, the authors make some more statements about the complexity of this part, including that the values of the shortest paths between external vertices can be reused for many neighbours and that setting $k$ to small values (2—4) is sufficient in most cases. I'm not sure if these considerations are already factored in, however I'm a bit stuck on "all possible values of $k$" in the above quotation.
My question is: what assumptions are necessary for the complexity result $O(d^3)$ to hold, with $d$ being the average degree of a vertex? How is the subset found in this case?


texts: Proving that a language of Turing machine descriptions is/is not Turing recognizable

texts:
How to approach to solve this question and the likes of it?

  Let $L$ be the set of strings $\langle M\rangle$ such that $M$ accepts all strings of even length and does not accept any strings of odd length.

  a) Is $L$ Turing-recognizable? Prove your answer.
  b) Is the complement of $L$ Turing-recognizable? Again prove your answer.

Please have a look at my approach, is it correct? :

  Since the string representation of set of all the Turing Machines (say S) is Infinite countable and Recursively Enumerable, there fore there exists a Turing Machine that accepts S. Now, if we choose the Turing Machines M1, M2, ... from S, in the given order, such that all the chosen machines accept even length string and reject odd length strings, then the set we get (Say T) will also be Infinite Countable and recursively Enumerable and will have a Turing Machine which accepts it. That is why it is language T is Turing Recognizable. Similarly complement of T is Turing Recognizable.

@Rick if I use the following code :

RL(<M>) =
  for n = 0, 1, ...
     for s = s0, ..., sn  \\in the standard order on all strings
       run M on s for one move
         if M(s) = accept AND |s| is odd
           reject // accept as string in L complement
     if not rejected for any string then accept as a string in L

This code will select all the $M$ which accept all strings of even length and do not accept any string of odd length. Then now since we have a membership algorithm for $L$ (as well as for $\overline L$), then can we say that the $L$ and $\overline L$ are recursive?


texts: Two Problems in understanding the algorithm for computing shortest paths in undirected graphs with possibly negative edge weights

texts:
Section 2 of this Lecture Note: Shortest Path Algorithms Luis Goddyn, Math 408 describes an algorithm using Edmonds' Minimum Weight Perfect Matching Algorithm to solve the shortest path problem for undirected graphs with negative-weight edges but no negative cycles.

I have two problems in understanding this algorithm:

In step 3, why must $G'$ have perfect matchings so that we can apply Edmonds' Minimum Weight Perfect Matching Algorithm to $G'$?
In step 4, why must each circuit in $S$ have total weight $0$?
(A possible argument is like this: Because there are no negative cycles, we only need to show that each circuit in $S$ cannot have positive total weight. Maybe this can be proved by contradiction. Suppose that some circuit in $S$ have positive total weight, we need to show that $M$ is not a mimimum weight perfect matching or this cannot be a circuit. However, I failed to reach a contradiction.)

Related post: Finding shortest paths in undirected graphs with possibly negative edge weights.


texts: Example of non extensible functions ( $f(x) \notin EXT $) for reduction

texts: This is the definition of $EXT = \{x\ | \varphi_x\ can\ be\ extended\ to\ a\ total\ computable\ function \}$. I'm trying to proof that $\overline{K} \le_{rec} EXP$ and I can't think of an example of a function that can't be extended


texts:
I'm working on problem H in the ACM ICPC 2004–2005 Northeastern European contest.

The problem is basically to find the worst case that produces a maximal number of exchanges in the algorithm (sift down) to build the heap.

Input: Input ﬁle contains $n$ ($1 \le n \le 50{,}000$).
Output:  Output the array containing $n$ different integer numbers from $1$ to $n$, such that it is a heap, and when converting it to a sorted array, the total number of exchanges in sifting operations is maximal possible.

Sample input: 6
Corresponding output: 6 5 3 2 4 1

And the basics outputs:

[2, 1]
[3, 2, 1]
[4, 3, 1, 2]
[5, 4, 3, 2, 1]
[6, 5, 3, 4, 1, 2]


texts:
I need to give the LL grammar for the language below and explain why the grammar is LL and what the value of $k$ should be:

$$L = \{ a^n c^m c^{n+m} : n \ge 1, m \ge 1 \}. $$

I have the following, but it works for $n \ge 0$ and $m \ge 0$. I'm not sure how to get rid of that case where $n$ and $m$ are 0.

$$
\begin{align*}
&S \to aSc \mid Z \mid \lambda \\
&Z \to bZc \mid \lambda
\end{align*}
$$


texts: Is there any relation between Global minimum cut problem and Maximal independent set?

texts:
I have simple undirected graph. I want to determine a size of minimum vertex cover, a size of maximal independent set and a size of a global minimum cut.

A minimum vertex cover is complementary to a maximum independent set. So, I can find one of this this and get both of them.

Is there any relation with global minimum cut? Or I have to find this size independent from other?


texts: Solution to the following recurrence relation and initial condition?

texts: With the initial condition being $a_0$ = 3, and the relation being $a_n = 2a_{n - 1}$, what would the solution be? Any help would be greatly appreciated.


texts: Finding all "smooth" numbers up to 10^6 -- problem with nested loops

texts:
A [smooth number] is one whose factors are all "small".  For a computational problem, I would like all smooth numbers up to $10^8$.

I think it's unfeasible to factor a billion numbers.  Instead, I am choosing a set of primes, $P = \{2,3,5,7,11,13,17,19,23,29,31\}$.  How can I find all possible product of them less than a billion?

$$\left\{ (k_2, \dots, k_{31}) :  N = \prod_{p \in P} p^{k_p} < 10^9 \right\}$$

The solution is not too hard since $\log_2 10^9 = 9 \log_2 10 < 9\cdot 4 = 36 $ I never have to go too high.

My original question: I really need to index over all possible product, but how do I avoid writing 13 nested loops?


texts: How to count the bits with a 1 bit error correction Hamming code?

texts:
I've seen both ways of counting the bits when determining where to place the parity bits in a 1 bit error correction Hamming code. Some people count the bits starting from the left, others do it by starting from the right.

When to use one or the other? Does this depends on the Endian ordering?


texts: Class of Algorithms where finding output of algorithm can be aided by output of same algorithm given a similar input

texts:
Sorry for the confusing title, but I'm trying to find out if a certain algorithm or class of algorithms fits this description. Given an algorithm A, computing A(x) can be computionally easier if A(g) is known, where g is close to x, and it's easier the closer g gets to x. So also, the amount of computation A has to do grows with respect to the size of the input.

You would also have to be able to calculate the output of A(x) given A(g), x-g, A(x-g). Does A exist for anything other than trivial artithemtic, and if so, is there an entire class of algorithms which A belongs to?


texts: round robin algorithm with multiple iteration

texts:
I am working on a music synthesis. I have to generate certain musical notes and let us say total number of notes equals to $t$.
I have $m$ number of methods (functions) named $m_1, m_2, m_3, \cdots$ and each of them generate specific kind of musical phrases (group of musical notes) consisting of $x_n$ musical notes.
Let us name these count of musical notes as $x_1, x_2, x_3,$ etc. corresponding to methods $m_1$, $m_2$ $m_3$ etc.
That means $t = x_1+x_2+x_3+ \dots  = 100\%$
Each method is also associated with % allocation of musical notes they have to generate and $100\%$ means $t$.
One method will not generate all required $x_n$ counts in one iteration and we may have to go for several iterations to reach their allocated $\%$.

Also once one method is called, the same method cannot be called immediately unless it has very high %. So we need to go for round robin concept and I will name each iteration $i$. Also number of notes generated in each iteration by each method ($=x_{ni}$) is known only after calling the method.

$x_n = x_{n1} + x_{n2} + x_{n3}+\dots$

It is assumed that number of notes in one iteration of respective method is always less than total allocated notes for that method ($x_{n_i} < x_n$)

Assuming 3 methods, distribution could be something like:
$t= x_{11} + x_{21} + x_{31} + x_{12} + x_{32} + x_{13}+ x_{22} + x_{14} + x_{33} + x_{15} + x_{23} = 100\%$
That means every method may not be called in every iterations.

Since number of notes generated by each method is known only after calling a method, we can not distribute in advance. After each iteration, we have to consolidate % notes distributed to that method and evaluate % allocation.

I thought of using knapsack algorithm, considering total weight $= 100\% = t$. But having difficulty with round robin distribution and due to iterative process.

Can anyone suggest best algorithm to handle this? Also any support is available to code in Java?


texts: How to refactor a grammar to be suitable for recursive descent?

texts:
I'm trying to learn how to use a recursive descent parser, and reading on this page I find this example:

$S \rightarrow AB \\
A \rightarrow a \\
A \rightarrow SA \\
B \rightarrow b \\
B \rightarrow SB$

By substituting $S$ we arrive at:

$S \rightarrow AB \\
A \rightarrow a \\
A \rightarrow ABA \\
B \rightarrow b \\
B \rightarrow ABB$

In an attempt to eliminate left recursion, we create $A'$:

$1.\text{ }S \rightarrow AB \\
2.\text{ }A \rightarrow aA' \\
3.\text{ }A' \rightarrow \epsilon \\
4.\text{ }A' \rightarrow BaA' \\
5.\text{ }B \rightarrow b \\
6.\text{ }B \rightarrow aA'BB$

At this point, it is stated

  The grammar is now in a form that will lend itself to recursive descent parser construction after some factoring and substitution.

I know that the problem production is $B \rightarrow aA'BB$ because it references $A'$, which comes before it. I can't figure out how to refactor it so that it does not refer to $A'$. When attempting to generate a series of rules that can be used to prove that a given string is in this grammar, I have trouble determining whether to use rule 3 or 4. Is this an $LL(k)$ grammar? If so, what is $k$?


texts: DFA that rejects $a^{23}$ but accepts $\{a^i|i\geq 24\}$

texts:
Construct a DFA $M$ with $\Sigma = \{a\}$ and max. 11 states so that $a^{23}\not\in L(M)$ but $\{a^i|i\geq 24\}\subset L(M)$.

I don't see how it is possible? Because it's a DFA and the alphabet only contains $a$, shouldn't I only be able to look at modulo 11? I could make 1 mod 11 not accepting but then $a^{34}$ would not be accepted as well.

EDIT: The prof confirmed it was a typo. We are looking for a NFA. Thanks everyone!


texts: If NP is not a proper subset of coNP, why does NP not equal coNP?

texts:
I am studying some lecture notes on the complexity of algorithms.
The notes give a proof that NP is not a proper subset of coNP.
However, they still assert that NP is a subset of coNP (which I agree with).
So, in this case, why does it not follow that NP is equal to coNP?


texts: Proving the security of Nisan-Wigderson pseudo-random number generator

texts:
Let $\cal{S}=\{S_i\}_{1\leq i\leq n}$ be a partial $(m,k)$-design and $f: \{0,1\}^m \to \{0,1\}$ be a Boolean function. The Nisan-Wigderson generator $G_f: \{0,1\}^l \to \{0,1\}^n$ is defined as follows:
$$G_f(x) = (f(x|_{S_1}) , \ldots, f(x|_{S_n}) )$$
To compute the $i$th bit of $G_f$ we take the bits of $x$ with indexes in $S_i$ and then apply $f$ to them.

Assume that $f$ is $\frac{1}{n^c}$-hard for circuits of size $n^c$ where $c$ is a constant.
How can we prove that $G_f$ is $(\frac{n^c}{2}, \frac{2}{n^c})$-secure pseudo-random number generator?

Definitions:
A partial $(m,k)$-design is a collection of subsets $S_1, \ldots, S_n \subseteq [l] = \{1, \ldots, l\}$ such that

for all $i$: $|S_i|=m$, and
for all $i \neq j$: $|S_i \cap S_j| \leq k$.

A function $f$ is $\epsilon$-hard for circuits of size $s$ iff no circuit of size $s$ can predict $f$ with probability $\epsilon$ better than a coin toss.
A function $G:\{0,1\}^l \to \{0,1\}^n$ is $(s, \epsilon)$-secure pseudo-random number generator iff no circuit of size $s$ can distinguish between a random number and a number generated by $G_f$ with probability better than $\epsilon$.
We use $x|_A$ for the string composed of $x$'s bits with indexes in $A$.


texts: Standard busy beaver function draws attention to final count of nonzero symbols on tape. We could instead look at largest amount of nonzero symbols appearing on tape at any point of computation. This function's lower bound would be $\Sigma(n)$ and upper bound would be $S(n)$ (max shifts function). Was there made any research on such functions? If so, are there any known values for this?


texts: What is a term for a problem that is hard to approximate within a factor $c$?

texts:
Let $f$ be a maximization problem. If there is a reduction from SAT to the following problem: "given an integer $c$, decide if there is an $x$ for which $f(x)\geq c$", then $f$ is NP-hard. Suppose there is a reduction from SAT to the following problem:

Given an integer $c$, return "yes" if there is an $x$ for which $f(x)\geq 3 c$, and return "no" if there is no $x$ for which $f(x)\geq c$ (otherwise, the reply is undefined).

This means that, unless P=NP, there is no 3-factor approximation to $f$. What complexity class does $f$ belong to?
Initially, I thought it must be APX-hard, since it is hard to approximate. But
Wikipedia defines a problem as APX-hard as: "there is a PTAS reduction from every problem in APX to that problem", and I am not sure it is equivalent.


texts: Is turing completeness related to recursive enumerable languages?

texts:
I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.

When I looked up for its relationship with recursive enumerable languages, I couldn't find anything substantial.

My question is:

  Will a turing computable machine always accept recursive enumerable
  languages?

Thanks in advance!


texts: Identifying and describing the language accepted by a Turing machine

texts: Given a Turing machine, how can I identify the language it accepts and write a set notation for L(M)?


texts: Prove the correctness of divide algorithm

texts:
This is the pseudocode for the algorithm:

function divide($y,z$)

comment Return $q,r \in \mathbf{N}$ such that $y=qz+r$ and $r<z$ where $y,z \in \mathbf{N} $
$r:=y$, $q:=0$, $w:=z$;
while $w \leq y$  do  $w:=2w$
while $w>z$ do
        $q:=2q$; $w:= \lfloor \frac{w}{2} \rfloor$;
        if $w \leq r$ then
        $r:=r-w;$ $q:=q+1;$
return $(q,r)$

This is what is says the invariant is:

The loop invariant is the following: $q_jw_j + r_j = y_0$ and $r_j < w_j$.

I tried solving it for $r_j<w_j$ for the $j+1$ iteration and ended up with this $y_0=2q_j \lfloor \frac{w_j}{2} \rfloor+r_j$ and I don't have any clue how to finish it, or it is quite possible that I failed to understand how to prove the invariant fot the $j+1$ element (just to carify, I'm talking about proving it with mathematical induction).
Any type of advice or hint is useful.


texts: So I am currently thinking about a problem with a friend that deals with classifying a huge list of statements (I cannot give more information for privacy reasons). My friend ran a K-means clustering algorithm on it and there seem to be groupings. I wanted to do a supervised approach but unfortunately, there always seem to be some possible inputs that will never be covered in any given training set. What ways are there to deal with this?


texts: Convolutional Neural Network with constant kernels

texts:
I'm starting to learn about CNNs, and I have this question that I haven't been able to answer. Sorry if it is too basic.

I know that in a CNN, the network learns to extract relevant features of images in order to classify them. My question is: if I just update the weights of the fully-connected layer and leave the kernels constant, will the network learn how to classify as well?

(The kernels might be a Gaussian blur or a sharpenning, or whatever comes to mind).


texts: Intelligent Agents-Probability and Beliefs

texts:
I am reading about probability and beliefs in artificial intelligent agents, and came across the following passage:

  Why the axioms of probability are reasonable

  The axioms of probability can be seen as restricting the set of probabilistic beliefs that an agent can
      hold. This is somewhat analogous to the logical case, where a logical agent cannot simultaneously
      believe $A$, $B$, and $\neg(A \wedge B)$, for example. There is, however, an additional complication. In the
      logical case, the semantic definition of conjunction means that at least one of the three beliefs
      just mentioned must be false in the world, so it is unreasonable for an agent to believe all three.
      With probabilities, on the other hand, statements refer not to the world directly, but to the agent's
      own state of knowledge. Why, then, can an agent not hold the following set of beliefs, given that
      these probability assignments clearly violate the third axiom?
      $$\begin{align*} P(A) &= 0.4 \\
    P(B) &= 0.3 \\
    P(A \wedge B) &= 0.0 \\
    P(A \vee B) &= 0.8\end{align*}$$

Source: Artificial Intelligence A Modern Approach

I do not understand the meaning of this paragraph. Previously, the book restated some axioms of probability, such that $P(A \vee B) = P(A) + P(B)$ for mutually exclusive events, and $P(A \wedge B) = P(A) \times P(B)$ for independent events.

From my understanding, the statement above says the following:

In a statement using purely logic, information represents the world itself. As such, laws of logic forbid maintaining simultaneously that $A$, $B$ and $\neg(A \wedge B)$ hold. As logic however is an individual's understanding of the world, then the set of probabilities above can be maintained even though they defy the axioms of logic.

My question is, wouldn't an agent have a built-in engine which signals when probabilities are not coherent with each other? How can an agent still maintain them?

Hope this makes sense! :)

Cheers!


texts:
In order to find Big O for a recursive algorithm, it is needed to know the stopping criteria of that algorithm. For the recursive algorithm to find Factorial of a number it is very easy to find the stopping criteria.

int fact(int n)
{
    if((n==1)||(n==0)) return 1;
    else retrun n*fact(n-1);
}

And we can make a mathematical definition of this problem as follow:

$
fact(n)=
\begin{cases}
1,& \text{if } n = 1 \vee n=0\\
n*fact(n-1), &{otherwise}
\end{cases} \tag{1}
$

Now my question is how is the correct mathematical definition for this algorithm:

void func(int n)
{
    if(n>0)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

Also, for the same algorithm if I change it as follow what is the stopping criteria and the mathematical definition of it?

int n = 5;
int rnd; // Random number between 0 and n
void func(n)
{
    if(n>rnd)
    {
        func(n-1);
    }
    else
    {
        print(n)
    }
}

Now the stopping criteria is random? So how can I define this in order to find Big O?


texts:
Assume this particular architecture of a machine. Say we have 4 processors and each processor has its private L1 cache and shared L2 cache. Now if we write to an address in one of the private cache's of the L1 cache then we Invalidate the blocks in the other private cache which contains the same address. Say P0(processor 0) reads an address 100 and so the block containing it say B0 gets stored in the private cache of P0 and as well as in the shared L2 cache. Now say P2  writes to the location 100. So we need to invalidate the block B0 from the private cache of P0. Now if P0 wants to read from address 100 again it will suffer a miss in its private cache, but will it get HIT or MISS in the L2 cache?
I think it will get HIT. Can anyone confirm.


texts: Finding the shortest sublist that contains all search terms

texts:
I've been trying to get better at writing algorithms and came across a problem that was something like this:

Given a list of words:

search_list = ["this", "is", "an", "issue"]

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence:

given_list = ["this", "tv", "is", "an", "state", "node", "is", "this", "issue", "issue", "an"]

Given these two lists, the correct result would be [6, 10], because the closest occurrences of the search_list, would start with the "is" at index 6, and finish with "an", at index 10.

Having said that, here are more details:

closest occurrences - definition

closest occurrence is the smallest subset of given_list in which all of the words occur. By "smallest subset", I simply mean the smallest absolute difference between the smallest occurring index, and the largest occurring index.

allowed inputs

1) search_list - a list or set of words that will only contain unique words. Again, no repeating words will be in this input parameter. This is the set of words that will be used to search given_list to find the shortest/closest subset or occurrences of.
2) given_list - a list or array of words that may contain duplicate words. This is the list that we need to find the smallest/closest subset of search_list in.

expected output

Find the closest occurrences of all of these words in another list, and return the first occurrence and last occurrence.

Here is what I've tried so far: To start, I thought it'd be helpful to find all of the occurrences of each word.

def find_sub_list(search_list, given_list):
    result_list = []
    for value in search_list:
        inner_list = [i for i, val in enumerate(given_list) if val == value]
        result_list.append(inner_list)
    return result_list

Given the variables above, this would result in:

[[0, 7], [2, 6], [3, 10], [8, 9]]

From these results, the correct answer would be [6, 10], because 4 is the shortest distance in which the words occur. However, I can't seem to find a better way to find the closest occurrences without checking every possible outcome. Is there a particular data structure that would make this process faster?

Edit

To further define "closest occurrences", I'll give an example.

search_list = ["one", "two", "three"]
given_list = ["one", "black", "two", "blue", "three", "green", "two", "three"]

The correct answer in this case would be [0, 4]. "two" and "three" occur at indices 6 and 7. However, "one" occurs at index 0, and "two" and "three"'s also occurs at 2 and 4. This subset with indices 0, 2, 4 is a smaller or closer subset than that of 0, 6, 7. Hopefully that makes more sense?

Other notes:

search_list cannot have repeating words. Items must be unique.


texts: Given an array arr[] of N integers. Do the following operation n-1 times

texts:
For every Kth operation:
Right rotate the array clockwise by 1.
Delete the (n-k+1)th last element.

eg:

A = {1, 2, 3, 4, 5, 6}. Rotate the array clockwise i.e. after rotation the array A = {6, 1, 2, 3, 4, 5} and delete the last element that is {5} so A = {6, 1, 2, 3, 4}. Again rotate the array for the second time and deletes the second last element that is {2} so A = {4, 6, 1, 3}, doing these steps when he reaches 4th time, 4th last element does not exists so he deletes 1st element ie {1} so A={3, 6}. So continuing this procedure the last element in A is {3}, so outputp will be 3

How to solve this?


texts:
Is the language

$$L = \{a,b\}^* \setminus \{(a^nb^n)^n\mid n \geq1 \}$$

context-free? I believe that the answer is that it is not a CFL, but I can't prove it by Ogden's lemma or Pumping lemma.


texts: Converting an infix expression to postfix

texts:
So the question is to convert the following expression to postfix:

(a+b)^(p+q)^(r*s*t)

The answer I get when I calculate is: ab+pq+^rs*t*^

But the answer is given to be ab+pq+rs*t*^^

I assume that the step when you need to push second '^' into stack when there is already a '^' in the stack is where I went wrong (I pop out the '^' before pushing). Shouldn't we pop out the first '^' as they are of equal precedence ? Or is it an exception to '^' operator ?


texts: STCON is NL complete - but why is the reduction in L?

texts:
I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity

I understand the reduction, but how is it logspace?

I understand each state is of $O(\log(n))$ space. What I don't understand is how I can create the graph in logspace.

I tried to do some kind of DFS, but remembering the states looks like it'd take $\log(n) * \log(n)$ because the longest path is $\log(n)$ and it costs $\log(n)$ to remember each one?

EDIT: to make sure, I do understand the why the language is in NL, but I don't understand how the reduction from lanuage L in NL to STCON is logspace.


texts: Counting Total Number of Non-Equivalent Configurations in a 2-D Grid

texts:
This is a challenging question I've been trying (unsuccessfully) to solve via programming, math or both.

Suppose you're given a 2D grid, whose width and height, $w$ and $h$, can each range from $1$ thru $12$ inclusive. Each cell in this grid can be in any of $k$ states (where $k$ ranges from $2$ thru $20$).

The problem is to find the total number of distinct (non-equivalent) state configurations of this grid.

Definition: Two configurations of a grid, $c_1$ and $c_2$, are deemed "equivalent" if it is possible to change $c_1$ to $c_2$ by swapping any pair of rows and/or any pair of columns (you can perform the swap operation as many times as you want).

To take an example, let's consider a grid with $w=2$, $h=2$, and $k=2$. We will represent each of the two states as $0$ and $1$ respectively.

One possible configuration of the grid is one where all the cells are in state $0$:

00
00

You could swap any rows and/or columns without changing anything. So the above counts as 1 configuration.

Another configuration is where only 1 cell is in state $1$. There are 4 possible arrangements:

01 10 00 00
00 00 01 10

But note that all of the 4 arrangements are "equivalent", because you can get any of the arrangements by swapping rows and/or columns. So the above counts as 1 configuration.

Next, exactly 2 cells are in state $1$:

11 00
00 11

Another (non-equivalent) way in which 2 cells are in state $1$:

10 01
10 01

And yet another:

10 01
01 10

So there are 3 non-equivalent configurations in which exactly 2 cells are in state $1$.

Next, exactly 3 cells are in state $1$:

10 01 11 11
11 11 10 01

1 configuration, just as in the case where only 1 cell was in state $1$.

Finally, all 4 cells are in state $1$:

11
11

1 configuration, just as in the case where all 4 cells were in state $0$.

So, counting them up, there are exactly $7$ distinct configurations for the case where $w=2, h=2, k=2$.

For reference, here are some brute-force test cases I ran on some additional examples (where the w,h,k values are fairly small):

w=2,h=1,k=1 Answer: 1
w=2,h=1,k=2 Answer: 3
w=2,h=1,k=3 Answer: 6
w=2,h=1,k=4 Answer: 10
w=2,h=1,k=5 Answer: 15
w=2,h=1,k=6 Answer: 21
...
So at least when w, h are fixed at 1,2 (or at 2,1), the pattern seems pretty obvious as k increases. Here is another suite of test cases for w=2, h=2:

w=2,h=2,k=1 Answer: 1
w=2,h=2,k=2 Answer: 7
w=2,h=2,k=3 Answer: 27
w=2,h=2,k=4 Answer: 76
w=2,h=2,k=5 Answer: 175
w=2,h=2,k=6 Answer: 351
...
This is much less obvious to me. If there is a pattern, I'm unsure how to find it.

One more suite of test cases for good measure:

w=2,h=3,k=1 Answer: 1
w=2,h=3,k=2 Answer: 13
w=2,h=3,k=3 Answer: 92
w=2,h=3,k=4 Answer: 430
w=2,h=3,k=5 Answer: 1505
...
yep I'm lost as to what insight if any can be gained.

So, for some arbitrary $w,h,k$, I'm wondering whether there is some type of closed-form formula or perhaps a way to get the answer via dynamic programming/recursion or perhaps divide-and-conquer? I've tried a few of these approaches and didn't really see any obvious breakthrough. The answers get very large very quickly (for example, for $w=2,h=3,k=4$, the answer is 430). I can only imagine how large the answer would be for, say, $w=12,h=12,k=20$.

I would appreciate any help on this. Thanks!


texts: Proving correctness of an iterative Fibonacci algorithm

texts:
One of the questions in the problem sets that I'm struggling in is this specific number that asks me to prove an iterative Fibonacci algorithm. The algorithm is written below:

function fib(n)
    if n = 0 then
        return(0)
    else
        a = 0; b = 1; i = 2;
        while i <= n do
            c = a + b
            a = b
            b = c
            i = i + 1
    return(b)

The way too prove correctness, according to my professor was to make sure that there are these three steps:

Initialization - the loop invariant must hold true prior to the first iteration
Maintenance - the loop invariant must hold true after an iteration
Termination - the loop invariant must hold true when the loop terminates

The loop invariant I've chosen is a <= b since I find this to be true for steps 1 through 3. First of all, I'm not sure if this is a valid loop invariant and this is the only observation I saw since i <= n isn't always true for inputs n that are natural numbers.

Assuming that I've chosen the correct loop invariant, I need to answer the proof by doing three steps so for this number I plan to answer it this way

Initialization - before the start of the loop a is assigned a value of 0 while b is assigned a value of 1 which starts the Fibonacci sequence. a <= b holds true prior to the start of the loop
Maintenance - during the loop, another variable c is added such that it is equal to the sum of a and b. After which, b is assigned to variable a while c is assigned to b thus making the invariant a <= b true during the iteration.
Termination - the loop ends when i > n. Before i is incremented, the procedures in the maintenance step is still done, thus the loop invariant still holds true

For my questions, is my loop invariant a <= b correct? And are the three statements I mentioned above sufficient to prove the correctness of an iterative Fibonacci algorithm?


texts: Help with understanding Simulated Annealing algorithm

texts:
I'm trying to wrap my head around it, but no matter what I read, I still can't fully understand it.
I tried to read a little bit about the annealing process in physics, but I have no background whatsoever in physics, let alone in thermodynamics, so I couldn't understand what is it exactly, and how it fits into the algorithm.
Here is the algorithm:

In the Hill Climbing algorithm, the reasoning can be easily described: Of all the successors of the current state - choose the highest-valued. But in Simulated Annealing... well, I can see what the algorithm does, I just don't understand the reasoning behind it:
1. It starts a timer.
2. It chooses a random successor.
3. It evaluates how "far away" the randomly chosen successor from current.
4. If the successor is indeed a "progress in the right direction" ($\Delta E > 0$) then we move ahead towards the direction of successor; otherwise, we move ahead towards the direction of successor with some (odd) probability that depends on the timer(?).

Why is randomly choosing a successor better then the Hill Climbing method?
Can someone please explain the reasoning behind it?
Do I really have to understand the annealing process? If so, can someone please explain it in layman terms?


texts:
I've been struggling with reduction while solving this exercise and I would really appreciate some help if not the solution.
Problem: [3-SAT-WITH-MAJORITY]
Input: A set of clauses $C = {\{c_1, \dots, c_k}\}$ over $n$ boolean variables $x_1, \dots, x_n$ where every clause contains exactly three literals.
Output: YES if there is a truth assignment to the variable such that both

every clause is satisfied under the assignment
there are at least k/2 clauses in which all 3 literals are set to true under the assignment.

NO otherwise.
Show that this problem is NP-complete.


texts: Unique path sums in a DAG using vertex instrumentation

texts:
I stumbled across this paper from Ball et al.
In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control flow graphs of programs), these values are summed up. Afterwards they are able to reconstruct the executed path from the sum of the values of the traversed edges.

For my research problem, I can not instrument edges, but vertices. To optimize vertex instrumentation I found a great paper from Knuth. However, I can not find a publication about determining vertex values that can be used in a manner as the edge values from the Ball paper.

Does anyone know about an algorithm to fulfill my task?


texts: Reduction examples from the strongly NPC problem 3-PARTITION

texts:
3-PARTITION is strongly NP-complete, i.e. it remains NP-complete even if the input is given in unary.

I'm searching two or three examples of (possibly well-known) non-numeric problems that have been proved to be NP-complete using a reduction from 3-PARTITION (and the reduction obviously relies on the strongly np-completeness). I would like the references to the original papers.


texts: Connection of "modern" runtimes and number of steps on a Turing machine

texts: Why an evaluation of Turing machine efficiency is equal to the algorithm which is implemented by this machine and vise versa? For example, we can say that efficiency of merge sorting algorithm is O(nlog(n)) and therefore Turing machine which implements this algorithm will do O(nlog(n)) steps. Why is this conclusion correct? And vise versa: if there's no deterministic Turing machine which takes less than exponential number of steps to solve some problem, we aren't able to find efficient algorithm solving this problem.


texts: if $f(n)$ is defined in the domain [0,1] then what $f(n) = O(1/n)$ actually means?

texts:
We know that $f(n) \in O(g(n))$ notation means shortly, that $f(n) \leq cg(n)$ for $n>n_o$ where n and c are some positive constants. And actually it gives the behavior of $f$ as $n$ goes to infinity.

But in the case $f(n) \in O(\frac{1}{n})$ where n is at most 1, shouldn't be more intuitive to say that the behavior of $f$ as $n$ goes to zero (and not to infinity) is $\frac{1}{n}$?

For example if $f$ gives the space consumption of an algorithm, then $f \in O(\frac{1}{n^2})$ is a lot better from $f \in O(\frac{1}{n})$ if we allow n>1. But if for any reason algorithm is restricted in the range $n \in [0,1]$ then we would like $f$ resembles $\frac{1}{n}$ and not $\frac{1}{n^2}$.

To make things even weirder suppose that $f(n) \leq \frac{1}{n}+\frac{1}{n^2}$. For n>1 the dominant term is the $\frac{1}{n}$ and someone could easily say that $f(n) \in O(1/n)$.
But if we restrict $n$ to be in $[0,1]$, the dominant term is the $\frac{1}{n^2}$. In that case is it right to say $f\in O(\frac{1}{n^2})$?


texts: Is this example in Skiena's Algorithm Design Manual correct?

texts:
i think the above is incorrect; specifically, i think H isn't bijective. say our alphabet is the lowercase letters [a-z] and that char(a) = 0. then, e.g., H("abc") = H("bc").

am i missing something?


texts: Given a tournament with $2^n$ vertices, show that there is a sub-tournament with at least $n + 1$ vertices that is acyclic

texts:
So a tournament is just a complete directed graph, I believe.

I'm having trouble proving this problem. I know it is induction however. I was thinking
the base case is $2^1$ vertices, and therefore we have a sub-tournament of 1 + 1 vertices, which holds.

Then in our induction step we have to show $2^{n + 1}$. But I'm not sure how to approach this. Any ideas would be extremely appreciated.


texts: Designing solution to critical section problem with two semaphores vs single semaphore

texts:
I came across following problem:

  Let two processes P1 and P2 are there:

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    //s1               |    //s3               |
|    //s2               |    //s4               |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
|    signal(mutex2);    |    signal(mutex2);    |
| }                     | }                     |
+-----------------------+-----------------------+

  Lets mutex1 and mutex2 both are initialized to 1. So in order to avoid deadlock s1, s2, s3 and s4 (respectively) will be replaced by
  (A) wait(mutex2), wait(mutex1), wait(mutex1), wait(mutex2)
  (B) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex1)
  (C) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex2)
  (D) wait(mutex1), wait(mutex2), wait(mutex1), wait(mutex2)

Doubt

Given solution is D, which I understood why. But I am guessing whether having two semaphores mutex1 and mutex2 serve any special purpose in above code?
Does below single semaphore based programs achieve same as what is achieved by above code?

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    wait(mutex1);      |    wait(mutex1);      |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
| }                     | }                     |
+-----------------------+-----------------------+


texts: Least number of guesses needed to determine all unknown subsets of a set

texts:
Say I have a set $\mathbb{S}=\{1,2,...,n\}$. I have an adversary who breaks up $\mathbb{S}$ into $k$ unknown and disjoint subsets. Denote this new set $\mathbb{A}$. I can guess any combination $s$ and my adversary has to tell me if $s$ is itself a subset of any element in $\mathbb{A}$.

For example, if $n=4$, a valid $\mathbb{A}$ might be $\{ \{2\}, \{1,3,4\}\}$. All "true" guesses are $\{1\}$, $\{2\}$, $\{3\}$, $\{4\}$, $\{1,3\}$, $\{3,4\}$, $\{1,4\}$, $\{1,3,4\}$.

What's the fastest algorithm and the upper bound on number of guesses I need to make to fully reverse engineer $\mathbb{A}$?

Obviously the brute force algorithm takes $^nC_1 + ^nC_2 + ... + ^nC_n $ guesses for every possible subset.

But I think I only need to test all possible subsets of size 2 i.e. exactly $^nC_2$ guesses?

Then, I can represent each of the correct guesses of size 2 as an undirected edge in a graph. Every member of $\mathbb{A}$ of size 3 or greater should form a simple cycle in this graph. So I just need to DFS on every node in this graph, removing the longest cycle detected from the graph, and repeat for all remaining nodes until only lone edges (subsets of size 2) or unconnected vertices (subsets of size 1) remain.

This graph should have $n$ vertices and at most $^nC_2$ edges. So the fastest algorithm has a time complexity of $\mathbb{o}(n^{2}\cdot{}^{n}C_{2})$. Is there an approach with fewer guesses or a faster graph algorithm?

P.S.: In case anyone's interested about the context: One example use case is if $n$ known services are hosted on unknown $k$ servers with unknown grouping, and you have some way to overload any subset of services to mount a denial attack on a server. The problem becomes if you can profile the servers with the least number of queries. I came across a similar scenario and thought this was a pretty interesting problem with no literature on.


texts: M is a Determinstic TM with one tape, c2 is c1 reachable, if it's reachable within finite positive time

texts:
$M=(Q,\sum,\Gamma, \delta, q_{0}, q_{accept}, q_{reject})$ is a TM with one tape.
let $c_{1}, c_{2}$ be two configurations of $M$.

A configuration is defined like this:

$uqv$  where $(q\in Q; u,v\in \Gamma^{*} )$

we say that $c_{1}$ is reachable from $c_{2}$ in $M$, if when $M$ is in configuration $c_{1}$ it can reach the configuration $c_{2}$ in a finite number of steps that is greater than 0.

Is the following language TR (Turing Recognizable), is it Decidable?

$L=\{\langle M, c \rangle  \mid M\text{ is a TM; configuration }c\text{ is reachable from configuration }c\text{ in }M\}$?

I know that the answer to this is no, $L$ is not Decidable. I just fail to see the logic behind that.

See I thought $L$ is Decidable because of the following justification:

$L$ is decided by the structure of $M$ it's self with no regards to whatever language $M$ accepts so it is intuitive.

Let's run $M$ non diterministically on any letter of it's alphabet until we get to cofiguration $d\ne c$ then again to reach another config. and so on until we get to configuration $c$ it's self after a threshold number of steps, let's say $N^{q}$ number of steps, where $N$ is the number of configurations in $M$ and $q$ is the number of letters in alphabet.

Kindly explain why language $L$ is TR and not Decidable.

Thank you in advance.


texts:
I learnt in my computer architecture course on Caches, that if we keep the memory speed of a machine the same and half the clock cycle time, the miss penalty doubles. Why does this happen? What is logic behind it? I have emailed my lecturer but he has not replied. In a lecture he just explained if we change one thing then something else has to change to keep the system constant.

I don't know if this is specific to my course or not but this was written in one of the slides I saw:

  lower CPI results in greater impact of stall cycles

I don't know if I should interpret this as a good thing or bad thing? Does it mean if we lower the cycles per instruction, that it will negatively affect the amount of stall cycles?

Similarly, I came across this question in an architecture book:

  We are trying to reduce the execution time by 30% but this leads to an
  increase of 20% in the CPI. What clock rate should we have to get this
  time reduction?

Why would decreasing the execution time cause a rise in CPI?


texts: Finding compound words with Trie in python

texts:
So I have a trie in python but its not leading to the runtime complexity I want from my algorithm to find compound words. I was originally trying to use this algorithm but had no luck https://stackoverflow.com/questions/1291734/finding-dictionary-words

So the words are

['bye','byeen','s','byeens']
# My Trie (*) denotes a word ending
# b - y - e* - e - n* - s* , s*

My algorithm checks the word byeens in the trie and if it exists and then checks if all the individual words exist

So it checks if

'Bye' exists, 'en' exists, and 's' exists. When checking if 'Byeens' is a compound word

While this works for most situations. It obviously doesnt work for this one. The way I found to remedy this is when checking the trie for byeens it constructs two different paths to check if either exist

['bye','en','s'] # doesnt exist
['byeens','s'] # does exist

However, what if the trie is composed of all a's? like this for example

a*-a*-a*-a*-a*

this gets big... really fast. To the order of 2^m-1 where m is the length of the word I believe.

Anyone found a better way to do this?


texts: show that special case of NP-complete problem is also NP-complete?

texts:
I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure that the special case version is also NP-complete but I have no idea how to prove that. Are there any general guidelines for how to do this?

For example, consider this version of the SUBSET SUM problem without repetition:

Given an integer I and a multiset S of integers in the range 1,2,...,10, is there a non-empty subset of S whose sum is I?

I could be wrong, but don't think the restriction of possible values in S to {1, ..., 10} affects the NP-completeness of the problem. How would one go about showing this?

EDIT: Apparently that version of the problem is actually in P. I might restate my question later.


texts: What is a good algorithm for generating random DFAs?

texts:
I am generating random DFAs to test a DFA reduction algorithm on them.

The algorithm that I'm using right now is as follows: for each state $q$, for each symbol in the alphabet $c$, add $\delta (q, c)$ to some random state.  Each state has the same probability of becoming a final state.

Is this a good method of generating unbiased DFAs?  Also, this algorithm doesn't generate a trim DFA (a DFA with no obsolete states) so I'm wondering if there is a better way of generating random DFAs that can somehow ensure that it is trim?


texts: Branch Prediction - LOCAL BHR without tag

texts:
I have a question about the common course "Computer Architecture".

How is it possible to have a LOCAL Branch Predecitor with 1024 entries, 3 bits for HISTORY but without a TAG.

As I understand,in that way i will get a Global branch predictor because i dont have a way to map a branch to an entry. Am I right? If not,How can it be possible?


texts: Regular expression for C-style /**/ comments

texts:
I am aware that a similar question was already asked here and that the recent question A DFA for recognizing comments is also related but I am not satisfied with the answers.

The point is that

  printf("/* This is not a comment */")

is a perfectly legal instruction in C and, as suggested by its name, the pattern to be printed is not a comment.

Is there a regular expression describing C-style /**/ comments in a correct C program?


texts: why quicksort can have a best big o notation of (n log n)

texts:
I don't really quite understand why quicksort has a big $O$ notation of $(n \log n)$. I would like some help understanding what exactly $(n \log n)$ is, and then how it applies to quicksort.
Also in $(n \log n)$, what is the base for the $\log$?
Thanks.


texts: Remove minimum number of vertices to disconnect the graph

texts:
Consider an undirected graph with a source and a sink vertex. We would like to remove minimum number of vertices in that graph to disconnect any path between source and sink.

Can we do this using say a max-flow, min-cut algorithm?


texts:
I'm working on an LLVM-like kit for .Net - because this is something that's lacking in .Net and I really want to learn the more advanced compilation theory.

I'm really struggling to find anything digestible for turning Phi into platform code (in this case MSIL). Consider the following SSA fragment:

inputs = a0
a1 = a0 + 1
br branch1 a0 > 100
  a2 = a1 / 2
  br branch1

branch1:
  a3 = phi(a1, a2)
  _ = Log(a3, a1)

Granted, this code makes no sense from a AST-to-SSA standpoint because you'd need a temp in the source language anyway - it's valid SSA nonetheless.

The solution I came up with is to create a directed graph out out of all instructions. Edges are directed from stores toward the future read. Essentially:

NB: direction of arrows next to the red node.

When storing to a register (keeping in mind that MSIL has "infinitely" many registers), you just follow the directed graph and store to the final register that you end up on. If more than one path can be taken, allocate temporary registers and continue down each path (recursively).

inputs = p
r1 = p + 1
r2 = r1
if r1 > 100
  r1 = r1 / 2
Log(r1, r2)

Because I'm using a graph, loops are a compounding problem (StackOverflow problems, not the website type). I decided on Tarjan's strongly connected components algorithm to do a topological sort and to identify cycles (what a beautiful algorithm). Creating a flyweight to indicate which variable(s) to assign to is then "merely" a matter of looping over the strongly connected components in reverse and maintaining some state.

The "merely" part of that is where I'm getting tripped up - things are becoming O(Nscary) very quickly. I also need to kludge in reading from inputs/parameters, because I'm using the last variableN that the values get stored to, to also load from (for obvious reasons). This gives me the idea that I've headed down the wrong path, and I'm out of ideas.

Does someone have a nudge in the right direction for me?


texts:
I am currently studying about formal languages and automata.
I am trying to solve a problem but there is a notation whose meaning I'm not sure of.

I have a question to find out the relationship between two languages $L_1$ and $L_2$:

$L_1:$

$S \to aSa|bS|e$

$L_2 \to L((ab+ba)^*)$

My question is, does it mean that $L(ab+ba)$ is the set $\{ab, ba\}$?

I mean, $L(ab+ba) = L(ab)\cup L(ba)$


texts: Context free grammar as minimal solution of a system of equations

texts:
It is a well-known fact that language generated by a context-free grammar is the minimal solution of a particular system of equations, for example:

$$\begin{align*}
X &=\{{\epsilon}\} \cup Y\\
X &=\{{a}\}Y \{{v}\}
\end{align*}$$

generates the language $\{a^nb^n : n \in \mathbb{N}\}$.

How can I prove that fact? How do I make the step from equations over sets to context-free grammars? In contrast to regular languages, which are accepted by automata without stack, it seems like the equations that generate CFG can't be easily transformed to pushdown automata.


texts: Closest Value instead of Max Value in Knapsack problem

texts:
I have a problem like the knapsack problem, except instead of finding the max value, I'm trying to find the closest value to a given value.

Anyone know where to start, have a name for this problem, or can point me to an example?

Thank you!


texts: Algorithm to generate self-avoiding random walk on a lattice

texts:
Where can I find some code to generate random self-avoiding walks on 2 and 3-dimensional lattices whose side-lengths are powers of two? The walk should pass through every point on the lattice More specifically, how can I find a random hamiltonian path on a large $2^n \times 2^n$ or $2^n \times 2^n \times 2^n$ grid graph?

The distribution doesn't have to be completely uniform, however in general the lattice should look wrinkled. The method used to generate the path should have low probability of producing extremely long stretches of straight line.


texts: Where does the interrupt handler return to?

texts: Say the CPU is currently handling an interrupt. Another interrupt arrives but it's lower priority than the current one so it gets put in the 'pending interrupt register'. My current interrupt is done so I use a 'return from exception' instruction. Where will this instruction jump to: the address which was interrupted, and then to the interrupt handler or will it immediatly jump to the handler of the new interrupt that is in the 'pending interrupt register'?


texts: Algorithm for finding an irreducible kernel of a DAG in O(V*e) time, where e is number of edges in output

texts:
An irreducible kernel is the term used in Handbook of Theoretical Computer Science (HTCS), Volume A "Algorithms and Complexity" in the chapter on graph algorithms.  Given a directed graph $G=(V,E)$, an irreducible kernel is a graph $G'=(V,E')$ where $E'$ is a subset of $E$, and both $G$ and $G'$ have the same reachability (i.e. their transitive closures are the same), and removing any edge from $E'$ would not satisfy this condition, i.e. $E'$ is minimal (although not necessarily the minimum size possible).

A minimum equivalent graph is similar, except it also has the fewest number of edges among all such graphs.  Both of these concepts are similar to a transitive reduction, but not the same because a transitive reduction is allowed to have edges that are not in $E$.  That said, [1] proves that for every DAG, it has a unique irreducible kernel, which is also its unique minimum equivalent graph and its unique transitive reduction, and thus there is no benefit in the transitive reduction to using edges not in the original graph (there is a difference between minimum equivalent graph and transitive reduction for some graphs with cycles, but not for DAGs).

HTCS says that there is an algorithm to calculate an irreducible kernel of a directed acyclic graph in $O(V*e)$ time, where $V$ is the number of vertices, and $e$ is the number of edges in the irreducible kernel, i.e. the output of the algorithm.  The reference given for this is the following paper, which I have not been able to find an on line source for yet (links or other sources welcome -- I can ask at a research library soon if nothing turns up).

Noltemeier, H., "Reduction of directed graphs to irreducible kernels", Discussion paper 7505, Lehrstuhl f. Mathematische Verfahrensforschung u. Datenverarbeitung (Operations Research & Data Processing), Univ. Göttingen, Gottingen, 1975.

Does anyone know what this algorithm is?  It surprises me a little that it includes the number of edges in the output graph, since that would mean it should run in $O(n^2)$ time given an input graph with $O(n^2)$ edges that represents a total order, e.g. all nodes are assigned integers from 1 up to $n$, and there is an edge from node $i$ to $j$ if $i < j$.  That doesn't seem impossible, mind you, simply surprising.

[1] Aho, Garey, and Ullman, "The Transitive Reduction of a Directed Graph", 1972 https://epubs.siam.org/doi/10.1137/0201008


texts:
Is there any systematic (algorithmic) method to convert a regular expression like

$(a^*)(b)(b^*)(a^*)c$

to an automaton (let's say a Buchi automaton)?


texts: Algorithm to maximize dot product between two sets of vectors

texts:
I have two sets of vectors $(\mathbf{l}_i)_{1\le i \le n}$ and $(\mathbf{r}_i)_{1 \le i \le n}$. Each vector $\mathbf{l}_i$ is in $[0,1]^4$, same for $\mathbf{r}_j$. I'd like to maximize the dot product $\mathbf{l}_i \cdot \mathbf{r}_j$, i.e. find tuples $(i,j)$ s.t. $\mathbf{l}_i \cdot \mathbf{r}_j$ is as big as possible.

To be clear, if $\mathbf{l}_i=(\mathbf{l}_{i,1},\mathbf{l}_{i,2},\mathbf{l}_{i,3},\mathbf{l}_{i,4})$ and $\mathbf{r}_{j}=(\mathbf{r}_{j,1},\mathbf{r}_{j,2},\mathbf{r}_{j,3},\mathbf{r}_{j,4})$, then:

$$\mathbf{l}_i \cdot \mathbf{r}_j=\sum_{k=1}^4 \mathbf{l}_{i,k} \mathbf{r}_{j,k}$$

The number of tuples I'd like to find should be ideally a parameter of the algorithm, i.e. find the $K$ tuples $(i,j)$ that lead to the greatest values of $\mathbf{l}_i \cdot \mathbf{r}_j$. I won't mention $K$ in the complexities below, let's say $K \ll n$.
I'm looking for $O(n \log^k n)$ ideas. The naive algorithm takes $\Theta(n^2)$ time, which is too big for me ($n \approx 2^{20}$).
My first idea was to try to solve the problem in dimension 2, with the additional constraint on the input $|\mathbf{r}_j|=1$. In that case it is easy to design a $O(n \log n)$ algorithm: sort all $\mathbf{r}_j$ according to their angle with $(1,0)$, then for all $i$, find $\mathbf{l}_i$ in that list by binary search.

In my opinion, intermediary tasks might be:

Try to generalize the formula $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}| |\mathbf{v}| \cos(\mathbf{u},\mathbf{v})$ to dimension $4$.
Try to remove the condition $|\mathbf{r}_j|=1$ from the algorithm in dimension $2$.

I have no idea on how to solve these two problems.

I'm asking this in a single question because I'm also interested in more general algorithms that may give approximations (e.g. that solve the "maximum dot product" problem in arbitrary dimension).


texts: Describing the asymtotic complexity of processing two-dimensional data structures

texts:
Consider the following Python function:

def count_chars(list_of_strings):
  chars = 0
  for s in list_of_strings:
    for c in s:  # intentionally avoiding len() here for the sake of example
      chars += 1;
  return chars

Clearly this is a linear operation, since we iterate over every element/character once. But I've often seen the Big-O of this function as $O(n*k)$ where $n$ is the length of the list, and $k$ is the length of the longest string. In a sense, that's polynomial or quadratic (at a minimum, I've heard people refer to this type of algorithm as such).

What is the appropriate way to refer to this type of function? Is there an intuitive way to understand this is linear, despite multiple variables?  In particular, how can we discuss that this is worse than a solution that uses len() (which is $O(1)$) without getting hung up on the fact that, in practice, both are linear?

Context: I'm posing an interview question that, while more complex than this example, involves identifying and eliminating $k$.  I've had candidates struggle to see that and it's felt like a communication issue more than a understanding problem.

I'm looking for ways to help guide a discussion, and to recognize that while this is linear, it is still asymptotically worse than an operation that avoids hitting each character individually.


texts: Count points enclosed by several planes in 3D space

texts:
I have for example 10 planes with their equation: Ax + By + Cz = D and a list of 3D points.
Those plane can make regions, some of them closed, and others not, the task is to count the number of points in each region.

I just need some ideas about how to solve, or if there is an algorithm for that.


texts:
Given the ambiguous CFG :
S → 01S1|SS|ϵ

I came up with the following CFG which I think is unambiguous:

S → 01X | 011X
X → 01X1 | ϵ

Is my CFG unambiguous and does it represent the same language?


texts: What is the equivalent of the integers symbol Z for n bit only integers?

texts: We refer to the set of all integers as $\mathbb{Z}$.  Now suppose we have a set of integers that can be held within a computer variable of $n$ bits width. Clearly they can only be of  $2^{n}$ range, signed or not. How would we symbolise that? Is there something that is done to the zed, or does it remain simply $\mathbb{Z}$?


texts: Name of a tree with arbitrary number of branches at each fork point?

texts:
A binary tree is a rooted tree with the root having an indegree of 0 and all other nodes of 1. The outdegree is 0, 1 or 2 for all nodes.

How do you call a rooted tree if the number of branches per node is arbitrary (outdegree of n) but the indegree 1 for all nodes other than the root node?


texts: Optimal flow in a network with non-constant edges' weights

texts:
I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather different so i need an advice.

Suppose that we have a weighted directed graph with two (possibly the same) vertices designated as "source" (S) and "target" (T). We can imagine that vertices represent the currencies and edges are conversion options. There is some initial amount of money in vertex S and it has to be converted to vertex T in such way that the resulting sum is maximum possible.

Conversion can be done in parts so if there is some sum S at vertex V and there are several edges coming from V then we can send different amounts of money along these edges (i.e. we are not obliged to use only one edge or to divide the sum in equal parts or to use multiples of some fixed lot etc.). We are also not obliged to convert total sum. It can be the case that the best option is to convert some part of it.

Now comes the trickiest part. Each edge's weight depends on amount of money that must be transported through an edge. For each edge E there is some function F(E) that receives amount of money entering the edge and returns amount of money leaving the edge. We can assume that ratio of output/input gets smaller when input gets bigger.

Thank you very much for any ideas. Any help will be highly appreciated.


texts: Elegant or readable way to store tree by user

texts:
Sorry if my title or question is unclear. I lack the vocabulary to formulate it properly.

I've got a classical tree structure with several layers.
I have to manage authorization for each user, as not every user has access to all elements, so each user has their own view of the same tree.

What is the best way to store this kind of tree?

Should I store all the tree and use booleans to know if each user has access to each element? Or should I only store an array of elements? Are there any alternatives?

In this case, readability is more important than pure performance.


texts: I'm asking the question on the behalf of my classmates. We have a trouble about parallel programming that we can't comprehend threads, semaphores, forks and etc. We have been taking third time the course called as system programming. The instructor of the course goes with Unix, C and POSIX standarts. There are some books like robbins concurrent programming(our course book), the linux programming interface. But, because of our lecturer explanation we can't understand usages  and benefits of parallel programming. If there was a chance to only study the course in a semester maybe we can accomplish some logics and ideas, but no.Even so, now he has given an assignment, we are on semaphores, threads and syncronazation and don't get anything about them. What can we do? How can we comprehend the logic of parallel programming and usages(how to use) of it?


texts: Finding arcs between strongly connected components

texts:
Having a graph and all of it's strongly connected components, I was wondering what the most efficient way to find arcs that connect two SCC. All the solutions I found involve running through all the nodes, and I was wondering if there was a way to do it without having done that, in particular, during the Tarjan algorithm I used to find SCC's in the graph. ANyway to do it in a linear fashion?

Thank you very much!


texts: Why can we drop the superscripts in the Floyd Warshall algorithm?

texts:
In the lecture notes, our professor mentioned that we can take down the space taken by the FW algorithm from $O(n^3)$ to $O(n^2)$ by dropping all the superscripts in the matrices (i.e. use one $n\times n$ array $D$).

I just want to check my understanding, is it because by default $D^k=D^{k-1}$ except for the values $i,j$ where $d_{ik}^{k-1}+d_{kj}^{k-1}<d_{ij}^{k-1}$ where we set $d_{ij}^k=d_{ik}^{k-1}+d_{kj}^{k-1}$ but in essence we are using the values in the $D^{k-1}$ matrix to update itself?

However, what if we change one value, say $d_{i_1j_1}^k$ in the $kth$ iteration but then we need to reuse the value $d_{i_1j_1}^{k-1}$ later on in the same $kth$ iteration, wouldn't it be lost?


texts: What if the electricity goes off while a file is being renamed?

texts:
Suppose I'm renaming a file and the electricity goes off right in the middle. Naively, it looks like the file could be in some “half-renamed” state. Maybe the name would have half the old name and half the new name. Or maybe the file could disappear altogether because it no longer exists under the old name but it doesn't exist yet under the new name.

How can a filesystem protect against loss of power while a file is renamed? Are these just theoretical techniques or are they used in practice?


texts: Time Complexity of a Knapsack-derived problem

texts:
Consider the following problem:

Let there be a set A of $n$ items $A=\{z_1, ..., z_n\}$, and let $W$ be a strictly positive integer.  Each item $z_i$ has a value $v_i$ and a weight $w_i$. Finding a subset $AS$ of $A$ so that the weight of $AS$ is less than $W$ and the value of $AS$ (the sum of the value of its items) is maximized is the 0/1 Knapsack Problem

Now, consider a deviation from it where the items in $A$ have certain dependency relationships between each other, and these dependencies can be captured by a directed acyclic graph $G(A, E)$.  The value of the set $AS$ is no longer the sum of the value of the items in $AS$. For each item in $AS$,  its value depends on which other items are also in $AS$.  More formally, if $v$ is in $AS$, its contribution to the value of $AS$ would be its own value, plus the value of all the ancestors of $v$ in $G$ not in $AS$.

My Questions

What is the complexity of this problem? Is it NP-Hard in the strongest sense or in the weak sense? (in the strongest sense (one for which no pseudo-polynomial algorithm is known)). I have tried to come up with a modification of the classic dynamic programming algorithm to solve it, but with no luck. I am thinking that I should try to reduce an NP-Hard problem for which no pseudo-polynomial time algorithm is known to this problem.  Do you know any of such problems that looks similar to this one?


texts: Can you recognize or decide if a Turing Machine has an infinite sized language?

texts:
That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language?

Similarly, can you recognize or decide if a Turing Machine has an uncountably-infinite language?


texts: Why is solving of diagonal quadratic equations over $\mathbb R$ and $\mathbb C$ in $P$?

texts:
Let $\mathbb F\in\{\mathbb R, \mathbb C\}$ the field of real or complex numbers. Then [1, page 22 in the middle] claims that the following equation can easily be solved in deterministic polynomial time:
$$ \sum_{i=1}^n a_ix_i^2=b$$
with $a_i, b\in\mathbb F$. Some discussion suggests, that the algorithmical model assumed in the paper is that of a machine that can perform field operations in one step.

My question is: What is the algorithm? Is it multidimensional Newton? That would be weird because this algorithm only converges (in some cases) and does not give an exact solution. I'm quite unused to computational models over fields like the reals or complex numbers and maybe for someone who is more experienced this is cristal-clear?

[1] Agrawal & Saxena, On the complexity of cubic forms, 2006.


texts: Is this depth-first top-down parsing algorithm a recursive descent top-down parsing algorithm?

texts:
In Thomas Sudkamp's book, Machine and Languages, there is a depth-first top-down parsing algorithm (please see the algorithm here).

My main question is:

1) Is this algorithm a (backtracking) recursive descent top-down parsing?
This is because I am confused with the difference between the terms depth-first top-down parsing and recursive descent top-down parsing.

Additionally, I would appreciate it if you would answer these two questions also, as it is related to the algorithm:

2) In Step 2.3.3.3, why there is a need to assign $i=0$? If we want to backtrack, isn't the correct way is to keep $i$ as it is?

3) Does this algorithm uses a pushdown automaton? Is parsing using pushdown automaton different than just using a stack?


texts:
According to complexity zoo:
Class UP (Unambiguous Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that

If the answer is “yes,” exactly one computation path accepts.
If the answer is “no,” all computation paths reject.

Class US (Unique Polynomial-Time) is defined as:
The class of decision problems solvable by an NP machine such that the answer is “yes” if and only if exactly one computation path accepts.

In contrast to UP, a US machine can legally have more than one accepting path that just means that the corresponding input is not in the language.

My question is:

Is there an example of a problem which is known to be in one class,
but not in other?  We know that UP $\cup$ coNP $\subseteq$ US.
It is known that class US is a subset of $P^{NP}$. A well-known example is USAT which is known to be US-hard (and coNP hard) but not known to be coNP. US is not known to be equal to coNP. Also, I know that coNP $\subseteq$ US. Can one give an intuitive reason for this?
How can a machine have more than one accepting path, but
that input is not in the language? (Maybe I am missing something
trivial here)


texts: Selecting random points at general position

texts:
How will you find a random collection of $n$ points in the plane, all with integer coordinates in a specified range (e.g. -1000 to 1000), such that no 3 of them are on the same line?

The following algorithm eventually works, but seems highly inefficient:

Select $n$ points at random.
Check all $O(n^3)$ triples of points. If any of them are on the same line, then discard one of the points, select an alternative point at random, and go back to 2.

Is there a more efficient algorithm?


texts:
if we define $F_n$ be the $n$th fibonacci number and $\varphi$ be golden number then can we say that

$2^{F_n} \in \Theta(2^{\varphi^n})$

or in other word

$2^{\frac{\varphi^n - (-\varphi)^{-n}}{\sqrt{5}}} \in \Theta(2^{\varphi^n})$

It's simple to show that $F_n \in \Theta(\varphi^n)$ but about above one I don't have any Idea


texts:
I want to give a grammar for the following language:

$$L = \{x^r \# y |x, y \in \{a, b, c\}^*\\
\text{
and }x\text{ is a contiguous sub-string of }y\}$$

where $x ^ r$ denotes the backward written word $x$

I have tried the grammar, is this right or have I made a mistake:

$S \to Sa \mid Sb \mid Sc \mid T$,

$T \to aTa \mid bTb \mid cTc \mid U$,

$U \to Ua \mid Ub \mid Uc \mid \#$


texts: Which address bits are used for set selection/tag check in a cache?

texts:
If

  Capacity = 24 KiB Associativity = 6 Line Size = 32 B

As far as I know:

$$Capacity = Associtivity * Line Size * Sets$$

so
$24576 = 32 * 6 * Sets$

$Sets = 128 = 2^7$

thus 7 least significant bits are needed to identify set number.

Am I doing it correctly?


texts: Sudoku Puzzles in O log n time although inefficient

texts:
Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles.  I then create the pseudo-code to demonstrate the algorithm.

The algorithm does a search to compare the indexes of elements
in the puzzle that are not listed as zero.
In other words, all the possible listed Sudoku
grids are compared until a solution is found matching solution sharing the elements with the
same index.

--

tuple=[.......]

tuple=[.......]

all possible Sudoku grids.

Here's our solver.

solver = input('enter the puzzle like this 10000030004000...)

if Element with Same Index solver == tuple1, tuple2,...

print (solution containing exact elements that share the indexes in
       both the solution and puzzle)

Will this algorithm solve all Sudoku Puzzles in O log n time?


texts:
I haven't been able to find whether this problem has been studied: we are given a graph $G$ and an ordered list of $k$ colors $L = [\ell_1, \cdots, \ell_k]$. Additionally, we are given a positive integer $s \le k-1$.
The decision question is whether $G$ can be properly colored such that every pair of adjacent vertices will receive two colors within distance $s$ in the list (i.e., if the two colors are $\ell_i$ and $\ell_j$, then $|i-j| \le s$).
This is of course equivalent to the standard coloring problem when $s = k-1$. Would be interested in both exact and approximation algorithms (if known).


texts: CFG for $w\#x$ where $|w| = |x|$ and $w \neq x^R$

texts:
How do I construct a context-free grammar for the following language?

$$L = \{w\#x \mid w, x \in \{0, 1\}^*, |w| = |x|, w \neq x^R \} $$


texts: Does anybody know whether the multiset of the determinants (possibly together with the order of the submatrix they refer to) of all the principal minors of the (symmetric) adjacency matrix of a graph is a complete invariant for graph isomorphism (i.e. that multiset uniquely identifies a graph up to isomorphism)?


texts: Existence of a route following one-way streets

texts:
I am trying to understand the approach for this problem:

  "If all streets are one way, there is still a legal way to drive from
  one intersection to another"

The question is to prove that it can be done in linear time. I am not looking for direct answers but the approach to this problem.

How can I think about this problem in terms of graph theory? AFAI understand, this will result in a DAG. But then should I choose BFS or DFS and why to prove it? (both are liner time algos)


texts: Text Segmentation Problem give Word Frequencies in a Universe

texts:
Given a dictionary of words and their frequencies (how many times they appear in a universe and given a string(no spaces, punctuation, etc.). What is the best way to segment into individual words? I believe a dynamic programming approach would be best. But I am not sure how to proceed about throwing away unnecessary prefixes of identified words and so on.

Ex. "theyouthevent"

 could be "the you the vent"
 or "they out he vent"
 or "the youth event" (most likely)

I think Peter Norvig outlines a pretty good approach in this http://norvig.com/ngrams/ch14.pdf

Just curious to see if there are any other good approaches suited for the specific problem with the data I have. Norvig has n-gram data while I only have word frequencies (which is essentially a unigram)


texts:
We need to select participants, based on the quotas provided. For example:

exactly 15 men
exactly 15 women

exactly 10 young
exactly 10 middle aged
exactly 10 old

exactly 10 poor
exactly 10 middle class
exactly 10 rich

The total number of participants should be exactly 30.

What algorithm should be used to do that?

Simpler, more detailed, example.
Let's say that output quota is: 4 people: 2 women, 2 men, 2 old, 2 young.

Input set is:

Man Young
Man Young
Man Old
Woman Old
Woman Young

So the matching output set should be:

Man Young
Man Old
Woman Young
Woman Old

If we'll just start adding people to the output set one by one, skipping those, that would go over the quota, we'll end up with:

Man Young
Man Young
Woman Old

We'll have Man Old and Woman Young left, but none of those would match the quota.


texts:
I have a small context-free grammar, which I would like to use to turn input strings into parse trees. I need to get all possibilities in case of ambiguity (so shift-reduce is out), and there's quite a lot of left-recursion (so recursive descent is out).

With these constraints in mind, I've implemented Earley's algorithm, which is functioning quite well…as a recognizer. The problem is, I need a parser as well.

The problem is small enough that I'm not worried about space complexity, and my intended application will require expanding out every possible tree anyway. So the packing mechanisms of an SPPF (shared packed parse forest) aren't necessary here.

Is there a simple algorithm to do this?


texts: An explanation for Barendregt use of Y combinator in an equation

texts:
I am going through the following lecture notes on lambda calculus by Barendregt and Barendsen :

http://www.cse.chalmers.se/research/group/logic/TypesSS05/Extra/geuvers.pdf

Here at page 12 , after introducing fixed point theorem a small exercise which is an attempt to prove the following has been posted :
$ \exists G  \forall X $ $GX =SGX $.

It first proceeds to  the implication

$Gx$ = $SGx$

which implies :
$G$ = $ \lambda x .SGx $

which implies :
$G $ = $ (\lambda gx.Sgx)G$

and then it concludes that :

$G$ = $Y$ $( \lambda g x.Sgx)$ where $Y $ is the fixed point combinator .

I am unable to figure out how was G found out to be  $Y$ $( \lambda g x.Sgx)$ in the last step ? How was this conclusion reached up to ?


texts: How to make logical inference from simulated data

texts:
I have data collected from a computer simulation of football games which seem to have
recurring patterns of the following form.

if madrid plays arsernal and the match ends under 3 goal, then on their next match against each others,
madrid will win. if madrid happens to loose and then plays against chelsea next, they will win 90% of the time.

how do I find such inferences from simulation generated data like this. There are other forms of hidden patterns that I believe exists in the dataset.


texts:
Does coNP-completeness imply NP-hardness? In particular, I have a problem that I have shown to be coNP-complete. Can I claim that it is NP-hard? I realize that I can claim coNP-hardness, but I am not sure if that terminology is standard.

I am comfortable with the claim that if an NP-complete problem belonged to coNP, then NP=coNP. However, these lecture notes state that if an NP-hard problem belongs to coNP, then NP=coNP. This would then suggest that I cannot claim that my problem is NP-hard (or that I have proven coNP=NP, which I highly doubt).

Perhaps, there is something wrong with my thinking. My thought is that a coNP-complete problem is NP-hard because:

every problem in NP can be reduced to its complement, which will belong to coNP.
the complement problem in coNP reduces to my coNP-complete problem.
thus we have a reduction from every problem in NP to my coNP-complete, so my problem is NP-hard.


texts: What's the difference between a bridge, a mediator and a wrapper?

texts: The slides from my course in software architecture hints that these are seperate terms, but I can't seem to find the difference. Aren't all of them just translating interfaces?


texts: CSP Forward checking with n-ary (and binary) constraints

texts:
I have implemented my own CSP solver using a Backtracking algorithm.
Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that only works with Binary constraints.

The problem I have is that the CSP I try to solve has lots of n-ary constraints, making the FC algorithm mostly redundant.

Is there a way to enhance or replace my FC algorithm, so it works with n-ary constraints.
Or is there a "simple" procedure to convert n-ary constraints to binary constraints?

EDIT:
Added pseudo code (attempt) of the Forward Checking algorithm:

function ForwardChecking(variable, csp) list of variables with new domains, or failure
    for each constraint in connectedConstraints(variable) do
        if connectedVariable is assigned then
            if constraint is not satisfied then
                return failure
        else
            for each value in connectedVariable.domain do
                connectedVariable.assign(value)
                if constraint is not satisfied do
                    remove value from connectedVariable.domain
                if connectedVariable.domain.count == 0 then
                    return failure
                add connectedVariable to solution
    return solution


texts: What are the examples of trivial and non-trivial properties of language recognized by a Turing machine?

texts:
Rice's theorem: Any nontrivial property about the language recognized by a Turing machine is undecidable.

I know the proof but I am not able to understand the theorem. I think trivial properties are like :language recognised by Turing machine contain at substring "aab". where as nontrivial property means is language accepted by Turing machine is finite etc.

My question : Give at least two example of trivial properties and two non-trivial property about the language  recognized by a Turing machine.