Skip to content

Latest commit

 

History

History
86 lines (68 loc) · 3.28 KB

README.md

File metadata and controls

86 lines (68 loc) · 3.28 KB
Raw

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)