Exam prep Flashcards
Primitive vs. Non-Primitive Data Types
Primitive Data Types: Basic types such as int, char, float, and double. They store single values and are directly supported by the system.
Non-Primitive Data Types: Complex data types like arrays, structures, linked lists, stacks, and queues. These are derived from primitive data types.
Postfix Expression Conversion
Expression: ((A + B) * C – (D – E)) / (F + G)
Steps:
Convert innermost parentheses: (A + B) becomes AB+ Convert D – E to DE- Apply multiplication: AB+C* Apply subtraction: AB+C*DE- Final postfix: AB+C*DE-/FG+
Priority Queue vs. Normal Queue
Normal Queue: FIFO (First In, First Out) order.
Priority Queue: Each element is associated with a priority. Elements with higher priority are dequeued before elements with lower priority, regardless of their insertion order.
Stack Operations with C Code
Basic Operations: Push, Pop, Peek
C Code (Push Example):
c
void push(int stack[], int top, int value) {
if (top == MAX - 1)
printf(“Stack Overflow\n”);
else {
(top)++;
stack[top] = value;
}
}
Circular Queue: Insertion & Deletion
void enqueue(int queue[], int front, int rear, int value) {
if ((rear + 1) % MAX == front)
printf(“Queue is full\n”);
else {
*rear = (rear + 1) % MAX;
queue[rear] = value;
}
}
Recursive Algorithms for Binary
int findMax(struct Node* root) {
if (root == NULL)
return INT_MIN;
int res = root->data;
int lres = findMax(root->left);
int rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
Kruskal’s Algorithm
Purpose: Find the Minimum Spanning Tree (MST) of a graph.
Steps:
Sort all edges in non-decreasing order of their weight. Pick the smallest edge. If it doesn't form a cycle, include it in the MST. Repeat until you have V-1 edges in the MST, where V is the number of vertices.
Dijkstra’s Algorithm
Purpose: Find the shortest path from a source node to all other nodes.
Steps:
Set the distance of the source node to 0 and all other nodes to infinity. Mark the source node as visited. Update the distances of adjacent nodes. Repeat for the next unvisited node with the smallest known distance.
Hashing: Separate Chaining vs. Open Addressing
Separate Chaining: Uses linked lists to handle collisions. Each bucket of the hash table is a linked list where elements are stored if they hash to the same index.
Open Addressing: Resolves collisions by probing through alternative locations in the hash table (linear probing, quadratic probing, etc.).
Binary Heap Deletion Example
Min-Heap Deletion:
Replace the root with the last element.
Heapify down from the root.
Example: Given Min-Heap:
markdown
10 / \ 20 30 / \ / 40 50 60
after deletion
20
/ \
40 30
/ \ /
50 60
Kruskal’s Algorithm Steps
Purpose: Find the Minimum Spanning Tree (MST) of a graph.
Steps:
Sort all edges in non-decreasing order of their weight. Pick the smallest edge. If it forms a cycle, discard it. Repeat until there are V-1 edges in the MST.
Example: Graph with edges and weights:
Edges: {(A, B, 1), (A, C, 3), (B, C, 2)}
MST edges after sorting: {(A, B, 1), (B, C, 2)}
Dijkstra’s Algorithm Steps
Purpose: Find the shortest path from a source node to all other nodes.
Steps:
Initialize distances: Set source distance to 0, all others to infinity. Mark the source node as visited. Update distances of adjacent nodes. Repeat until all nodes are visited.
Example: From Node A to others in a weighted graph.
DFS vs. BFS for Tree Traversal
Depth-First Search (DFS):
Traversal Order: Pre-order, In-order, Post-order. Use Cases: Finding paths, topological sorting.
Breadth-First Search (BFS):
Traversal Order: Level-order. Use Cases: Shortest path in unweighted graphs, finding connected components.
Bellman-Ford Algorithm for Shortest Paths
Purpose: Find shortest paths from a single source, even with negative weights.
Steps:
Initialize distances from source to all other vertices as infinite. Set the distance to the source itself as 0. Relax all edges V-1 times. Check for negative weight cycles.
Infix to Postfix Conversion Example
Infix Expression: ((A + B) * C - (D - E)) / (F + G)
Step Symbol Stack Postfix Expression
1 ( (
2 ( ((
3 A (( A
4 + ((+ A
5 B ((+ AB
6 ) ( AB+
7 * (* AB+
8 C (* AB+C
9 - (- AB+C*
10 ( (-( AB+C*
11 D (-( AB+CD
12 - (-(- AB+CD
13 E (-(- AB+CDE
14 ) (- AB+CDE-
15 ) AB+CDE-
16 / / AB+CDE-
17 ( /( AB+CDE-
18 F /( AB+CDE-F
19 + /(+ AB+CDE-F
20 G /(+ AB+CDE-FG
21 ) / AB+CDE-FG+
22 End AB+CDE-FG+/
Postfix Expression: AB+C*DE-FG+/
Postfix Evaluation Example
Postfix Expression: 52+83-*4/
Step Symbol Stack Explanation
1 5 5 Push 5 onto the stack.
2 2 5, 2 Push 2 onto the stack.
3 + 7 5 + 2 = 7, push 7.
4 8 7, 8 Push 8 onto the stack.
5 3 7, 8, 3 Push 3 onto the stack.
6 - 7, 5 8 - 3 = 5, push 5.
7 * 35 7 * 5 = 35, push 35.
8 4 35, 4 Push 4 onto the stack.
9 / 8.75 35 / 4 = 8.75, push 8.75
Result: 8.75
Depth-First Search (DFS) Example
A
/ \
B C
| |
D E
Starting from A:
Step Vertex Visited Stack Traversal
1 A A A
2 B A, B A B
3 D A, B, D A B D
4 Backtrack to B A, B A B D
5 Backtrack to A A A B D
6 C A, C A B D C
7 E A, C, E A B D C E
DFS Traversal: A B D C E
Breadth-First Search (BFS) Example
A
/ \
B C
| |
D E
Step Vertex Visited Queue Traversal
1 A A A
2 B B, C A B
3 C C, D A B C
4 D D, E A B C D
5 E E A B C D E
BFS Traversal: A B C D E
Kruskal’s Algorithm Example
Edges:
(A, B) = 1
(A, C) = 3
(B, C) = 2
(C, D) = 4
Step Edge Added Selected Edges Total Weight
1 (A, B) = 1 A-B 1
2 (B, C) = 2 A-B, B-C 3
3 (A, C) = 3 Discard (cycle) 3
4 (C, D) = 4 A-B, B-C, C-D 7
Minimum Spanning Tree: A-B, B-C, C-D
Total Weight: 7
Dijkstra’s Algorithm Example
Graph with Weights:
A
/ \
B C
| |
D E
Weights:
A-B: 1, A-C: 4, B-D: 2, C-E: 5
Step Vertex Processed Shortest Path Estimate Explanation
1 A A: 0, B: 1, C: 4 Start from A.
2 B A: 0, B: 1, D: 3 Process B, update D.
3 C A: 0, B: 1, D: 3, E: 9 Process C, update E.
4 D A: 0, B: 1, D: 3 Process D, no update.
5 E A: 0, B: 1, D: 3, E: 9 Process E. Done.
Shortest Path Estimates from A:
A -> B = 1 A -> D = 3 A -> C = 4 A -> E = 9
Prim’s Algorithm: Calculating Minimum Spanning Tree (MST) Weight
Prim’s Algorithm also finds the Minimum Spanning Tree, but it starts from a single vertex and grows the tree by adding the smallest edge that connects a vertex already in the tree to a vertex not yet in the tree.
A
/ \
1 3
B—–C
\ /
2
D
Start from vertex A:
Add the smallest edge connected to A (i.e., A-B = 1). Now the tree contains vertices A and B. Next, add the smallest edge connected to these vertices that does not form a cycle (i.e., B-D = 2). Add A-C = 3 to connect C.
Step Edge Added Tree Formed Total Weight
1 A-B = 1 A-B 1
2 B-D = 2 A-B-D 1 + 2 = 3
3 A-C = 3 A-B-D-C 3 + 3 = 6
MST Total Weight: 6
