An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
0
votes
0answers
7 views
Solving travelling salesman problem using Ant colony optimization in Java
I wrote this program for doing ant colony TSP (travelling salesman problem) like four years ago, and I decided to refactor the code, which led me to this:
Ant.java:
...
2
votes
2answers
55 views
Inversion count algorithm
I implemented the inversion count algorithm using the merge sort approach for this question.
The question begins with a number t = number of test cases and then for each test case you input size of ...
2
votes
0answers
19 views
n-Knapsack and 0/1-Knapsack implementation
It seems alright to me with some basic test cases. The idea is, as I understand, to solve the sub-problems with smaller to bigger weights up until the maximum allowable weight, and to vary the items ...
2
votes
0answers
37 views
Brute force shortest path in Java
I had to ask myself a couple years ago: before Edsger Dijkstra invented his famous shortest path algorithm, how brute force approach would seem. Below is my version. It's super slow, but I find it ...
10
votes
3answers
74 views
Producing and comparing maximum sub array sum algorithms
This is an exercise in implementing the maximum sub-array sum problem.
It asks for several solutions of complexity:
\$O(n)\$
\$O(n \log n)\$
\$O(n^2)\$
\$O(n^3)\$
For an additional challenge I ...
-2
votes
0answers
39 views
Pattern matching in generic lists in Java using naive and Knuth-Morris-Pratt algorithms
Given a sequence of objects \$\langle x_1, x_2, \dots, x_n \rangle\$ and a pattern sequence \$\langle y_1, y_2, \dots, y_m\rangle\$, the pattern matching problem asks, whether there exists an ...
1
vote
4answers
277 views
4
votes
1answer
199 views
4
votes
4answers
87 views
4
votes
4answers
548 views
Plus Minus in Python
You're given an array containing integer values. You need to print the
fraction of count of positive numbers, negative numbers and zeroes to
the total numbers. Print the value of the fractions ...
2
votes
1answer
33 views
Dead-end filling maze solver in Python
I was reading Wikipedia about maze-algorithms, and I decided to write my own maze-solver. It uses dead-end-filling as it seemed simple to implement (it seemed, I said).
The code I wrote is pretty ...
1
vote
3answers
41 views
Diagonal difference
Given
You are given a square matrix of size N×N. Calculate the absolute difference of the sums across the two main diagonals.
Input Format
The first line contains a single integer N. The ...
10
votes
2answers
259 views
Unique value finder
For our first assignment in our algorithm class we are suppose to solve several different questions using information from a 2D array. We are also suppose to optimize our code to get more marks on our ...
1
vote
3answers
217 views
Finding a peak in an array
This finds a peak element in an array. Please consider I want only one peak element. Also, my code should follow only C++11/14 and not C++03.
...
1
vote
2answers
31 views
Decimal to Roman numeral conversion algorithm
I have written a program to convert a decimal to a Roman numeral. I am wondering if my algorithm is okay or not. If it's not okay, I want suggestions on improving my code. This code only works in ...
5
votes
2answers
56 views
Finding prime divisors with wheel factorization
I am just starting to learn C++, and I wrote was the following implementation of the trial division algorithm to find the prime factors of a positive integer. I'm hoping the community here can suggest ...
1
vote
0answers
42 views
Binary Bayes network classifier in Java - Part II/II
This is the continuation of Binary Bayes network classifier in Java - Part I/II
TERMINOLOGY
We are given a directed acyclic graph (dag) \$G = (V, A)\$, where \$V\$ is the set of nodes and \$A ...
3
votes
3answers
91 views
Project Euler #3 Largest prime factor
Given
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
Solution
...
4
votes
2answers
46 views
Memoized implementation of change-making algorithm
Recently, I wrote a simple program to solve the change-making problem. Rather than the tabular dynamic programming solution (described in the link), I tried to write a solution that uses memoization.
...
2
votes
0answers
57 views
Bayesian network query tool in Java
Suppose you are running a business of repairing cars. You know all the parts (graph nodes) and the way they affect other parts (directed edges), and you know the probabilities of each part failing. If ...
5
votes
1answer
81 views
Minimum window substring which includes all the characters from substring
I recently came across this problem which is as follows:
Given a string S and a string T, find the minimum window in S which
will contain all the characters in T in complexity O(n).
For ...
1
vote
0answers
63 views
Apriori algorithm for frequent itemset generation in Java
I have this algorithm for mining frequent itemsets from a database. In that problem, a person may acquire a list of products bought in a grocery store, and he/she wishes to find out which product ...
3
votes
0answers
25 views
Cache with timeout per key
I wrote a general purpose library for in-memory cache with custom timeout for each key.
...
2
votes
0answers
95 views
A simple graph walk interception algorithm in Java
I have that girl whose graph walk I want to intercept, but because I am not good at running algorithms in my head, I had to program my computer to do that for me. I would not consider the problem to ...
6
votes
2answers
88 views
Using BubbleSort to sort numbers into ascending & descending order
I have created a simple implementation of the bubble sort algorithm. I have tried to make it as efficient as possible by following pseudocode which I have provided below, making some slight ...
10
votes
2answers
219 views
The median of the given AVL tree
A long time ago I found this question and asked about an algorithm here.
My code is also available on GitHub.
Given a self-balancing tree (AVL), code a method that returns the
median.
...
4
votes
2answers
60 views
Find duplicate files using Python
Most Python "duplicate file finder" scripts I found do a brute-force of calculating the hashes of all files under a directory. So, I wrote my own -- hopefully faster -- script to kind of do things ...
5
votes
1answer
35 views
Dividing valuable items so that two persons get the most similar value possible
You have n items, each one of those has a certain value, represented here as an integer.
How do you give to two persons the most similar value?
No comment from me here as my code already ...
5
votes
1answer
68 views
Find maximum element in bitonic array
An array is bitonic if it is composed of an increasing sequence of integers followed immediately by a decreasing sequence of integers. Write a program that, given a bitonic array of N distinct ...
6
votes
4answers
221 views
Character to decimal conversion
This converts from character representation of integers to their decimal value:
...
10
votes
1answer
99 views
Calculate the area of rectangles union
I've been given the following task:
Given N rectangles with edges parallel to axis, calculate the area of the union of all rectangles. The input and output are files specified in program ...
12
votes
2answers
720 views
Battleship algorithm
Im looking to improve my search algorithm in my battleship game. Code is not perfect but would appreciate any suggestions or recommendations.
Running the simulation using a 100x100 grid (10,000 ...
7
votes
1answer
60 views
Search iteratively in a ternary search tree
I was trying to write an iterative search function for my Ternary Search Tree class based on a pseudo-code, and now it seems to work, but I think it can definitely be improved.
...
2
votes
2answers
97 views
Sorting dates (DD/MM/YYYY) with insertion sort [closed]
I'm having troubles with a coding problem. Yes, I need to write a C++ program which sorts dates. I've tried several methods. Using 2D arrays and now parallel arrays.
The problem I have with my ...
2
votes
0answers
74 views
Best team of three programmers
I have the following exercise:
Consider a weighted undirected graph G = (V, E) representing a group of programmers and their affinity for team work, such that ...
1
vote
0answers
37 views
A* pathfinder in C
Now I have this implementation of A*. Basically it is the same as the Dijkstra's algorithm in my previous post, yet I bothered to make it more cohesive by making functions for handling all the state ...
4
votes
1answer
32 views
Find a triangle in a graph represented as an adjacency list
I have a graph represented as an adjacency list. I need to find a triangle in this graph. A triangle is a triple of vertices u, ...
7
votes
2answers
73 views
Merge Sort without pointers in C
As part of an online course exercise, I was supposed to implement Merge Sort in C. Pointers were still not discussed prior to this exercise, so I have to work with arrays. Memory efficiency is not ...
4
votes
1answer
51 views
Dijkstra's shortest path algorithm in C
Now I have this C implementation of the famous algorithm:
dijkstra.h:
...
5
votes
1answer
60 views
Find minimum in rotated sorted array
The given code find the minimum element in a sorted array rotated by some fixed distance.
Eg: [1, 2, 3, 4, 5, 6, 7] -> [3, 4, 5, 6, 7, 1, 2]
The elements in the ...
4
votes
2answers
60 views
Function that shortens a String based on a term/abbreviation mapping with special cases
This is a update of this question since the requirements for this task changed.
I have a function that takes a description as a String and returns a shortened ...
2
votes
3answers
82 views
Implementation of Brent's Algorithm to find roots of a polynomial
I made a program that contains a root-finding algorithm for polynomials as a function and contains 3 test polynomials. The algorithm is Brent's method and is based entirely off the pseudocode from ...
7
votes
1answer
63 views
Return Y integer with same bit sets as X & having | X - Y | minimum value
I happened to come across one question:
Given an integer 'x' (Only positive), write an algorithm that returns
integer 'y' such that it has the same number of bits set as 'x' and is
not equal ...
5
votes
4answers
85 views
Recursive binary search in Python
I have implemented a recursive binary search in Python and tried to implement some verification to my code. Other than that, is there any optimization I am missing?
...
11
votes
1answer
114 views
IDA*: Iterative Deepening A* implementation
I created a generic version of IDA*. I am attempting to create the following code with exceptional quality and performance. I'm hoping to try and create short code tutorials regarding. However, the ...
7
votes
3answers
145 views
Finding the shortest excerpt that contains all search terms
Write a function called answer(document, searchTerms) which
returns the shortest snippet of the document, containing all of the
given search terms. The ...
5
votes
2answers
68 views
Finding the rod pieces in the rod cut issue
I have been reading the chapter 15 of "Introduction to Algorithms" (3rd edition) by Cormen, etc. The chapter 15 is about dynamic programming, and the first example they show us is the "rod cut ...
8
votes
3answers
97 views
Calculating longest increasing sub-sequence recursively
I have trouble understanding recursion, so I'm trying to implement algorithms using it. I wrote this code that calculates the length of the longest increasing sub-sequence. How can I improve this?
...
6
votes
0answers
57 views
Bounding volume hierarchy
I'm building a bounding volume hierarchy in Golang. I can tell my code works because I did some test on it and it gives the same results as the brute force implementation (brute force is to test all ...
14
votes
4answers
246 views
Numbers, pairs, and a difference
Problem statement:
Write a function which returns the total number of combinations whose difference is k.
For example, ...
