Algorithm Wiki - New pages [en]

YouEnTiVi

2020-07-31T10:09:52Z

Matt: Removed spam.

UNTV

2020-07-31T10:06:00Z

Matt: Removed spam.

Eat diver

2020-07-29T14:27:00Z

Matt: Removed spam.

Portal:Science

2020-07-29T14:23:43Z

Matt: Removed spam.

Portal:Mathematics

2020-07-29T14:23:12Z

Matt: Removed spam.

Portal:History

2020-07-29T14:22:48Z

Matt: Removed spam.

Portal:Geography

2020-07-29T14:22:35Z

Matt: Undo revision 1046 by FuckMatt (talk)

TADM2E 5.33

2020-07-29T11:11:28Z

Matt:

''There is no problem 5.33 in the textbook. This page can be ignored.''

Shot

2020-07-27T10:22:47Z

Matt: Blanked the page

Sore

2020-07-27T10:22:31Z

Matt: Blanked the page

TADM2E 6.10

2020-07-22T15:39:00Z

Bkarpov96: Undo revision 877 | Why are u doing this? What's the point? It's wiki for learning book

<pre>
1. DFS from any vertex when found back edge add it to F.
2. Applying the Kruskal's algorithm
- First multiply the weights of all edges by -1
- If an edge is found during the algorithm execution, both ends of which belong to the same component, add it to F
By multiplying all edges by -1, the edges with the highest weight will be processed first => the edges with the lowest weight will be added to F
An alternative statement of the problem from point 2 is to find the complement to the maximum spanning tree.
</pre>
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 15:38, 22 July 2020 (UTC)

PHILIPPINES 2000

2020-07-17T02:53:00Z

Ufsuraifs: Created page with "Andito na si swabe"

Andito na si swabe

SpEc

2020-07-17T02:52:14Z

Ufsuraifs: Created page with "DhajraltiariakaehE6lDhxhHrrsdhrualaleyraylalrhLryqlehsfjtslrusfstiwfaztiststagtiwwtsykgzsytavstissfjs vfsstusg;d6osgjpmfeyfpirlxteu"

DhajraltiariakaehE6lDhxhHrrsdhrualaleyraylalrhLryqlehsfjtslrusfstiwfaztiststagtiwwtsykgzsytavstissfjs vfsstusg;d6osgjpmfeyfpirlxteu

A

2020-07-14T01:53:06Z

FuckYou: Created page with "[En.wikipedia.org]"

[En.wikipedia.org]

EthanGamer

2020-07-14T01:43:22Z

FuckYou: Created page with "Hey Gamers!!!!!"

Hey Gamers!!!!!

TADM2E 5.22

2020-07-07T08:17:40Z

Matt: Undo revision 1064 by FuckMatt (talk)

<pre>
Working with the list of edges of an undirected graph G
Read the edges of G and create an adjacency matrix A, and simultaneously calculate the degree of each vertex in the array B # O(m)
- Consider an edge UW, if the data about it already exists A[U][W] == A[W][U] == 1, then a multiple edge is found, skip it
Initialize the queue Q
Add to Q all vertexes whose degree is 2 # O(n) iterations, O(1) get the vertex degree via the array B
- The presence of a vertex in the queue is noted in the array C, which consists of bool flags
Loop until the queue Q is empty: # O(n) iterations
- Extract vertex V from Q # V has degree 2 => V located between vertexes U and W
- Delete the edge UV, B[U] -= 1
- Delete the edge VW, B[W] -= 1
- Delete vertex V, C[V] = False
- If U and W are not adjacent, connect U and W with an edge and increase the degrees of U and W by 1 # Checking the adjacency O(1) via the adjacency matrix
- If U's degree is 2 and U is not in queue Q, add U to Q # Getting vertex degree via B O(1), checking for presence in the queue via C O(1)
- If W's degree is 2 and W is not in queue Q, add W to Q
</pre>--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 08:17, 7 July 2020 (UTC)

TADM2E 5.20

2020-07-06T08:53:31Z

Bkarpov96: Undo revision 884 | Why are u doing this? What's the point? It's wiki for learning book

<pre>
Traversing the graph G DFS O(n + m)
- If vertex M has degree >= k, add it to U
- - If vertex J (parent of M) was added to U, then add an edge MJ to R
- Continue DFS for children of vertex M with the pointer on M and a flag indicating whether M was added to U

