Is this grammar really LL(1) while not being LR(1)? $S \rightarrow S$, $L(G) = \{\}$

LL(1) analysis:

We estabilish $FIRST(S)$ to be empty and $FOLLOW(S)$ to be $\{\$\}$.
$FIRST(S)$ doesn't contain ε, so the parse table looks like this:

+---+---+
|   | $ |
+---+---+
| S |   |
+---+---+

and correctly rejects any input including ε.

LR(1) analysis:

We start with the initial state 0:

$S' \rightarrow \bullet S [\$]$

calculate its closure:

$S' \rightarrow \bullet S [\$]$

$S \rightarrow \bullet S [\$]$

and the only transition, which leads to state 1 on S:

$S' \rightarrow S \bullet [\$]$

$S \rightarrow S \bullet [\$]$

State 1 has a reduce/reduce conflict.

Now, obviously there must be something I'm missing, since LL(k) grammars are a proper subset of LR(k) grammars. Would anyone care to point out the error?

I've just consulted a parsing book, and it indeed requires that $S \Rightarrow^+ S$ be impossible, if $S$ is the starting symbol, before a grammar is considered $LR(k)$. As you said yourself, this is not required for a grammar to be $LL(k)$.

Usually, it is implicitly assumed grammars 'behave' when we make statements about them, such as $LL(k) \subset LR(k)$. For instance, $S \Rightarrow^+ S$, absence of symbols not derivable from $S$, and absence of symbols not deriving terminal strings are all properties of 'well behaved' context free grammars.

If we assume these things, we are spared some weird oddities of context-free grammars: for example, if we have some grammar with starting symbol $S$, by adding a nonterminal $T$ and productions $T \to \epsilon$, $S \to T S$, we can force the grammar to have infinitely many parse trees for every string in the language it represents. In contrast, if we do assume 'well behaved' grammars, we are guaranteed only finitely many parse trees exist for any input.


Is CS more like software and CE more like hardware? At my university, a degree is "Computer Science and Engineering" but at US universities I understand that the degrees are different so what is the fundamental difference? Is computer engineering lower level like hardware and operating systems while computer science is more like language technologies?

This is actually an easy one, particularly if you just want to see some meaningful distinction drawn by an organization people listen to. Consider the ACM/IEEE guidelines on computing curricula.

The differences between Computer Science and Computer Engineering can be seen when comparing the respective bodies of knowledge:

Computer Science (2008)

Discrete Structures, 43 core hours
Programming Fundamentals, 47 core hours
Algorithms and Complexity, 31 core hours
Architecture and Organization, 36 core hours
Operating Systems, 18 core hours
Net-Centric Computing, 15 core hours
Programming Languages, 21 core hours
Human-Computer Interaction, 8 core hours
Graphics and Visual Computing, 3 core hours
Intelligent Systems, 10 core hours
Information Management, 11 core hours
Social and Professional Issues, 16 core hours
Software Engineering, 31 core hours
Computational Science, no core hours

The total core hours for CS add up to 290 hours.

Computer Engineering (2004)

Algorithms, 30 core hours
Computer Architecture and Organization, 63 core hours
Computer Systems Engineering, 18 core hours
Circuits and Signals, 43 core hours
Database Systems, 5 core hours
Digital Logic, 57 core hours
Digital Signal Processing, 17 core hours
Electronics, 40 core hours
Embedded Systems, 20 core hours
Human-Computer Interaction, 8 core hours
Computer Networks, 21 core hours
Operating Systems, 20 core hours
Programming Fundamentals, 39 core hours
Social and Professional Issues, 16 core hours
Software Engineering, 13 core hours
VLSI Design and Fabrication, 10 core hours
Discrete Structures, 33 core hours
Probability and Statistics, 33 core hours

The total core hours for CmpE add up to 486.

A fair way to compare the two might be to find a percentage makeup based on the above curricula. The conclusion would seem to be that CS is at or above CmpE in subjects they have in common, and has fewer other subjects, whereas CmpE is lower in common areas to both programs, but has more subjects not studied in CS, mostly related to EE. This seems to be consistent with the distinction I normally draw, so I'm happy with the overall result of the analysis, but you might draw your own conclusions.


Maximum flow properties I was trying to solve problems in max flow algorithms.
And I came across this MIT Lecture Quiz.

http://people.csail.mit.edu/moitra/docs/6854hw4.pdf

solution : http://people.csail.mit.edu/moitra/docs/6854hw4solns.pdf

Questions :

(a) In any maximum flow, and for all vertices v and w, either the amount of flow from v to
w (f(v, w)) or the amount of flow from w to v (f(w, v)) is 0.

(b) Consider a directed graph G = (V, E). There always exists a maximum flow of G such
that, for all vertices v and w, either the amount flow on vw or the amount of flow on wv
is 0.

These two problems look one and the same.
And both are based on the trick of 'Flow conservation on any vertex'.
The main properties of both problems are the same. except that

first problem ---> any flow (all flow)

second problem --> a flow   (at least one flow)

So this made the difference

problem 1 -> False (because any flow on subtraction and add to incoming and out going we can make it non zero. So the statement 'ALL FLOWS' makes this statement false)

problem 2 -> True (because any flow on subtraction and add to incoming and out going we can make it non zero, so whatever be the flow, we can make manipulations such that one is zero and other is non zero. so there is 'A FLOW' with this property. this 'A FLOW' makes this statement true.

Am I right in my understanding of the key difference in both the questions, thought both look almost the same ?

A helpful way to build intuition: Try working through an example!  Can you find an example of a graph and a flow where property (a) is true?  Then, ask yourself: is property (b) true in that one?  What made the difference?

Spoiler (but it's best to try the above first; it will help you learn more from this exercise):

   The crucial difference is between "for every maximum flow" vs "there exists a maximum flow".  That's the difference between $\forall$ vs $\exists$.  As you probably know, $\forall x . P(x)$ can be false even if $\exists x . P(x)$ is true.


A Formula For Generalized Josephus problem There is a formula in wikipedia for the general case of josepus problem

Josephus Problem

But there is no reference for it, I don't know where it came from and I need too find out...
Maybe Donald Knuth's Art of Programming?

In "Concrete Mathematics" by Graham, Knuth, Patashnik. Look in Chapter 3: Integer functions.


Why is heap insert O(logN) instead O(n) when you use an array? I am studying about the arrays vs heap for make a priority queue

For check the heap implementation I am reviewing this code:  Heap

, but I have the following question.

Heap is based on array, and for creating an array you need O(n), for inserting into a heap you need O(logN), so if you have a unordered list of task and you want to create a heap, you need O(NLogN).

If you use an array, you need O(n), to create the array, and O(NlogN) to sort the array, so you need O(NLogN).

So if you need implement some similar to this:

function priorityQueue(listOfTask l)

There isn't a diference betwen use an Array or an Heap right? So, why I should use a heap instead an array for solve this function?

Thanks

Given your link, you seem to be interested in data structures supporting the following operations:

Create(m): create a new instance with room for m elements.
Size(): return the number of elements currently stored in the instance.
Insert(k): insert an element with priority k.
ExtractMax(): return the maximal priority currently stored, and remove it.

Since Size() is easy to implement in constant time as part of the other operations, I will not discuss it below.

Here are three sample implementations:

Unsorted array:

Create() simply allocates memory.
Insert() simply inserts the element at position i+1, where i is the current number of elements.
ExtractMax() goes over the entire array, finding the maximum; and then "compacts" the array by moving all elements to the right of the maximum one entry to the left.

Sorted array: (your implementation)

Create() simply allocates memory.
Insert() first scans the array to find the proper location for the element, then moves all elements to the right of the intended location one entry to the right, and finally stores the element.
ExtractMax() returns and removes the ith element, where i is the number of elements currently in the instance.

Binary heap:

Create() simply allocates memory.
Insert() and ExtractMax() are described on Wikipedia.

Binary heaps are implemented using "partially sorted" arrays. That is, the order of elements in the array is not arbitrary, but it is also not completely determined. Rather, we are only guaranteed that A[i] ≥ A[2i],A[2i+1]. This freedom allows us to trade-off the running time of the two operations Insert() and ExtractMax().

In all of these implementations, Create() is roughly the same, so to compare the various implementations it suffices to consider the two operations Insert() and ExtractMax():

$$
\begin{array}{c|c|c}
\text{Implementation} & \text{Insert()} & \text{ExtractMax()} \\\hline
\text{Unsorted array} & O(1) & O(n) \\
\text{Sorted array} & O(n) & O(1) \\
\text{Binary heap} & O(\log n) & O(\log n)
\end{array}
$$

Here $n$ is the number of elements currently in the array.

If you perform many Insert() and ExtractMax() operations, a binary heap is likely to be more efficient.

Another operation which you mentioned is

Initialize(A): add to an empty instance the elements in A

You can add support to this operation to all different implementations mentioned above:

Unsorted array: simply copy A to the array. Running time: $O(|A|)$.
Sorted array: copy A and sort the resulting array. Running time: $O(|A|\log|A|)$.
Binary heap: run Insert() for each element of A. Running time: $O(|A|\log|A|)$.

Considering this operation doesn't strengthen the case of your implementation.


Find the minimum subset of a set of numbers with product divisible by a given integer The following problem was part of a local programming contest I attended..(I solved it via the obvious Brute Force solution)
I was wondering whether there was a cleaner Dynamic Programming solution.
Problem Statement:
You have an array $a$ of $n$ integers and an integer $k$. Your task is to find a subset $m$ of a where the following 2 conditions hold:
1) $\prod\limits_{x\in m}x \equiv 0\mod k$.
2) Size of $m$ is minimal possible (size of $m \gt 0$).
Constraints:
$1 \le n \le 10^4$
$1 \le a_i \le 10^9$
$2 \le k \le 10^9$
Time Limit = 3 seconds
Memory Limit = 256 MegaBytes
(I am a beginner in the concept of DP, so I am looking for a detailed explanation and if possible. some code.  Thanks in advance :D)

