# Search Results

• ### Allocation algorithm help, using Python.

##### - by Az
Hi there, I've been working on this general allocation algorithm for students. The pseudocode for it (a Python implementation) is: for a student in a dictionary of students: for student's preference in a set of preferences (ordered from 1 to 10): let temp_project be the first preferred project check if temp_project is available if so, allocate it to them and make the project UNavailable to others Quite simply this will try to allocate projects by starting from their most preferred. The way it works, out of a set of say 100 projects, you list 10 you would want to do. So the 10th project wouldn't be the "least preferred overall" but rather the least preferred in their chosen set, which isn't so bad. Obviously if it can't allocate a project, a student just reverts to the base case which is an allocation of None, with a rank of 11. What I'm doing is calculating the allocation "quality" based on a weighted sum of the ranks. So the lower the numbers (i.e. more highly preferred projects), the better the allocation quality (i.e. more students have highly preferred projects). That's basically what I've currently got. Simple and it works. Now I'm working on this algorithm that tries to minimise the allocation weight locally (this pseudocode is a bit messy, sorry). The only reason this will probably work is because my "search space" as it is, isn't particularly large (just a very general, anecdotal observation, mind you). Since the project is only specific to my Department, we have their own limits imposed. So the number of students can't exceed 100 and the number of preferences won't exceed 10. for student in a dictionary/list/whatever of students: where i = 0 take the (i)st student, (i+1)nd student for their ranks: allocate the projects and set local_weighting to be sum(student_i.alloc_proj_rank, student_i+1.alloc_proj_rank) these are the cases: if local_weighting is 2 (i.e. both ranks are 1): then i += 1 and and continue above if local weighting is = N>2 (i.e. one or more ranks are greater than 1): let temp_local_weighting be N: pick student with lowest rank and then move him to his next rank and pick the other student and reallocate his project after this if temp_local_weighting is < N: then allocate those projects to the students move student with lowest rank to the next rank and reallocate other if temp_local_weighting < previous_temp_allocation: let these be the new allocated projects try moving for the lowest rank and reallocate other else: if this weighting => previous_weighting let these be the allocated projects i += 1 and move on for the rest of the students So, questions: This is sort of a modification of simulated annealing, but any sort of comments on this would be appreciated. How would I keep track of which student is (i) and which student is (i+1) If my overall list of students is 100, then the thing would mess up on (i+1) = 101 since there is none. How can I circumvent that? Any immediate flaws that can be spotted? Extra info: My students dictionary is designed as such: students[student_id] = Student(student_id, student_name, alloc_proj, alloc_proj_rank, preferences) where preferences is in the form of a dictionary such that preferences[rank] = {project_id}

• ### image processing algorithm in MATLAB

##### - by user261002
I am trying to reconstruct an algorithm belong to this paper: Decomposition of biospeckle images in temporary spectral bands Here is an explanation of the algorithm: We recorded a sequence of N successive speckle images with a sampling frequency fs. In this way it was possible to observe how a pixel evolves through the N images. That evolution can be treated as a time series and can be processed in the following way: Each signal corresponding to the evolution of every pixel was used as input to a bank of filters. The intensity values were previously divided by their temporal mean value to minimize local differences in reflectivity or illumination of the object. The maximum frequency that can be adequately analyzed is determined by the sampling theorem and s half of sampling frequency fs. The latter is set by the CCD camera, the size of the image, and the frame grabber. The bank of filters is outlined in Fig. 1. In our case, ten 5° order Butterworth11 filters were used, but this number can be varied according to the required discrimination. The bank was implemented in a computer using MATLAB software. We chose the Butter-worth filter because, in addition to its simplicity, it is maximally flat. Other filters, an infinite impulse response, or a finite impulse response could be used. By means of this bank of filters, ten corresponding signals of each filter of each temporary pixel evolution were obtained as output. Average energy Eb in each signal was then calculated: where pb(n) is the intensity of the filtered pixel in the nth image for filter b divided by its mean value and N is the total number of images. In this way, en values of energy for each pixel were obtained, each of hem belonging to one of the frequency bands in Fig. 1. With these values it is possible to build ten images of the active object, each one of which shows how much energy of time-varying speckle there is in a certain frequency band. False color assignment to the gray levels in the results would help in discrimination. and here is my MATLAB code base on that : clear all for i=0:39 str = num2str(i); str1 = strcat(str,'.mat'); load(str1); D{i+1}=A; end new_max = max(max(A)); new_min = min(min(A)); for i=20:180 for j=20:140 ts = []; for k=1:40 ts = [ts D{k}(i,j)]; %%% kth image pixel i,j --- ts is time series end ts = double(ts); temp = mean(ts); ts = ts-temp; ts = ts/temp; N = 5; % filter order W = [0.00001 0.05;0.05 0.1;0.1 0.15;0.15 0.20;0.20 0.25;0.25 0.30;0.30 0.35;0.35 0.40;0.40 0.45;0.45 0.50]; N1 = 5; for ind = 1:10 Wn = W(ind,:); [B,A] = butter(N1,Wn); ts_f(ind,:) = filter(B,A,ts); end for ind=1:10 imag_test1{ind}(i,j) =sum((ts_f(ind,:)./mean(ts_f(ind,:))).^2); end end end for i=1:10 temp_imag = imag_test1{i}(:,:); x=isnan(temp_imag); temp_imag(x)=0; temp_imag=medfilt2(temp_imag); t_max = max(max(temp_imag)); t_min = min(min(temp_imag)); temp_imag = (temp_imag-t_min).*(double(new_max-new_min)/double(t_max-t_min))+double(new_min); imag_test2{i}(:,:) = temp_imag; end for i=1:10 A=imag_test2{i}(:,:); B=A/max(max(A)); B=histeq(B); figure,imshow(B) colorbar end but I am not getting the same result as paper. has anybody has aby idea why? or where I have gone wrong? Refrence Link to the paper

