Go on. Explore!

lvl 0 • 0 xp

lvl 1

Home Market Decks Interests

Code

memorize.ai (lvl 286)

(0)

14 cards

()

Section 1

Preview this deck

Floyd-Warshall

Front

1 / 14

Programming

0.0

0 reviews

5			0
4			0
3			0
2			0
1			0

Active users

All-time users

Favorites

Last updated

6 years ago

Date created

Mar 1, 2020

Cards (14)

Section 1

(14 cards)

Floyd-Warshall

Front

dist ← |V| × |V| matrix of minimum distances initialized to ∞ for each vertex v dist[v][v] ← 0 for each edge (u,v) dist[u][v] ← w(u,v) for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if dist ← |V| × |V| matrix of minimum distances initialized to ∞ next ← |V| × |V| matrix of vertex indices initialized to null for each edge (u,v) dist[u][v] ← w(u,v) next[u][v] ← v for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][k] + dist[k][j] < dist[i][j] then dist[i][j] ← dist[i][k] + dist[k][j] next[i][j] ← next[i][k]

Back

BinarySearch

Front

static string BinarySearch<T>(T[] array, int low, int high, T value ) where T:IComparable{ if(low > high){ return "Value " + value + " not found."; } var middle = (low + high) / 2; if(array[middle].CompareTo(value) < 0){ return BinarySearch(array, middle + 1, high, value); } else if(array[middle].CompareTo(value) > 0){ return BinarySearch(array, low, middle - 1, value); } else if(array[middle].CompareTo(value) == 0){ return "Value " + array[middle] + " found on index " + middle + "."; }

Back

InsertionSort

Front

static T[] InsertionSort<T>(T[] unsortedArray) where T: IComparable { for(int j = 1; j < unsortedArray.Length; j++) { var key = unsortedArray[j]; var i = j - 1; while(i >= 0 && unsortedArray[i].CompareTo(key) > 0) { unsortedArray[i + 1] = unsortedArray[i]; i = i - 1; } unsortedArray[i + 1] = key; } return unsortedArray; }

Back

Graph: DFS iterative

Front

procedure DFS-iterative(G,v): let S be a stack S.push(v) while S is not empty v = S.pop() if v is not labeled as discovered: label v as discovered for all edges from v to w in G.adjacentEdges(v).reverse() do S.push(w)

Back

Linked List

Front

LIST-SEARCH(L,k) p = L.start while p ≠ NIL and p.data ≠ k p = p.next return p LIST-INSERT(L,k) p = L.start while p.next ≠ NIL and p.next.data ≤ k p = p.next p.next = new Node(k, p.next) return LIST-DELETE(L,k) p = L.start while p.next ≠ NIL and p.next.data ≤ k if p.next.data == k p.next = p.next.next return p = p.next return

Back

Doubly Linked List

Front

public class Node<T> where T : IComparable { T Value; Node<T> Next; } public class SortedLinkedList<T> where T : IComparable { Node<T> Start; } public class DoublyLinkedNode<T> { DoublyLinkedNode<T> Prev; // A reference to the previous node DoublyLinkedNode<T> Next; // A reference to the next node T Value; } public class DoublyLinkedList<T> { DoublyLinkedNode<T> FirstNode; // points to first node of list DoublyLinkedNode<T> LastNode; // points to last node of list } Insert a new value after/before a certain node in a doubly linked list function insertAfter<T>(DLList<T> list, DLNode<T> node, T newValue) function insertBefore<T>(DLList<T> list, DLNode<T> node, T newValue) Insert a new value at the beginning and end of a doubly linked list function insertBeginning<T>(DLList<T> list, T newValue) function insertLast<T>(DLList<T> list, T newValue) Delete a certain value in a doubly linked list function remove<T>(DLList<T> list, T value)

Back

Graph: DFS recursive

Front

procedure DFS(G,v): label v as discovered for all edges from v to w in G.adjacentEdges(v) do if vertex w is not labeled as discovered then recursively call DFS(G,w)

Back

MergeSort

Front

static void MergeSort<T>(T[] unsortedArray, int p, int r) where T:IComparable { if(p < r) { int q = (p + r)/2; MergeSort(unsortedArray, p, q); MergeSort(unsortedArray, q + 1, r); Merge(unsortedArray, p, q, r); } } static void Merge<T>(T[] unsortedArray, int p, int q, int r) where T: IComparable { var n1 = q - p + 1; var n2 = r - q; var subArray1 = new T[n1]; var subArray2 = new T[n2]; for (int i = 0; i < n1; i++) { subArray1[i] = unsortedArray[p + i]; } for (int j = 0; j < n2; j++) { subArray2[j] = unsortedArray[q + j + 1]; } int l = 0; int m = 0; for (int k = p; k <= r; k++) { if(m < subArray2.Length && l < subArray1.Length) { if(subArray1[l].CompareTo(subArray2[m]) <= 0 ) { unsortedArray[k] = subArray1[l]; l = l + 1; } else { unsortedArray[k] = subArray2[m]; m = m + 1; } } else if(l < subArray1.Length && !(m < subArray2.Length)) { unsortedArray[k] = subArray1[l]; l = l + 1; } else if(m < subArray2.Length && !(l < subArray1.Length)) { unsortedArray[k] = subArray2[m]; m = m + 1; } } }

Back

Graph: BFS

Front

Breadth-First-Search(Graph, root) for each node n in Graph: n.distance = INFINITY n.parent = NIL create empty queue Q root.distance = 0 Q.enqueue(root) while Q is not empty: current = Q.dequeue() for each node n that is adjacent to current: if n.distance == INFINITY: n.distance = current.distance + 1 n.parent = current Q.enqueue(n)

Back

BubbleSort

Front

static T[] BubbleSort<T>(T[] unsortedArray) where T:IComparable { for (int i = 0; i < unsortedArray.Length; i++) { for (int j = unsortedArray.Length - 1; j >= i + 1; j--) { if(unsortedArray[j].CompareTo(unsortedArray[j - 1]) < 0) { var temp = unsortedArray[j]; unsortedArray[j] = unsortedArray[j - 1]; unsortedArray[j - 1] = temp; } } } return unsortedArray; }

Back

Linear Search (Sequential Search)

Front

static string LinearSearch<T>(T[] array, T value) { for(int i = 0; i < array.Length; i = i + 1) { if(array[i].Equals(value)){ return "Value " + value + " found on index " + i + "."; } } return "Value " + value + " not found."; }

Back

Stack

Front

public interface StackInterface<T> { void push(T e); T pop(); T peek(); boolean isEmpty(); }

Back

Queue

Front

public interface QueueInterface‹T> { void enqueue(T e); T peek(); T dequeue(); boolean isEmpty(); }

Back

Dijkstra

Front

function Dijkstra(Graph, source): create vertex set Q for each vertex v in Graph: // Initialization dist[v] ← INFINITY // Unknown distance from source to v prev[v] ← UNDEFINED // Previous node in optimal path from source add v to Q // All nodes initially in Q (unvisited nodes) dist[source] ← 0 // Distance from source to source while Q is not empty: u ← vertex in Q with min dist[u] // Source node will be selected first remove u from Q for each neighbor v of u: // where v is still in Q. alt ← dist[u] + length(u, v) if alt < dist[v]: // A shorter path to v has been found dist[v] ← alt prev[v] ← u return dist[], prev[]

Back