algorithms – Reduction from Edge-Coloring and Vertex-Coloring to a new problem

I have a question from a test I did and failed, a question I failed to do.

In short:

the question is about reduction from Vertex-coloring and Edge-coloring, to a new problem they have defined.

The new problem is called Min-Monochromatic. Want to show that this problem belongs to $NP$ , and later make a reduction from Edge-Coloring and Vertex-Coloring to it.

The question has three parts, all parts are related to each other. The first part, which is the easiest of the three I was able to do in my opinion.

The second part shows a reduction from Vertex-Coloring to Min-Monochromatic, ie $Vertex-Coloring leq_p Min-Monochromatic$:
I could not do that properly.

The third part should show a reduction from Edge-Coloring to Min-Monochromatic, i.e. $Edge-Coloring leq_p Min-Monochromatic$ : I also could not do for the same reasons of the second part, and in addition the question is more complex, there is a reference between Edge-Coloring and Vertex- Coloring.

The question:

Let’s look at the Min-Monochromatic problem. In this problem, we are given 3 things:

  • Undirected graph, G = (V, E).
  • Natural number $k in mathbb{N}$ so that $k> 0$.
  • Another natural number $l in mathbb{N}$ so that $l> 0$.

We are asked if there is a color function $varphi : Vrightarrow begin{Bmatrix} 0,cdots,k-1 end{Bmatrix}$ so that there are at most $l$ pairs of neighbors with the same color. Note that the color function $varphi$ is not necessarily valid (in this problem we are allowed to have neighbors of the same color, the goal is only to minimize the number of cases). We want to show that the problem is NP-complete. We will see this in parts.

Part One:

Show that $Min-Monochromatic(G,k,l) in NP$. You must explain the correctness of the validation algorithm and analyze the runtime.

My answer:

Given an instance $(G, k, l)$ of the Min-Monochromatic problem. The witness who is a subgroup $U subseteq V$. Graph $G_U = (U,E_U)$ was built.

The validation algorithm will first count the different colors that the vertices in the graph have. If the number is less than or equal to k, we will continue.

After this we will define a counter c = 0. For each edge in the graph, if the color of the vertices to which it is connected is the same, we will increase the counter by 1.

If the counter is less than or equal to $ l $, we return true

The algorithm is polynomial, we will go through each edge and each vertex exactly once.

Part Two:

Show that $Min-Monochromatic$ is $NP-complete$. You must:

  • Build a reduction that will see it.
  • Prove its correctness.
  • Analyze the running time.

(Instruction: You can show $Vertex-Coloring leq_p Min-Monochromatic$ reduction and assume that $Vertex-Coloring $ is NP-complete.)

My answer:

Here I could not continue. I was thinking of doing a reduction from $Min-Monochromatic$ to $Vertex-Coloring$ . You can add one more color, each time of adjacent vertices with the same color, delete the edge between them, and connect them to the new vertex. But in question they asked for the reduction and vice versa, so I could not continue.

Part Three:

Rely on the previous reduction and show $Edge-Coloring leq_p Min-Monochromatic$.

You must:

  • Build a reduction that will see it.
  • Prove its correctness.
  • Analyze the running time.

In addition: Based solely on our conclusion from section B and this reduction, can it be determined to which class Edge-Coloring belongs? Explain and detail

My answer:

I think show reduction: $Edge-Coloring leq_p Vertex-Coloring$.And because of the reduction from the second part it should work.

To show reduction from Edge-Coloring to Vertex-Coloring, it’s not complicated.

Reduction from Edge-Coloring to Vertex-Coloring, creates a vertex for each edge, and creates an edge $(v_e, v_f)$ between each pair of different e and f edges that share a vertex.

In my opinion it is not possible to know only by the reduction in Part B to which class Edge-Coloring belongs. Because Edge-Coloring does not participate in this reduction at all.

I would be happy to help regarding the second and third part, which I could not understand properly, and the second part I could not do.

java – How do I know if I’m taking too much time to solve a programming problem?