• ### Optimizing WordWrap Algorithm

##### - by Milo
I have a word-wrap algorithm that basically generates lines of text that fit the width of the text. Unfortunately, it gets slow when I add too much text. I was wondering if I oversaw any major optimizations that could be made. Also, if anyone has a design that would still allow strings of lines or string pointers of lines that is better I'd be open to rewriting the algorithm. Thanks void AguiTextBox::makeLinesFromWordWrap() { textRows.clear(); textRows.push_back(""); std::string curStr; std::string curWord; int curWordWidth = 0; int curLetterWidth = 0; int curLineWidth = 0; bool isVscroll = isVScrollNeeded(); int voffset = 0; if(isVscroll) { voffset = pChildVScroll->getWidth(); } int AdjWidthMinusVoffset = getAdjustedWidth() - voffset; int len = getTextLength(); int bytesSkipped = 0; int letterLength = 0; size_t ind = 0; for(int i = 0; i < len; ++i) { //get the unicode character letterLength = _unicodeFunctions.bringToNextUnichar(ind,getText()); curStr = getText().substr(bytesSkipped,letterLength); bytesSkipped += letterLength; curLetterWidth = getFont().getTextWidth(curStr); //push a new line if(curStr[0] == '\n') { textRows.back() += curWord; curWord = ""; curLetterWidth = 0; curWordWidth = 0; curLineWidth = 0; textRows.push_back(""); continue; } //ensure word is not longer than the width if(curWordWidth + curLetterWidth >= AdjWidthMinusVoffset && curWord.length() >= 1) { textRows.back() += curWord; textRows.push_back(""); curWord = ""; curWordWidth = 0; curLineWidth = 0; } //add letter to word curWord += curStr; curWordWidth += curLetterWidth; //if we need a Vscroll bar start over if(!isVscroll && isVScrollNeeded()) { isVscroll = true; voffset = pChildVScroll->getWidth(); AdjWidthMinusVoffset = getAdjustedWidth() - voffset; i = -1; curWord = ""; curStr = ""; textRows.clear(); textRows.push_back(""); ind = 0; curWordWidth = 0; curLetterWidth = 0; curLineWidth = 0; bytesSkipped = 0; continue; } if(curLineWidth + curWordWidth >= AdjWidthMinusVoffset && textRows.back().length() >= 1) { textRows.push_back(""); curLineWidth = 0; } if(curStr[0] == ' ' || curStr[0] == '-') { textRows.back() += curWord; curLineWidth += curWordWidth; curWord = ""; curWordWidth = 0; } } if(curWord != "") { textRows.back() += curWord; } updateWidestLine(); }

• ### Good book for THINKING in terms of algorithms?

##### - by chrisgoyal
Before you mark this is a duplicate, let me explain why this is different. Most of the books on algorithms are more of a reference. You basically have a list of algorithms at your disposal. But what happens when you need to create a new algorithm for something? These books don't teach how to think in terms of algorithms. So I'm looking for books that will teach me the thinking-process of creating algorithms. Any good suggestions?

• ### I need to choose a compression algorithm

