Algorithms Forum RSS Feed

5k+1 array

Sun, 30 Nov 2008 13:51:29 -0700

Hi,

is there any linear time algorithm to solve this problem?

An array of length 5k+1 having k+1 distinct elements with k elements repeating 5 times each. The goal is to find the element which doesn't repeat.
Can we do this in linear time?

O(nlogn) algorithm is to sort the array using any of the standard sorting algorithms and then just find this element. Is there a linear time algo for this?

Thanks.

Finding the proper Algo (2D sorting)

Tue, 25 Nov 2008 16:02:59 -0700

I am supposed to create an O(n(logn)^2) algorithm wich, given as input a sequence S of points in the two dimensions (each point is discribed by a x value and a y value) the algorithm sould give or each point:

the number of elements from which each point is strictly bigger( both x and y bigger)

any help or idea would be appreciated!

Greedy Algorithm Problem: Blocks and Containers

Tue, 25 Nov 2008 07:19:21 -0700

Hello everyone! I have the following problem and I need to find a greedy algorithm which will solve it:

There are N numbered containers (1...N). In the containers, there are blocks in K-colors, but in all containers there is no more than N blocks of the given color.
Capacity of the i-th container is Pi (it can hold maximum of Pi blocks). Find an algorithm that will rearrange the blocks so that in each container there is at most one block each color. In one step, you are allowed to move only one block from the container to its neighbour (from i-th container, you can move a block to either (i+1)-th or (i-1)-th container, you can also move blocks between 1'st and n-th container).

I'd really appreciate any help. Can anyone give me any clues how to solve this problem using a greedy algorithm?
Many thanks.

pathcover..

Mon, 24 Nov 2008 22:33:46 -0700

A path cover of a directed graph is a set of paths such
that every vertex is included in exactly one path. The size of a path cover is the number of paths in the set.
can any one tell me how to reduce the problem of finding
a minimum-sized path cover in a directed acyclic graph to the problem of
finding a maximum-sized matching in a bipartite graph. such that the total running time of the algorithm should be in O(na).

unsigned long long int compression functions

Mon, 24 Nov 2008 11:36:48 -0700

Hello!
It my first post here :)

I need help with unsigned long long int compression for writing it to file.

Any ideas ?

Thanks.

Greedy algorithms

Mon, 17 Nov 2008 04:56:23 -0700

Hi guys, recently i got a theme for my term paper. And it is, as you guessed, Greedy Algorithms. For bad i dont have lots of info about this algorithms and i would be very thankful if u could post here links or send some e-books on my e-mail: tyap4uk@gmail.com or just tell me some interesting tasks dealing with these algorithms . Thanks everybody beforehand

Program for computing Internal path length of binary search tree.

Tue, 11 Nov 2008 23:33:10 -0700

HI Friends,

Can anyone post the program for the question below....

write a program for computing the Internal path length of a binary search tree. Use it to investigate empirically the average number of key comparisons for searching in a randomly generated binary search tree.

Finding an algorithm

Mon, 10 Nov 2008 11:23:00 -0700

Right, first off I am not an advanced programmer and am self taught in what I do know so please keep that in mind.

is it possible to reverse engineer an algorithm, if I had an output code based on multiple events and had all of these events logged and also had multiple instances of this code and the events. Would it be possible to:

a) Write a program that takes all of the data I have collected (output code and input data) and work out the algorithm used to create that code.

b) Use the algorithm with my own input data to create my own codes.

And how would I go about writing a program to do this?

binary search

Fri, 31 Oct 2008 07:51:33 -0700

You are given an infnite array A[] in which the first n cells contain integers in sorted order and
the rest of the cells are filled with1. You are not given the value of n. Describe an algorithm that
takes an integer x as input and finds a position in the array containing x, if such a position exists,
in O(log n) time. (If you are disturbed by the fact that the array A has infnite length, assume
instead that it is of length n, but that you don't know this length, and that the implementation
of the array data type in your programming language returns the error message 1 whenever
elements A[i] with i > n are accessed.)

sorting +VE & -VE numbers

Thu, 16 Oct 2008 05:57:55 -0700

Hi all.
I am trying to sort numbers that are mixed, i.e. positive numbers and negative numbers (with a'-' in front to indicate -ve). I am using the following code that I found on the forum to test:
**********************************************
Public Sub OrderNumbers(ByRef iInputArray() As Integer, ByVal iArraySize As Integer)
Dim iArray() As Integer
Dim iOrdered() As Integer
Dim iCounter As Integer
ReDim iArray(0 To iArraySize - 1)
ReDim iOrdered(0 To iArraySize - 1)

For iCounter = 0 To iArraySize - 1
iArray(iCounter) = iInputArray(iCounter)

