ew0s/ITMO_Algorithms2

Second semestre labs

C++

ITMO algorithms second semestr

Laboratory work №1 - BFS

A - Adjacency Matrix

B - Is unoriented

C - Parallel edges

D - Connected component

E - Shortest path in unweighted graph

Laboratory work №2 - DFS

C - Is bipatite

D - Graph condensation

E - Hamilton way

Laboratory work №3 - MST

A - Top's degree

B - Spanning tree (Prim's algorithm O(V^2 + E))

C - Spanning tree 3 (Prim's algorithm O(E * LogV))

Laboratory work №4 - Shortest paths in a graph

A - Shortest path between two vertexes (Dijkstra O(V^2 + E))

B - Shortest path from all to all vertexes (Belman Ford algorithm O(V * E))

C - Shortest path from first vertex to all (Dijkstra O(E * logV))

D - Shortest path and etc (Belman Ford algorithm O(V * E))

E - Negative cycle (Belman Ford algorithm O(V * E))

Laboratory work №5 - Flows in a graphs

B - Max matching

C - Decomposition of the flow (Dinic's algorithm)

D - Graph's circulation

Laboratory work №6 - substrings searching

A - Naive substring search

B - Fast substring search (KMT algorithm)

C - Prefix function

D - KMT machine