##### - by chiz
I need to choose a compression algorithm to compress some data. I don't know the type of data I'll be compressing in advance (think of it as kinda like the WinRAR program). I've heard of the following algorithms but I don't know which one I should use. Can anyone post a short list of pros and cons? For my application the first priority is decompression speed; the second priority is space saved. Compression (not decompression) speed is irrelevant. Deflate Implode Plain Huffman bzip2 lzma

• ### Algorithm - find the minimal time

##### - by exTyn
I've found this problem somewhere on the internet, but I'm not sure about the proper solution. I think, that it has to be done by greedy algorithm, however I haven't spend much time thinking about that. I suppose, You may enjoy solving this problem, and I will get my answer. Win-win situation :). Problem N people come to a river in the night. There is a narrow bridge, but it can only hold two people at a time. Because it's night, the torch has to be used when crossing the bridge. Every person can cross the bridge in some (given) time (person n1 can cross the bridge in t1 time, person n2 in t2 time etc.). When two people cross the bridge together, they must move at the slower person's pace. What is the mimimal time for the whole grup to cross the bridge?

• ### Properties of bad fibonacci algorithm

##### - by John Smith
I was looking at the canonical bad fibonacci algorithm the other day: public static int fib(int n) { // Base Case if (n < 2) return 1; else return fib(n-1) + fib(n-2); } I made the interesting observation. When you call fib(n), then for k between 1 and n fib(k) is called precisely fib(n-k+1) times (or fib(n-k) depending on your definition of fib(0) ). Also, fib(0) is called fib(n-k-1) times. This then allows me to find that in fib(100) there are exactly 708449696358523830149 calls to the fib function. Are there other interesting observations on this function you know of?

• ### Interval tree algorithm that supports merging of intervals with no overlap

##### - by Dave Griffiths
I'm looking for an interval tree algorithm similar to the red-black interval tree in CLR but that supports merging of intervals by default so that there are never any overlapping intervals. In other words if you had a tree containing two intervals [2,3] and [5,6] and you added the interval [4,4], the result would be a tree containing just one interval [2,6]. Thanks Update: the use case I'm considering is calculating transitive closure. Interval sets are used to store the successor sets because they have been found to be quite compact. But if you represent interval sets just as a linked list I have found that in some situations they can become quite large and hence so does the time required to find the insertion point. Hence my interest in interval trees. Also there may be quite a lot of merging one tree with another (i.e. a set OR operation) - if both trees are large then it may be better to create a new tree using inorder walks of both trees rather than repeated insertions of each interval.

• ### Algorithm to generate numerical concept hierarchy

##### - by Christophe Herreman
I have a couple of numerical datasets that I need to create a concept hierarchy for. For now, I have been doing this manually by observing the data (and a corresponding linechart). Based on my intuition, I created some acceptable hierarchies. This seems like a task that can be automated. Does anyone know if there is an algorithm to generate a concept hierarchy for numerical data? To give an example, I have the following dataset: Bangladesh 521 Brazil 8295 Burma 446 China 3259 Congo 2952 Egypt 2162 Ethiopia 333 France 46037 Germany 44729 India 1017 Indonesia 2239 Iran 4600 Italy 38996 Japan 38457 Mexico 10200 Nigeria 1401 Pakistan 1022 Philippines 1845 Russia 11807 South Africa 5685 Thailand 4116 Turkey 10479 UK 43734 US 47440 Vietnam 1042 for which I created the following hierarchy: LOWEST ( < 1000) LOW (1000 - 2500) MEDIUM (2501 - 7500) HIGH (7501 - 30000) HIGHEST ( 30000)

• ### Algorithm for analyzing text of words

##### - by Click Upvote
I want an algorithm which would create all possible phrases in a block of text. For example, in the text: "My username is click upvote. I have 4k rep on stackoverflow" It would create the following combinations: "My username" "My Username is" "username is click" "is click" "is click upvote" "click upvote" "i have" "i have 4k" "have 4k" .. You get the idea. Basically the point is to get all possible combinations of 'phrases' out of a sentence. Any thoughts for how to best implement this?

• ### Time complexity of Sieve of Eratosthenes algorithm

##### - by eSKay
From Wikipedia: The complexity of the algorithm is O(n(logn)(loglogn)) bit operations. How do you arrive at that? That the complexity includes the loglogn term tells me that there is a sqrt(n) somewhere. Suppose I am running the sieve on the first 100 numbers (n = 100), assuming that marking the numbers as composite takes constant time (array implementation), the number of times we use mark_composite() would be something like n/2 + n/3 + n/5 + n/7 + ... + n/97 = O(n) And to find the next prime number (for example to jump to 7 after crossing out all the numbers that are multiples of 5), the number of operations would be O(n). So, the complexity would be O(n^2). Do you agree?

• ### Robust and fast checksum algorithm?

##### - by bene
Which checksum algorithm can you recommend in the following use case? I want to generate checksums of small JPEG files (~8 kB each) to check if the content changed. Using the filesystem's date modified is unfortunately not an option. The checksum need not be cryptographically strong but it should robustly indicate changes of any size. The second criterion is speed since it should be possible to process at least hundreds of images per second (on a modern CPU). The calculation will be done on a server with several clients. The clients send the images over Gigabit TCP to the server. So there's no disk I/O as bottleneck.

• ### Modifying Bresenham's line algorithm

##### - by sphennings
I'm trying to use Bresenham's line algorithm to compute Field of View on a grid. The code I'm using calculates the lines without a problem but I'm having problems getting it to always return the line running from start point to endpoint. What do I need to do so that all lines returned run from (x0,y0) to (x1,y1) def bresenham_line(self, x0, y0, x1, y1): steep = abs(y1 - y0) > abs(x1 - x0) if steep: x0, y0 = y0, x0 x1, y1 = y1, x1 if x0 > x1: x0, x1 = x1, x0 y0, y1 = y1, y0 if y0 < y1: ystep = 1 else: ystep = -1 deltax = x1 - x0 deltay = abs(y1 - y0) error = -deltax / 2 y = y0 line = [] for x in range(x0, x1 + 1): if steep: line.append((y,x)) else: line.append((x,y)) error = error + deltay if error > 0: y = y + ystep error = error - deltax return line

• ### How to generate a unique hash for a URL ?

##### - by Jacques René Mesrine
Given these two images from twitter. http://a3.twimg.com/profile_images/130500759/lowres_profilepic.jpg http://a1.twimg.com/profile_images/58079916/lowres_profilepic.jpg I want to download them to local filesystem & store them in a single directory. How shall I overcome name conflicts ? In the example above, I cannot store them as *lowres_profilepic.jpg*. My design idea is treat the URLs as opaque strings except for the last segment. What algorithms (implemented as f) can I use to hash the prefixes into unique strings. f( "http://a3.twimg.com/profile_images/130500759/" ) = 6tgjsdjfjdhgf f( "http://a1.twimg.com/profile_images/58079916/" ) = iuhd87ysdfhdk That way, I can save the files as:- 6tgjsdjfjdhgf_lowres_profilepic.jpg iuhd87ysdfhdk_lowres_profilepic.jpg I don't want a cryptographic algorithm as it this needs to be a performant operation.

• ### which is best algorithm?

##### - by Lopa
Consider two algorithms A and B which solve the same problem, and have time complexities (in terms of the number of elementary operations they perform) given respectively by a(n) = 9n+6 b(n) = 2(n^2)+1 (i) Which algorithm is the best asymptotically? (ii) Which is the best for small input sizes n, and for what values of n is this the case? (You may assume where necessary that n0.) i think its 9n+6. guys could you please help me with whether its right or wrong?? and whats the answer for part b. what exactly do they want?

• ### jump search algorithm

##### - by davit-datuashvili
i am doing jump search algorithm but it show me that element is not in array while it is here is code import java.math.*; public class jamp { public static int min(int a,int b){ return a } public static void main(String[]args){ int a[]=new int[]{3,7,9,12,14,15,16,17,18}; int l=14; System.out.println(jumpsearch(a,a.length,l)); } public static int jumpsearch(int a[],int n, int l ){ int t=0; int b=(int)Math.sqrt(n); while (a[min(b,n)-1]=n) return -1 ; } while (a[t] return -1 ; if ( a[t]==l) { return t; } } return -1; } } please help