Compute all the prime factors of $k$. It would take $O(\sqrt{k})$ time $\approx$ $10^5$ time. Note that, there could be at most $10$ different prime factors of $k$ since considering the $10$ smallest prime numbers gives the product: $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 \cdot 17 \cdot 19 \cdot 23 \cdot 29$ which exceeds $10^9$. Let us call the prime factors of $k$ as: $f_{1}, \dotsc,f_{10}$ with multiplicities $m_{1}, \dotsc,m_{10}$, respectively. The sum of multiplicities (or total number of prime factors) $\sum_{i = 1}^{10}m_{i}$ could be at most $30$ since $2^{30}$ exceeds $10^{9}$.
Now, you also need to factorize the numbers given in array $a$. However, you do not need to obtain all its factors. You just need to obtain the factors which are among $f_{1},\dotsc,f_{10}$ since other prime factors are irrelevant for $\prod\limits_{x\in m}x \equiv 0\mod k$. Therefore, just check that if an array entry $a[j]$ is divisible by some factors $f_{i}$ (obtained in step 2) and obtain its multiplicity in $a[j]$. Let $m_{i}^{j}$ denote the multiplicity of factor $f_{i}$ for an array entry $a[j]$. Computing all $m_{i}^{j}$ would take at most $\sum_{i = 1}^{10}m_{i} \cdot n = 30 \cdot n$ time $\approx 10^{6}$ time.
Now, you just need a Dynamic Programming approch to obtain the minimum value on size of $m$. Let $A$ denote a matrix of dimension $(m_{1}+1)$x $(m_{2}+1)$ x $\dotsc$x $(m_{10}+1)$ x $n$ such that an entry $A[j_{1}][j_{2}] \dotsc[j_{10}][t]$ denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{t}\}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$. In otherwords, $k'$ is composed of all possible combinations of the factors $f_{1}, \dotsc,f_{10}$. Therefore $k'$ can take at most $(m_{1}+1) \cdot (m_{2}+1) \dotsc (m_{10}+1) \approx 2^{10} \approx 10^{3}$ different values. This bound is based on the assumption that all $10$ factors are distinct. If all the factors are the same the we have $k' \leq 30$ since $2^{30}$ exceeds $10^9$. So I believe $k'$ would take at most $\approx 2 \cdot 2^{10} \approx 2 \cdot 10^3$ different values.