I’m learning Java for a few months, mainly through the Deitel‘s book “Java – How To Program, 10th Edition“, and now I am on the Chapter 7 learning about Arrays and ArrayLists where things started to get harder, so I decided to go back to Ch.4 to solve its questions (that I skipped) and improve my skills.

After 1h30min programming the Q17, I finally solved it and then found myself in the following question: “Am I taking a long time to solve these problems? Am I going around and around with something that could have been solved in a much simpler way?”.

As a beginner, I have no idea if this is a good time or not. I’d like to receive some opinions from experienced programmers and some tips to improve myself more and more.

Here’s the mentioned question:

4.17 (Gas Mileage) Drivers are concerned with the mileage their automobiles get. One driver has kept track of several trips by
recording the miles driven and gallons used for each tankful. Develop
a Java application that will input the miles driven and gallons used
(both as integers) for each trip. The program should calculate and
display the miles per gallon obtained for each trip and print the
combined miles per gallon obtained for all trips up to this point. All
averaging calculations should produce floating-point results. Use
class Scanner and sentinel-controlled repetition to obtain the data
from the user.

What is the problem of using a self signed-certificate for a game?

You don’t seem to understand the issue with self-signed certificates, so allow me to explain.

Generally, when people say “Don’t use self-signed certificates!”, they mean in the context of a web-server, in which you expect the general public to connect via a web browser. In such a situation, if a self-signed certificate is used, this will lead to an error message:

Self-Signed Certificate Warning

Users will naturally want to ignore the warning and proceed – after all, that’s the only way for them to use your website. So if an attacker intercepts the connection and presents his own self-signed certificate, the user would not be able to see that. After all, the error message is seen as a natural part of the process.

Self-Signed Certificates in other settings

Companies usually have a self-signed certificate as a root-certificate for internal services. This certificate is distributed internally (usually via Active Directory) and thus trusted by all clients.

This is a normal setup and works as intended. If an attacker would attempt to intercept the connection, an error would occur, as his certificate would not be trusted.

Self-Signed Certificates for your game

I assume that you have a server, which manages the game state, and a game client (likely a native client). In this situation, there is nothing wrong with using a self-signed certificate. Simply distribute the certificate with the client and keep the private key on the server.

Can the attacker just steal the private key?

Only if your server has a vulnerability, which would allow the attacker to do so. But that risk would also exist with a certificate signed by an external certificate authority.

wordpress – Adsense earnind problem wp-rocket

I am small devoloper manage site. I informed Google Adsense on the night of 31 March that my Adsense CPC has increased a lot.

As Google has told that if your CPC is increased, then inform Google Adsense Otherwise Google Adsense account may be suspended. I got suspicious as soon as my CPC increased and I told Google Adsense.

After informing my CPC became normal after one or two hours! But after March 31, every month my earning kept decreasing. But on the contrary, the traffic on my website increased every month. And with that the impressions and clicks of Google Ads also increased.

And my question is why after 31st March my earning kept decreasing and traffic increased?

Note: I Start using Wprocket from 28 march
enter image description here

algorithms – issue with a task scheduling problem asked during a recent software engineering interview

I recently went through a interview session for a SWE/CS role at a well known company.
It wasn’t specifically a “coding-round” but was titled a “domain interview” session, so I assumed the interviewer was interested in an discussion/high-level-solution related to the problem.

The problem:

You’re given a computation graph with nodes representing computations, edges representing dependence, and the values on edges representing the data-size in MB (input or output) at that edge.
You want to schedule this graph on a single-processor with limited memory X MB.
To execute a node/computation, both inputs and outputs data should fit within X memory of the processor.
It’s given for for each node sum of its inputs/outputs data <= X.
If at any time the data the total data that needs to be stored execeeds X, then there is extra cost per MB of fetching data from the disk. (it can happen with node n1 has produced an output that needs to be used by n2 but not all predecessors of n2 have run yet).
How would you schedule this graph?

