# All Questions

29,681 questions
32 views

### Show that for each even n, there exists a graph with n vertices, such that the 2-approx VC alg returns a VC which is exactly twice the Minimum-VC

Question: Show that for each even n, there exists a graph with n vertices, such that the ALG(algorithm) returns a vertex cover which is exactly twice the size of minimum vertex cover. Define ALG: ...
12 views

### Decision Tables Column Colouring

I am learning about decision tables and am confused by the colouring in the text book's mark scheme for a question I'm working on. I can not see why some of the columns have been coloured grey. Rather ...
47 views

### Prove that the next multiple of 4 is obtained using the next formula

I was reading an assembly procedure that needed to align addresses on 4 bytes boundary for performance reasons so it has used the next statement that i formulated as a theorem to be proven. Let $s$ ...
40 views

### Does P=NP? (The big question) [closed]

If you know much about theoretical computer science, you have heard the question before. This site has plenty of questions posted about the implications of one answer or another to this question (...
96 views

### Solving recurrence equation $T(n)=T(n^{2/3})+17$

How can the following recurrence equation be solved by one of three main ways: $$T(n)=T(n^{2/3})+17$$ I have tried solving it by the iteration way. However it does not work for me since I can't find ...
36 views

### Complexity of an encoded turing machine

This is an example of an assignment question, there are 3 of them so I created my own in order to better understand it. First, we have the variable m which is a ...
9 views

### Graph Layout: Fixed node locations

I'm aware of a large amount of literature on the problem of graph layout. Usually this involves taking a list of nodes and edges, and choosing locations and paths for both respectively. Are there any ...
9 views

### How to print a multi class ROC plot? [closed]

I am making classifier of 4 classes and I need to print the ROC graph of it. I have the metrics (TP, FP, TN, FN), now I am using this link to print ROC - https://scikit-learn.org/stable/auto_examples/...
62 views

### NP-hard in what parameter?

I often read statements such as "the run-time of algorithm X is polynomial in m and n". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one ...
69 views

### Definition of M-type in type theory

According to nLab, M-types are the dual of W-types. What are the introduction and elimination rules for M-types? Edit: For example, the formation/introduction/elimination rules for W-types are: \...
23 views

### DFA where number of 0s or 1s or both are divisible by 2 [duplicate]

Design a DFA for the language defined over {0,1} where number of 0s or 1s or both are divisible by 2
75 views

### Can all $O(n)$ problems be solved without nested loops?

There are examples of algorithm implementations that contain nested loops but are of complexity O(n), and some of them have corresponding implementations that contain no nested loops. So here comes a ...
5k views

### If I can solve Sudoku, can I solve the Travelling Salesman Problem (TSP)? If so, how?

Let us say there is a program such that if you give a partially filled Sudoku of any size it gives you corresponding completed Sudoku. Can you treat this program as a black box and use this to solve ...
14 views

### BP as an operator

The class $BP.C$ (BP operator applied to the complexity class C) is defined as in this paper. $BP.C$ is the set of all languages $L$ such that there is some polynomial $p$ and some set $A \in C$ ...
8 views

### Simple HTML code and integrating CSS, Python, and JavaScript with the existing HTML code [closed]

Tonight I started programming a makeshift webpage thats not really a webpage. I downloaded Notepad++, opened it and started writing HTML code. I am making a table of information that has (at the ...
42 views

### How to partition a set in order to minimize the number of the elements and their interactions?

Given two sets $S_1$ and $S_2$ of $n$ elements each. Each set $S_1$ (resp. $S_2$) has a revenue $R_1$ (resp. $R_2$). Each element $i$ of $S_1$ (resp. $S_2$) has a gain $g_{i1}$ (resp. $g_{i2}$). From ...
11 views

### Data Instructions [closed]

Asking for your answer on this questions. Memory Map and the initial contents of each internal register 0200:0000 FF 8A 41 E6 29 DE FA AC 11 11 94 72 07 25 11 28 0200:0010 EC E1 ...
21 views

### Why object non-optional ignore its weak property? [Swift] [closed]

I have 2 classes Car and Owner, they have weak preference to each other. After I assign nil to one object. That object is still not deallocated. Like code bellow, as far as I understand object vinfast ...
26 views

### FSM (Finite State Automaton and PDA (Push Down Automaton

Say we have the following language, some number of a's and b's followed by three a's followed by some number of a's and b's Show how you can create a finite state machine that will accept the words ...
52 views

### How to find big-O for an in-place perfect shuffle algorithm

I've found a simple algorithm to interleave two halves of an array in place. It involves swapping the first 1/2 of the items into the correct place, then unscrambling the permutation of the 1/4 of ...
50 views

### Combinatorial Optimization: Shortest distance given sets of drivers and riders

Problem: I have 2 sets, one of drivers and one of riders. All my participants need to reach one common destination. I wish to calculate the shortest combined distance in order for all participant to ...
51 views

### Is it possible to make partition of Quicksort run in O(lg n)?

I was thinking maybe I can make it 2T(n/2) + C split the list into two halves and work on them recursively to partition the list.
27 views

### Show that the following languages are equal [duplicate]

I have the following exercise: Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$. My idea was to write the words of each of the languages in the following way,for example for the ...
39 views

### Brute Force Approach for LCS and its Time Complexity

I have read several Algorithm books where it is been told brute force approach of Longest Common Subsequence takes 2^n which is exponential time complexity. Whereas, I've noticed that while I am ...
38 views

### construct regular expression for a language [duplicate]

I want a regular expression for the following language. (a+b+c)*, but does not contain substring "abab". That means it can be any combination of (a, b, c) except "abab". I tryed to construct it ...
15 views

### Finding current levels when encoding information in a channel

I am stuck with the following question: In a noised channel with a bandwidth of 4 kHz that has the signal-noise ratio of 30 decibels, if it is known that the maximal broadcasting speed is 16000 bps,...
16 views

### Kernel Language vs Computation Model [closed]

Suppose that a certain Kernel Language (let's call it KL) operates according to a certain Computation Model (Programming Paradigm), let's call it CM. My question is: is KL or CM defined first?
13 views

### Code to enter Passwords into pptx [closed]

I intend to start a new project to create a code (ideally in Python) for a Brute Force algorithm and A Dictionary Search algorithm. I wish to test it on a MS Powerpoint File. However, I don't know how ...
13 views

### Maximal number of parallel cellular calls with no adjacent cells in a hexagonal setting

Is it possible to find an optimization to the following theoretical case? Given is a cellular (phone) system with hexagonal cells, where the volume of transmission and the size of the cells are ...
253 views

### Implicit nil checks in algorithms

I am reading algorithms in a CS book where a potentially nil value is passed to a function, but neither the caller nor the callee check if the value is nil. Is this a common practice in algorithms? ...
20 views

### How to find the big o running time if the recursion function have different cases of recursion with different fraction of n?

How to find the big o running time if the recursion function have different cases of recursion with different fraction of n? If I have a recursive function like this for example (This is just an ...
36 views

### Partitioning connected graphs in the plane

This is a geographic problem, where we have several connected graphs embedded on the plane, where none of them have overlapping edges/nodes. How can we divide the plane using line segments in such a ...
34 views

### What does Stroustrup mean by 7/8ths of MIPS being in the vector units?

In his article Software Development for Infrastructure Stroustrup states the following: Hardware improvements make the problems and costs resulting from isolating software from hardware far worse ...
87 views

### Proof of Brzozowski's algorithm for DFA minimization?

Brzozowki's algorithm is cited widely. Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it ...
28 views

### Running time complexity of finding maximal power of divisor that divides natural number

Given $n \in \mathbb{N}$, a divisor $p\vert n$, I would like to efficiently find $e\in\mathbb{N}$ with $p^e \vert n$, and $e$ maximal with this property. I will assume that multiplication/division of ...
135 views

### Can this system of polynomial equations be solved in polynomial time?

I have these $n$ equations, with $n$ variables. Variables are first $n$ positive integers, constants can be any rational number including zero. Given that there is always a solution, how do we find a ...
33 views

### Doubt in definition of Float

Can anyone tell the meaning of the bold portion? Float: It is used to store decimal numbers (numbers with floating point value) with single precision.
50 views

### How do I become one of the best programmer in the world? [closed]

I have given my 12 boards and wanted to become an excellent programmer, I wanted to work in big companies like Google what should be my road map. I have heard about hackerrank, Spoj and geeks for ...
36 views

### Expected value of the distance between nodes in a binary tree

If there are 16 leaves in a full binary tree and two nodes $a$ and $b$ chosen at random, then what is the expected value of the distance between $a$ and $b$ in T? My question here is, how do I ...
31 views

### Minimizing catastrophic risk in Gale-Shapley matching

In the hospital-resident assignment problem we have to match a large set of med students with a small set of hospitals. Hospitals may accept multiple students, but the number of students is much ...
19 views

### Communication complexity: fooling set bound for inner product function

I am trying to prove that the fooling set method does not give a good lower bound for the communication complexity of the inner product function. Specifically, I am trying to show that the best bound ...
12 views

### Proving k-partition problem is NP [duplicate]

For any integer k ≥ 2, the k-Partition problem is said to be a sequence of positive integers (w1, w2, . . . , wn), is it possible to partition them into k groups having equal sums? I'm confused on ...
118 views

### Amortized analysis of max-heap

Consider an ordinary binary max-heap data structure with $n$ elements that supports insert and extract-max in $O(\log n)$ worst-case time. Question: If extract max is $O(1)$ amortized does that ...
40 views

### Can someone explain why the MAX-CUT problem is in NP?

Given an undirected graph $G = (V, E)$ and an integer $k$, is there a partition of the vertices into two (nonempty, nonoverlapping) subsets so that $k$ or more edges have one end in each subset? I'm ...
65 views

### 3SAT instance with EXACTLY 3 instances of each literal

I'm trying to solve a question which requires me to prove that an instance of 3SAT where each literal appears in exactly 3 clauses (positive and negative appearances combined) and each clause ...
22 views

### O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?

Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem. If s = little string and S = len(s) b = big string and ...
60 views

### Smallest convex set containing given point

Given a set $M$ of $m$ points in $R^n$, where the number of points $m$ is much larger than the dimension $n$, and given a point $x$ in $R^n$ that we may assume is in the convex closure of $M$, is ...
521 views

### Prove that the total distance is minimised (when travelling across the longest path)

Here is the problem: Given a tree $T$, I need to visit every node in the tree once. I can start and end anywhere I want. I would like to travel the least distance possible when doing so. I don't have ...
Given the grammar $G = (Ν, Σ, Π, S)$, where $Ν = \{S\}$, $Σ = \{0, 1\}$, $Π = \{S → ε, S → 0, S → 1, S → 0S0, S → 1S1\}$, and $S$ is $S$. What is the language generated by the grammar?
How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?