All Questions

Filter by
Sorted by
Tagged with
0
votes
0answers
4 views

Python “list” anamoly [closed]

visited = [[False] * 4] * 4 visited[0][0] = True visited I created a list here. ...
4
votes
1answer
16 views

The same outgoing and incoming degree in graph

I have an undirected graph with $n$ vertices and $m$ edges. How to determinate in $poly (n, m)$, is it possible (and how is it necessary) to orient all the edges so that each vertex has the same ...
1
vote
0answers
6 views

A genral turing model with one tape to define sublinear space (L,NL,..)

A genral turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
0
votes
0answers
19 views

Is it true that if you solve an NP-complete problem in non-polynomial time, the solution also solves other NP-complete problems as well?

This relates to an answer for this question. The opinion said that: Personally, I don’t see much value in coding interviews. The problems I’ve seen asked as coding questions have been (for the most ...
0
votes
0answers
10 views

segmentation fault (core dumped) error when I try to reverse a huge text file?

I'm trying to reverse a text file with 500,000 words and I get a segmentation fault (core dumped) error, how am I able to fix this? thank you. ...
1
vote
1answer
16 views

AEP with a Twist!

We know by AEP that if random variables $X_1,X_2,...$ are i.i.d. drawn from $P_X$ then the probability of the vectors in the weak typical set $$A_{\epsilon}^n = \{\vec x \in \mathcal{X}^n: |\frac{-1}{...
0
votes
1answer
22 views

Is automaton not practical in real coding?

This question relates with this question and answer. May I know why "Writing a structured program for any tangle of an automaton is possible in principle, but probably not worth the hassle (...
1
vote
0answers
24 views

Playing video games to solve SAT instances

This paper shows that computer games, such as Super Mario, are NP-hard, by reduction from SAT. It may be possible to use this reduction to help solve hard instances of SAT: use the reduction to ...
0
votes
0answers
8 views

to draw ER diagram in DBMS

In one of my assignment I am asked to draw an ER diagram but the following question I am unable to do. Can you please help me to do it as it is part of my assignment. Q: A student uses a particular ...
0
votes
1answer
14 views

Example for Database architecture

PHPMyadmin is stated as a 3 tier database architecture.How is this possible,Isn't it a 2 tier architecture.What are the real world examples of 1-tier and 2-tier architecture.
0
votes
1answer
16 views

Biparite maxium matching with added constraints

Suppose you have two lists as follows List A = $(a_1, a_2, ..., a_m)$ List B = $(b_1, b_2, ..., b_n)$ Each element in list A can be paired with many or no elements in list B. I have a function $f(a_i, ...
0
votes
0answers
17 views

How would I convert separate digits to an actual number?

In Dr. Racket, how would I combine the digits w, x, y, z to wxyz (for example 3, 7, 8, 9 to 3,789)? I haven't gotten very far on this: (define digits-to-numbers w x y z)
-1
votes
0answers
9 views

Big-$\mathcal{O}$ Complexity of Converting a Base 10 Integer to Base $b$ [duplicate]

Let $N$ be a positive integer. (1) I would like to convert $N$ to base-$2$ (2) I would like to convert $N$ to base-$b$, where $b$ is an arbitrary base. Question: How may I accomplish this in a ...
0
votes
3answers
43 views

If a function f(n) belongs to big Theta, then will f(n/x) also belong?

Suppose the following is true for some f(n) and g(n): $f(n) = \Theta(g(n))$ Does that mean $f(n/x) = \Theta(g(n))$ for any x values > 0? I know that for the above to be true, there must exist ...
2
votes
1answer
12 views

Sufficient condition for $xy^*z \subseteq L$ for a DFA with $n$ states

In chapter 2 of the New Turing Omnibus, the author considers an unknown finite automata with 6 states. Through trial and error, it is deduced that the words 0101, 0100101, 0100100101 are accepted. It ...
2
votes
1answer
14 views

Nielsen & Chuang Exercise 3.15: Lower bound for compare-and-swap based sorts

From Nielsen & Chuang (page 138): Suppose an $n$ element list is sorted by applying some sequence of compare-and-swap operations to the list. There are $n!$ possible initial orderings of the list....
1
vote
0answers
27 views

Are intersection and union redundant? Possibility to get smaller output without negation?

I've just started learning relational algebra, so I'm reading a lot of articles for this topic. Not so long ago I've encountered two statements that seem to be quite weird to me. ∩ and ∪ (...
0
votes
1answer
38 views

Converting Decimal Numbers between 0 and 1 to Binary

I've been playing around with a program I wrote that converts decimal numbers to binary numbers and i've noticed that eventually, after applying the algorithm (multiply by 2, subtract 1 if greater ...
1
vote
0answers
8 views

How does an assembler manage varying offsets when using a literal pool?

I am trying to write a simple multi-pass assembler. Wikipedia states that: Multi-pass assemblers create a table with all symbols and their values in the first passes, then use the table in later ...
1
vote
0answers
15 views
1
vote
2answers
42 views

Is a file a string of zeros and ones?

Is a computer file just a string of zeroes and ones? If so, can it start with zeroes? I have not been able to find an answer, surprisingly.
-2
votes
1answer
26 views

“what does the 1 to 10 mean?” FOR number ← 1 TO 10

"what does the to 10 mean?" FOR number ← 1 TO 10
0
votes
0answers
10 views

libraries to be learnt for getting the job as data scientist having strong knowledge in python [closed]

now I am confused to go in which path either into data science field or web development field through python. If I choose the data science field what frameworks and libraries I need to learn? and If I ...
-1
votes
0answers
28 views

Are some algorithms inherently recursive “like”?

Are some algorithms inherently recursive "like" ? As in, rewriting it in tail-recursive/iterative form a stack is still needed. Struggled to implement ...
0
votes
0answers
20 views

Proving the L' = {w|deleting one symbol from a string in L} is regular when L is regular

I have looked up a question like this online and found this solution. I couldn't understand what the new NFA A' looks like. Could anyone give me an example of NFA A'?
1
vote
1answer
21 views

Algorithm for maximizing the number of same-sized groups

Let's say you have groups of objects, and a certain amount of objects you can add to these groups (you cannot create new groups, and do not necessarily have to use all your extra objects), and the ...
2
votes
1answer
35 views

Sort half-edges around common vertex in 3d

I'm trying to figure out this problem for very long time and am no getting nowhere. I'm working on a simple 3d modeler that uses half-edge data structure. Say I have non-manifold geometry where two ...
-2
votes
0answers
47 views

What's the name of the program that's used as a sample to test the verbosity/expressiveness of programming languages?

A remember seeing on Wikipedia, a program invented for the purpose of testing how verbose/expressive a programming language is. It's an abstract program specified in pseudocode, consisting of input ...
-2
votes
0answers
22 views

Probability of false positive for lookup in hashtable

I am going over Mikkel Thorups notes on hashing, as revision, and I came to the following exercise that i cannot see how to tackle (even initially - I know this is not ideal for a question.) $$ \...
0
votes
0answers
26 views

3SAT and directed graph

Given a 3SAT instance (a Boolean expression in three conjunctural normal form), we draw a directed graph, where for each Boolean variable $x_{i}$ we have the nodes $x_{i}$ and $!x_{i}$; for each ...
2
votes
1answer
22 views

Minimize range of distances between two sets of points

I have two sets of n points each in 2D Cartesian coordinates. I want to find a one-to-one pairing between the points in sets A ...
1
vote
1answer
15 views

SGD statistical guarantee

I have a question regard online learning with SGD. Is there a way to give a statistical guarantee that the value obtained after $n$ samples deviates at most $\epsilon$ from the real value? Thank you ...
1
vote
1answer
44 views

Count subset divisible by 3

I'm trying to solve this puzzle but I get stuck. I thought about trying to use the law of total probability to solve intermediate problems with subset of size $k$ but it didn't helped me that much. Is ...
1
vote
2answers
11 views

PDA for a language where the second part is not the reverse of the first part

I came across an exercise for constructing a PDA for the following language: $$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$ Where $L \subseteq ({a,b,c})^*$ So $n$ and $m$ are both a ...
2
votes
0answers
14 views

Find a maximum flow that also maximizes the flow over a specific edge

Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the ...
-2
votes
0answers
13 views

Left-linear and right-linear grammars

My task is to find left-linear and right-linear grammars for the following languag: L1:={w ∈ {a,b}*|w does not include the subword abaab} My solution for right-linear: $$\text{S → bS | aA | λ}\\\text{...
1
vote
2answers
29 views

Do languages in $\mathsf{coRE} \setminus \mathsf{R}$ have Turing machines?

What can we say about languages in $\mathsf{coRE} \setminus \mathsf{R}$? Are there Turing machines for these languages? I know that $\overline{HP} \in \mathsf{coRE}$ doesn't have a Turing machine, and ...
0
votes
0answers
15 views

Risc-V extension for dismissible loads

Certain architectures have "dismissible loads" in addition to normal loads: when the load is denied, instead of issuing an exception (leading to a segmentation fault), a default value (e.g., ...
0
votes
0answers
19 views

How to traverse the order relationship between string elements in linear time [closed]

I have a string and I want to get the order relationship between string elements in linear time. For example, the string "abc", there are three partial order relations, namely ab, bc, ac
0
votes
0answers
21 views

Operating system scheduling doubt

Consider a uniprocessor system executing three tasks T1,T2 and T3 each of which is composed of an infinite sequence of jobs (or instances) which arrive periodically at intervals of 3, 7 and 20 ...
0
votes
0answers
9 views

can virtual address map any on virtual memory on disk?

I was reading a textbook which says that: If the valid bit is set, the address field indicates the start of the corresponding physical page in DRAM where the virtual page is cached. If the valid bit ...
1
vote
1answer
25 views

Floating-point oblivious way to compute multiset numbers

I have to compute $R = \left(\!\!{n + 1\choose k}\!\!\right)$, which happens to be: $$ R = \left(\!\!{n+1\choose k }\!\!\right) = \binom{n+k}{k} = \frac{(n + k)!}{n!k!} = \frac{(n+1)(n+2)\cdots(n+k)}{...
2
votes
2answers
33 views

What roadblocks are there to HSA becoming standard, similar to floating point units becoming standard?

I remember when my dad explained to me for the first time how a certain model of computer he had came with a "math coprocessor" which made certain math operations much faster than if they ...
0
votes
1answer
23 views

What is the complexity of k-clique problem with a predetermined vertex in the solution?

Clique (from WikiPedia): Clique is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent; that is, its induced subgraph is complete. K-Clique ...
0
votes
1answer
45 views

Knapsack Problem with Constraints on Item Values

Given $n$ items with weights $w_1,...,w_n$ and values $v_1,...,v_n$, and a weight limit $W$, the purpose is still maximizing the total value of items to be carried (while not exceeding the weight ...
2
votes
1answer
81 views
+100

How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?

Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
2
votes
2answers
49 views

Master theorem: what to do with constant in parenthesis?

In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations. What should be done in the case that there is a constant factor in the numerator following T? $$ ...
1
vote
1answer
26 views

How to convert a decision tree to an automaton?

From what I know, a problem can be transformed to a yes/no answer, which can be described by a decision tree. Solution to a problem also can be represented by a set of strings (a language), which ...
-3
votes
0answers
27 views

Question relating to NFA

Is there any NFA that can accept every alternate symbol in a given string. Ex. if w = abab, the NFA should accept bb
1
vote
7answers
3k views

Why can't we say that a Neural Network is a NP problem solver?

From this video lecture from MIT https://youtu.be/moPtwq_cVH8?t=1229 there is mention how NP complexity works with finding a "lucky" algorithm and luck can never be accounted for. The ...

15 30 50 per page
1
2 3 4 5
749