My approach/What I discussed:

  • I answered by saying that “in general” this problem is intractable(NP-complete) for multi-processor systems, and likely too for single-processor system due to the memory constraint.
  • Then I suggested a greedy approach based on keeping track of all ‘ready’ nodes at a given time that can be executed as their predecessors have been executed.
  • Which specific node to schedule next from several available/ready
    ones can be done based on trying to minimize the cost associated with
    memory constraint (i.e. seeking to schedule the one with the min cost
    associated with data transfer).
  • If there are several nodes with same minimum cost associated with
    data transfer, the pick the node among them with the biggest
    input+output mem requirement.

During the session, the interviewer didn’t suggest many things or gave any tips or direction on which directions he may have wanted me to lead to, so it turned out to be very open-ended.

He was almost neutral or very slight camera/tight-lipped smile taking notes most of the time.

I couldn’t gauge exactly what interviewer may have been looking for due to the intractableness of the problem — it’s hard to come up with a general optimal algo for such at the top of your head.

Later I came to know I received a ‘no’ decision for this session.

Issue:

This has me puzzled. I’ve been racking my brain on if I didn’t approach it correctly, or if the interviewer was expecting one to talk about something else that the things I mentioned.

Is there something optimal or direct I missed?

Could there be some specific algo that interviewer may have been looking for that generally one is expected to know?

During the session, I thought I was providing a reasonable solution given the constraints of the problem, and could have deep-dived into any direction that interviewer may have asked me to.

But didn’t get any push-back or suggestions from the interviewer during the session, i’m interested to know what i missed or how I should have approached this problem.

java – Daily coding problem: Job scheduler invoking a function after specific time

This is a problem from Daily Coding Problem. I have implemented it in Java.
For a function f I have used Runnable interface.

Problem:

This problem was asked by Apple.

Implement a job scheduler which takes in a function f and an integer n, and calls f after n milliseconds.

Solution:

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;

class Ideone {

    interface JobScheduler {
        void schedule(final Runnable f, int n);
    }

    static class JobSchedulerImpl implements JobScheduler {
        private final AtomicInteger idValue = new AtomicInteger(0);
        private final Map<Integer, Thread> jobs = new ConcurrentHashMap<>();

        private int getNextId() {
            return idValue.incrementAndGet();
        }

        @Override
        public void schedule(final Runnable f, final int n) throws IllegalArgumentException {
            if (n < 0) {
                throw new IllegalArgumentException("n cannot be nagative");
            }
            int id = getNextId();
            Thread job = new Thread() {
                @Override
                public void run() {
                    try {
                        Thread.sleep(n);
                        f.run();
                        jobs.remove(id);
                    } catch (InterruptedException e) {
                        jobs.remove(id);
                    }
                }
            };
            jobs.put(id, job);
            job.start();
        }
    }

