All Questions

6 views

What is Least-Constraining-Value?

In constraint satisfaction problems, heuristics can be used to improve the performance of a bactracking solver. Three commonly given heuristics for simple backtracking solvers are: ...
11 views

Can NP-Hard be converted to NP?

I get that all problems in NP can be reduced in polynomial time to some NP-Hard problem. An NP-Hard problem is also supposed to be harder or at least as hard as any NP problem. Can an NP-Hard problem ...
6 views

Prove the complexity of Heap sort

everyone! The question is that if all elements are different, in the best case HeapSort would work O(n log(n)). Stating that HeapSort takes O(n) to build the heap, then O((n-1)log(n)) to push ...
6 views

Subset sum algorithm time complexity [on hold]

Algorithm: INPUT: An ordered set of integers S and an integer N. For i := 1 to |S|: Let x equal the sum of the first i numbers from the set S (ordered from smallest up). If x equals N then a ...
21 views

Finding median of three sorted array (the same length)

I think about following problem: There are given three sorted arrays $A,B,C$ (each of them is length $n$). Every array has distinct elements. Find median of union $A,B,C$. I consider following ...
20 views

efficient cumulative all over combinations of boolean vector elements

Problem Given a vector of bools of length n I wish to compute the logical and over all subsets up to length k. By logical ...
27 views

How to progress from writing toy example to real programs [on hold]

How does one continue from the basic stuff of programming such as; variables, loops, classes, objects and arrays, to more advanced topic that can actually do things. An example. I wrote a grocery ...
10 views

What graph to plot in order to meet theinstructions and apply the Bellman algo?

I'm actually studying the Bellman algorithm. I have to draw a graph from this array. \begin{array}{|l|c|r|B|d|} Rhythme & A & B& C& D\\ \hline Normal & 5 & - & - & -\\ ...
12 views

A variation of the baseball elimination problem

