khasanovaa/algorithms_and_data_structures

Algorithms and data structures on c++ and python

NP-COMPLETE TASKS:

1. knapsack.cpp
   The knapsack problem: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible
   input: the amount of things, their weight, their value, a given limit.
   output: the max total value, number of things, that were used to reach max total value.
   

2. Vertex-cover
   Find a K-vertex cover. input: the amount of vertexes, amount of edges and K, list of edges. output: if the K-vertex exists: YES and vertexes in vertex-cover, else: NO

FINITE AUTOMATION:

1. DFA.cpp
   input: N - amount of conditions, then N strings with condition description: (1-condition is terminal or 0-condition is not terminal), T - amount of transitions, then T descriptions off transitions (symbol, condition), then M - amount of strings to check this automat. output: M+1 string: 1-the automat accepts the word, 0-the automat doesn't accepts the word.

2. NFA.cpp
   input: N - amount of conditions, then N strings with condition description: (1-condition is terminal or 0-condition is not terminal), E- emount of epsilon-transitions, E number of epsilon-transitions, T - amount of transitions, then T descriptions off transitions (symbol, condition), then M - amount of strings to check this automat. output: M+1 string: 1-the automat accepts the word, 0-the automat doesn't accepts the word.

ALGORITHMS:

1. Ford_Belman_longest_path.cpp
   Finding longest path with Ford-Belman algorithm
   input: amount of vertexes, adjacency matrix
   output: the length of path

2. LargeFactorial.cpp
   Calculationg N! for N < 100000.
   input: N in decimal notation
   output : N!

3. LargeSort.cpp
   Sorting text file lexicographical by strings.
   input: text
   and limit on memory in file memory.txt.
   output: sorted text

4. bridges.cpp
   Finding bridges in graph.
   input: amount of vertexes, list of edges,
   output: numbers of edges-bridges as in input
   

5. closest_points.cpp
   Finding two closest points
   input: amount of points, coordinates
   output: distance between two closest points
   

6. merge_sort.cpp
   Realization of merge sort
   input: size of array, array
   output: sorted array
   

7. piramidal_sort.cpp
   Realization of piramidal sort
   input: size of array, array
   output: sorted array
   

8. quick_sort.cpp
   Realization of quick sort
   input: size of array, array
   output: sorted array
   

9. radix_sort.cpp
   Realization of radix sort
   input: size of array, array
   output: sorted array
   

10. red-black tree.cpp
    Realization of red-black tree structure without using set, multiset, map, multimap, unordered_set, unordered_multiset, unordered_map, unordered_multimap, etc.
    input: n - amount of requests, n request : (0, v_i) = put v_i in tree or (1, v_i) = find out if v_i is in the tree
    output: YES/NO for requests. Then the tree in format: KEY LEFTKEY RIGHTKEY COLOR
    

11. shortest_path.cpp
    Finding the shortest path from vertex A to B
    input: amount of vertexes, list of edges, A, B
    output: the shortest path.

12. stl.cpp
    Realization of some of stl library templates
    

13. utf-coding.cpp
    Coding a word with utf-8.
    input: word
    output: coded word

14. utf-decoding.cpp
    Deoding a word from utf-8.
    input: coded word
    output: decoded word