Next

For iCounter = 0 To iArraySize - 1
iOrdered(iCounter) = GetLargest(iArray, iArraySize)
iArray(buffer) = 0
Next

For iCounter = 0 To UBound(iOrdered)
iInputArray(iCounter) = iOrdered(iCounter)
Next
End Sub

Private Function GetLargest(ByVal iInputArray() As Integer, ByVal iInputSize As Integer) As Integer
Dim i As Integer
Dim n As Integer
Dim iBuffArray() As Integer
ReDim iBuffArray(0 To iInputSize - 1)

iBuffArray = iInputArray

For i = 0 To iInputSize - 1
If iBuffArray(i) > n Then
n = iBuffArray(i)
buffer = i
End If
Next
GetLargest = n
************************************

I noted that when I put a single negative number with a "-" and debugged, the algorithm 'cannot read' the value and therefore gives me a value of "0".

Any thoughts around this would be appreciated!!!

Tembss

Run Length Encoding problem

Mon, 15 Sep 2008 21:26:23 -0700

Hello!

I have to solve a run length coding problem in matlab, compressing a vector containing integer numbers between 0 and 255, to a new vector with numbers between 0 and 255 using the following method:

* A number 0 ≤ n ≤ 127 in the encoded data means that the following n+1 numbers will be direct copies from the original data
* A number 129 ≤ n ≤ 255 in the encoded data means that the next number has existed 257-n times in a row in the original data
* The number 128 means that the sequence is over.

For example, the following vector: [0 1 2 9 9 9 4 5 6 7]
can be encoded to: [2 0 1 2 254 9 3 4 5 6 7 128]
or to: [9 0 1 2 9 9 9 4 5 6 7 128]
of which each encoding is equally good, since they are equally long (but longer than the original though).

Now I tried to find an algorithm which will always provide an optimal solution to this problem, using dynamic programming, but I realized it was too long since I last solved a similar problem. I just can't figure out how to come up with such an algorithm, but I suspect one could do it with dynamic programming. I would really appreciate if someone could help me out here!

Thanks in advance!

Hamilton subgraph

Tue, 02 Sep 2008 13:09:10 -0700

Hello all,

I have a problem to solve and I'm not able to find a solution.
I'm searching for some algorithm for finding a Hamilton subgraph in an oriented graph.
I don't want to find all subgraphs (i need only one), and it is not necessary to be the subgraph with maximum size (50% from the maximum size would be acceptable). Also, each node has maximum two edges. My problem is that I have a huge number of nodes. But I think that with all the simplifications (not maximum, maximum 2 edges for each nodes) the complexity could be reduced a lot.
If you can recommend some algorithms, sites or functions (can be for pascal, c/c++, visual C, Matlab) I would be very happy. I found many packages and sites on internet but most of them were for undirected graphs, and they can not search for subgraphs (they say: the graph is hamilton and this is the path, or: no hamilton graph -> no path).

Thank you,
KPanda

Free Algorithms ebooks

Tue, 26 Aug 2008 12:13:08 -0700

hi,

You can find really helpful C# books at the following link...

http://books-pdf.blogspot.com/search/label/Algorithms

http://books-pdf.blogspot.com
http://freebooksandmagazines.blogspot.com
http://www.ebooksboard.com/

What Algorithm i should use???

Fri, 22 Aug 2008 00:49:40 -0700

newb here...

currently doing a thesis. my thesis is a game.. a board game...

now my problem is what algorithm should i use when generating a path to

the start point and to end point. the objective is the path must be random when generating in each level also it adds 1*level of block.

what algorithm should I use??? now im currently studying the Breadth first search algorithm and depth first search algorithm. is this the right algos?

tnx

function module

Fri, 08 Aug 2008 05:33:39 -0700

need help to write a sumsquare function module and then rewrite that fuction module into an algorithm from this pseudocode.

count integer
square integer
sumsquare integer
count = 0
square = 1
do while count <= 2
count = count + 1
sumsquare = sumsquare + square
end do

this is not home work or stuff like that, this is a class work which i probably wont get an answer for any time soon.

Spanning tree modification

Sat, 05 Jul 2008 07:36:32 -0700

Hail to you my fellow geeks
I would like to find a polynomial algorithm for the following problem for my project:
Suppose you have a graph (normal, not directed). You want to find a spanning tree (any, doesnt have to be minimum), but it has to respect one rule: the edges are separated into n groups and each of these groups has a positive integer X assigned to it meaning "from this group, no more than X edges can be used in the spanning tree".
Can this be done in polynomial time? Any hints will be greatly appreciated, thanks.

The Cipher Challenge

Thu, 19 Jun 2008 07:40:13 -0700

