Questions related to design and analysis of algorithms
2
votes
1answer
10 views
Expected number of times heapify will be called
I need to analyze the time complexity of an algorithm to keep track of minimum $K$ numbers from a stream of $R$ numbers . The algorithm is
...
0
votes
0answers
5 views
Locate an index with a recursive approach
Given an array of n integers $A [0 \ldots n-1]$, such that $∀ i, 0 ≤ i ≤ n$, we have that $|A [i]-A [i +1] | ≤ 1$, and if $A [0] = x$, $A [n-1] = y$, we have that $x <y$. Locate the index $j$ such ...
0
votes
1answer
9 views
Given a set X and z ∉ X indicate between which would be immediate positions z in X
Im studying for the computer science subject test as an exercise i need to provide a pseudocode for this problem recursively or with an iterative aproach. The problem is as fllows:
Given a set $X$ ...
0
votes
0answers
43 views
How to calculate Complexity Time O()? [duplicate]
Can anybody give me a way that i can use to calculate Complexity Time problems, i mean a way that will work on any complex code whatever it was.
I can solve basic problems, but whenever the problem ...
0
votes
0answers
17 views
Problem with storing an existing triangulation in a DCEL
I am new to StackExchange, and I already made the mistake of posting a new question as a response to a previous question. Here, I rewrote my question more clearly and separately.
I am trying to store ...
1
vote
1answer
12 views
Immediate positions algorithm?
Im studying for the computer science subject GRE test, as an exercise i need to implement the followin algorithm in java, any idea on how to aproach it?.
Given a set $X$ and $z$ not in $X$, indicate ...
5
votes
0answers
37 views
Minimal size of contracting a DAG into a new DAG
We have a DAG. We have a function on the nodes such that $F(x)=n|x\in V,n\in \mathbb N$ (losely speaking, we number the nodes). We would like to create a new directional graph with these rules:
...
0
votes
0answers
10 views
Python Simple Problem [migrated]
I'm trying to write a simple python algorithm to solve this problem. Can you please help me figure out why my code is not working:
Problem:
Jakub is trying out a one-dimensional keyboard. It ...
0
votes
0answers
7 views
Python algorithm not working [migrated]
I'm trying to write a simple python algorithm to solve this problem. Can you please help me figure out why my code is not working:
Problem:
If any character is repeated more than 4 times, the ...
0
votes
1answer
13 views
FFT for expanded form of equation multiplication
I know how to use the FFT for multiplying two equations in $O(n\,log\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?
For example, if you are multiplying ...
-1
votes
0answers
22 views
the answer to the question 1.4 of the book the design of approximation algorithms david p. williamson
In the uncapacitated facility location problem, we have a set of clients $D$ and a set of facilities $F$. For each client $j\in D$ and facility $i\in F$, there is a cost $c_{ij}$ of ...
0
votes
0answers
40 views
Assigning Groups based on Preference List (Take 2)
I have been working on a problem I am having, and have gotten to the point that I need some help.
I am trying to assign groups of people based on a list of preferences. I asked a question about this ...
0
votes
2answers
66 views
Fundamental algorithms in formal language-automata theory
I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ...
0
votes
1answer
25 views
MapReduce Pseudocode
Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents:
...
-1
votes
0answers
12 views
MapReduce Example [closed]
Is this an example of a MapReduce Problem:
Suppose we want to do the following: $1+2 + \cdots + 10$. This is the master problem. Then we delegate the following to worker nodes:
$$1+2$$ $$3+4$$ ...
