Basic-Algorithms-in-Python

This repository contains some popular algorithms implemented in Python:

• binary_search.py

• change.py

• covering_segments.py

• different_summands.py

• dot_product.py

• fibonacci.py : Input is a single natural number n and output is the n-th Fibonacci number

• fibonacci_huge.py : Input consits of two natural numbers n and m separated by a space and output is n-th Fibonacci number mod m. We use Pisano periods for fast computations.

• fibonacci_last_digit.py : Input is a single natural number n (possibly large) and output is the n-th Fibonacci number mod 10

• fibonacci_partial_sum.py : Input consits of two natural numbers n and m (n > m) separated by a space and output is the sum of n-m+1 Fibonacci numbers (from the m-th to the n-th) mod 10

• fibonacci_sum_last_digit.py : Input is a single natural number n and output is the sum of the first n+1 Fibonacci numbers (from the 0-th to the n-th) mod 10

• fractional_knapsack.py

• gcd.py : Input consits of two natural numbers a and b separated by a space and output is GCD(a,b). We use the Euclidean algorithm.

• inversions.py

• knapsack.py

• largest_number.py

• lcm.py : Input consits of two natural numbers a and b separated by a space and output is LCM(a,b).

• majority_element.py

• primitive_calculator.py

• quick_sort.py : Implementation of the Quick Sort algorithm

• selection_sort.py : Implementation of the Selection Sort algorithm

• merge_sort.py : Implementation of the Merge Sort algorithm