I suppose you are all familiar with the baseball elimination problem (it is about determining whether some team with particular number of points can finish in the first place, when there are still ...
25 views

Number of subnet IP

The address of a class B host is to be split into subnets with a 6-bit subnet number. What is the maximum number of subnets and the maximum number of hosts in each subnet? What would be the total ...
9 views

Ways to perform “batch” Approximate Member Queries efficiently

In this problem, I'm first given n number of values which I have to store in a space efficient manner. Then I'm given m number ...
12 views

What bit patterns are represented by the following hexadecimal pattern? [on hold]

What bit patterns are represented by the following hexadecimal pattern? 5FD97 I already figured out the number. But is it 010111111101100100000111 or 01011111110110010111? I'm not sure which one is ...
44 views

I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results?

I have a piece of code that applies recursive Binary and Ternary searches on sorted arrays of increasing size, i.e. 500, 1000, 2000, 4000, etc. The entire code segment is about 200 lines so I've been ...
21 views

Efficient algorithms for dealing with linear algebra over the rationals

I'm an academic mathematician. While trying to verify a counterexample to something in my research, the following computational problem has arisen: Fix a vector space $V = \mathbb{Q}^n$. Here $n$ ...
15 views

NFA and regular expressions [on hold]

I'm trying to draw the regular expression: epsilon + a(a+b)* + (a+b)aa(a+b). Do I draw each of the three terms independently, and then link them with an epsilon? So will the final NFA have three ...
540 views

Can a regular expression be infinite?

I know that languages which can be defined using regular expressions and those recognisable by DFA/NFA ( finite automata's ) are equivalent. Also no DFA exists for the language $\{0^n1^n|n \ge 0\}$. ...
11 views

Fastest “Narrowest” Path Algorithm [on hold]

Ive an opposite of a widest path problem in which given a connected weighted undirected graph, I am to find the max edge weight of a path from s to t whose maximum edge weight is the minimum of all ...
25 views

Computing mod inverse?

How might one compute $4^{-1} \mod 17$ I know the answer is 13. I'm just not sure how to arrive at that number, and can't find any good explanations. Any help would be great
6 views

Any possibility to assign character array to float array [on hold]

We know that we can use ATOF function as : float = atof () this is used to assign character array to float variable, but is there any way to assign character array to float array?
16 views

Selection algorithm variant for an array

Have a problem that's a variant of the linear time selection algorithm of a randomized array that I'm struggling with. Let $A = A[1], ..., A[n]$ be an array of $n \ge 4$ distinct keys. ...
15 views

Backpropagation for 'Classification' Neural Network

Question: How does one formulate a back propagation algorithm (either batch, gradient, anything that works) for a neural net, playing a game of Tic Tac Toe? (Java is being utilized) Scenario: There ...
23 views

Determine the move in which a LOGO turtle crosses a point that it has already visited

I was given the following problem in an test (at codility.com) A turtle starts at (0, 0) on a cartesian graph. We have a non-empty zero-indexed "moves" list that contains positive integer ...
13 views

Root Color of a Black Red Tree

It is required that, in a black red tree, the color for the root is always black. However, wikipedia argues that this rule can be omitted as a red root can always be changed to black but not vice ...
14 views

20 views

Hey there.can anyone tell me what genetic algorithm is [on hold]

What are genetic algorithm in simple concept in artificial intelligence with examples
19 views

Expressing a computer program [on hold]

If I want to express a computer program as a function of some variables, what would be those variables? for eg, the memory used, or API calls it made... etc
24 views

How to calculate computation cost matrix using DAG? [on hold]

I take it from journal, here how they are calculated computation cost matrix using DAG In distributed computing task to be schedule, they are using application DAG to calculate execution time, data ...
53 views

Optimal schedule for broadcasting a file in a complete graph with overheads

I am trying to solve the following problem and despite having performed quite extensive literature review, I do not seem to find any similar problem or technique that would be useful here. PROBLEM ...
22 views

How to check the ability to satisfy demand?

We have Stocks in several discrete positions, let say: A B C 40 20 80 And Demand, which may be satisfied by one or more Stock positions (if no specified ...
37 views

Find pairs in an array that when multiplied to each other gives you sum x

So this is the pseudo code I came up with but the run time is very slow. Is there a way to write this code to get it in terms of O(n)? First for loop (starts at 0) grabs the first value of the array ...
49 views

What's the Big O of this algorithm? And Why?

I am stuck by analyzing the Big O of the following algorithm: ...
24 views

Adder circuit with sign bit (not twos complement)

I've found and implemented a full adder to be able to do unsigned or two's complement addition on wikipedia: https://en.wikipedia.org/wiki/Adder_(electronics)#Full_adder However, in my particular ...
37 views

Generative power of new grammars/ language-generating systems [on hold]

[Edited] When defining new grammars or language-generating systems, how do we find to what extend their generative capacity are? I am trying to compare it with Chomsky languages - by building ...
50 views

Is this a new compression approach?

I've come up with an idea on how to compress data. But I'm not sure if the approach already exists. I would like to know if it does already, and if so, what its name is. The approach is to: Convert ...
27 views

How to speed up process of finding duplicates/similar items in a large amount of strings?

Our software receives documents (in the order of tens of thousands) from various providers, each document flows through a number of steps, one of those steps finds duplicates and similar documents ...
612 views

how to count total number of increasing subarrays in c++ [on hold]

suppose an array is given as {1,4,2,3}. A subarray A[i, j], where 1 ≤ i ≤ j ≤ N, is a sequence of integers A[i], A[i+1], ..., A[j]. A subarray A[i, j] is non-decreasing if A[i] ≤ A[i+1] ≤ A[i+2] ≤ ... ...
33 views

Help me visualize this question! [on hold]

What is it asking me? WHAT AM I LOOKING FOR? An ArrayA contains n - 1 unique integers in the range [0; n-1]. That is, there is one number in this range that is not in A. Describe in pseudo-code an ...
9 views

Modal logic- tableaux solver [on hold]

I am currently learning theory of Modal logic. Since, I am aiming to implement tableaux solver for some modal logics, I would like to find out what programming language would be the best for this ...
10 views

stuck on this problem- computer networks [on hold]

Hi i'm stuck on this problem and unsure how to handle this. I would appreciate if anyone could point me to a good reference or provide a formula for this. ...
29 views

Hex Bit Pattern to IEEE 754 standard Floating Point Number

The question asks for the decimal number that 0x0C000000 represents if it is a floating number. I'm not too sure on how to approach this, but here's my thought process: 0x0C000000 = 0000 1100 0000 ...
25 views

How can I minimize a time value given by a graph depending on a cost value given by another graph?

Consider a company that wants to lunch a new subsidiary. To do so, four phases are needed: A, B, C, D which have to be done in this order. The length of each depends on how much money is invested in ...
46 views

What is the maximum number of classes resulting from partitioning by DFA as function of number of states?

I was wondering whether it is possible (and if so, then how) to tell what is the maximum number of equivalence classes generated by a DFA as per Myhill-Nerode theorem (assuming it has no redundant ...
45 views

How to solve this problem about algorithm designing? [on hold]

In Gutenberg’s printing press, each line of text is assembled by placing individual metal letters in a rack, applying ink to the letters and then pressing them onto paper. Gutenberg needs to print ...