Runtime of algorithem when the internal for depend on the external for I'm trying to find the running time of this pseodocose:

int x=0,i,j
for (i=1;i<=n;i++)
    for(j=1;j<=n+r;j=j+i)
       x=x+j;

What I did: First I checked  what happened on the first iteration of the external for:

$i=1:$ the internal for will run $n+r$ times, so $j\in\{1,2,3,4,\dots,n+r\}$ so $\color{blue}{a_n=n}$
$i=2: $ the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,3,5,7,\dots,k\}$ so $\color{blue}{a_n=2n-1}$
$i=3$: the internal for will run from $j=1$ to some $k\leqslant n+r$ such that $j\in\{1,4,7,10,\dots,k\}$ so $\color{blue}{a_n=3n-2}$

So the runnig time should be $\color{blue}{\underbrace{n+(2n-1)+(3n-2)+(4n-3)+\dots}_{ n+r \text{ times}}}$

But what should I to now? I should find the running time in $\Theta$ terms, I am trynig to find the runnig time without using any calculator

For $i=1$ the internal loop runs for $n+r$ times, for $i=2$ the internal loop runs for $\lceil (n+r-1)/2 \rceil+1$ times, for $i=3$ the internal loop runs for $\lceil (n+r-1)/3 \rceil+1$ times, and so on till $i=n$ when the internal loop runs for $\lceil (n+r-1)/n \rceil+1$ times.

You now need to sum these numbers. I suggest you read about harmonic series.


Being stuck and frustrated with my masters project I'm doing a masters in CS that requires me to implement from scratch most of the neural network models and because python libraries aren't applicable to what i want.

The problem is that i don't feel capable of implementing those from scratch. Even the MLP seems very difficult, i always try but get stuck and restart. Meantime, i feel that my supervisor think it's a natural thing and i shouldn't have problems implementing those algorithms.

I know that when we are talking about research, it shouldn't be easy - because anyone else would do it if so - but i'd be glad to receive some advices about this process i am going  through: Am I not prepared enough for this or is it an overambitious idea to implement all these networks from scratch? Should i continue this? I've already thought about giving up.

Ps: any good materials (books, videos, etc) focusing in implementation of neural networks are welcome.

I have been implementing a branch and bound solver with heuristics for an NP-hard problem. It got complicated at some points and had to reimplement parts a couple of times. The problem was (I think), that I started implementing with only an intuition about the design and how it looks like. That is bad software engineering and is catastrophic in big project.

So forget your computer for now. Bring a bunch of white papers and a pen. Describe the steps of the algorithm precisely. Design the program, decide the data structures and how they will communicate. Decide where data should be kept and how it should be commuted. When you have the details drawn on papers, coding is just a matter of writing it down and doing some optimization.

Another good advise is to start by writing the simplest version you can imagine. Implement only what you need to have, in the simplest way you can think of. No optimization, no copy/reference calls thinking just get it to run correctly at first. Once you are at that point you have something to deliver, start making it better. Check where you are doing stuff naively where you can do it better. Find all copies where you could have just done it on the original structure. Because if you kept optimizing and adding features while implementing you will never finish. There will always be something to add.


Forward checking with conflict directed backjumping Can somebody explain me how can I join forward checking with conflict directed backjumping in my CSP solver? I understand that when the consistency fails when I add a value to a variable, I should save all the instantiated variables of the restriction that fails, on the conflict set of the variable to which I gave a value. But what happens when there's no consistency failure but when I'm doing the inferences of the forward checking I found a contradiction? Do I need to know which restrictions failed and add the variables to the current variable conflict set?

My current approach:

My function that solves the CSP is recursive. So right now I'm doing the following, for each the current variable (the one I'm in the recursive step) I'm checking if the value that I give to her is consistent, if not, I add all the attributed variables of the restriction that fails to the conflict set of this variable. When I'm backjumping in the recursivity, I return this conflict set, and if any variable is contained in this set, it will try to change his value. (this implements the basic backjumping and with some other small changes I put my algorithm using conflict directed backjumping). I tested this part and it's working.

Now, when I add the forward checking, I need to get from the forward checking some informations when it finds contradictions (and this is the problem). Right now, I'm getting the variable where the contradiction occurs and all the attributed variables related to restrictions that failed.

Is this all the infromation I need from the backjumping?