    public static void main(String() args) {
        JobScheduler jobScheduler = new JobSchedulerImpl();
        jobScheduler.schedule(new Runnable() {
            @Override
            public void run() {
                System.out.println("Job1 launched at: " + System.currentTimeMillis());
            }
        }, 10000);
        jobScheduler.schedule(new Runnable() {
            @Override
            public void run() {
                System.out.println("Job2 launched at: " + System.currentTimeMillis());
            }
        }, 1000);
    }
}
```

Hello I have this problem

Hello I have this problem, any solution thanks …

.

Optimization problem where the variables have to sum to a specific value

I have been working with an optimization problem with some convex function $f$ which is supposed to be minimized w.r.t. some variables $z_1, dots, z_d in (0,1)$. The additional restriction here is that $$sum_{k=1}^d z_k = 1.$$

I have been trying to find a good algorithm to solve such a minimization problem but couldn’t think of one. For example, I have tried the algorithms from NLOpt such as COBYLA but they do not work (even though COBYLA is supposed to support equality constraints). The reason is that with this problem, whenever we make a step in one direction (in some dimension) then we have to make the opposite step in another dimension.

However, when the COBYLA algorithm tries to deviate in one dimension it only notices that the resulting point is not feasible anymore. As this even happens when taking a single step in a single direction which is less than the tolerance, the algorithm terminates rather quickly with the original guess.

Are there algorithms/approaches that are commonly used to solve this problem? I would assume that it is much simpler than regular convex optimization.

functional analysis – Recovering the objective function from the solution of a linear programming problem

There is a compact, convex space $T subset mathbb{R}^N$ of parameters and a finite set $X$ of cardinality $N$. I know that each $x_1, …,x_i, …, x_N$ is associated with a value $c_{i}(t_{i})$: the $i$-th entry of the $t$ vector shifts around the value of selecting each $x_i$. This generates a problem of choosing a vector of probabilities $(P_{x_1}, …, P_{x_N})$ to maximize $sum_{i} P_{x_i} c_i(t_i)$ subject to additional linear constraints on the selection probabilities $P_{x_i}$ for each item $i$ that are independent of $t$.

I have an upper hemi-continuous correspondence $P^*:Trightarrow X$ that is the solution to the linear programming problem. I need to recover the objective function ${c_i(t_i)}_{t in T, i in {1,…,N}}$ that generated $P^*(t)$, and it must be continuous and bounded. By “recover”, I don’t mean it literally in the sense of an algorithm that I could run on a computer, but instead as an existence claim: “there exists a function $c(t)$ such that $P^*$ is the argmax correspondence”.

I can almost do it using an approach based on Michael’s Selection Theorem and the Separating Hyperplane Theorem, but from that I can only conclude that I can recover continuous functions $c_i(t)$, but not $c_i(t_i)$. I have tried adding additional assumptions about the form of $P^*$, but I just can’t find a straightforward way to eliminate the dependence of $c_i(t)$ on the $t_j$‘s besides $t_i$. I can make additional assumptions about $P^*$, and I have, but I continually run into the same kinds of meta-problems about existence of certain kinds of continuous functions.

Another thing to say is, if $T$ were finite, I could use Brouwer’s fixed point theorem to find what I’m looking for through a process that continuously adjusts guesses for the $c$‘s. I was thinking about (a) taking a finite subset of $T$ and letting the set get large, and trying to argue that it converges in some sense to a continuous function or (b) trying to go straight to Schauder’s FPT and argue that the set of functions I’m interested in is compact in the way required by the theorem. I tried yet another approach based on solving infinite systems of inequalities, but that doesn’t guarantee a continuous solution. But if there’s an easy answer to this question, I don’t want to do any of that, obviously — I’ve already wasted too much time on this piece of a larger puzzle.

I am just stuck and mostly looking for references, to a theorem or paper or book or researcher who does this kind of “inverse optimization”. This feels like the kind of question where someone with a good background in Constrained Optimization or Operations Research or Convex Analysis will roll their eyes and say, “That’s just Foo’s theorem, and there’s an obvious trick based on duality.” Great, sure, I love duality, tell me about the Foo.

algorithms – Reduction from IS problem to other problem

Given graph 𝐺 = (𝑉, 𝐸) it is said that it is a star if there is a vertex $𝑣_0 ∈ 𝑉$ so that all the other vertices are connected exclusively to it (and not to each other.)

That is, $𝐸 = ${ $(𝑣_𝑖, 𝑣_0) | 𝑣_𝑖 ∈ 𝑉 $ }. Also, given graph 𝐺 = (𝑉,𝐸) we will also look for its sub-graphs, which are a star. Which is the center of the star.) For example, the following graph:

Is not a star, but it contains an induced sub-graph (above the vertices π‘Ž, 𝑏, 𝑐, 𝑒, 𝑓) which is a star of size 5:

In the optimized version of the problem, we will be interested in finding the largest induced sub-graph that is a star. In the decision version, we also receive as input a natural number π‘˜, and are asked “Is there an induced sub-graph of 𝐺 which is a star ≀ k.”?

Formally:

STAR = { $left langle G,k right rangle | $There is a $ Usubseteq V $subgroup so the induced sub-graph $ G_U = (U, E_U) $ which is a star ≀ k in size. }

We want to show that the problem is NP-complete. We will see this in parts.

section A

Show that 𝑆𝑇𝐴𝑅 (𝐺, π‘˜) ∈ 𝑁𝑃. You must explain the correctness of the validation algorithm and analyze its runtime.

section B

Show that 𝑆𝑇𝐴𝑅 is NP-complete. You must:

  • Build a reduction that you will see,
  • prove its correctness,
  • and analyze its running time.

(Instruction: You can show a reduction 𝑆𝑇𝐴𝑅 ≀𝑃 𝐼𝑆 and assume that 𝐼𝑆 is NP-complete)

The direction I was thinking of is to first show that STAR belongs to NP, to say that there is a graph G and a natural number k. The witness will give us an example of the graph and then it will be possible to verify or reject if the graph is STAR.

After this, show a reduction from IS to STAR, say that there is a graph $G_{IS}$, which belongs to IS, and from it make a reduction to STAR, what can be done is to add one more vertex to IS, and then it will be STAR.

In terms of correctness, it should be seen that if you add a vertex to IS it becomes STAR, and if you remove a vertex that is connected to all the other vertices in STAR, it is IS.

It is a polynomial run time that is passed over each edge once, and the number of edges can be, as the number of vertices squared.

This is the solution I’m thinking of, but I do not know if it is a
correct solution, there are a number of things that need to be done
and proven, and I do not know if I do it right and list it properly.

For the first part I think I did it right, for the second part is not
complicated, but I do not know if I explained enough

section A:

Given a graph 𝐺 = (𝑉, 𝐸) and a natural number π‘˜ ∈ β„• our witness will be a subset of vertices π‘ˆ βŠ† 𝑉. We initialize an array C by the size of the number of vertices V ← 0.
We will go through each pair of different 𝑒1, 𝑒2 ∈ π‘ˆ vertices and check whether (𝑒1, 𝑒2 ∈ 𝐸)?
If so, we will increase the content in the position of the vertices in the array by 1. If there is a vertex whose counter is equal to | V | -1 and all the other vertices of their counter are 1, we will return true, otherwise we will return false.

correctness:

(𝐺, π‘˜) ∈ STAR ⇔ There is a group π‘ˆ βŠ† 𝑉 almost independent in size π‘˜ β‰₯ | π‘ˆ | ⇔ There is one vertex with a degree of | V | -1 and the other vertices with a degree of 1 ⇔ have π‘ˆ βŠ† 𝑉 in size π‘˜ β‰₯ | π‘ˆ | For which the verification algorithm returns truth ⇔ there is a witness for whom the verification algorithm will return truth ⇔ the verification algorithm gets the (𝐺, π‘˜).

section B

We will reduce $IS leq _p STAR$, given the instance $(G, k)$ of the IS problem. We will create a new vertex x. We will define $widetilde{V} = 𝑉 cup {π‘₯, 𝑦}$. Also, $widetilde{E} = E cup begin{Bmatrix}
(x,e_1),cdots,(x,e_{|v|}) end{Bmatrix}$
. That is, the vertex is connected to the other vertices finally $widetilde{G} = (widetilde{V}, widetilde{E})$. We will define our reduction function: $f(G,k) = (widetilde{G},k+1)$.

The reduction performs a fixed amount of operations, and is therefore polynomial.

We will see its correctness:

$(G,k) in IS Leftrightarrow (widetilde{G},k+1) in STAR$

$Rightarrow $

Suppose that $(G,k) in IS$

We can add vertex x, to subgroup U of vertices V. and | U | Greater than or equal to k. Because we add one vertex, we will turn a set of vertices that have no edge between them, into a set of vertices that are all connected only to vertex x.

That is $(widetilde{G},k+1) in STAR$

$Leftarrow $

Suppose that $(widetilde{G},k + 1) in STAR$. There is a subset $widetilde{U}$ of the vertices $widetilde{V}$. and | $widetilde{U}$ | Greater than or equal to k + 1.

We know that there is an x vertex to which all the other vertices are connected, we will delete that vertex. We get a set of vertices in size | V | Of IS, and with vertices not connected to each other

That is $(G,k) in IS $

Not sure if I answered the question properly, I also have a hard time showing the correctness of section 2, I do not know if my correctness covers all cases. I'm not sure if I answered it correctly.