# All Questions

41,456 questions
Filter by
Sorted by
Tagged with
25 views

### What are the job names for researching neural networks & deep learning?

I am a student who wishes to research neural networks (ANN, CNN, RNN) and deep learning, write papers on those topics, and actively participate in forums like CVPR. My question is: Which professions ...
11 views

### For classifier systems, how is the genetic algorithm run on delayed class?

I am reading Signals and Boundaries and came across Classifier Systems. In the book, John Holland seems to imply that the signals in the input, as they come from a live environment, don't have an ...
19 views

### How do you prove that a solution to the 0-1 knapsack problem is optimal?

Given a boolean vector b representing a solution to the knapsack problem with n elements k capacity and where each element has integer weight and value. Proving that the solution is a solution is ...
34 views

### Finding a simple algorithm for an assignment problem

I have an assignment problem where I need to assign resources to consumers. Each consumer has a list of resources it'd like to acquire, ordered by preference, and each consumer can have at most one ...
14 views

### How to find the number of common edges in two sequences?

Lets say I have two sequences such as these: Sequence 1: A B C E D F Sequence 2: A B D F C E Both sequences contain the same set of elements and each element is unique. I want to find the number of ...
56 views

### What's so difficult about computer verifiable proofs?

What's so hard about creating a piece of software with as minimal as possible mathematical axioms, defining a formal language in which one can create new constructs based on the existing ones, and ...
34 views

### Why does Prim’s algorithm work?

I recently started learning Prim’s Algorithm for finding a Minimum Spanning Tree for a connected graph. However, I am having a problem understanding why the algorithm will indeed produce a MST every ...
18 views

### SAT formula for connected graphs on the grid

In the answer to an earlier question "SAT algorithm for determining if a graph is disjoint" a formula is constructed that is satisfiable iff a given graph is connected. The formula uses a ...
25 views

### How many /20-subnets are in the network 130.149.0.0/16?

I'm new to networking so please bear with me. My textbook gives 4 as an answer, but I'm not sure I understand the question: What's a "/20-subnet"? My understanding is that a network mask (/...
16 views

### Understand what this phrase is in the Turing

I had a test a few days ago and failed it. There was a question that was not clear to me. This is the question: For the purpose of describing the drawing on the tape of a Turing machine at each step ...
25 views

### Process Response time in CPU scheduling

I'm Confused about Response time in CPU scheduling because i found different definition for it, so what is exactly the Response time ? Is it : the time between a process enters ready queue and get ...
30 views

### Complexity of n & (n - 1) should be O(1) or O(log n)?

I'm looking at the methods posted in https://www.geeksforgeeks.org/program-to-find-whether-a-no-is-power-of-two/ for checking whether n is a power of 2. Method 5, ...
26 views

### How to know if language is in comp or np?

I'm new to the site. I had a test a few days ago and failed it, I had a question I did not understand. This is the question: Let's look at the FALSE language: Collect all the verses P in the form of ...
14 views

### Bus Bandwidth Calculations

I cannot understand this question and the model answer for it and I wonder if anyone here is able to help me. Question: ...
18 views

### Nearest neighbor algorithm for TSP when triangle inequality holds

The output given by this nearest neighbor algorithm for the Travelling Salesman Problem can be arbitrarily bad. In the example constructed here, the triangle inequality doesn't hold in most cases. Let ...
23 views

### Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, prove $L(M)=CLIQUE$

Given graph $G=(V,E)$ and weight function $w\,:\,E\to\mathbb{N}$, function $f(G,w)$ finds the heaviest clique in the graph, when the sum of a clique is the sum of the weights on all of the edges. I ...
22 views

### comparision based sorting algorithms

The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a ...
27 views

### Can the “closest neighbor” algorithm get arbitrarily bad in TSP?

Let's consider the following simple algorithm for attacking the Travelling Salesman Problem: Choose the pair of cities $(A,B)$ where $A\neq B$ and the distance between $A, B$ is minimal amongst all ...
38 views

### SUBSET SUM reduction to PARTITION

This is the PARTITION problem: Given a multiset S of positive integers, decide if it can be partitioned into two equal-sum subsets. This is the SUBSET SUM problem: Given a multiset S of integers ...
47 views

### What is the complexity of computing $C(n + m, m)$?

$C$ here represents combinations. $$C(n + m, m) = \frac{(n + m)!}{n! m!} = \frac{(n + m) * (n + m - 1) * \ldots * (n + 1)}{m!}$$ In this formula it looks like it's $O(m)$ because both the numerator ...
17 views

### Minimum weight $k-$path cover on a DAG proof verification

Suppose you are given a directed acyclic graph $G$ with $n$ vertices and an integer $k \leq n$. Each edge has an associated weight $w(u,v)$. We want to find $k-$vertex-disjoint paths that cover all ...
28 views

### What is the nature of the two bits of data held in a computer memory cell?

I hope this question doesn't offend anyone. I start off by saying that I have and always had difficulty understand the language used in computer science so I have to interpret everything into the ...
43 views

### Designing a context free grammar for a language

Design a grammar for the language $$F = \{x^a y^b zx^b y^a\mid a, b\geq 1\}$$ I'm trying to get a stronger grasp of designing grammars for languages. A thorough explanation of how to design the ...
34 views

### What is the name of this data structure?

I am trying to solve a problem efficiently. The problem is to recurse over a set $\{0,1,\dots,n-1\}$ (as array) in ascending or descending order, while removing or re-adding items in $O(1)$ time. A ...
79 views

### Proving that a problem is not FPT using reduction

In the Inclusive Vertex Cover problem, For a given graph $G=(V,E)$, each vertex $u\in V(G)$ has weight $u_{w} \in \mathbb{N}$ and value $u_{v}\in \mathbb{N}$. The value and weight of a set cover $S$ ...
52 views

### Merging all adjacent and overlapping rectangles in a grid to bigger rectangles

I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where ...