Algorithms examples

Some example algorithms for the Algorithmics course in the [School of Computer Science] (https://ingenieriainformatica.uniovi.es/) in the [University of Oviedo] (http://www.uniovi.es).

You can run the JUnit test cases to check whether everything is working properly.

However, some test cases are skipped because some algorithms are not complete. Please, try to complete them and after that you can remove the @Ignore attribute in the corresponding test cases in order to execute all of them.

If you do not know how to complete any of the code snippets, you can see and download the code snippets in Gists (links are indicated below).

Topics

Sorting

TOC

• Bubble (Bubble.java)
• Bubble with sentinel (ImprovedBubble.java)
• Direct insertion (Insertion.java)
• Direct selection (Selection.java)
• Quicksort (Quicksort.java)

Divide and Conquer

TOC

• Factorial of a number (Factorial.java)
• Fibonacci series (Fibonacci.java)
• Sum of elements (VectorSum.java)
• Sequential search (SequentialSearch.java)
• Binary (dichotomous) search (BinarySearch.java)
• Quicksort (Quicksort.java)
• Mergesort (Mergesort.java)
• The majoritarian element (MajoritarianElement.java)
• Mode of a set of numbers (Mode.java)
• Median of a set of numbers (Median.java)
• Maximum sum of subsequences of elements (MaxSum.java)

Missing code snippets

• fact2()
• fib4()
• sequentialSearch2()
• binarySearch2()
• majoritarian2()
• mode2()
• median1()
• maxsum2()

Parallel algorithms

TOC

• Obtaining the square of the values of an array (RecursiveActionSquare.java)
• Comparison of different thresholds and CPUs (RecursiveActionComparison.java)
• Sum of the elements of an array (RecursiveTaskSum.java)
• Fibonacci series (FibonacciTask.java)
• Processing files concurrently (FileProcessingTask.java)

Greedy algorithms

TOC

• The problem of the change (Change.java - OPTIMAL)
• The problem of the change (ChangeNotOptimal - NOT OPTIMAL)
• The knapsack problem (Knapsack.java - OPTIMAL)
• The knapsack problem (0/1) (Knapsack01.java - NOT OPTIMAL)
• Maximize the number of files on a disk (FilesDisc1.java - OPTIMAL)
• Minimize the free space on a disk with files (FilesDisc2.java - NOT OPTIMAL)
• The diligent plumber (Plumber.java - OPTIMAL)
• Some diligent plumbers (SomePlumbers.java - OPTIMAL)
• The truck driver in a hurry (TruckDriver.java - OPTIMAL)
• Prim (Prim.java - OPTIMAL)
• The horse jumping problem (ChessHorseSimpleHeuristic, ChessHorse.java - OPTIMAL SOMETIMES)
• The problem of assigning tasks to agents (AgentsTasks.java, AgentsTasksRandomValues, AgentsTasksDifferentSizesTimes - NOT OPTIMAL)

Missing code snippets

• calculate()
• getTotalTimeOfWait()
• orderInWhichTasksAreHandledBESTWAY()
• assignTasksToPlumbersBESTWAY()
• minimumSpanningTree()
• jump()
• newMovement()
• greedy2()
• getCost2()

Dynamic programming

TOC

• Fibonacci series (Fibonacci.java)
• Combinations (Combinations.java)
• The knapsack problem (0/1) (Knapsack01.java)
• The problem of the change (Change.java)
• Cheaper travel on the river (RiverTravel.java)

Missing code snippets

• fib2()
• combinationsDivideAndConquer()
• change()
• riverTravel()

Backtracking

TOC

• Permutations of elements (Permutations.java, PermutationsTimes.java)
• Subsets of a given sum (SubsetsGivenSum.java)
• The problem of the n queens (ChessQueensOne.java, ChessQueensAll.java)
• The horse jumping problem (ChessHorseOne.java, ChessHorseAll.java)
• The problem of assigning tasks to agents (AgentsTaskTimes.java)

Missing code snippets

• backtracking() (queens)
• backtracking() (horse - one)
• backtracking() (horse - all)
• findBestSolution()
• calculateCost()
• assigned()
• printBestSol()

Branch and bound

TOC

• The problem of assigning tasks to agents (AgentsTasks.java)
• The problem of the puzzle (EightPuzzle.java)
• Optimal placement of rectangles (RectanglesPlacement.java)

License

License [GNU General Public License] (https://en.wikipedia.org/wiki/GNU_General_Public_License)

Copyright (C) 2016 - [Vicente García Díaz] (http://www.vicegd.com)