Hello everyone, my algorithms teacher told us to look for an algorithm solving this problem and explaining it, help is very appreciated as we are not that deep into algorithms yet.

Given a list of 4, 5, 6 ... or 10 integers (between 1 and 100) find the way of getting another integer between 1 and 2000, using only the basic operations: add, substract, multiply and divide. each number in the list can only be used once.

challenge: design, implement and document a solution to the problem, faster than the example program (which I will link later", for sizes between 6 and 10, and that it cannot lose a solution, the program must indicaite all the reachable numbers between 1 and 2000, using the input data.

here is the link, if you need help understanding it just let me know, drop me a message or something

http://dis.um.es/%7Eginesgm/files/cifras.exe

thanks in advance!

Multiple paths in a graph

Fri, 06 Jun 2008 09:07:55 -0700

Hi,

I would like to know if there is any special algorithm to find, in a graph a certain number of paths (say =MAX_PATHS, the case when the number of paths are less than MAX_PATHS must also be taken care of )from a given source to all the other vertices in the graph.
By special I imply that this algorithm must not be like applying the standard algorithms like DFS, BFS etc multiple times by removing the edges already used.

Thanks,
Virajith

Fast multidimensional indexing

Fri, 06 Jun 2008 03:39:02 -0700

I devised an algorithm that, given a set of points in a multidimensional space, can find all the points in an arbitrary box very efficiently.
My algorithm needs space O(n log^(d-1)n) and answers a query, in the worst case, in time O(log^(d-1)n), where d is the dimension of the space.
For instance, if the space is two-dimensional, it requires space O(nlogn) and answers a query, in the worst case, in time O(logn). As you can see, it's *very* fast, but requires some space.
I think it's an important result from a theoretic point of view and not only.
You can find my paper here:
http://wcemdi.blogspot.com/

Technical papers, as always, make algorithms look *much* more complex than they really are. If you want to discuss a part of the paper, you find an error, or there is a point particularly unclear, don't hesitate to ask.

Greener developing and collaboration

Thu, 29 May 2008 13:36:39 -0700

Want to cut down on CO2? Enable in-context collaboration for multi-site software development and collaboration. Find out in Florida! (Tech-Ed related info)

http://www.rationalheroes.com/

Solve quation

Thu, 15 May 2008 02:24:53 -0700

I wish to solve this euqtion to find LC 90 .
I need to figure out the value of concentration which would kill 90% of toxic material.

The value of a,b,c,d is known from regression .

Y%=Exp^(a*con+b)+Exp^(c*con+d)

I need to cut down the quation to find con value.

10%=Exp^(a*con+b)+Exp^(c*con+d) which should give me

con= ?

Could any body help me solve this equation.

Regards
Pac

3D Delauney

Tue, 15 Apr 2008 15:13:08 -0700

Hi

I have a 3D surface in existence which is defined by a series of points. So each point is (x,y,z). Now I need to find the 3D Delauney map of the surface such that I can then find the normals to each polygon (triangle on the surface). I know how the algorithm works, but dont want to re-invent the wheel. Does anyone have a suggestion about where to go to find an algorithm to do this.

1. I don't need to introduce vertices's - these are in existence so the surface is already there.
2. Must be three dimensional.
3. Should be easy to implement and free.

Most grateful for any help. Thanks in advance.

Navigation Systems

Sun, 06 Apr 2008 17:22:53 -0700

Hi guys!

I am doing a research about algorithms used on navigation systems. Can someone give me some links with good information?

Thanks!

Hiding Data in Text File

Wed, 19 Mar 2008 13:29:16 -0700

Hi guys...
I have successded in hiding data in a text file without changing/replacing/distorting any of the readble/printable letters of the text file and even the size of the text file remains unchanged after hiding the data.
All the techniqs that i have checked...change the file size and replace characters/append the data.But my techniq does not change the file size,does not append the data or does not replace/change/distort any readable/printable characters.
Is this techniq already in use or what i am claiming is something new?

amortized analysis time complexity problem

Mon, 17 Mar 2008 15:18:48 -0700

Hi all

Is there anybody who can solve this problem? This is not a easy problem. (At least not for me.)

Here is the problem.

Problem:

Assume that George(S,X) is a function that returns a Boolean value, where S is a stack, and that the time complexity of George is O( log |S| ) , where |S| is the current size of the stack.

Consider the following block of pseudo code.

S <-- the empty stack
For i from 1 to n do
Read (Xi)
While (S! = Ø) and George(S, Xi) do
Pop (S)
End while
Push Xi onto S
End for
Assume that reading, popping and pushing take O (1) time.

Use Amortized analysis to prove that the block of code runs in O (n logn) time.

Please describe your answer in detail if you know the solution.

Any help is appreciated.