If forward checking detects that the potential assignment of a variable $x_1$ leaves no valid assignments for the variable $x_2$, one simple strategy is to just make the assignment to $x_1$ and then queue $x_2$ as the next variable to be assigned.  When the assignment of $x_2$ inevitably fails, your backjumping machinery will do what it always does and you need not code any special information gathering related to forward checking.  In the meantime, you've saved all the time that would have been wasted doing (and undoing) a potentially exponential number of unrelated assignments that do nothing to resolve the inevitable conflict between $x_1$ and $x_2$.


design of self-loops and final states in fsm I am learning about automata and finite state machines. Consider the following automaton, that accepts the word 'ab', does not have to be infinite, just once:

alphabet: 'a','b'
states: 1,2, 3 (3 is the final state and 1 is the initial state)

transitions:

state 1, symbol a, state 2
state 2, symbol b, state 3

First part of my questions:

Question 1. Is it required to add self-loops at 1 for 'b', and a self-loop for 'a' at 2?

Question 2. What about at state 3(final)? Should I add self-loops for 'a' and 'b'?

I basically need to know, how to design my final state. So that even if my alphabet was expanded (say a, b, c), and I have a 'dump' state, with the following transitions:

state 1, symbol a, state 2
state 1, symbol b or c, state dump

state 2, symbol b, state 3
state 2 symbol a or c, state dump

Question 3. Now from final state 3, should I add a transition to dump state, with symbol values a,b,c ???

Your assistance is much appreciated.

Your original automaton is fine, it accepts the singleton $\{ab\}$. Here is a pictorial representation:

In the above automaton it's implicit that given a state and a letter for which there is no arrow going out of that state, then the automaton "crashes". If you want to be complete, you can add a dead state that absorbs strings that don't belong in the language. Here is the complete automaton:

If you add self-loops at 1 and/or 2, you will change the language that the automaton accepts. Look at this:

The self-loop at 1 labeled with $b$ changes the language to $\{ab, bab, bbab, bbbab, \dots\}$.


Bellman-Ford variation I have a "smarter" version of Bellman-Ford here; this version is more clever about choosing the edges to relax.

//Queue Q; source s; vertices u, v; distance to v d(v)
Q ← s // Q holds vertices whose d(v) values have been updated recently.
While (Q !empty) {
  u ← Dequeue(Q)
  for each neighbor v of u {
    Relax(u, v)
    if d(v) was updated by Relax and v not in Q
      Enqueue(v)
  }
}

But, can anyone explain why this improved version correctly finds the shortest path from $s$ to every other vertex in a directed graph with no negative cycles?

Also, what is the worst-case runtime if every shortest path uses at most $v$ edges?

This is precisely Moore's 1957 formulation of what is now more commonly known as the Bellman-Ford algorithm.

Why does it work?

Moore's algorithm is a special case of Ford's more general relaxation strategy for computing single-source shortest paths:

while any edge is tense
    relax any tense edge

This generic algorithm will always halt after a finite number of relaxation steps with a shortest path tree, unless some negative-weight cycle is reachable from the source vertex (in which case, there is always at least one tense edge, so the algorithm will never halt).

For Moore's algorithm, it is not hard to the following observation by induction:

  Every tense edge leaves a vertex that is in the queue.