Since the condition requires finding the maximum induced subgraph, all matching vertexes and edges are added during the DFS.
If U and R do not contain elements at the end of the DFS, then the induced subgraph does not exist.
</pre>--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 08:53, 6 July 2020 (UTC)

TADM2E 5.12

2020-06-30T07:48:08Z

Matt: Undo revision 1145 by FuckyouMatt (talk)

<pre>Algorithm:
BFS of each vertex v ∈ V, O(|V| * (|V| + |E|))
Saving adjacent vertexes to an adjacency matrix or adjacency list O(1)

Extensions:
BFS stops at a depth of 2
- Depth 1-adjacent v in the original graph
- Depth 2-adjacent v in the graph square
BFS uses the vertex statuses unopened, open, and processed
- Open and processed vertexes are not added to the queue again

Time complexity of the algorithm O (|V| * (|V| + |E|)) = O((|V|)^2 + |V * E|)) = O(|V * E|)
- The number of edges does not grow slower than the number of vertexes
- In a graph of 1 vertex, when adding 1 vertex, 1+ edge is added
- In a complete graph of n vertices, the number of edges is determined by the Handshaking lemma
- - For a complete directed graph |E| = n * (n - 1) edges
- - For a complete not directed graph |E| = n * (n - 1) / 2 edges</pre>
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 07:48, 30 June 2020 (UTC)

TADM2E 5.10

2020-06-29T16:13:25Z

Bkarpov96: Undo revision 861 by Bkarpov96Wars (talk)

Pre-ordered DFS: process left, process right, process current
<pre>
If current node is number:
return number

If current node is calculation:
do calulation on DFS(left_child) and DFS(right_child)
save result in current node
forget edges to children
return number
</pre>
Modification from 5.9 - reduction of nodes.<br>
--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 16:13, 29 June 2020 (UTC)

TADM2E 4.18

2020-06-19T17:36:21Z

Bkarpov96: Undo revision 887 | Why are u doing this? What's the point? It's wiki for learning book

<pre>
from random import choices

def group_by_color(data, start, stop, color):
operations_counter = 0

while start < stop and start < len(data) and stop >= 0:
# data[start] is equal to examine(data[start]) except swap function call

while start < len(data) and data[start] == color: # Finding first element with incorrect color from start
start += 1 # Element with correct color already on right position, moving forward
operations_counter += 1

while start < stop and stop >= 0 and data[stop] != color: # Finding first element with correct color from end
stop -= 1 # Element with incorrect color will be swapped later or keep on that position, moving backward
operations_counter += 1

if start < stop:
data[start], data[stop] = data[stop], data[start] # Equal to swap(start, stop)
operations_counter += 1

assert operations_counter <= len(data) * 2 # Check O(2*n) restriction
return start # Return last element with specified color

colors_list = choices(['red', 'white', 'blue'], k=100)
red_ending = group_by_color(colors_list, 0, len(colors_list) - 1, 'red') # Sort red O(n)
group_by_color(colors_list, red_ending + 1, len(colors_list) - 1, 'white') # Sort white O(n)
# Blue already sorted
</pre>

First pass: group red elements from 0 to k. Swapping not red elements found from begin and red elements found from end.

Second pass: group white elements from k to j. Swapping not white elements from k and white elements from end.

Blue elements already groupped from j to n.

--[[User:Bkarpov96|Bkarpov96]] ([[User talk:Bkarpov96|talk]]) 17:36, 19 June 2020 (UTC)

TADM2E 2.34

2020-05-27T07:06:54Z

Ur3000:

This task refers to this song The_Twelve_Days_of_Christmas_(song)

So we have to calculate the sum like this

1 day - 1 gift

2 day - 1 gift + 2 gifts

3 day - 1 + 2 + 3

n day - 1 + 2 + 3 + ... + n

Formula is

<math>
\begin{align}

&\sum_{i=1}^n \sum_{j=1}^n j\
= \sum_{i=1}^n \frac{n(n+1)}{2} =\\
&= \frac{1}{2}\sum_{i=1}^n n^2 + \frac{1}{2}\sum_{i=1}^n n=\\
&= \frac{n(n+1)(2n+1) + 3n(n+1)}{12} = \frac{(n+1)(n^2+2n)}{6}\

\end{align}
</math>