All Questions

0
votes
0answers
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: ...
0
votes
0answers
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 ...
2
votes
1answer
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$ ...
-3
votes
0answers
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 (...
0
votes
3answers
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 ...
0
votes
1answer
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 ...
2
votes
0answers
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 ...
0
votes
0answers
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/...
2
votes
3answers
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 ...
0
votes
0answers
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: $$\...
-2
votes
0answers
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
2
votes
1answer
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 ...
21
votes
2answers
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 ...
0
votes
0answers
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$ ...
-1
votes
0answers
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 ...
2
votes
1answer
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 ...
0
votes
0answers
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 ...
-1
votes
1answer
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 ...
-2
votes
1answer
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 ...
1
vote
0answers
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 ...
1
vote
1answer
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 ...
0
votes
2answers
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.
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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,...
0
votes
0answers
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?
0
votes
0answers
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 ...
0
votes
0answers
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 ...
2
votes
1answer
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? ...
0
votes
2answers
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 ...
5
votes
1answer
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 ...
2
votes
2answers
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 ...
7
votes
1answer
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 ...
1
vote
2answers
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 ...
6
votes
2answers
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 ...
-2
votes
1answer
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.
-3
votes
0answers
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 ...
0
votes
1answer
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 ...
3
votes
2answers
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 ...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
1
vote
2answers
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 ...
1
vote
2answers
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 ...
3
votes
1answer
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 ...
2
votes
2answers
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 ...
4
votes
1answer
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 ...
4
votes
2answers
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 ...
-4
votes
2answers
41 views

What is the language L, generated by the grammar G?

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?
-2
votes
2answers
57 views

How to solve equations using big Θ [duplicate]

How would I prove that the statement $10n^3+3n=Θ(n^3)$ is true/false?

15 30 50 per page