Algorithms examples

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.

Main topics (there are more in the code)

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

• Fibonacci series (Fibonacci.java)
• Greatest common factorial (GCGTest.java)
• Factorial of a number (Factorial.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)

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)

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)

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)

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) 2023 - [Vicente García Díaz] (http://www.vicentegarciadiaz.com)