Now, assuming 1 based indexing for the matrix $A$, we define the DP steps as follows.
The Main DP step:
$$
    A[j_{1}][j_{2}]\dotsc[j_{10}][t+1] = \min \left\{\begin{array}{lr}
        A[j_{1}][j_{2}]\dotsc[j_{10}][t], & \textrm{do not pick $a[t+1]$}\\
        1 + A[j_{1}-m_{1}^{t}][j_{2}-m_{2}^{t}]\dotsc[j_{10}-m_{10}^{t}][t], & \textrm{pick $a[t+1]$}\\
        \end{array}\right.
  $$
The Base Step:
$A[j_{1}][j_{2}]\dotsc[j_{10}][1] = 1$ if $j_{i} \leq m_{i}^{1}$ for all $1 \leq i \leq 10$. And $A[j_{1}][j_{2}]\dotsc[j_{10}][1] = \infty$ otherwise. Here $\infty$ means that it is not possible to satisfy the constraint $\prod\limits_{x\in m}x \equiv 0\mod k'$ given $m \subseteq \{a_{1} \}$ and $k' = \prod_{i = 1}^{10} j_{i} \cdot f_{i}$.
The Required Ouput:
The output of the DP procedure would be the solution: $A[m_{1}][m_{2}]\dotsc[m_{10}][n]$ which naturally denote the minimum size value of $m$ such that $\prod\limits_{x\in m}x \equiv 0\mod k'$ for $m \subseteq \{a_{1},\dotsc,a_{n}\}$ and $k' = k = \prod_{i = 1}^{10} m_{i} \cdot f_{i}$.
Running Time Analysis of DP:
The size of the matrix $A$ is $(\textrm{number of possible value of $k'$}) \cdot n \approx 2 \cdot 10^3 \cdot 10^4 \approx 2 \cdot 10^{7}$. Computing each entry takes 2 or 3 operations. Therefore total running time would be $\approx 6 \cdot 10^7$.

Thus the overall running time is $\approx 10^5 + 10^6 + 6 \cdot 10^ 7 \approx 10^8$. I have done the loose analysis, so it should be doable in 3 sec.
Total Space Complexity  $\approx $ size of the matrix $A$ $\approx 2 \cdot 10^7$


Is there a method to compress all data without loss (lossless compression)? I know that the answer is no but I'm not sure why. Here's where I started. We know that all data with length $n$ Bits and minimum $1$ Bit can be compressed, either lossless or lossy. But how do I continue? Why is it impossible to compress all the data without loss?

There are $2^n$ bitstrings of length $n$, but only $2^n-1$ bitstrings of length smaller than $n$. Hence there is no one-to-one mapping which maps every bitstring of length $n$ to a bitstring of strictly smaller length. In other words, for any (lossless) compression scheme there will always be a string which it doesn't compress.


Floating point arithmetic on division I am trying to figure out how $(x/y)$ in floating point arithmetic

$fl(fl(x) / fl(y))$ where $fl(x) = x(1-\delta_1)$, $fl(y) = y(1-\delta_2)$, $fl = (1-\delta_3)$

I have:

$= x/y \cdot ((1-\delta_1)/(1-\delta_2))(1-\delta_3)$

after arithmetic

$= x/y \cdot (\delta_3 \delta_1 - \delta_1 - \delta_3 + 1)/(1-\delta_2)$

Not sure how to fully write the rest I believe i have to shorten them using the info that $\delta < \epsilon$ and $\delta^2 \leq \delta$

I don't know exactly where you're trying to get to with this, but I think you probably want to Taylor expand the division:

$$\frac{1}{1 - \delta_2} = 1 + \delta_2 + \delta_2^2 + \delta_2^3 + \cdots$$

Then, for example, if $\epsilon$ is the machine epsilon and $\delta_2 > 0$:

$$1 + \delta_2 \le \frac{1}{1 - \delta_2} \le 1 + \delta_2 + \epsilon$$

That is quite a tight bound, when you think about it. (Exercise: Prove that this is true if $\delta_2 \le 0$, too.)


What is the runtime of the 'Risch Algorithm'? I have been trying to find the upper bound on the runtime of the 'Risch algorithm' used for finding the integral of mathematical functions, but have been unable to do so.

https://en.wikipedia.org/wiki/Risch_algorithm

Does anyone know where I would be able to find the runtime of the 'Risch Algorithm'?

The Risch algorithm is undecidable by Richardson Theorem if absolute value is allowed or semi-undecidable with $\log_2, \pi, e^x, \sin x$.
Akitoshi Kawamura in his dissertation Computational Complexity in Analysis and Geometry has proved that integration is $\#P{-}complete$ operation.

There are multiple modifications of the Risch algorithm, but still nobody have implemented the full algorithm (source: Wolfram, survey over CAS systems) in algebraic case.


Can an algorithm be truly non-deterministic? I read the term "non-deterministic algorithm" in many places but I don't see how an algorithm can be truly non-deterministic. Typically, there is some source of randomness in these algorithms. If the output of the randomness source is considered an input, the algorithm reduces to a deterministic algorithm. So the only non-deterministic algorithm possible is one that produces truly random numbers with no input or the same input. I have read that this is not possible.

Refer: Can a computer generate a truly random number?

So why are certain algorithms called "non-deterministic algorithms"?

There are two meanings of non-deterministic.
Meaning #1: nondeterministic means the algorithm uses non-determinism, in the sense of a non-deterministic Turing machine: in other words, at each step the algorithm can branch into multiple execution paths, and the algorithm accepts if any of these paths accepts.  Or, equivalently, you can think of the algorithm as being able to make a guess at any point it wants, and a space alien magically guarantees it will always make the right/lucky guess.  Such an algorithm can't actually be implemented in practice (except by simulating it in an inefficient way), so it is more of a thought experiment.
Meaning #2: non-deterministic means "it is not a deterministic algorithm".  For instance, such an algorithm might be randomized.
An algorithm that uses random numbers would be considered non-deterministic in the sense of Meaning #2 but not in the sense of Meaning #1.
Usually when you see the phrase "nondeterminism" in complexity theory or algorithms, it will typically mean the former meaning, but no guarantees.  You might have to infer which was meant from context.
See also Differences and relationships between randomized and nondeterministic algorithms?.


Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$? How to find which of $2^{n}$ to $n^{a}$ is an (upper bound, tight bound asymptotically larger, etc..)? I tried to use the formula:

$$ \lim_{n\to\infty} \frac{f(n)}{g(n)} $$

where $f(n) = n^{a}$ and $f(n) = 2^{n}$

But I cannot figure out how to use L'Hospital's rule to solve it.  We are guaranteed that $a \in \mathbb{N}$.

As a hint, $n^\alpha = 2^{\alpha \log_2 n}$. Now, you can compute the ratio between these functions by subtracting the exponents. There's no need to use l'Hôpital's rule.


An error on Introduction to Algorithms 3rd edition about closest pair of points In the book Introduction to Algorithms of Cormen 3rd edition page 1041 about of Closest Pair of Point divide and conquer algorithm, Is there an error? It's said: "...Create an array Y', which is the array Y with all point not in the 2$\delta$-wide vertical strip removed...", it should be: "...Create an array Y', which is the array Y with all point in the 2$\delta$-wide vertical strip removed..."?

Just the two lines before, (or last two lines of page 1040 if you want) say the following:

Observe that if a pair of points has distance less than $\delta$, both
points of the pair must be within $\delta$ units of line $\lambda$. Thus,
as Figure 33.11(a) shows, they both must reside in the 2$\delta$-wide

Meaning that if you want to be able to combine them after divide and conquer phases, you specifically are going to look within the 2-$\delta$ range. And this is why the first step is to remove all the points that exceed that limitation, therefore that they do not satisfy such constraint.
You want to keep only the points within that window-range.


What is the complexity to show this theorem? Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1).

There is need to show that the sum of all regular expressions is either equal to or not equal to the regular expression, which is n-1 concatenations of (0+1).

I want to know what is the complexity to show this theorem?

Actually it is possible to open up all brackets and parentheses, but this increases number of regular expressions in the sum to some exponential number.

Proof in this way is very long and requires a lot of large papers.

I want to know if there is more easier, efficient and faster way to do this proof?

This is just SAT in disguise. Given a clause, you can encode the set of assignments falsifying the clause as a sum of the type you indicated. The formula is unsatisfiable iff every assignment falsifies some clause, that is, iff the sum of the regular expressions is $(0+1)^{n-1}$.


For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an efficient algorithm which computes the minimal $t$ such that $G(t)=(V,E(t))$ is connected.

I can sort all the edges with $|E|\log|E|$ complexity and try to take edges out of the graph from the heaviest to the easiet one, and to check with DFS if it is still connected, but its not effiecnt enough,

Any suggestions?

Compute a minimum bottleneck spanning tree of the graph. (Actually just compute a minimum spanning tree, as a minimum spanning tree is a minimum bottleneck tree.)
Determine the maximum edge weight from MBST, this will be your $t$.
Remove all edges whose weight is higher.

This can be done in linear time in the sum of the number of nodes and edges (see wiki).


Post numbers in DFS tree of an undirected graph How could you prove:
An edge (u,v) is part of an undirected graph G. If post(u) $<$ post(v) (i.e. the post number of u is smaller than that of v) then it implies that v is an ancestor of u in the DFS tree.

So far I have understood that it does in fact imply that so I need to prove this. I have thought of doing it by contradiction but not exactly sure how I would go about doing that.

You conclusion is correct.

Here is (the sketch of) a proof.

If pre($u$) < pre($v$), the search must discover and finish $v$ before it finishes $u$, since $v$ is on $u$’s adjacency list. That is, post($v$) < post($u$) and $v$ is in the subtree rooted at $u$.
If pre($v$) < pre($u$), the search must discover and finish $u$ before it finishes $v$, since $u$ is on $v$’s adjacency list. That is, post($u$) < post($v$) and $u$ is in the subtree rooted at $v$.


Buchi Automaton G(Xa->b) I have a question regarding buchi automatons. The automata for the LTL formula, G(Xa->b) is as the attached picture. Why dosen't a have to be true in order to make the automaton correct?

My suggestion

Best regards

The formula states that for all $n$, if $a$ holds at time $n+1$ then $b$ holds at time $n$. If $a$ never holds then the formula is trivially true.


Prove the language $\{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$ for regular language $L$ is regular Let $\Sigma=\{0,1\}$ and $L$ be a regular language. Prove that
$$Z(L) = \{x \in \Sigma^* : \exists w \in \Sigma^* \ xww \in L \}$$
is a regular language.

I tried to build a NFA based on the DFA that accepts $L$ but failed to do so. I don't know how to ensure the $\, ww \,$ part. Please advise.

Let $A = (Q, \delta, q_0, F)$ a DFA that accepts $L$. For $q, q' \in Q$, define:

$L_{q,q'} = \{u\in \Sigma^*, \delta^*(q, u) = q'\}$;
$L_{q',F} = \{u\in \Sigma^*, \delta^*(q', u) \in F\}$.

It is quite easy (can you prove it?) to see that those languages are regular.
Now the language $\{x\in \Sigma^*\mid \exists w\in\Sigma^*, xww\in L\}$ can be written as:
$$\bigcup\limits_{q\in Q}L_{q_0,q}\cdot M(q)$$
Where $M(q) = \left\{\begin{array}{rl}\emptyset&\text{if }\bigcup\limits_{q'\in Q}L_{q,q'}\cap L_{q',F}=\emptyset\\\{\varepsilon\}&\text{otherwise}\end{array}\right.$
$M(q)$ is regular since it is either $\emptyset$ or $\{\varepsilon\}$, so that means that $Z(L)$ is regular.


Most Efficient Way to Map Generic Input To Generic Output Lookup tables are one way to map x values to f(x) values.  This lets you do computation in advance, and can give a low cost (performance wise) answer to complex calculations when they are needed in performance intensive applications.

Another method to map x values to f(x) values is to use the chinese remainder theorem to encode values into a (often large) number and use modulus to get the values back out

For instance, if the modulus "lookup table" was the number 27, it could encode the values 2,1,0 by using divisors 5,2,3 respectively:

$\begin{array}{c|c}
\text{Input (x)} & \text{Math} & \text{Output (f(x))} \\
\hline
0 & 27 \% 5 & 2 \\
1 & 27 \% 2 & 1 \\
2 & 27 \% 3 & 0 \\
\end{array}
$

(More info on that technique here: http://blog.demofox.org/2015/11/13/hiding-a-lookup-table-in-a-modulus-operation/)

The modulus method seems like it would always be slower and take more memory than a straight lookup table.

Is there a more efficient mapping of input values to output values than just using a table?

I'm interested mainly in efficiency of computation time to pull a result out of a mapping, but memory efficiency is also interesting, as well as efficiency in creating the object to begin with, if anyone has any interesting info on that.

Thanks!

From an asymptotic perspective: No, there's no more efficient mapping than just using a table.  Lookup in a table is $O(1)$, and you can't beat $O(1)$.

From a practical perspective: The answer will depend upon the exact application domain.  For instance, sometimes using a cache will speed up things (by only a constant factor, but in practice constant factors can help), if the access pattern exhibits some locality.  It's impossible to give a general answer without knowing the specifics of the particular way you plan to use the lookup table.

However, no, you shouldn't expect there to be some clever number theory trick to build a faster lookup table.  Roughly speaking, a lookup table is as fast as you can get; all that remains is some practical optimizations.

Memory efficiency is a different matter, and depends upon the function f.  Sometimes it can be faster to compute f(x) from scratch than to look up x in the table.  Sometimes, if you've previously computed f(x') and if x' is "close" to x, then you can efficiently compute f(x).  It all depends on the function.


Formulas vs Circuits In boolean circuit complexity, a circuit is just defined by a Directed Acyclic Graphs with designated input and output nodes, where the intermediate nodes compute a specific boolean function. A circuit is called a formula if the underlying graph is a tree. i.e., the fan-out of each node is $1$. Is it true that for a formula, (given that its fan-out is already $1$, by defintion) the fan-in is also constant?

In the usual definition of formulas, this is never spelt out(Its always defined as a circuit where all gates have fan-out $1$). But somehow I seem to carry around this intuitively that formulas are always bounded fan-in. (It might be partly due to the fact that poly-sized boolean formulas correspond to $\mathsf{NC^1}$ which is a complexity class defined by bounded fan-in circuits of logarithmic depth).

So my question is, if you bound the fan-out of the circuit to be $1$, does it imply even the fan-in should be constant for every gate? I tried to use a counting argument, that says that the indegree and outdegree of the graphs must sum to the same, but somehow a water tight proof eludes me. First of all, is my intuition correct?

No. Take for example $\mathsf{AC^0}$. It is polynomial-size bounded-depth circuits. Being DAG or tree doesn't change the class. The fan-in can be arbitrarily large.

If the fan-in is bounded we end-up with $\mathsf{NC^0}$ which is much weaker. It cannot compute any function where the output depends on more than a bounded number of inputs as each gate with at least two inputs will decrease the number of usable wires by one and there is no way of increasing them.

Note also that the number of gates (ignoring single input gates like negation) in any circuit with $n$ inputs and with fan-out $1$ is going to be at most $n-1$.


Computing exam averages in less than linear time This is the question:

A spreadsheet keeps track of student scores on all the exams in a course.  Each row of the spreadsheet corresponds to one student, and each column in a row corresponds to his/her score on one of the exams.  There are r students and c exams, so the spreadsheet has r rows and c columns. Devise an algorithm to compute the exam averages for each student and the class average for each exam.

(It's from an ungraded practice problem set, not homework).

It seems fairly straightforward to me to do this in linear time($O(c*r)$), but I suspect there is a faster way to do it. Is there a reasonable way to do this with better O()?

My thoughts: At first I thought I could do this by storing the average values and  updating them, but I don't think this would really satisfy the requirements of the problem: given just the exam scores, getting the averages would take at least  as much time, if not more.

Any help is appreciated! In particular, helpful hints are welcomed, and a helpful hint leading me to the answer will be accepted as an answer.

To compute the exact mean (no confidence interval or estimate) of each exam, you must at least observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this for, this problem should take at least $\Omega(c \cdot r)$ time.


Reducing linear programming to positive linear programming Suppose we have an oracle that solves problems of the form

\begin{align*}
\text{maximize} ~~ & c^T x
\\
\text{subject to} ~~ & A x = b, x\geq 0
\end{align*}

when $c\geq 0$ (all coefficients in the maximization target are non-negative).

Can it be used to efficiently solve general linear programs?

FAILED ATTEMPT #1: replace each variable $x_i$ that appears with a negative coefficient in $c^T x$, with another variable $y_i := - x_i$.
Unfortunately, this $y_i$ does not satisfy the non-negativity constraint.

FAILED ATTEMPT #2: Ensure that all elements in $b$ are non-positive (multiplying the equation by -1 if necessary). Then create the dual LP:

\begin{align*}
\text{maximize} ~~ & - b^T y
\\
\text{subject to} ~~ & A^T y \geq c
\end{align*}

Here, all the coefficients in the objective are non-negative. However, this form does not match the form that the oracle can solve, since the constraints are not equational constraints and the variables $y$ are unbounded.

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system.

Except for the condition $y\geq 0$. That is where $c_0$ comes in. We need to make $c_0$ large enough that for some feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c_0\geq 0$. In that case it does not matter that non-negativity cuts away parts of the feasible space. The optimal value is still the same.

So how to choose $c_0$? I am not an expert in linear optimization. Is finding some feasible $x_0$ easier than finding one that maximizes the objective function? If so, we can take $c_0$ to be $-c^Tx_0$.

If the given coefficients are rationals, there is another way.
First, let us establish that the polytope of feasible $x$ has vertices (unless it is empty):
Let $p$ be a point in a minimum-dimensional boundary cell of said polytope.
For contradiction, assume that the dimension of this cell is $\geq 1$.
Then, there is a different point $q$ in the same cell. As the cell has minimum dimension, it is unbounded, so points of the form $r=p+t(q-p)$ are in the same cell and thus in the polytope. As $q-p\not=0$, some such $r$ have negative coordinates, contradicting the polytope condition $r\geq 0$.

Now, make all coefficients of $A$ and $b$ integer by multiplying with the common denominator. Let $n$ be the dimension (the length of the vector $c$) and let $M$ be the maximum absolute value of any coefficient of $A$, $b$, or $c$. Then we can bound the coordinates of any vertex of the feasible polytope by $n!\cdot M^n$. Thus, choose $c_0:=n\cdot n!\cdot M^{n+1}$.

[EDIT]

Yet another approach, in case you are willing to call the oracle multiple times: First, try the above with $c_0=0$. If you get a solution or the answer "unbounded", you are fine. If the answer is "unsolvable", you need to find out if there are solutions with negative objective function. Hence, set $z=-c^T$ and maximize $z$ instead. If you get a solution, you can use it as $x_0$. If you get "unsolvable" again, you are done as well. The last case is the answer "unbounded". Then, you need to try out ever larger $c_0$ (for few oracle calls, use a fast-growing function; the Ackermann function may do) until you get a solution.


What is the asymptotic runtime of this nested loop? I am trying to analyse the runtime of this algorithm:

for(i=1; i < n; i++){
   for(j=1; j <= i; j++){
         statement1;
   }
}

Expanding the above loop into.

First :

for(j=1; j <= 1; j++){
   statement1;          //complexity O(1)
}

Second:

for(j=1; j <=2 ; j++){
   statement1;          //complexity O(2)
}

...

n-th:

for(j=1; j <= n; j++){
   statement1;          //complexity O(n)
}

So the runtime of the loop should be

$\qquad \displaystyle O(1) + \dots + O(n) = O\Bigl(\frac{n(n+1)}{2}\Bigr) = O(n^2)$.

Can I reason like this, or what is the proper way to analyse nested for-loops?

The result is correct, but your reasoning is not. You can't mix big-oh with ellipses. It happens to work here because of extra conditions that happen to be true but that you haven't checked.

Why summing big-ohs just doesn't work

Fundamentally, you are abusing notation. For example, it doesn't make much sense to write $O(1)$, $O(2)$, $O(3)$, etc. as if they were different things — after all, they all mean “bounded function”.

The definition of big-oh depends on some values that differ from one $O(…)$ to the next. When you write $O(1) + \ldots + O(n)$, the constants could be different in each term of the sum, and if they are, you can't say anything about the sum. $f(n) = O(g(n))$ means that there exists some threshold $N$ and some factor $C$ such that if $n \ge N$ then $f(n) \le C g(n)$. When you have a variable number of big-ohs like $O(f_1) + \ldots + O(f_n)$, each term of the sum has its own threshold and factor. Your reasoning assumes that the threshold and factor are the same, and it's true that in this example you can pick them to be the same, but it isn't true in general.

The first hurdle is what $O(1) + \ldots + O(n)$ actually means. This is a sum whose general term is $O(k)$: $O(1) + \ldots + O(n) = \sum_{k=1}^n O(k)$. The general term of the sum could depend on both $k$ (the index into the sum) and $n$ (the number of terms)! Big-oh is defined in terms of a variable, it describes what happens when that variable approaches infinity. If you consider the general term as a function of $k$, then $O(k)$ means that there exists some threshold $K_n$ and some factor $D_n$ such that if $k \ge K_n$ then $f_k(n) \le D_n k$. If you consider the general term as a function of $n$, then $O(k)$ means that the function is bounded for any given $k$, i.e. that there exists a bound $B$ such that $\forall n, f_k(n) \le B_k$.

To illustrate how the sum can get big under the first interpretation, consider the function
$$ f'_k(n) = 2^n k $$
For any given $n$, $f'_k(n) \le D_n k$ where $D_n = 2^n$ so $f'_k(n) = O(k)$ as a function of $k$. Yet the sum is
$$ \sum_{k=1}^n f'_k(n) = f'_1(n) + \ldots + f'_n(n) = 2^n \cdot 1 + 2^n \cdot 2 \ldots + 2^n \cdot n = 2^n \cdot (1 + 2 + \ldots + n) = 2^n \frac{n(n+1)}{2}$$
which is not $O(n^2).

To illustrate how the sum can get big under the second interpretation, consider the function
$$ f''_k(n) = k^2 $$
The general term $f''_k(n)$ is constant with respect to $n$, so it is $O(k)$ as $n$ goes to infinity (since $k$ is fixed, this is the same as writing $O(1)$). Yet the sum is
$$ \sum_{k=1}^n f''_k(n) = f''_1(n) + \ldots + f''_n(n) =
   1^2 + 2^2 + \ldots + n^2 = \frac{n(n+1)(2n+1)}{6} $$
which is not $O(n^2)$.

What actually works

Here, you have a special case which does make sense. It's not any sum of big-ohs — it's the same function every time:
$$ f(1) + f(2) + \ldots + f(n) = \sum_{k=1}^n f(k) $$
where $f(k) = O(k)$. Now we have a function of a single variable, which makes the analysis simpler. By the definition of big-oh, there is a threshold $N$ and a factor $C$ such that for all $k \ge N$, $f(k) \le C k$. Therefore, if $n \ge N$, then
$$ \sum_{k=1}^n f(k) = \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n f(k)
   \le \sum_{k=1}^{N-1} f(k) + \sum_{k=N}^n C k
   \le \sum_{k=1}^{N-1} f(k) + C \frac{n(n+1) - N(N-1)}{2} $$
This last term is of the form $C n^2 + B n + A$, so it is $O(n^2)$ and thus $\sum_{k=1}^n f(k) = O(n^2)$.

If $f$ is monotonically increasing (which is often but not always the case for complexity bounds), then there is an easier way to prove this:
$$ \sum_{k=1}^n f(k) \le \sum_{k=1}^n f(n) = n f(n) $$
and since $f(n) = O(n)$, the sum is $O(n \cdot n) = O(n^2)$.

Note that we are taking the sum of the values of a function which is $O(n)$. This is crucially different from summing functions, each of which is $O(n)$.

Application to a loop

Consider a loop

for i = 1 to n do
    /*do something*/

If the running time of /*do something*/ does not depend on $n$, then we are in the case that works. For example, take your nested loop:

for i = 1 to n do
    for j = 1 to i do
        statement

Assuming that statement runs in constant time, the run time of the inner loop is $j$ which is $O(j)$. The run time of the outer loop is thus $O(n^2)$. Of course, you don't need to remark that $j = O(j)$ to see this — you could directly remark that $j \le n$ and therefore statement is executed at most $n$ times per run of the inner loop and thus at most $n^2$ times per run of the outer loop.

The general way to analyze the complexity of loops is by summing the complexity of the iterations. You cannot sum big-ohs, you need to write an actual mathematical expression. If the final desired result is a big-oh approximation, then you don't need to write an exact computation: it is enough to find an upper bound for each term and then calculate an upper bound for the sum of the upper bounds.


What is storing an instruction like? Texts on microprocessors use lines like the following ones :

"The instructions in an instruction set of a microprocessors have their own address "

"In the first clock cycle the instruction is fetched from its address and then the operands (variables)

"It was a breakthrough to realize that both the instructions and variables can be stored in the memory "

In all these lines what is meant by "storing an instruction at a particular address " ?

I tried thinking about it and deconstruct it and it was alog the following lines :
In case of an instruction like say ,ADD, when the address bus of the microprocessor assumes the values as in the bits of the address of an instructor , an adder circuit is activated and the values in the next two registers,following the one pointed by program counter ,are transferred to the adder circuit for computation .

I realize that Thinking along these lines result in complicated structures to facilitate a larger set of instructions but that is all I can come up with at present .

Please help me understand what exactly does it mean to store an instruction at an address .
(I hope it's a bit confusing because an instruction by definition is not a number but a process or some action to be followed)

There are many theoretical ways to express an (arbitrarily complex) function in numbers, historically starting with the abstract model known as the Turing Machine. Those aren't always efficient for real problems, and in engineering we've settled on a pretty straightforward model.

Microprocessors (CPU's) have an associated memory which holds instructions. (1)
Instructions are discrete operations, which change the CPU is a well-defined way. There is a finite and numbered set of instructions. Instructions may have operands, such as registers to operate on, or constants to use, and these operands are also encoded as number.

The instruction pointer (or program counter) indicates where exactly in memory the next instruction is stored. It normally increments if an instruction finishes, but a jump or branch instruction can change it in different ways.

As instructions are stored as numbers, they must be decoded when the numbers are retrieved from memory. As you correctly assume, this is non-trivial. The instruction decoder will map an instruction number to a particular bit of hardware to implement the actual instruction.

Let's assume a new CPU design, not compatible with an existing CPU, to keep this simple. As a designer, we know have the freedom to choose which numbers are associated with which instructions. We're still talking CPU's, so a number is a bitstring. We can therefore decide that an instruction is a 32 bit number. We can say that the first bit decides whether the instruction is some type of jump instruction. If so, we send off the number bits to the hardware that changes the instruction pointer. Here we look at the 2nd bit to decide whether it's an unconditional jump. For simplicity, let's assume it is. The third bit may decide whether it's a branch (push IP on stack) or not. Decoding this bit is simple: if set, push. The 4th bit may indicate whether it's an absolute or relative jump. A relative jump would require us to use the arithmetic hardware of the CPU, so for simplicity assume we have an absolute jump. The 5th bit can decide whether to take the destination address from a register, or from an operand. Assuming we use an operand, we see that another number is needed from the instruction stream. This means we issue another read, using the incremented instruction
pointer (operand follows instruction). The fetched operand value becomes the new instruction pointer.

1) It's irrelevant here whether this memory is shared with data, or if it's augmented with caches.


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

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

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

For example:

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

"Understanding" is a human concept ie a term used for human psychology. It may be used with machine learning systems informally. However, being flexible in interpretation of your question & not strictly literal, there is of course an open scientific question/ research program of how these systems actually "work". In ML, one "trains" systems and the systems exhibit the desired "behavior" but some of this relates to an old psychology theory of "behaviorism" where only the observed behavior is seen to be relevant and attributing particular mental states is seen to be something of a problematic/nonobjective ("anthropomorphic") projection by the experimenter.

With that caveat, the current scientific understanding of (deep) neural networks, with lots of related research and active/ongoing, is roughly that they build/ use feature detection. This overlaps with neurobiology theory and knowledge of the visual cortex in mammals. The exact features that are evolved (via "emergence") in the network are somewhat unique to each network, but general trends have been observed also, namely orientation columns (eg esp in "lower levels"). These types of features are also known to arise with sparse coding techniques/ mathematics.

There is a hierarchy of features. Higher level features are built out of lower level features inside the network hierarchy.

So the answer is roughly "yes", the network develops "spatial/ visual concepts" in the form of  features. The networks recognize structural patterns in common across many images of real-world objects. These types of patterns include different/ various orientations, placements, relative spatial relationships, and sometimes more abstract "styles" of images found eg in paintings/even architecture etc.


Can a Minimum Possible Efficiency be proven? Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of $O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have $O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently than $\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform at least $n \log_2 n + o(n \log n)$ comparisons. If we assume that a comparison takes a constant amount of time, that means that the sort must take at least $\Omega(n \log n)$ time.

A radix sort could beat this by discovering more than one bit of information per query.

A similar argument shows that binary search is optimal. You are trying to find a number between $1$ and $n$, which means discovering $\log_2 n$ bits of information. If your query operation returns one bit of information, you need at least $\log_2 n$ queries to find an element.

It's a similar story with space usage. Suppose that you need to store a permutation in memory. By an identical argument, this requires at least $n \log_2 n + o(n \log n)$ bits of storage. Since you need $\log_2 n$ bits to store an integer between $1$ and $n$, you essentially can't do any better than storing $n$ integers.


How would I write an if-statement in continuation passing style without an if-statement? Using continuation passing style, many common language constructs can be written in a simple language with recursion, such as loops (using trampolining), exceptions, generators and even function returns. I have found numerous examples of other language constructs, but all examples I have seen use if-statements directly. Noting the power of CPS, I got curious: Can one write an if-statement in CPS without using an if-statement directly?

The naive attempt would be something along these lines:

if_cps(condition, true_body, false_body, current_continuation)
{
    if(condition) true_body(current_continuation);
    else false_body(current_continuation);
}

but obviously this is a failure, since I used an if-statement directly.

I think you are over-attributing things to CPS.  First, CPS lets you model exceptions, generators, and functional calls, but it doesn't create them.  For example, modeling exceptions with CPS only gives me exception-like behavior in code that is itself in CPS.  I can, of course, use CPS as an implementation mechanism, an intermediate language, for exceptions or generators.  Compare this to a language with first-class continuations, e.g. Scheme's call-with-current-continuation.  With that, I could implement exceptions as a library.

Second, recursion gives you loops, not CPS.  If you had a language which couldn't express recursion nor had built-in loops, CPS transforming would clearly not change this.  You also don't need CPS to express loops as recursion, though it may be useful for things like break and continue.

To address your specific question, in some sense if is part of the definition of booleans.  If you want to do anything non-trivial with a boolean, you must at some point use if.  You could choose a different, non-abstract representation of booleans via their Church encoding, but converting the "native" booleans to this representation would require if, and at any rate this would just be word play.  While our if-cps would not require using if in this representation, this would only be because if is represented by the identity function in this representation.  Or to put it another way, we are using this representation's if.


Minimum hamming distance of multiple binary words Our task is to compute the minimum hamming distance for the following 16-bit words:

0000000000000000
0011001100110011
0101010101010101
0000111111110000
0011111111000000
1100110000000000
1111111111111111

This minimum distance is defined as the minimum of all distances between every combination of two of these bitstrings, so the first approach would be to calculate all of these individual distances. I'm pretty sure this is not the right way to do it, since there are 21 possible combinations.

Then I came across this answer on StackOverflow which says that:

  We have a theorem that d_min=weight(sum(all codes)); weight is the
  number of non zeros in the result string . In your example modulo add
  all string codes like first column of all and second....... then we
  get code as [ 0 0 1 1 0 ], weight of this is 2 ( no. of non zeros),
  i.e the minimum distance of hamming code

but is that really true? If we for example take the three bitstrings

0000
1000
1110

the minimum hamming distance is obviously 1 but the calculation based on that answer would result in 0110 and would suggest that the minimum distance is 2. Am I right about this and is that answer wrong? Or did I miss something really simple that I'm just not noticing?

I also read this answer which - if I understood it correctly - states that there is no simple way of finding the result.

You are correct.

Here's what's going on.  There are two subtly different questions here.  The Stack Overflow question is asking: "given a set of bitvectors that form a Hamming code, how do I find the minimum distance?".  In contrast, it sounds like you might be asking "given an arbitrary set of bitvectors, how do I find the minimum distance?".  Those aren't the same question.  Unsurprisingly, they have two different answers.

The answer on Stack Overflow you're referring to isn't 100% clear, but I suspect it is making the following claim: if you have a set of bitvectors that form a Hamming code, then the minimum distance can be obtained by computing the Hamming weight of the xor of all the bitvectors.  I don't know whether that claim is true, but let's suppose it is.  That still doesn't help you with (what I think is) your question, because in your problem you have an arbitrary set of bitvectors -- they might not form a Hamming code.

It is easy to find counterexamples to demonstrate that the claim doesn't hold in general, for an arbitrary set of bitvectors.  For instance, your example is a perfectly good disproof of that.

There are techniques for finding the minimum distance of a set of arbitrary bitvectors (at least, there are heuristics), but hopefully this is enough to answer the question you asked.


How to determine if prolog query will give an answer or not? Explain what will happen if we try to evaluate the query “path(a,e).”. When the query was actually run, it kept looping.I used the following method. Is it correct?

When evaluating $path(Z,e)$, if $path(Z,e):-edge(Z,e)$ was chosen, it would have returned true since there is $edge(b,e)$. But why did the program choose the recursive rule? Or am I missing something here?

Another similar question was evaluated the same way,

The order of clauses matters in Prolog: they are tried in order. So, the first clause is always tried first, and the second one would only be considered after the first clause fails. As you discovered, this never happens because the first gets stuck in a loop.

If Prolog used a breadth-first resolution algorithm, the clause order would not matter (but it would be far more consuming in terms of memory). Since instead SLD resolution is depth-first, the order does matter because of infinite paths which can lead to non-termination.


Finding $L^*$ when $L=\{a^nb^n | n \geq 1\}$ Let $L=\{a^nb^n | n \ge 1\}$, then $L^\star=L^0 \cup L^1 \cup L^2 \cup L^3 \cup \dots = \{\epsilon\} \cup \{a^nb^n\} \cup L^2 \cup L^3 \cup \cdots$ .

How to find $L^2$ and $L^3$, and is $L^2=\{a^nb^na^nb^n\}$? In this video https://youtu.be/rnGpW6RRAcw at 31:51, the professor said that $L^2 = \{a^{n_1}b^{n_1}a^{n_2}b^{n_2}\}$, how did she find this form.

$L^2 = LL = \{uv | u,v\in L\}$. In words, $L^2$ is a set of all strings that formed by concatenation of all strings from $L$. For instance, if $u=a^kb^k \in L$ and $v=a^tb^t \in L$ then $uv = a^kb^ka^tb^t$. That's why $L^2 =\{ a^{n_1}b^{n_1}a^{n_2}b^{n_2}\}$ for all $n_1, n_2 \geq 1$.
Similarly $L^3, L^4,\dots$

Example with a finite set: $L=\{ab, cd\}$. Then $L^2 = \{abab, abcd, cdab, cdcd\}$.


Selection Sort vs Insertion Sort For Reversed Array I had a question in a test, which asked me the following question:

  Selection sort runs faster than Insertion sort for an array in reverse order.

Now, according to my knowledge, both of them have a time complexity of $O(n^2)$ in case of this particular input arrangement, so comparing the running time of them is not possible because it becomes a question of how the algorithms are implemented. A poorly written selection sort could be much slower than insertion sort and vice versa, so an argument can be made for both cases.

But the answer key says that since selection sort has lesser number of swaps (order of $n$) compared to insertion sort (quadratic comparisons), selection sort should be faster than insertion sort for this particular case.

Which is the correct solution? Can selection sort be faster under certain assumptions?

This is an awful question for a test.

Selection sort always has about n^2/2 comparisons and n swaps. Insertion sort has between n and n^2/2 comparisons and the same number of swaps. But as you said absolutely correctly, the actual time depends on the exact implementation.

For example if you look for the smallest element in selection sort like this:

smallest = a[k]
smallestIndex = k
for k+1 ≤ j ≤ n
    if a[j] < smallest
        smallest = a[j]
        smallestIndex = j

you see that that the code in the if-statement will be executed with every execution of the loop.

On the other hand, in the insertion code the moving can be done with some highly optimised code.

So I wouldn't be at all surprised if insertion sort were faster on some particular implementation even in this situation, even though it is the worst case for insertion sort. (I would also not be surprised if selection sort were faster).


Algorithm to find a minimal regular language containing given context-free language I am not sure that the problem is in general solvable, but here's an example of what I mean:

Any context-free language has a trivial regular language that contains it: $\Sigma^*$.
The language $L_1=\{a^nb^n\;|\;n\geq 0\}$ is contained in $L_2=\{a^nb^m\;|\;n,m\geq 0\}$, which is obviously a subset of $\Sigma^*$.

Questions

Is there a way to prove $L_2$ is the "smallest"* language which contains $L_1$?
Is there an algorithm for finding such language pairs given the context-free one?

"smallest" means that there is no other language which also satisfies the requirement and is its proper subset.

PS
Sorry, I now realized that I cannot actually find the minimal language with the requirement given above, for example: $L_3=\{ab, aabb\} \cup \{a^nb^m\;|\; n,m \geq 2\}$ would be smaller than $L_2$, and one could continue constructing languages like that ad infinitum.  So, maybe an alternative definition for "smaller" could be "having least states"?
I'm sorry for indecisiveness.  Please feel free to put this on hold until I figure out the good requirement.  Or suggest one yourself, if you feel like there may be an interesting one.

There is no "smallest" regular language containing any non-regular langauge.

First, note that every finite language is regular, so any non-regular language $L$ must be infinite.  Consider some regular language $R\supset L$. $R\setminus L$ must also be infinite since, if it were finite, then $L = R\setminus (R\setminus L)$ would be regular, because regular languages are closed under difference. So, in particular, we can take any finite $S\subset R\setminus L$ and the langauge $R\setminus S$ is regular, is a strict subset of $R$ and a strict superset of $L$.

In other words, whenever you have a non-regular $L$ and a regular $R$ such that $L\subset R$, there is another regular $R'$ such that $L\subset R'\subset R$ (and, in fact, infinitely many of them).


categories of registers and and storage in them The Wikipedia article on processor registers mentions:

  Address registers hold addresses and are used by instructions that indirectly access primary memory.

Which addresses does this sentence refer to?

RAM addresses or addresses of I/O devices. For example, in x86 architecture an IP (instruction pointer) register holds the memory address of the next instruction that is going to be read and executed. This register cannot be accessed directly (it can be modified by jumps though). Also, in x86 an SP (stack pointer) register shows the top of the stack structure (mostly used to hold local variables of functions) and is implicitly modified by push, pop, call, ret instructions (and interrupts). Of course, there are more examples.


Why can PDAs have infinite stack but FSMs cannot have infinite state? A Finite State Machine cannot accept the language
$$L = \{ 0^n1^n \mid n > 0  \} $$
because it will require infinite amount of memory to remember the number of zeros. But a Push Down Automaton can recognize it with an infinite stack.
Why are we allowing infinite storage for the stack of PDA but not for the states of an FSM? If we can do with an infinite stack, we can also do it with an infinite FSM. So, why is there no "Infinite State Machine"? What's the problem with it?

One of the crucial properties of a model of computation is that each automaton has a finite description. Both FSMs and PDAs have finite description. In contrast, an "infinite state machine" won't necessarily have a finite description, unless it is constrained somehow.
Also, as mentioned in the comments, an unconstrained infinite state machine can accept any language. Indeed, we can construct a machine whose states are $\Sigma^*$. We define the transition function so that after reading the word $w$, the machine is at state $w$. Thus, by choosing the accepting states, we can obtain any language, making the model uninteresting.


Fastest way to search a word in a word list? I have a word list like "English Open Word List" used to create word games.
The list is in txt file with space between words, like;
aa
aah
aahed
.........and so on.
I want to search it while typing the letters in the word, like google suggestions in the search bar.
What is the fastest algorithm to do it? In any language?

Trie might help, it stores your "word list" like this:

              a
             / \
           [a]   a
           /      \
         [a]       h
                    \
                     e
                      \
                      [d]

And you can query by some operation like trie['a']['a']['h']['e'], which is just array index operation. It takes large memory but it's very efficient. The complexity of the query operation is $ O(n) $, n is the length of the queried string.


Does there always exist a reduction between two NP-hard problems? Let $A$ and $B$ be NP-hard problems. For all tuples $(A, B)$ does there exist a polynomial time reduction from $A$ to $B$ and from $B$ to $A$?

Context: I want to prove some problem is NP-hard. Can I pick any problem in NP-hard to reduce from?

A decision problem $L$ is NP-hard when for every problem $H$ in NP, there is a polynomial-time reduction from $H$ to $L$. This is important because it does not necessarily go the other way, you can not say there is a polynomial time reduction from $L$ to $H$. This is because a problem can be NP-Hard and not be in NP. If $A$ and $B$ in your question are both not in NP then there may not be a reduction.


time complexity of erasing repeated entries This problem involves the time complexity of erasing entries that occur more than once in a list. I think it might be  $n \log n$.
Problem
The input is a   finite set $S$   and a  finite list $T$ whose entries are in $S$.   The size of the input is  $n= |S|+ |T|$, where $|T|$ is the length of the list.  The output is a list of the elements of $S$ that occur in the list $T$, an output  list having  no repeated elements of $S$.  Does there exist a linear-time, $n p(\log n)$, where $p$ is a polynomial, or subquadratic-time algorithm for this problem?
I would be grateful for any ideas, direction, pseudo-code.

The basic algorithm is to first put all the members of S into a hash table $\mathcal{S}$.  Then walk down the list T, recording its elements in a hash table $\mathcal{T}$ as you go.  If an element has already been recorded in hash table $\mathcal{T}$ then you delete it from T.  If an element does not appear in hash table $\mathcal{S}$ then you delete it from T.  When you've completed your walk down T, there will be no repeated elements left in it and every remaining element will be a member of S.

Hash table insertions and lookups have amortized O(1) runtime so the whole algorithm scales O(n).


FA for when length of $w$ is $4$ or $w$ contains the substring $01$ I have been trying to create an FA for the language.
$\{w \in \{0, 1\}^∗ , |w|= 4 \vee w \text{ contains the substring }01\}$
I created one that accepts words that contain the substring $01$, but I have a hard time finding a solution for the length part.
This is my attempt so far:

Any help is greatly appreciated.

The easiest way to construct a deterministic automaton for such a language is to use the product construction:

Construct an automaton for all words of length $4$.
Construct an automaton for all words containing the substring $01$.
Use the product construction to construct an automaton for the union.

If you are allowed to use a nondeterministic automaton, then you can replace the product automaton with a "union automaton", that is, add a new initial state and connect to the the initial states of the two automata with $\epsilon$ transitions.


What's wrong with this LL(1) grammar? I am trying to build a LL(1) parse table for the following grammar:

S -> L
L -> L : L
L -> id R
R -> ( L )
R -> ( )
R -> Epsilon

There are two problems here. First, the L rules are a left recursion and the R rules have ( as the same prefix.

So I modified the Grammar to this one:

S -> L
L -> id R X
X -> : L X
X -> Epsilon
R -> ( P
R -> Epsilon
P -> L )
P -> )

I then checked the grammar with the JFLAP Tool and it says that my grammar is not LL(1). But I just don't see the problem.

Can somebody help me out here?

Your original grammar is ambiguous:

L → L : L
L → id R

Suppose we have id : id : id. (For simplicity, I'm just letting R derive the empty string, but any valid derivation of the Rs would end up with the same ambiguity.) That needs to be derived from S → L → L1 : L2, but from there, either L1 or L2 can derive L : L. In effect, the two cases correspond to : associating to the left or associating to the right, but with longer sequences of :-separated id R clauses, the number of possible parses increases exponentially.

Your rewrite does not eliminate this ambiguity, it just makes it harder to see.

In short, you need to decide how : associates. It probably makes most sense for it to associate to the left, but an LL grammar really only handles right-association. (That's not a huge problem since you can reassociate the AST easily enough, but with an LR parser generator you wouldn't have to do any of this.) If we rewrite L as right-associative, we automatically eliminate the left-recursion problem:

S  → L
L  → L'
L  → L' : L
L' → id R

(Really, L' is not very useful in this case; it would have been almost as simple to write L → id R | id R L. But in either case, you end up needing to factor out the common prefix.)


When generating a PDA from a CFG do I have a receiving state? Thw Wikipedia article on Pushdown automata doesn't explain what the receiving state is for the generated PDA it just states that there is but one state.

Assuming that you mean accept state when you say receiving state, the construction given in the wikipedia article has one accept state, being the only state in the machine. It accepts when you reach the end of the input with an empty stack. However, the construction used there requires a slight abuse of notation, as you need the starting symbol from the grammar to be pushed to begin with, and you have to be able to push more than one symbol at a time. This isn't so bad, but a more detailed construction makes the conversion more obvious.

The basic approach is to simulate the CFG using the PDA, informally it reads symbols off the stack, if it's a nonterminal, it replaces it with its production, if it's a terminal, it matches it off the input. The input alphabet for the PDA is the same as the CFG, the stack alphabet is the input alphabet plus the set of nonterminals in the CFG and the end of stack symbol.

The basic backbone of the PDA is:

Where $\$$ is the special end of stack symbol, and $S$ is the start symbol of the grammar.

The "production rules" transition represents a bunch of loops that simulate each production of the grammar. Given a production $X \rightarrow \chi_{1}\ldots\chi_{n}$ where the $\chi_{i}$'s are either terminals or nonterminals, we add a loop starting and ending at $q_{3}$ that looks like:

Note that I've opened the loop, and the first and last state are the same.

The last past is the "terminal rules" loop, which represent a bunch of loops (one for each terminal symbol), that match terminals pushed onto the stack by the productions to terminals in the input:

So hopefully you can see how the simulation works, the PDA literally walks through the steps of the CFG, sticking terminals and nonterminals on the stack, replacing nonterminals with their productions, and matching terminals off the input. Then it can only reach the accept state if you can match the entire input (and hence there must be some series of grammar rules that get you there).


Not understand exchanging argument proof for optimal prefix code I am currently reading the Algorithm Design textbook by Kleinberg and Tardos and I am having difficulty understanding a proof using an exchange argument

Statement: A binary tree corresponding to the optimal prefix code is full

Proof: This is easy to prove using an exchange argument. Let $T$ denote the binary tree corresponding to the optimal prefix code, and suppose it contains
a node $u$ with exactly one child $v$. Now convert $T$ into a tree $T′$ by replacing node $u$ with $v$.
To be precise, we need to distinguish two cases. If $u$ was the root of the tree, we simply delete node $u$ and use $v$ as the root. If $u$ is not the root, let $w$ be the parent of $u$ in T. Now we delete node $u$ and make $v$ be a child of $w$ in place of $u$. This change decreases the number of bits needed to encode any leaf in the subtree rooted at node $u$, and it does not affect other leaves. So the prefix code corresponding to $T′$ has a smaller average number of bits per letter than the prefix code for $T$, contradicting the optimality of $T$.

Number of things I do not understand.

1) I thought in an exchange argument, you assume you have a solution T and an optimal solution $T^{*}$ and you prove that your solution T is no worse than $T^{*}$ implying T is an optimal solution, but they're not doing that here.

2)  They also state that they will "convert $T$ into a tree $T'$ by replacing node $u$ with $v$" but they don't assume that $T'$ is an optimal solution. Why?

3) How does contradicting optimality of $T$ prove that "A binary tree corresponding to the optimal prefix code is full"?

What Kleinberg and Tardos show is that given a tree $T$ containing a node with a single child, they can come up with a strictly better tree $T'$, showing that $T$ isn't optimal. Therefore an optimal tree cannot have a node with a single child. Whether this qualifies as an exchange argument or not is not so important.

More generally, the form of the argument is "if X doesn't satisfy P then X is not optimal; hence any optimal X satisfies P". In order to show that X not satisfying P cannot be optimal, they modify X to obtain a better X'. This is a common enough pattern which doesn't usually have a name attached to it.


Present syntax rules in a more succinct way I am resuming syntax rules for a small language:

\begin{eqnarray*}
e_C &::=& \epsilon \mid constant \\
\textit{prefix-op} &::=& - \\
\textit{infix-op} &::=& + \mid - \mid * \\
e_E &::=& e_C \mid \textit{prefix-op} \; e_E \mid e_E \; \textit{infix-op} \; e_E \mid \textit{function}_E (e_{E,0}, e_{E,1},\ldots) \mid \textit{specialE} \\
e_V &::=& e_C \mid \textit{prefix-op} \; e_V \mid e_V \; \textit{infix-op} \; e_V \mid \textit{function}_V (e_{V,0}, e_{V,1}, \ldots) \mid \textit{specialV}
\end{eqnarray*}

The expressions $e_E$ and $e_V$ have something common: $e_C$. Some of their operators look same: $\textit{prefix-op}$ and  $\textit{infix-op}$. Their functions $\textit{function}_E$ and $\textit{function}_V$ are 2 different sets, and $\textit{specialE}$ and $\textit{specialV}$ are totally different.

I am wondering if it is still possible to present this syntax more succinct, more compact in a conventional way... Could anyone help?

One direct way of solving this problem is to make the syntax rules parameterised, as follows:

\begin{eqnarray*}
e_{X,Y} &::=& e_C \mid \textit{prefix-op} \; e_{X,Y} \mid e_{X,Y} \; \textit{infix-op} \; e_{X,Y} \mid Y (e_{X,Y}, e_{X,Y},\ldots) \mid X \\
\end{eqnarray*}

And then to set
\begin{eqnarray*}
e_E &::=& E_{\mathit{specialE},~\mathit{function}_E} \\
e_V &::=& E_{\mathit{specialV},~\mathit{function}_V} \\
\end{eqnarray*}

This is using notation I just invented, and it could probably be reworked, but you get the idea, I hope.


What is the use case for multi-type-parameter generics? In C#, one can define a class/method/function with multiple type parameters. For example,

// function
void foo<T1, T2>(T1 x, T2 y) { /*body*/}

// class
class Bar<T1, T2> { /*body*/ }

I understand how to use it, but I don't understand why I need it. So I'm hoping someone can answer the following questions:

1) What is the use case for multiple type parameters?

2) Based on the use case given in Question 1, what are the alternative solutions for that use case if multiple type parameters is not a feature of the language in use?

Some use cases for multiple type arguments include

maps/dictionaries Map<K,V>, where you have one key parameter and one value parameter
product types Pair<A,B>
sum types, AKA variants Variant<A,B>, which represent a value which might be either of type A or of type B
Function-like types Func<A,B> representing a function from A to B
"Visitor" objects for parametric types. I.e. a visitor for List<A> is ListVisitor<A,R> where R is the return type of the visitor.

If we did not have multiple type arguments, or any other way to emulate multiple argument types (e.g. nested parametric classes class T<A> { class U<B> { ... which are a sort-of curried version of the two-arguments class), we could not express the examples above in a generic way.

Of course, a programming language could disallow generic classes and still have a specific primitive type for some of the examples above. For instance, Func<A,B> could be a primitive type, instead of a user/library-defined class type.


How to efficiently determine whether a given ladder is valid? At my local squash club, there is a ladder which works as follows.

At the beginning of the season we construct a table with the name of each
member of the club on a separate line.
We then write the number
of games won and the number of games played next to each name (in the form: player wins/games).

Thus at the beginning of the season the table looks like this:

Carol 0/0
Billy 0/0
Alice 0/0
Daffyd 0/0

Any two players may play a match, with one player winning. If the player nearest the bottom of the table wins, then the position of the players is switched. We then repeat step 2., updating the number of wins and games next to each player. For example, if Alice beats Billy, we have

Carol 0/0
Alice 1/1
Billy 0/1
Daffyd 0/0

These matches go on throughout the season and eventually result in players being listed in approximate strength order.

Unfortunately, the updating happens in a rather haphazard way, so mistakes are made. Below are some examples of invalid tables, that is, tables which could not be produced by correctly following the above steps for some starting order (we have forgotten the order we used at the beginning of the season) and sequence of matches and results:

Alice 0/1
Billy 1/1
Carol 0/1
Daffyd 0/0

Alice 2/3
Billy 0/1
Carol 0/0
Daffyd 0/0

Alice 1/1
Billy 0/2
Carol 2/2
Daffyd 0/1

Given a table, how can we efficiently determine whether it is valid? We could start by noting the following:

The order of the names doesn't matter, since we have forgotten the original starting order.
The total number of wins should be half the sum of the number of games played. (This shows that the first example above is invalid.)
Suppose the table is valid. Then there is a multigraph - a graph admitting multiple edges but no loops - with each vertex corresponding to a player and each edge to a match played. Then the total number of games played by each player corresponds to the degree of the player's vertex in the multigraph. So if there's no multigraph with the appropriate vertex degrees, then the table must be invalid. For example, there is no multigraph with one vertex of degree one and one of degree three, so the second example is invalid. [We can efficiently check for the existence of such a multigraph.]

So we have two checks we can apply to start off with, but this still allows invalid tables, such as the third example. To see that this table is invalid, we can work backwards, exhausting all possible ways the table could have arisen.

I was wondering whether anyone can think of a polynomial time (in the number of players and the number of games) algorithm solving this decision problem?

This is not a complete answer.
I give a simpler statement of the problem
and some remarks.
We start with a graph where vertices are labeled with $[n]$.
We have an operation that adds a directed edge from $v$ to $u$ to the graph,
and if $label(v)<label(u)$ switches their labels.
Given a directed multi-graph $G$ with $n$ vertices and $e$ edges,
check if it can be obtained using using the operation above.
It is easy to see that the problem is in $\mathsf{NP}$:
a certificate is a (polynomial size) sequence of operations resulting in the $G$.
Observation
It seems that we can assume without loss of generality that
all edges to the last vertex are added at the end of the sequence and
all edges from it are added at the start of the sequence.
This can be generalized to other vertices.
Assume that we have remove all vertices with labels larger than $label(v)$.
All edges to $v$ are added at the end of the sequence and
all edges from $v$ are added at the start of the sequence.
I think it should be possible to combined this observation with Havel-Hakimi to give a polynomial time algorithm.


Denotational semantics of expressions with side effects I'm doing revision for a module on programming language semantics and
I'm having trouble understanding the introduction of side-effects in
expressions.

We assume a standard syntax for arithmetic expression, with the four
usual operations, plus the unary prefix and postfix operator
$\texttt{++}$, defined as in language C, applicable to variables only
as in $\texttt{V++}$, and assigment statement $\texttt{V:=E}$.

We have seen how to define the denotation function
$[\![\texttt{E}]\!]_{\mathrm{Exp}}$ when we have to evaluate an
expression $\texttt{E}$ without side-effect, to return a value
resulting from that evaluation.

In order to give a denotational semantics for expressions with side-effects, we need to change the type of the denotation function $[\![\texttt{E}]\!]_{\mathrm{Exp}}$ for expressions $\texttt{E}$, so that it returns both the value of the expression and the state as modified by the side-effects. I.e., we want to define a denotation function

$[\![\texttt{E}]\!]_{\mathrm{Exp}} : State → Int×State$

by induction on the form of expressions $\texttt{E}$. For example, in the case $\texttt{E}$ has the form $\texttt{E1+E2}$, we define:

$[\![\texttt{E1+E2}]\!]_{\mathrm{Exp}}(S) = (n_1 + n_2, S_2)$

where $(n_1, S_1) = [\![\texttt{E1}]\!]_{\mathrm{Exp}}(S)$

and $(n_2, S_2) = [\![\texttt{E2}]\!]_{\mathrm{Exp}}(S_1)$

This says first evaluate the leftmost expression $\texttt{E1}$, giving the integer value $n_1$ and updated state $S_1$, then evaluate $\texttt{E2}$ in that updated state, giving the integer value $n_2$ and updated state $S_2$; the value of the expression is $n_1 + n_2$, and evaluation has the side effect of updating the state to $S_2$.

However this does not show when side effects actually take place, and I do not know how to write the denotation function for expressions that do produce side-effects. Can you tell me how to complete the inductive definition of $[\![\texttt{E}]\!]_{\mathrm{Exp}}$, including the case where $\texttt{E}$ is of the form  $\texttt{V++}$?

Then, how should one change
 the definition of
 the denotation function $[\![\texttt{V:=E}]\!]_{\mathrm{Pgm}}$ for the assignment statement, to take account of the changes in the definition of $[\![\texttt{E}]\!]_{\mathrm{Exp}}$, which it necessarily uses?

Are there other changes that would need to be made to the denotational semantics of the language?

Since the question does not fully describe the language, I assume the simpler case when
 the $\texttt{++}$ operator applies only to variables given by an identifier, for
 example: $\texttt{foo++}$.  Short of having more examples of the way you write denotational semantic, I
 have to improvise a bit. In particular, I avoid lambda notation since I do not know whether
 you are using it, but I would prefer using it.

Other arithmetic binary operators (substraction, multiplication) are
similar to the $\texttt{E1+E2}$ case described in the question, and are explained similarly.

The simplest case is that of an expression which is only a lone variable $\texttt V$:

$[\![\texttt{V}]\!]_\mathrm{Exp}(S)=  (S(\texttt V), S)$

What it says is to get the value $S(\texttt V)$ associated to the variable $\texttt V$ in the state $S$ and to return that value, of course, but associated with the state $S$ unchanged, since the type of the denotation function requires such a pair as result.

Then we complement as follow for the prefix and postfix $\texttt{++}$ operator the
definition of the semantic function $Exp$ for expression $\texttt E$, when $\texttt E$ has
the form $\texttt{V++}$ or $\texttt{++V}$, i.e., when it is a variable.

$[\![\texttt{V++}]\!]_\mathrm{Exp}(S)=  (S(\texttt V), S1)$
  where $S1(v_1)=\;\; \text{ if } v_1=\texttt V \;\text{ then } S(\texttt V)+1 \;\text{ else } S(v1)$

The value returned is the same as in the case of the variable $\texttt
V$ alone. However, the state $S$ has to be changed to a new state $S1$
where the value corresponding to $\texttt V$ is incremented by $1$,
the rest of the state being unchanged.

$[\![\texttt{++V}]\!]_\mathrm{Exp}(S)=  (S(\texttt V)+1, S1)$
  where $S1(v_1)=\;\;\text{ if }v_1=\texttt V \;\text{ then }S(\texttt V)+1\;\text{ else }S(v_1)$

This case is identical to the previous one, except for the fact that
the value returned is also incremented by one, i.e. is the value
provided by the state $S$ for  $\texttt V$, but incremented by $1$.
But the state $S1$ returned is the same as in the previous case.

For the assignment statement, it would be easier if the question included the definition of $[\![\texttt{V:=E}]\!]_\mathrm{Pgm}$ that is
supposed to be modified. I am guessing, trying to be in accordance with what little information you give.

I suppose the result should be something like:

$\mathrm{[\![\texttt P]\!]_{Pgm} : State \to State}$

$[\![\texttt{V:=E}]\!]_\mathrm{Pgm}(S)= S2$
   where $S2(v_1)=\;\; \text{ if } v_1=\texttt V \;\text{ then } n \;\text{ else } S1(v_1)$
   and $(n,S1)= [\![\texttt E]\!]_\mathrm{Exp}(S)$

What this says in the first line is that the denotation of a statement
is a function that takes a state as argument, and returns another
state. The role of a statement is to modify the state.

Then the denotation function for the assignment statement
$\texttt{V:=E}$ will first evaluate the expression $\texttt E$ in the
environment $S$ provided as argument. This returns a value $n$ and a
new environment $S1$ which may be different from $S$ if there have
been side-effects while evaluating $\texttt E$. Then this environment
$S1$ is modified into an environment $S2$ which associate the value
$n$ to the variable $\texttt V$, and is otherwise identical to $S1$.
This environment $S2$ is the one produced by execution of the
assignment statement.

Other changes are probably necessary to fully account for side-effects
in the language. But I cannot know exactly what because the question
does not provide enough details about other language features.
There are many ways to write denotational semantics, and it depends on the whole of the language and the way features interact.

The version given above is a bit simplified, assuming that $\texttt V$
is the actual variable name. I chose this simpler version because you
do not provide examples of denotational semantics without
side-effects, and I was not sure what presentation to choose. But
there are other ways to present that.


Minimization of amount in the change coins problem using the dynamic programing approach I'm learning the dynamic programming approach to solve the coins change problem, I don't understand the substitution part

Given: amount=9, coins = [6,5,1],

the instructor simplified it with this function:

minCoins = min {(9-6)+1 , (9-5)+1, (9-1) +1} = min{4, 5, 9} = 4

I don't understand the logic of this min method: why we say that to change amount of 9 coins, we can simply, take the minimum of: 9  - {all coins} +1 ?

here's a Gif that visualizes the instructor's approach: https://i.stack.imgur.com/Zx2cG.gif

(*taken from the Algorithmic Toolbox course/ instructor: Prof. Pavel A. Pevzner)

Your formula is wrong (I would like to see where exactly this formula appears in the course, it is not in the gif you linked).

The correct formula is the following:
Let $n$ be your amount. Let minCoins be an array of $n+1$ elements indexed from $0$ to $n$, where minCoins$[i]$ is the minimum amount of coins needed to give change for the amount $i$. Let $c_1, \dots, c_k$ be the denominations of coins you have available.

Then minCoins$[0]=0$ and, for $i>0$:
$
\text{minCoins}[i] = \min_{\substack{j=1,\dots,k\\c_j \le i}} \{1 + \text{minCoins}[i-c_j] \}.
$

In your specific example:

$$
\begin{align*}
\text{minCoins}[9] &= \min \{\text{minCoins}[9-6]+1 , \text{minCoins}[9-5]+1, \text{minCoins}[9-1] +1\} \\
&= \min \{\text{minCoins}[3]+1 , \text{minCoins}[4]+1, \text{minCoins}[8] +1\} \\
&= \min\{ 3+1, 4+1, 3+1\} \\
&=  \min\{ 4, 5, 4\} = 4.
\end{align*}
$$


Why is $O(|V| + |E|)$ the bound on DFS and BFS instead of just $O(|E|)$? In one sense I understand why the bound on BFS and DFS is $O(|V| + |E|)$. Every vertex gets considered, hence the $O(|V|)$, and over the course of considering all adjacent vertices, we end up considering $2|E| = O(|E|)$ vertices total because $\sum_{v \in V} d_v = 2|E|$. What I don't understand is why we even bother specifying $O(|V| + |E|)$ in the first place because it seems to me that the tightest bound you can really have in any situation is $O(|E|)$. I.e., it seems to me that the $O(|V|)$ doesn't help you at all. To see why, consider two cases:

The graph is connected. Then of course $|E| \ge |V - 1|$.
The graph isn't connected. Then you are "stuck" in the connected component you start in. Once again, inside the connected component $A$ you start in you have $|E_A| \ge |V_A - 1|$. Maybe there are more edges and vertices elsewhere. But once again the $O(|V|)$ seems redundant.

Another way I think about it: Adding a vertex alone doesn't create any more work since the vertex will just be floating in space. Adding edges can create extra work.

So why/when is the $O(|V|)$ useful?

You have missed an important element of graph search: the outer loop.

Here is typical pseudocode for a graph search algorithm:

S <- new empty set
T <- new empty set
for each vertex u in V:
    add u to T
    while T is not empty:
        v <- remove some element from T
        add v to S
        do something with v
        for each vertex w that is adjacent to v:
            if w is not in S and not in T:
                add w to T

Notice the outer loop on the variable u. This loop is present in some descriptions of DFS/BFS/etc. and absent in others. Why is this? The answer is that graph searches are used for different purposes. Sometimes, you have a particular start vertex u and you just want to search for everything that is reachable from u. However, other times you are using the graph search to find the connected components of the graph, or as part of an algorithm for computing some other property of the entire graph such as biconnected components. In these cases, the outer loop is necessary.

The crucial special property of graph search is that, even with the outer loop, the runtime is still bounded by $O(|V| + |E|)$, and not just by $O(|V| \cdot |E|)$. This property is what makes efficient algorithms possible for computing connected components, etc.

It's also worth noting that the $O(|V| + |E|)$ bound assumes that the white/gray/black status of a vertex (i.e. which set it is in) can be checked and modified in $O(1)$ time. This can be achieved by creating an array of size $V$, or by attaching a flag to each vertex; either way, it takes $O(V)$ time to initialize all the vertices into the white set at the start of the algorithm. If you don't use one of these methods, you probably have to add a logarithmic overhead for tracking the vertices in set data structures. This is true even in cases where you don't need the outer loop.


Why $xx^TM$ requires $O(dk)$ operations? Suppose $x \in \mathbb{R}^d$ and $M \in \mathbb{R}^{d \times k}$.

Why $xx^TM$ requires $O(dk)$ operations?

The matrix $xx^T$ has the $(i,j)$th entry $x_i x_j$. Hence
$$
(xx^TM)_{ij} = \sum_k (xx^T)_{ik} M_{kj} = \sum_k x_i x_k M_{kj} = x_i \sum_k x_k M_{kj}.
$$
We can compute $\sum_k x_k M_{kj}$ for each $j$ in linear time. Given that, we can compute the product matrix in linear time using the above formula.


Selection Sort Analysis I'm having difficulty understanding the big-O analysis of the selection sort algorithm. Here is my pseudocode (with line numbers):

    procedure SELECTION (A(n), limit)
1.  for j <- 0 to limit - 1 do
2.      min_index <- j
3.      for k <- j + 1 to limit do
4.          if A(k) < A(min_index)
5.              min_index <- k
6.          end-if
7.      end-for
8.      temp <- A(min_index)
9.      A(min_index) <- A(j)
10.     A(j) <- temp
    end-for
end-SELECTION

Our professor wants us to work from the inside out; in other words, analyze the statements the furthest away from the conceptual vertical line that denotes hierarchies. Therefore, I start at line 5, and work out from there. Here's what I've understood so far:

The time complexity of lines 4-6 is O(1) (constant).
Because lines 4-6 are "contained" in the for loop on line 3, you must use the rule of sums to multiply line 3 and lines 4-6. In other words, if line 3 is a program fragment f(x) and lines 4-6 are a program fragment g(x), then the time complexity of lines 3 - 6 is f(x) * g(x).

This is where I get confused. Because var limit is referencing the size of the array, wouldn't the for loop on line 3 run limit-1 times, because k is equal to 1 and is running to limit? To put it another way, if k were equal to zero, wouldn't the loop run limit times? Every video and website I've looked at has not given me a clear representation of that expression, because they've analyzed it differently.

On top of this question, how do I determine which asymptotic notation to use to describe this problem? Is it Big-Oh, Big-Omega or Big-Theta?

Thank you.

The number of iterations of the loop 3–7 depends on the value of $j$: it is $\mathit{limit} - j$. Therefore the running time of lines 3–7 is $O(\mathit{limit} - j)$. Lines 8–10 run in $O(1)$ time, so the body of the loop 1–11 runs in time $O(\mathit{limit}-j) + O(1) = O(\mathit{limit}-j)$ (using $j < \mathit{limit}$). Finally, the total running time is
$$
O\left(\sum_{j=0}^{\mathit{limit}-1} \mathit{limit}-j\right) =
O\left(\sum_{j=1}^{\mathit{limit}} j\right) =
O(\mathit{limit}^2),
$$
using the formula $\sum_{j=1}^n j = \frac{n(n+1)}{2}$.


recognize strings of 1's and 0's which are multiples of 3 Construct a minimized Deterministic Finite Automaton that recognizes strings of 1's and 0's that are multiples of 3.

This was one of the questions asked in my cycle test.

What would be a correct interpretation to this question?

Strings having a number of 0's and 1's that are multiple of 3, e.g.000111, 011010
Strings of 0's and 1's which in binary notation is a multiple of 3, e.g. 11, 110
Or any other radix notation, taking 0's and 1's, and checking if they are multiples of 3

If the question intends anything other than your option 2 (binary representations of natural numbers that are divisible by 3), then it is a badly written question.

If the qeustion meant strings in which the number of 0s and the number of 1s are both divisible by 3, it would have said that. It would be bizarre to have numbers whose digits are all 0s and 1s and intend some base other than binary without mentioning that.


Why does the distribution of pseudorandom numbers change when operating like this? We were introduced to the standard C rand() function, and how to use it.

At some point during the class we were asked how to roll a die. The simple answer was to create a random number, take its modulo 6, and add 1.

rand()%6 + 1

However, the right answer was building a function that returns a value in the range [0,1) and then operating with that function to get a random number between 1 and 6.

Since most people in my class haven't seen probability yet, we weren't told why this was the right answer, but the class's assistant told us that taking the modulo of the random number produces a normal distribution of the numbers, while the other function we built:

rand / ((double) RAND_MAX + 1)

produces a uniform distribution.

Could anyone explain why this happens? I'm not a CS student myself so my knowledge is very basic

Thanks in advance.

rand() returns an integer uniformly distributed between 0 (inclusive) and RAND_MAX (exclusive).

When using modulo to partition those possibilities into 6 buckets you will end up with a few buckets that has 1 more possibility than the others. This means the random result ends up biased.

However the exact same thing happens if you use divide. The only difference lies in which buckets get biased.

This is due to pigeon stuffing. There is no way to divide a population of $2^n$ individuals into 6 groups perfectly evenly.

Instead you should check whether one of the biassing results is returned from rand() and generate a new number if so:

int bias = RAND_MAX % 6;
int divisor = (RAND_MAX - bias)/6;

while(true){
    int random = rand();
    if(random < RAND_MAX - bias)
        return random / divisor;
}

The difference between divide and modulo for partitioning the data has to do with which bits are more random. Many implementations of rand() use a simple linear congruential generator where the more significant bits have better randomness than the lesser significant bits. In a good RNG every bit is equally random and it does not matter whether you use modulo or divide.

Having said all that if you really cared about randomness you would use a proper high quality random number generator that doesn't have some of the well known issues you'll find in a LCG.


What happens when we increase or decrease capacities in the minimum flow? I am confused from these 2 true-false questions on the max flow and am seeking clarity on the basics.

If in a network we increase the capacity of an edge in the minimum cut, the maximum
flow gets increased.
If in a network we decrease the capacity of an edge in a minimum cut, the maximum
flow gets decreased.

My thoughts:

Increase case: I think this is not always true as increasing the minimum could result in what was originally the $2^{nd}$ min flow becoming the lowest value and thus the new max flow. Hence because it isn't always true, the answer is false. This question indicates that max flow needs to be recalculated.

Decrease case: I think this is true because we already have the minimum cut so lowering the minimum brings us to a new minimum. Hence the answer is true.

Is my reasoning correct or is there something I misunderstood.

Case 1, increase the weight.  Consider a path on at least three vertices with capacity 1 for every edge.  Max-flow is 1, min-cut is 1.  Increase one of the edges' weight, and the max-flow will still be 1, hence the claim is false.
Case 2, let $C$ be a minimum cut with cost $w(C)$.  Decrease the weight of one of the edges in $C$ to get a new minimum cost $w'(C)$.  Since $C$ is still a cut in the graph, but $w'(C)$ is smaller than any other minimum cut, the claim is true.


Equivalent expression in English: Set Notation $\{0,1\}^K$ I am overviewing this expression given in set notation. Could someone translate what M "Element of" $\{{0,1}\}^k$ stands for? Im looking for an explanation in English like what I did below.

$K_e = \text{Encryption Key} $
$K_d = \text{Decryption Key}$
$\mathcal{E}_K(M)$ = Encryption using Key with Message M

$D_K(C)$ = Decryption using Key with Ciphertext

$K \oplus M$

Right now I think $K$ is just the word length of the string. Meaning the key could be either $0^k$ or $1^k$ which corresponds to the key being $0$ or $1$ being repeated $k$ times. e.g. $0^3 = 000$ or $1^5 = 11111$. I believe this is wrong though.

In set theory $B^A$ denotes the set of functions from $A$ to $B$. Thus, an element $f\in B^A$ is a function $f:A\rightarrow B$.

In your specific case $\{0,1\}^k$ is the set of functions from the natural number $k$ -- a set with $k$ elements -- to $\{0,1\}$. An element $M\in\{0,1\}^k$ is then a $k$-tuple of zeros and ones, i.e., a binary string of length $k$, as said by Yuval Filmus in a comment.

Note that not any combination of 0's and 1's up to length $k$ is valid, but only those with exact length $k$.