• ### Computational geometry: find where the triangle is after rotation, translation or reflection on a mi

##### - by newba
I have a small contest problem in which is given a set of points, in 2D, that form a triangle. This triangle may be subject to an arbitrary rotation, may be subject to an arbitrary translation (both in the 2D plane) and may be subject to a reflection on a mirror, but its dimensions were kept unchanged. Then, they give me a set of points in the plane, and I have to find 3 points that form my triangle after one or more of those geometric operations. Example: 5 15 8 5 20 10 6 5 17 5 20 20 5 10 5 15 20 15 10 I bet that have to apply some known algorithm, but I don't know which. The most common are: convex hull, sweep plane, triangulation, etc. Can someone give a tip? I don't need the code, only a push, please!

• ### fast algorithm to sort very small set

##### - by aaa
hello. This is the problem I ran into long time ago. I thought I may ask your for your ideas. assume I have very small set of numbers (integers), 4 or 8 elements, that need to be sorted, fast. what would be the best approach/algorithm? my approach was to use the max/min functions only. At this point it becomes somewhat hardware dependent , so let us assume Intel 64-bit processor with SSE3 . Thanks

• ### Tail-recursive pow() algorithm with memoization?

##### - by Dan
I'm looking for an algorithm to compute pow() that's tail-recursive and uses memoization to speed up repeated calculations. Performance isn't an issue; this is mostly an intellectual exercise - I spent a train ride coming up with all the different pow() implementations I could, but was unable to come up with one that I was happy with that had these two properties. My best shot was the following: def calc_tailrec_mem(base, exp, cache_line={}, acc=1, ctr=0): if exp == 0: return 1 elif exp == 1: return acc * base elif exp in cache_line: val = acc * cache_line[exp] cache_line[exp + ctr] = val return val else: cache_line[ctr] = acc return calc_tailrec_mem(base, exp-1, cache_line, acc * base, ctr + 1) It works, but it doesn't memorize the results of all calculations - only those with exponents 1..exp/2 and exp.

