Posts Tagged by algorithm
Practical Earley Parsing (Aycock & Horspool 2002): How to add back pointers?
September 17, 2014  Posted by forumadmin under TechQns 
Comments off

I’ve already coded an Earley parser with back pointers but it doesn’t handle nullable grammars very well. I’ve also implemented Aycock & Horspool 2002’s solution which is to make PREDICT skip over the nonterminal token if it is nullable. Unfortunately this does not tell you exactly which particular path the token needs to take to […]
How does this Javascript decrypter work?
September 7, 2014  Posted by forumadmin under TechQns 
Comments off

I have found these two Javascript decrypters around the web. I know nill about decryption, but from short research it looks like some base62 permutation encryption/decryption. Both decryptors receive code split into arrays of 3 strings each, with each string containing an encrypted portion of the code. I couldn’t find any consistency or patterns in […]
Tracing this algorithim, is my trace right?
August 30, 2014  Posted by forumadmin under TechQns 
Comments off

For a classwork problem I am doing, I am supposed to trace (check for bugs) the following algorithm (in psuedocode): num < 2 count < 1 while count < 5 { count < count * num if count / 2 < 2 print “Hello” else while count < 7 { count < count + 1 […]
Divide it into 2 groups such that No two people who know each other are together?
August 28, 2014  Posted by forumadmin under TechQns 
Comments off

The Question is: We have a delegation of 4 people and I want to divide it in 2 groups such that no two individual, who knows each other are together. Given example: There are 4 people coming for delegation. 1 <————> 2(1 knows 2) 1 <————> 3(1 knows 3) 2 <————> 4(2 knows 4) Now […]
Arange array of positive and negative numbers
August 28, 2014  Posted by forumadmin under TechQns 
Comments off

Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and viceversa maintaining the order of appearance. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If […]
Finding Minimal lexicographical Array
August 28, 2014  Posted by forumadmin under TechQns 
Comments off

I tried solving this interview question. My code runs for test cases but fails for all the real input test cases. I tried hard to find the mistake but unable to do so. Please find my code below the question Bob loves sorting very much. He is always thinking of new ways to sort an […]
using insertion sort once in quicksort
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

According to here Use insertion sort…for invocations on small arrays (i.e. where the length is less than a threshold k determined experimentally). This can be implemented by simply stopping the recursion when less than k elements are left, leaving the entire array ksorted: each element will be at most k positions away from its final […]
Evenly distributing byte array into buckets
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I’m trying to implement a minimal perfect hash function, and one of the primary ways to to this is to be able to take the known universe of keys and split them into decently even buckets of a small size (the smaller the better within reason). The problem is I cant figure out how to […]
What is the easier way to initialize a matrix in Python?
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I’m working in a 2D matrix with a simple polynomial algorithm: for i in range(len(content1)): for j in range(len(content2)): if content1[i]==content2[j]: matrix[i][j]=1 else: matrix[i][j]=0 This code itself do not compile for a simple reason. dot_matrix is not initialized. So what is the easier way to do that? Also, how could I implement the same logic […]
How to find the longest distance along a vector within a polygon?
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

Given a direction vector and an arbitrary polygon (which can be nonconvex), what is an efficient algorithm to find the longest straight line along the vector bounded by the polygon? note: the original problem is given a triangle, find the largest bounded similar triangle within a given polygon, which I thought it could be translated […]
Complexity and explanation of a part of a C program which uses data structures
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

We have the following piece of a C program.I want to understand what this part of code does and its complexity. void sortLike (node* p) node* q; node* min; node *head = (struct node*) malloc (sizeof (struct node)); head>next = L; p = head; // We have to sort the list,obviously.We have the variable p […]
Are there Algorithms for generating textures using vector primitives?
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I’m doing image generation with Canvas, for fun and I’d like to generate textures using canvas alone. That is I’d like to stay just in canvas and generate paper, stone, sand, wood textures. I’ve tried but they tend to remain vector looking. But, I’m wondering if there are algorithms that I could look at to […]
How can I define and associate functions to form arbitrary objects?
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I have the following problem. I have a list of conditions that are mapped to a function. E.g. employee_count which is evaluated by a function that does a query in the database that is as simple as count the employee number. Another could be employee_age which returns the employees above or bellow a certain age […]
Rearrange array in alternating positive & negative items with O(1) extra space
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

Given an array of positive and negative numbers, arrange them in an alternate fashion such that every positive number is followed by negative and viceversa maintaining the order of appearance. Number of positive and negative numbers need not be equal. If there are more positive numbers they appear at the end of the array. If […]
siftdown heapsort algorithm code
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

As I have just started on algorithms, I came across this website(http://pages.cpsc.ucalgary.ca/~boyd/331/heaps.html) and saw a algorithm on sift down and couldn’t understand the whole siftdown algorithm at all. procedure siftdown( T[1..n], i ) k = i repeat j = k if 2j <= n and T[2j] > T[k] then k = 2j if 2j < […]
How to design an algorithm that iterates through many lists in an unknown order at compile time?
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I’m creating a program which processes data according to userdefined settings. During the processing, I have a few related lists that must be iterated through according to these userdefined settings; the user decides the order in which these lists are iterated through. I’m wondering how I can design an algorithm for iterating though these lists […]
GJK (Gilbert–Johnson–Keerthi collision) algorithm fail
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I implemented this 3D GJK algorithm in fortran but it fails sometimes: module GJK implicit none integer ( kind = 4 ) :: maxInteraction = 30 contains function cross (a, b) real ( kind = 8 ) :: cross (3) real ( kind = 8 ), intent(in) :: a (3), b (3) cross(1) = a(2) […]
Finding groups of k disjoint rows in a matrix
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

Problem statement: Let S be a set of integers, e.g. S = {1,2,…,12}. M is an integer matrix whose rows can be viewed as subsets of S, whose length divides the number of elements of S, in particular every row of M contains only distinct elements/integers. I am trying to produce Matlab code that can […]
all solutions to change making with dynamic programming
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I was reviewing my handouts for our algorithm class and I started to think about this question: Given different types of coins with different values, find all coin configurations to add up to a certain sum without duplication. During class, we solved the problem to find the number of all possible ways for a sum […]
Many independent pseudorandom graphs each with same arbitrary y for any input x
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

By ‘graph’ I mean ‘function’ in the mathematical sense, where you always find one unchanging y value per x value. Python’s random.Random class’s seed behaves as the xcoordinate of a random graph and each new call to random.random() gives a new random graph with all new xy mappings. Is there a way to directly refer […]
Optimized way to find if a number is a perfect square
August 27, 2014  Posted by forumadmin under TechQns 
Comments off

I had a question in my assignment to find whether a number was perfect square or not: Perfect square is an element of algebraic structure which is equal to the square of another element. For example: 4, 9, 16 etc. What my friends did is, if n is the number, they looped n – 1 […]
General Method for Handling Fragmented input from a socket
August 26, 2014  Posted by forumadmin under TechQns 
Comments off

This question is a little generic, but I’ve found myself coming up against it in various situations over the last couple of years, so figured there must be a standard solution. I was wondering if there were standard algorithms for handling situations whereby data is being read from some kind of socket/stream, using some kind […]
Who has more related friends in FB
July 29, 2014  Posted by forumadmin under TechQns 
Comments off

I’m developing one application, that will have multiple Facebook users. I’m trying to figure out the best way of knowing who (from a list of up to about 20), has most connections (friends) with others from that list. So, let’s say this situation: list = [A, B, C, D, E, F...]; where, A is friend […]
NZEC Error C# Identify
July 28, 2014  Posted by forumadmin under TechQns 
Comments off

Hey I am trying to do a code challenge and I have coded this following code. One test case gets success, but all others get a runtime error NZEC error. I am stuck with this for two days. Please help me. Problem Statement: Bob loves sorting very much. He is always thinking of new ways […]
What factors are best for image resizing?
July 22, 2014  Posted by forumadmin under TechQns 
Comments off

Let’s say I have an image that is 3000 px wide. I know (at least I think I do) that if I downsize it to be 1500 px wide (that is, 50%), the result will be better than if I resize it to be 1499 or 1501 px wide. I suppose that will be so […]
Wrong algorithm: AES or Rijndael required when encrypting with AES/DES with padding
July 22, 2014  Posted by forumadmin under TechQns 
Comments off

The other questions were somewhat helpful but I wanted to know if there is a method to do this all. I have a program that encrypts the inputted text and also lets the user select which encryption algorithm to use and what padding to use with that algorithm. The supported algorithms are AES/DES/Blowfish. Without padding, […]
Wave generation with the "Hugo Elias" algorithm please! Java
July 15, 2014  Posted by forumadmin under TechQns 
Comments off

I appear to have hit a wall in my most recent project involving wave/ripple generation over an image. I made one that works with basic colors on a grid that works perfectly; heck, I even added shades to the colors depending on the height of the wave. However, my overall goal was to make this […]
Finding intersection between sets of points describing a curve
July 14, 2014  Posted by forumadmin under TechQns 
Comments off

Say I have two sets of points p1, p2, p3,… ,pn and q1, q2, q3,…, qn which describe two paths (curves) in a plane. The points may not be evenly sampled from the curve, but they are “in order” (with regard to parameterizations of the curves). What is a good way to find out where […]
How to avoid StackOverflowError caused by the number of recursion calls in Java?
July 14, 2014  Posted by forumadmin under TechQns 
Comments off

I want to solve this problem: https://www.hackerrank.com/challenges/findmedian ,i.e. find the median element in unsorted array. To do this I perform quickselect algorithm. My program works correctly on my computer. However when I submitted in the system it gave me StackOverflowError. I think this is because of the depth of the recursion calls. I guess I […]
Whats the time complexity of this algorithm for Palindrome Partitioning?
July 6, 2014  Posted by forumadmin under TechQns 
Comments off

Palindrome Partitioning Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. Personally I think, the time complexity is O(n^n), n is the length of the given string. Thank you Dan Roche, the tight time complexity = O(n* (2^n)), check details below. […]
Java: bring value in [0,1] range
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

If I have a LinkedList of double with positive and negative value, for example: [1000, 34, 0, 700, 12] How I can do to bring in [0,1] range? If I have only positive number I can do: (x – Xmin) / (XmaxXmin) But with both positive and negative value? Asked By – Neptune […]
Algorithm for Shortest Path with a contraint, BFS or DFS
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Question stated as follow: Given a map which has some obstacles in it. Given a starting point S and ending point E, find the shortest path from S to E. Note you can choose any(4) direction from S, but during the process, you can only go straight from the previous direction, unless you hit an […]
Shellsort – if an array is gsorted then hsorted, the array is still gsorted
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Following is an exercise from coursera’s algorithm course from Princeton. If an array is both 3sorted and 5sorted, then is it also 6, 7, 8, 9, and 10sorted ? I know that any sequence if gsorted then hsorted, it still is gsorted. But how does this explain the question? If an array is 3sorted and […]
iterative kary tree pre and postorder traversal
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

I have a kary tree, and I want to traverse it using iteration. It is a scene graph, so every time I encounter a transform node I put its matrix on a stack, and every time a encounter a mesh node it is rendered using the matrixstack. This both must be pre order. But when […]
Modifying Dijkstras algorithm for least changes
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

I’m using a version of Dijkstra’s algorithm written in Python which I found online, and it works great. But because this is for bus routes, changing 10 times might be the shortest route, but probably not the quickest and definitely not the easiest. I need to modify it somehow to return the path with the […]
Linked list implementation in assembly
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Here’s my linked list implementation: node: node struc prev dw 0 next dw 0 data dw 0 node ends this function adds new node: tail – pointer to linked list’s tail _data – data we want to append node_add proc near c tail:word, _data_:word mov bx,tail mov ax,[bx] .if ax==0 ;if there’s no any nodes […]
Unity3d Terrain Generation Instantiates to much prefabs
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

I’ve got a block of code in my ‘Update()’ function wich gets the active chunk in my scene, when it has found that chunk, it passes those coordinates to the ‘generateFromMiddleOfChunk()’ function. That function will generate all the chunks in a 3 radius around the player, it does that with 25 ‘Instantiate()’ functions and a […]
Asymptotic Tight Bound for Quadratic Functions, revisited
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

The overall question I’d like to ask has been answered here in the accepted answer: asymptotic tight bound for quadratic functions but I’d like to focus on a subpart of the answer that I can’t understand. Specifically, it is this part: “So we can bound from above the inside of the sqrt(…) with 4b^2″. I […]
Minimum sum with subarray length > 0
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Given an array of numbers, find the minimum sum and the subarray cannot be of length 0. I know I can use kadane’s algorithm but the question requires that the length of subarray should not be 0. Hence, my implementation can’t handle the cases where all the elements of the array are positive. For example, […]
"for" loop hanging itself in recursive algorithm
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

I was trying to create a specific version of the minmax algorithm, but unfortunately it doesn’t seem to work as intended. The function pasted below should generate every possible outcome(scenario) for tictactoe and fill a list with nonnegative results. Unfortunately, it doesn’t seem to work it appears to suddenly stop (not crash it still works, […]
How to increase bitrate of file transmission over the sound card?
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

I need to transfer files using only the sound card. my algorithm so far is based on amplitude shift keying (ASK). Transmitter: The program writes to a WAV file the modulated data. Simply write “noise” (create wave) when the bit is 1, and write “silence” (0 amplitude) otherwise. The number of samples for silence and […]
Linear time when running merge sort and quick sort
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

As far I learned from my University, it is proved that the lower bound of an comparisonbased algorithm that sorts random data is Ω(nlogn). I also know that the average case of Heapsort and Quicksort is O(nlgn). Therefore, I tried to plot the times these algorithms needed to sort a set of random data. I […]
Difference between elements of array exceds a value K
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

i have an array lets say A[]={ 4 8 9 10 15 25 } // (sorted) and i have 2 index .say 2 ,4 (indexing of array starts from 0) I need to find whether difference between any 2 successive element between these 2 index exceeds a value K. example if index1=2(value equal to 9) […]
How to make a 2D matrix with desired number of submatrices?
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Hi I am working on my own personal project and need to build a 2D matrix( I am coding in c++) with only 4 numbers (11 12 13 14). Also the condition given is that the number of submatrices in the 2D matrix should be as close (preferrably equal to) some number which is user […]
Grouping Algorithm
July 5, 2014  Posted by forumadmin under TechQns 
Comments off

Fruits = [ {name:apple, color:red, taste:good, price:medium}, {name:apple, color:red, taste:bad, price:medium}, {name:apple, color:red, taste:good, price:low}, {name:apple, color:red, taste:bad, price:medium}, {name:apple, color:red, taste:good, price:medium}, {name:apple, color:green, taste:bad, price:medium}, {name:apple, color:green, taste:bad, price:medium} ]; Here I want to count apples of one kind, i.e apples which are red, taste good & price medium, for this type the […]
Offset/limit to page/size conversion
July 2, 2014  Posted by forumadmin under TechQns 
Comments off

This should be an interresting challenge. I’m looking for an algorithm that doesn’t exist yet (to the best of my knowledge) We have a database accessing function that can read pages of records at a time, using a pagenumber and pagesize as arguments. Lets call this function getFromDatabase(int page, int size). We want to offer […]
Database for saving date span
July 2, 2014  Posted by forumadmin under TechQns 
Comments off

I have a question generally about database design. I need to store price for different room types for different hotels for different dates. The date could be a interval or it could be specific weekdays during that time interval, and the interval is totally random. So there are two solutions I try to evaluate: Store […]
c – skyline algorithm confusion
May 27, 2014  Posted by forumadmin under TechQns 
Comments off

I am trying to write a code which gives coordinates of corners of a skyline, it was one of my friends’ homework and I am trying it as a practice for myself. So, here is my code: #include <stdio.h> #include <stdlib.h> typedef struct building { int start, height, width; } BUILDING; int main() { FILE […]
Algorithm for register allocation
May 1, 2014  Posted by forumadmin under TechQns 
Comments off

I’m trying to implement a code generation/register allocation algorithm for Trees in favor of my old one, where I put everything on stack. Now I’m trying to implement SethiUllman algorithm but from only contents I’ve found on Wikipedia and some web pages some parts of the algorithm remain unclear to me. I’m looking for an […]
A way to simplify the following code
April 27, 2014  Posted by forumadmin under TechQns 
Comments off

I have the following code, written in Matlab, to find the combination MW of three units: Units 1, 2 and 3. The logic is the following: Combine total of Unit 1, store it. Combine total of Unit 2, store it. Combine total of Unit 3, store it. Combine total of Unit 1 and Unit 2, […]