If fact, this lemma holds if we replace the queue with any other data structure that supports the operations "insert this" and "give me something".  (For example, using a priority queue gives us Dijkstra's algorithm!) The algorithm halts when the data structure is empty.  Thus, by the previous lemma, when the algorithm halts, there are no tense edges, so we have a shortest-path tree.

What is the running time?

We can naturally divide the execution of the algorithm into phases by adding an artificial token to the queue immediately after the source vertex, just before the main loop begins.  Each phase ends when we dequeue the token; if the queue is not empty, we enqueue the token again and start the next phase.  If the queue is empty after we dequeue the token, the algorithm ends.

Each vertex in the graph is dequeued at most once in any phase.  (Here I'm assuming that enqueuing a vertex that is already in the queue does not actually change the queue.)  Thus, each edge in the graph is relaxed at most one in any phase.  So each phase runs in $O(m)$ time.

Let $dist_i(v)$ denote the distance value stored in vertex $v$ after $i$ phases.  Initially, we have $dist_0(s) = 0$ and $dist_0(v) = \infty$ for all $v\ne s$.  It is easy to prove by induction that

  $dist_i(v)$ is at most the length of the shortest walk from $s$ to $v$ that uses at most $i$ edges.

This lemma immediately implies that the algorithm ends after at most $n-1$ phases (unless there is a negative cycle).  So altogether the algorithm runs in $O(mn)$ time.

For more details, see my lecture notes, or better yet, Bob Tarjan's excellent monograph Data Structures and Network Algorithms.  I believe Tarjan was the first to observe that Moore's algorithm is equivalent to Bellman-Ford.


Non-deterministic Turing machine for $L_1 = \{w\#0^n|w \text{ is a suffix of some $x$ in $L$ with } |x|=n\}$ Show if L is in NP, then also L1 is in NP

  $$L_1 = \{w\#0^n|w \text{ is a suffix of some  $x$  in  $L$  with } |x|=n\}$$

I know that if L is in NP, then there exists a NTM $M_L$ than accepts $x$, with $|x|=n$. I can use $M_L$ to describe an NTM $N$ for $L_1$. I have a problem by understanding which is the best non-deterministic operation in $N$ to create an $x$ string for $L$.

Let us describe an NTM $N$ that computes $L_1$ in polynomial time. The machine "guesses" the first $n - |w|$ letters of a word $x'$ (it makes all possible guesses non-deterministicly) and append $w$ to $x'$ then it simulates $M$ on the resulting word. If $M$ accepts on any of the guesses the machine $N$ halts and accepts. If all reject, $N$ also rejects.

Since, we have $n$ zeroes as a part of the input, the guesses are done in linear time in the size of the input. The simulation also runs in polynomial time in an NTM by assumption, hence, we get a total polynomial running itme and hence, $L_1$ is in NP. The correctness of $N$ is straight forward.


Partitioning list into two parts of almost equal sum I was given this problem in class, and I have no idea how to solve it. The problem is:

"Given a list of positive integers, divide the numbers into 2 groups such that the difference between the sum of each group is minimal, print that difference. The algorithm must be efficient."

I guess by efficient they mean do not just brute force every option, any ideas?
I tried summing all the numbers and dividing by 2, then the problem is equivalent to finding a group that is the closest to that number, also now you can go over all  the options but once you get to a point where you can only add numbers but your above that number you  can stop.

As Yuval Filmus points out, this is an optimization version of the PARTITION problem. The problem is weakly NP-complete, so any polynomial time solution to your problem would immediately solve partition (simply check if the minimum difference between the sums of the two sets is $0$).
You can solve the problem in pseudo-polynomial time $O(nS)$, where $S$ the sum of the input integers, using dynamic programming, or in time $O(n \cdot 2^{n/2})$ using the split-and-list technique. Pick the best of the two algorithms depending on the value of $S$.
The dynamic programming algorithm is as follows.
Let $A = \{a_1, \dots, a_n\}$ be the input (multi-)set of numbers, and let $S=\sum_{a \in A} a$.
Consider a partition of $A$ into two sets $B$ and $C$, and assume w.l.o.g. that $\sum_{b \in B} b  \le \sum_{c \in C} c$ (since otherwise you can swap $B$ and $C$).
The cost (to minimize) of this partition is:
$$
\sum_{c \in C} c - \sum_{b \in B} b =
\left(S- \sum_{b \in B} b\right) - \sum_{b \in B} b
= S - 2 \sum_{b \in B} b.
$$
Showing that the problem is equivalent to finding a subset $B$ of $A$ whose sum of elements is at most $\lfloor S/2 \rfloor$ and, subject to this constraint, it is maximized.
For $i=0, \dots, n$, and $x=1,\dots,\lfloor S/2 \rfloor$, let $OPT[i,x]$ be true if and only if there exists a subset $B$ of $\{a_1, \dots, a_i\}$ with $\sum_{b \in B} b = x$.
Then $OPT[0,0]=\top$ and, for $x>0$, $OPT[0,x]=\bot$.
If $i>0$:
$$
OPT[i,x] = \begin{cases}
OPT[i-1,x] \vee OPT[i-1,x-a_i] & \mbox{if $a_i \le x$} \\
OPT[i-1,x] & \mbox{otherwise}
\end{cases}.
$$
There are $O(nS)$ values $OPT[i,x]$ and each of them can be computed in constant time (in increasing order of $i$).
The maximum value of $\sum_{b \in B} b$ is $\max \left\{ x \in \{0, \dots, \lfloor S/2 \rfloor \} \mid OPT[n, x] = \top \right\}$.


Array with queries to decrement or find sum of range I have been given an array of integers of size n and q queries which can be of 2 types:
1.Decrement all elements in the given range by some value
2.Find sum of all elements in the given range
1<=n,q<=10^5
I have tried brute force but it gives TLE
Same goes for prefix sum and even segment trees which improve sum query but slow down updation
I cannot figure out how to update in O(log n)
Would lazy propagation help ?
If not , how else can i proceed with this?
P.S. First timer here . Apologies if i missed out on something

Suppose that your array is $a_1,\ldots,a_n$, but instead of storing it this way, you store the differences $\delta_i = a_i - a_{i-1}$ (where $a_0 = 0$). Decrementing $a_i,\ldots,a_j$ by $x$ is then the same as decrementing $\delta_i$ by $x$ and incrementing $\delta_{j+1}$ by $x$. Querying the prefix sum $a_1 + \cdots + a_j$ (using which you can query the sum of any range) amounts to calculating
$$
\sum_{t=1}^j \sum_{k=1}^t \delta_k = \sum_{k=1}^j \sum_{t=k}^j \delta_k = \sum_{k=1}^j (j-k+1)\delta_k = (j+1)\sum_{k=1}^j \delta_k - \sum_{k=1}^j k\delta_k.
$$
The idea now is to use a Fenwick tree, which is an array data structure which can perform both element updates and prefix sums in $O(\log n)$. We use two Fenwick trees, one storing $\delta_1,\ldots,\delta_n$ and the other storing $\delta_1,2\delta_2,\ldots,n\delta_n$ (we can in fact merge them into a single Fenwick tree which stores information for both values at every node). Above we have outlined how to perform each of your two queries in $O(\log n)$.


Formal names of nested functions I have a nested function as follow:

def make_adder(n):
    def add(x):
        return x + n
    return add
>>> plus_3 = make_adder(3)
>>> plus_5 = make_adder(5)
>>> plus_3(4) 7
>>> plus_5(4) 9

What's the formal names of make_adder and add?
Can I call them 'outer function' and 'inner function'?

A function that either takes a function as argument or returns a function as result is called a High Order Function in functional programming. Your function make_adder is doing the latter.


What is the current status of parallel or concurrent programs in the Curry-Howard isomorphism? In Girard's Proofs and Types we can read :

  From an algorithmic viewpoint, the sequent calculus has no
  Curry-Howard isomorphism, because of the multitude of ways of writing
  the same proof. This prevents us from using it as a typed $\lambda$-calculus,
  although we glimpse some deep structure of this kind, probably linked
  with parallelism.

  Proofs and Types, J.Y Girard (Page 28)

But we can also read (about Linear Logic) that

  From the viewpoint of computer science, it gives a new approach to
  questions of laziness, side effects and memory allocation [GirLaf,
  Laf87, Laf88] with promising applications to parallelism.

  Proofs and Types, J.Y Girard (Page 149, written by Yves Lafont)

How are parallel programs linked to the Curry-Howard isomorphism ? What are the current thoughts about that ?

The Concurrent Logical Framework is one interesting area including its descendants, like Linear Meld and LolliMon.  This is based on intuitionistic linear logic.

Classical linear logic has connections to the Linear Chemical Abstract Machine (CHAM) as described by e.g. A Calculus for Interaction Nets Based on the Linear Chemical Abstract Machine which explicitly describes the result as a Curry-Howard type result.

Alexander Summers' thesis Curry-Howard Term Calculi for Gentzen-Style
Classical Logics which I have not read seems to be aimed directly at the problem of providing a Curry-Howard correspondence for Gentzen-style calculi.  The $\lambda\mu$-calculus by Curien and Herbelin introduced in The Duality of Computation is a seminal work in this vein of (non-linear) lambda calculi corresponding to classical logics.

At any rate, this is all still a lively area of research.  There are many recent papers on this topic.  The above doesn't even mention the even more substructural side of separation logic and the corresponding Hoare Type Theory which focuses on imperative programming languages.  For example, there's Towards type-theoretic semantics for transactional concurrency whose references you can trace for prior work.

(As a bit of a pedantic note, most of these are focused on concurrency, not parallelism per se.)


In Ada95 how many bytes does integer occupied in memory? Also asking for float, character, ect.

Ada does not have primitives in the same way as most languages. Instead when you define an Integer or Floating Point Type you provide a range.

The compiler then ensures the Type has that range in whatever underlying type it chooses on that system.

The Standard library does however provide some predefined types...

See http://en.wikibooks.org/wiki/Ada_Programming/Type_System

http://www.adahome.com/rm95/rm9x-03-05-02.html