• ### algorithm diagram

##### - by tunl
This is the max searching algorithm diagram: So, I wonder how can draw diagram for Recursion in HaNoi Tower program: package tunl; public class TowersApp { static int n = 3; public static void main(String[] args) { TowersApp.doTowers(3, 'A', 'B', 'C'); } public static void doTowers(int n, char from, char inter, char to) { if (n == 1) { System.out.println("disk 1 from "+ from + " to " + to); } else { doTowers(n-1, from, to, inter); System.out.println("disk " + n + " from " + from + " to " + to); doTowers(n-1, inter, from, to); } } } I can't draw it. Anyone can help me !!!

##### - by Il-Bhima
I'm working on a multithreaded program where I have a number of worker threads performing tasks of unequal length. I want to load-balance the tasks to ensure that they do roughly the same amount of work. For task T_i I have a number c_i which provides a good approximation to the amount of work that is required for that task. I'm looking for an efficient (O(N) N = num tasks or better) algorithm which will give me "roughly" a good load balance given the values of c_i. It doesn't have to be optimal, but I would like to be able to have some theoretical bounds on how bad the resulting allocations are. Any ideas?

• ### Algorithm: Build a recommendation for movies you might like

##### - by Faruz
I need help designing an algorithm for recommendations on movies. Every user in the system grades movies on a score between 1-100. Tables consist of: Table Movies ID Name Year Rating Runtime Table Con_MoviesToGenres MovieID GenreID Table Con_MovieToUser MovieID UserID Grade I'm trying to build a SELECT query to return 5 most recommended movies for a specific movie. Bearing in mind, I want to integrate in some way, similar genres, highest grades & movie Rating (so you want be recommended an R rated movie for a PG rated movie, unless it's really recommended in every other aspect). Also, if movie matches more than one genre, it will increase its recommendation ratio. Bonus: If a user gives a low grade to a movie - it will lose recommendation ratio.

• ### Looking for evolutionary music example code

##### - by Dan Dyer
I would like to implement an interactive evolutionary algorithm for generating music (probably just simple melodies to start with). I'd like to use JFugue for this. Its website claims that it is well-suited to evolutionary music, but I can't find any evolutionary examples. I already have a framework to provide the evolutonary machinery. What I am looking for is some simple, working code that demonstrates viable approaches for the musical part (e.g. suitable encodings and evolutionary operators for the evolved tunes). I have some ideas how it might be achieved, but I'm not particularly knowledgeable about music theory, so to start with I'd like to just reimplement something that is known to work. So does anybody have, or know of, any freely available code (any language is fine) that demonstrates one or more approaches to evolutionary music? EDIT: I'm specifically looking for evolutionary code rather than other techniques that could be used for music synthesis.

• ### Algorithm question.

##### - by Lukasz Lew
I can't solve it: You are given 8 integers: A, B, C representing a line on a plane with equation A*x + B*y = C a, b, c representing another line x, y representing a point on a plane The two lines are not parallel therefore divide plane into 4 pieces. Point (x, y) lies inside of one these pieces. Problem: Write a fast algorithm that will find a point with integer coordinates in the same piece as (x,y) that is closest to the cross point of the two given lines. Note: This is not a homework, this is old Euler-type task that I have absolutely no idea how to approach.