8000 Merge branch 'master' into master · Deyems/Algorithms-Explanation@d0290cb · GitHub
[go: up one dir, main page]
Skip to content

Commit d0290cb

Browse files
ashwekashwek
authored
Merge branch 'master' into master
2 parents cd6aa3d + 2070488 commit d0290cb

File tree

8 files changed

+376
-11
lines changed

8 files changed

+376
-11
lines changed

‎Data Structures/Graph/Bellman-Ford.md

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
# Bellman-Ford
2+
3+
#### Problem Statement
4+
5+
Given a weighted directed graph G(V,E) and a source vertex s ∈ V, determine for each vertex v ∈ V the shortest path between s and v.
6+
7+
#### Approach
8+
9+
- Initialize the distance from the source to all vertices as infinite.
10+
- Initialize the distance to itself as 0.
11+
- Create an array dist[] of size |V| with all values as infinite except dist[s].
12+
- Repeat the following |V| - 1 times. Where |V| is number of vertices.
13+
- Create another loop to go through each edge (u, v) in E and do the following:
14+
1. dist[v] = minimum(dist[v], dist[u] + weight of edge).
15+
- Lastly iterate through all edges on last time to make sure there are no negatively weighted cycles.
16+
17+
#### Time Complexity
18+
19+
O(VE)
20+
21+
#### Space Complexity
22+
23+
O(V^2)
24+
25+
#### Founder's Name
26+
27+
- Richard Bellman & Lester Ford, Jr.
28+
29+
#### Example
30+
31+
```
32+
# of vertices in graph = 5 [A, B, C, D, E]
33+
# of edges in graph = 8
34+
35+
edges [A->B, A->C, B->C, B->D, B->E, D->C, D->B, E->D]
36+
weight [ -1, 4, 3, 2, 2, 5, 1, -4 ]
37+
source [ A, A, B, B, B, D, D, E ]
38+
39+
40+
41+
// edge A->B
42+
graph->edge[0].src = A
43+
graph->edge[0].dest = B
44+
graph->edge[0].weight = -1
45+
46+
// edge A->C
47+
graph->edge[1].src = A
48+
graph->edge[1].dest = C
49+
graph->edge[1].weight = 4
50+
51+
// edge B->C
52+
graph->edge[2].src = B
53+
graph->edge[2].dest = C
54+
graph->edge[2].weight = 3
55+
56+
// edge B->D
57+
graph->edge[3].src = B
58+
graph->edge[3].dest = D
59+
graph->edge[3].weight = 2
60+
61+
// edge B->E
62+
graph->edge[4].src = B
63+
graph->edge[4].dest = E
64+
graph->edge[4].weight = 2
65+
66+
// edge D->C
67+
graph->edge[5].src = D
68+
graph->edge[5].dest = C
69+
graph->edge[5].weight = 5
70+
71+
// edge D->B
72+
graph->edge[6].src = D
73+
graph->edge[6].dest = B
74+
graph->edge[6].weight = 1
75+
76+
// edge E->D
77+
graph->edge[7].src = E
78+
graph->edge[7].dest = D
79+
graph->edge[7].weight = -3
80+
81+
for source = A
82+
83+
Vertex Distance from Source
84+
A 0 A->A
85+
B -1 A->B
86+
C 2 A->B->C = -1 + 3
87+
D -2 A->B->E->D = -1 + 2 + -3
88+
E 1 A->B->E = -1 + 2
89+
```
90+
91+
92+
#### Code Implementation Links
93+
94+
- [Java](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Graphs/BellmanFord.java)
95+
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Dynamic%20Programming/Bellman-Ford.cpp)
96+
- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/graph/bellman_ford.py)
97+
- [C](https://github.com/TheAlgorithms/C/blob/master/data_structures/graphs/Bellman-Ford.c)
98+
99+
#### Video Explanation
100+
101+
[A video explaining the Bellman-Ford Algorithm](https://www.youtube.com/watch?v=hxMWBBCpR6A)
102+
103+
#### Others
104+
105+
Sources Used:
106+
- https://www.geeksforgeeks.org/bellman-ford-algorithm-dp-23/
107+
- https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

‎Data Structures/Linked Lists/Doubly Linked List.md

Lines changed: 112 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,112 @@
1+
# Doubly Linked List
2+
3+
Singly Linked List is a linear and connected data structure made of Nodes. Each node is composed of a variable `data` where its content is stored and a pointer to the next Node on the list. The Linked List has a pointer to the first element of this Node sequence and may also have another pointer to the last Node to make operations at the far end less time-consuming. You can also store a `length` variable to store the total length.
4+
5+
A **Doubly Linked List (DLL)** contains an extra pointer, typically called previous pointer, together with next pointer and data which are there in singly linked list.
6+
7+
### Advantages over singly linked list
8+
- A DLL can be traversed in both forward and backward direction.
9+
- The delete operation in DLL is more efficient if pointer to the node to be deleted is given.
10+
- We can quickly insert a new node before a given node.
11+
In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.
12+
13+
### Disadvantages over singly linked list
14+
- Every node of DLL Require extra space for an previous pointer. It is possible to implement DLL with single pointer though (See this and this).
15+
- All operations require an extra pointer previous to be maintained. For example, in insertion, we need to modify previous pointers together with next pointers. For example in following functions for insertions at different positions, we need 1 or 2 extra steps to set previous pointer.
16+
17+
### Time Complexity
18+
19+
| Operation | Average | Worst |
20+
|:---------:|:-------:|:-----:|
21+
| Access | Θ(n) | O(n) |
22+
| Search | Θ(n) | O(n) |
23+
| Insertion | Θ(1) | O(1) |
24+
| Deletion | Θ(1) | O(1) |
25+
26+
## Example
27+
28+
```java
29+
class LinkedList {
30+
31+
Node head; // Pointer to the first element
32+
Node tail; // Optional. Points to the last element
33+
34+
int length; // Optional
35+
36+
class Node {
37+
int data; // Node data. Can be int, string, float, templates, etc
38+
Node next; // Pointer to the next node on the list
39+
Node prev;
40+
41+
Node(int data) {
42+
this.data = data;
43+
}
44+
}
45+
46+
47+
// Adding a node at the front of the list
48+
public void push(int new_data) {
49+
50+
/* 1. allocate node
51+
* 2. put in the data */
52+
Node new_Node = new Node(new_data);
53+
54+
/* 3. Make next of new node as head and previous as NULL */
55+
new_Node.next = head;
56+
new_Node.prev = null;
57+
58+
/* 4. change prev of head node to new node */
59+
if (head != null)
60+
head.prev = new_Node;
61+
62+
/* 5. move the head to point to the new node */
63+
head = new_Node;
64+
}
65+
66+
/* Given a node as prev_node, insert a new node after the given node */
67+
public void InsertAfter(Node prev_Node, int new_data) {
68+
69+
/*1. check if the given prev_node is NULL */
70+
if (prev_Node == null) {
71+
System.out.println("The given previous node cannot be NULL ");
72+
return;
73+
}
74+
75+
/* 2. allocate node
76+
* 3. put in the data */
77+
Node new_node = new Node(new_data);
78+
79+
/* 4. Make next of new node as next of prev_node */
80+
new_node.next = prev_Node.next;
81+
82+
/* 5. Make the next of prev_node as new_node */
83+
prev_Node.next = new_node;
84+
85+
/* 6. Make prev_node as previous of new_node */
86+
new_node.prev = prev_Node;
87+
88+
/* 7. Change previous of new_node's next node */
89+
if (new_node.next != null)
90+
new_node.next.prev = new_node;
91+
}
92+
}
93+
```
94+
95+
### Adding node at front
96+
97+
![Tracing of algorithm](https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/03/DLL_add_front1.png)
98+
99+
### Add a node after a given node
100+
101+
![Tracing of algorithm](https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/03/DLL_add_middle1.png)
102+
103+
## Code Implementation Links
104+
105+
- [Java](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/DoublyLinkedList.java)
106+
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Data%20Structure/Doubly%20Linked%20List.cpp)
107+
- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/linked_list/doubly_linked_list.py)
108+
- [Go](https://github.com/TheAlgorithms/Go/blob/master/data-structures/linked-list/double-linkedlist.go)
109+
110+
## Video Explanation
111+
112+
[A CS50 video explaining the Doubly Linked List Data Structure](https://www.youtube.com/watch?v=FHMPswJDCvU)

‎Data Structures/Linked Lists/Singly Linked List.md

Lines changed: 3 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -25,24 +25,21 @@ Singly Linked List is a linear and connected data structure made of Nodes. Each
2525

2626
```.java
2727
class LinkedList {
28-
2928
Node head; // Pointer to the first element
30-
Node tail; // Optional. Points to the last element
29+
Node tail; // Optional. Points to the last element
3130

32-
int length; // Optional
31+
int length; // Optional
3332

3433
class Node {
35-
3634
int data; // Node data. Can be int, string, float, templates, etc
3735
Node next; // Pointer to the next node on the list
38-
3936
}
4037
}
4138
```
4239

4340
## Code Implementation Links
4441

45-
- [Java](https://github.com/TheAlgorithms/Java/blob/master/data_structures/Lists/SinglyLinkedList.java)
42+
- [Java](https://github.com/TheAlgorithms/Java/blob/master/DataStructures/Lists/SinglyLinkedList.java)
4643
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Linked%20List.cpp)
4744
- [Python](https://github.com/TheAlgorithms/Python/blob/master/data_structures/LinkedList/singly_LinkedList.py)
4845

‎Search Algorithms/Binary Search.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ Binary Search should return -1 as 9 is not present in the array
4444
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Binary%20Search.cpp)
4545
- [Python](https://github.com/TheAlgorithms/Python/blob/master/searches/binary_search.py)
4646
- [C-Sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/searches/binary_search.cs)
47-
- [C](https://github.com/TheAlgorithms/C/blob/master/Searches/BinarySearch.c)
47+
- [C](https://github.com/TheAlgorithms/C/blob/master/searching/Binary_Search.c)
4848

4949
#### Video Explanation
5050

‎Sorting Algorithms/Heap Sort.md

Lines changed: 72 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,72 @@
1+
# Heap Sort
2+
3+
#### Problem Statement
4+
5+
Given an unsorted array of n elements, write a function to sort the array
6+
7+
#### Approach
8+
9+
- Build a max heap from the input data.
10+
- At this point, the largest item is stored at the root of the heap. Replace it with the last item of the heap followed by reducing the size of heap by 1. Finally, heapify the root of tree.
11+
- Repeat above steps while size of heap is greater than 1.
12+
13+
#### Time Complexity
14+
15+
O(n log n) Worst case performance
16+
17+
O(n log n) (distinct keys)
18+
or O(n) (equal keys) Best-case performance
19+
20+
O(n log n) Average performance
21+
22+
#### Space Complexity
23+
24+
O(1) Worst case auxiliary
25+
26+
27+
#### Example
28+
```
29+
Input data: 4, 10, 3, 5, 1
30+
4(0)
31+
/ \
32+
10(1) 3(2)
33+
/ \
34+
5(3) 1(4)
35+
36+
The numbers in bracket represent the indices in the array
37+
representation of data.
38+
39+
Applying heapify procedure to index 1:
40+
4(0)
41+
/ \
42+
10(1) 3(2)
43+
/ \
44+
5(3) 1(4)
45+
46+
Applying heapify procedure to index 0:
47+
10(0)
48+
/ \
49+
5(1) 3(2)
50+
/ \
51+
4(3) 1(4)
52+
The heapify procedure calls itself recursively to build heap
53+
in top down manner.
54+
```
55+
56+
![heap-image](https://upload.wikimedia.org/wikipedia/commons/1/1b/Sorting_heapsort_anim.gif "Heap Sort")
57+
58+
#### Code Implementation Links
59+
60+
- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/HeapSort.java)
61+
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Sorting/Heap%20Sort%20.cpp)
62+
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/heap_sort.py)
63+
- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/Heapsort.go)
64+
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Sorting/heap_sort.rb)
65+
- [C-sharp](https://github.com/TheAlgorithms/C-Sharp/blob/master/sorts/heap_sort.cs)
66+
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/HeapSort.c)
67+
- [Javascript](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/heapSort.js)
68+
69+
70+
#### Video Explanation
71+
72+
[A video explaining the Selection Sort Algorithm](https://www.youtube.com/watch?v=MtQL_ll5KhQ)

‎Sorting Algorithms/Insertion Sort.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,7 +55,7 @@ and elements from 11 to 13 will move one position ahead of their current positio
5555
- [C](https://github.com/TheAlgorithms/C/blob/master/Sorts/InsertionSort.c)
5656
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Sorting/Insertion%20Sort.cpp)
5757
- [C#](https://github.com/TheAlgorithms/C-Sharp/blob/master/sorts/insertion_sort.cs)
58-
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/sorts/InsertionSort.scala)
58+
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/InsertionSort.scala)
5959
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/insertion_sort.py)
6060

6161
#### Video Explanation

‎Sorting Algorithms/Selection Sort.md

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -56,10 +56,10 @@ Indexes: 0 1 2 3
5656
- [Java](https://github.com/TheAlgorithms/Java/blob/master/Sorts/SelectionSort.java)
5757
- [C++](https://github.com/TheAlgorithms/C-Plus-Plus/blob/master/Sorting/Selection%20Sort.cpp)
5858
- [Python](https://github.com/TheAlgorithms/Python/blob/master/sorts/selection_sort.py)
59-
- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/selection_Sort.go)
60-
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Selection_Sort.rb)
59+
- [Go](https://github.com/TheAlgorithms/Go/blob/master/sorts/selection_sort.go)
60+
- [Ruby](https://github.com/TheAlgorithms/Ruby/blob/master/Sorting/selection_sort.rb)
6161
- [C](https://github.com/TheAlgorithms/C/blob/master/sorting/SelectionSort.c)
62-
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/Selection%20Sort.scala)
62+
- [Scala](https://github.com/TheAlgorithms/Scala/blob/master/src/main/scala/Sort/SelectionSort.scala)
6363
- [Javascript](https://github.com/TheAlgorithms/Javascript/blob/master/Sorts/selectionSort.js)
6464

6565

0 commit comments

Comments
 (0)
0