Basic Equivalences
Some Conversions |
𝐴 →𝐵≡¬𝐴∨𝐵 |
¬(𝐴 →𝐵)≡𝐴∧¬𝐵 |
𝐴 →𝐵≡𝐴∧¬𝐵→False |
∧ and ∨ are associative |
(𝐴 ∧𝐵)∧𝐶 ≡𝐴∧(𝐵∧𝐶) |
(𝐴 ∨𝐵)∨𝐶 ≡𝐴∨(𝐵∨𝐶) |
∧ and ∨ are commutativity |
𝐴∧𝐵≡𝐵∧𝐴 |
𝐴∨𝐵≡𝐵∨𝐴 |
∧ and ∨ are Distributivity |
𝐴∧(𝐵∨𝐶)≡(𝐴∧𝐵)∨(𝐴∧𝐶) |
𝐴∨(𝐵∧𝐶)≡(𝐴∨𝐵)∧(𝐴∨𝐶) |
Proof Rules
Conjunction (Conj) |
𝐴, 𝐵 / 𝐴∧𝐵 |
Simplification (Simp) |
𝐴∧𝐵 / 𝐴 and |
𝐴∧𝐵 / 𝐵 |
Addition (Add) |
𝐴 / 𝐴∨𝐵 and |
𝐵 / 𝐴∨𝐵 |
Disjunctive Syllogism (DS) |
𝐴 ∨ 𝐵, ¬𝐴 / 𝐵 |
𝐴 ∨ 𝐵, ¬𝐴 / 𝐵 |
Modus Ponens (MP) |
𝐴, 𝐴 →𝐵 / 𝐵 |
Conditional Proof (CP) |
From𝐴, derive 𝐵/𝐴 →𝐵 |
Double Negation (DN) |
¬¬𝐴 / 𝐴 |
𝐴 /¬¬𝐴 |
Contradiction (Contr) |
𝐴, ¬𝐴 / False |
Indirect Proof (IP) |
From¬𝐴, derive False / 𝐴 |
These are all fractions with the first term appearing on top and the second one on the bottom.
/ this slash denotes where a fraction will be located
CS 310 Lecture 5
Array Data Structure |
A linear data structure defined as a collection of elements with the same or different data types. |
| |
They exist in both single and multiple dimensions |
Terms to understand the concept of Array. |
o Element − Each item stored in an array is called an element. |
| |
o Index − Each location of an element in an array has a numerical index. |
CS 310 Lecture 5
Array Update Operation |
1. Start |
2. Set LA[K-1] = ITEM |
3. Stop |
CS 310 Lecture 5
Common Features of Linked List |
➢Node: Each element in a LL is represented by a node, contains two components: |
➢Data: The actual data or value associated with the element. |
➢Next Pointer: A reference or pointer or address to the next node in the LL. |
➢Head: The first node in a LL is called the “head.” It serves as the starting point. |
➢Tail: The last node in a linked list is called the “tail.” |
➢Data structures can be added to or removed from the LL during execution. |
➢Unlike an array, LL is a dynamically allocated DS that can grow and shrink. |
➢No elements need to be shifted after insertion and deletion. |
➢Various DSs can be implemented using an LL, such as stack, queue, graphs, hash, etc. |
➢Linked list contains 0 or more nodes. Last node points to null(address 0) |
CS 310 Lecture 5
LIST-Traversal (L)
1. Curr = L.head
2. While Curr.next != NULL
3. PRINT Curr
CS 310 Lecture 5
Linked List: Searching a Node |
LIST-Searching (L,k) |
1. Curr = L.head |
2. While Curr != NULL and Curr.key != k |
3. Curr = Curr.next |
4. return Curr |
CS 310 Lecture 5
Doubly-linked list: Inserting at the beginning
➢The task can be performed by using the following 5 steps:
➢Firstly, allocate a new node.
➢Now put the required data in the new node.
➢Make the next of new_node point to the current head of the DLL.
➢Make the previous of the current head point to new_node.
➢Lastly, point head to new_node.
|
|
Basic Equivalences
Disjunction |
A ⋁ True ≣ True |
A ⋁ False ≣ A |
A ⋁ A ≣ A |
A ⋁ ¬A ≣ True |
Basic Equivalences
Absorption Laws |
𝐴∧(𝐴∨𝐵) ≡ 𝐴 |
𝐴∨(𝐴∧𝐵) ≡ 𝐴 |
𝐴∧(¬𝐴∨𝐵) ≡ 𝐴∧𝐵 |
𝐴∨(¬𝐴∧𝐵)≡𝐴∨𝐵 |
Program Correctness
AA (Assignment axiom) |
{𝑄(𝑥/𝑡)} 𝑥 ≔ 𝑡 {𝑄} |
Consequence rules (A & B) |
𝑃 →𝑅 and {𝑅} 𝑆 {𝑄} / {𝑃} 𝑆 {𝑄} |
{𝑃} 𝑆 {𝑇} and 𝑇 →𝑄 / {𝑃} 𝑆 {𝑄} |
Loop invariants: A loop invariant is a condition that does not change after a loop has executed I.e. P
Derived Proof Rules
Modus Tollens (MT) |
𝐴 →𝐵, ¬𝐵 / ¬𝐴 |
Hypothetical Syllogism (HS) |
𝐴 → 𝐵, 𝐵 → 𝐶 / 𝐴 → 𝐶 |
Proof by Cases (Cases) |
𝐴∨𝐵, 𝐴→𝐶, 𝐵→𝐶 / 𝐶 |
Constructive Dilemma (CD) |
𝐴 ∨ 𝐵, 𝐴 → 𝐶, 𝐵 → D / 𝐶 ∨D |
Destructive Dilemma (DD) |
𝐴 →𝐵, 𝐶 →𝐷, ¬𝐵∨¬D / ¬𝐴∨¬𝐶 |
CS 310 Lecture 5
Operations in Arrays |
o Traverse − print all the array elements one by one. |
o Insertion − Adds an element at the given index. |
o Deletion − Deletes an element at the given index. |
o Search − Searches an element using the index or value. |
o Update − Updates an element at the given index. |
o Display − Displays the contents of the array. |
CS 310 Lecture 5
Array Search Operation |
1. Start |
2. Set J = 0 |
3. Repeat steps 4 and 5 while J < N |
4. IF LA[J] == ITEM THEN GOTO STEP 6 |
5. Set J = J +1 |
6. PRINT J, ITEM |
7. Stop |
CS 310 Lecture 5
➢Singly Linked List: Every node stores the address of the next node in the list and the last node
has the next address NULL.
CS 310 Lecture 5
Linked List: Operations |
➢Accessing Elements/Traversing: Accessing a specific element in a linked list takes O(n) time since nodes are stored in non-contiguous locations, so random access is not possible. |
➢Searching: Searching a node in an LL takes O(n) time, as the whole list needs to be traversed in the worst case. |
➢Insertion: If we are at the position where we insert the element, insertion takes O (1) time. |
➢Deletion a/Destroy the list: Deletion takes O(1) time if we know the element’s position to be deleted. |
CS 310 Lecture 5
➢Doubly Linked Lists: Each node has two pointers: one pointing to the next node and one
pointing to the previous node. Allows for efficient traversal in both directions.
CS 310 Lecture 5
LIST-Insert (L,x,k)
1. if L.Head == NULL
2. L.Head = x and Exit
3. While Curr.key !=k and Curr !=NULL
4. prevN = Curr
5. Curr = Curr.Next
6. If PrevN == NULL
7. x.next = L.Head
8. Head = x and exit
9. PrevN = Curr and Curr = Curr.Next
10. x.Next = Curr
11. PrevN.Next = x
CS 310 Lecture 5
Doubly-linked list: Inserting at the end
➢This can be done using the following 7 steps:
➢Create a new node (say new_node).
➢Put the value in the new node.
➢Make the next pointer of new_node as null.
➢If the list is empty, make new_node as the head.
➢Otherwise, travel to the end of the linked list.
➢Now make the next pointer of last node point to new_node.
➢Change the previous pointer of new_node to the last node of the list.
|
|
Basic Equivalences
Conjunction |
A ⋀ True ≣ A |
A ⋀ False ≣ False |
A ⋀ A ≣ A |
A ⋀ ¬A ≣ False |
Basic Equivalences
Absorption Laws |
𝐴∧(𝐴∨𝐵) ≡ 𝐴 |
𝐴∨(𝐴∧𝐵) ≡ 𝐴 |
𝐴∧(¬𝐴∨𝐵) ≡ 𝐴∧𝐵 |
𝐴∨(¬𝐴∧𝐵)≡𝐴∨𝐵 |
Program Correctness
AA (Assignment axiom) |
{𝑄(𝑥/𝑡)} 𝑥 ≔ 𝑡 {𝑄} |
Consequence rules (A & B) |
𝑃 →𝑅 and {𝑅} 𝑆 {𝑄} / {𝑃} 𝑆 {𝑄} |
{𝑃} 𝑆 {𝑇} and 𝑇 →𝑄 / {𝑃} 𝑆 {𝑄} |
Composition rule |
{𝑃} 𝑆1 {𝑄} and {𝑄} 𝑆2 {𝑅} / {𝑃} 𝑆1;𝑆2 {𝑅} |
If-then Rule |
{𝑃 ∧𝐶} 𝑆 {𝑄} and 𝑃 ∧¬𝐶 → 𝑄 |
{𝑃} if 𝐶 then 𝑆 {𝑄} |
If-then-else rule |
{𝑃 ∧𝐶} 𝑆1 {𝑄} and {𝑃 ∧¬𝐶} 𝑆2 {𝑄} / {𝑃} if 𝐶 then 𝑆1 else 𝑆2 {𝑄} |
While rule |
{𝑃 ∧𝐶} 𝑆 {𝑃} / {𝑃} while 𝐶 do 𝑆 {𝑃 ∧¬𝐶} |
Loop invariants: A loop invariant is a condition that does not change after a loop has executed I.e. P
CS 310 Lecture 5
Array Deletion Operation |
1. Start |
2. Set J = K-1 |
3. Repeat steps 4 and 5 while J < N |
4. Set LA[J] = LA[J + 1] |
5. Set J = J+1 |
6. Set N = N-1 |
7. Stop |
N - is the size of the array
CS 310 Lecture 5
Array Insertion Operation |
1. Start |
2. Create an Array of a desired datatype and size. |
3.Initialize a variable 'i' as 0. |
4. Enter the element at the i-th index of the array. |
5. Increment i by 1 |
6. Repeat Steps 4 & 5 until the end of the array. |
7. Stop |
CS 310 Lecture 5
➢Circular Linked Lists: A circular linked list is a type of linked list in which the first and the last
nodes are also connected to form a circle. There is no NULL at the end.
CS 310 Lecture 5
Linked List: Empty List
➢If a list currently contains 0 nodes, it is called the empty list.
➢In this case, the list head points to null
CS 310 Lecture 5
LIST-Append (L; x)
1. if L.head == NULL
2. L.head = x and Exit
3. Curr = L.head
3. While Curr.next != NULL
Curr = Curr.next
4. Curr.next = x
New Node is added to the end of the list
CS 310 Lecture 5
Adjusting pointer around the node to be deleted
LIST-Delete (L, k)
1. if L.Head == NULL
2. Exit
3. While Curr.key !=k and Curr !=NULL
4. PrevN = Curr
5. Curr = Curr.Next
6. If PrevN == NULL
7. Curr = Head.Next
8. delete Head and exit
9. PrevN.Next = Curr.Next
10. Delete Curr
CS 310 Lecture 5
Circular-linked list operations:
➢Insertion: Inserting At the Beginning, at the end, and after a given node.
➢Deletion: Deleting from the Beginning, the end, and a Specific Node
➢Display: This process displays the elements of a CLL.
|
|
Basic Equivalences
Implication |
A → True ≣ True |
A → False ≣ ¬A |
True → A ≣ A |
False → A ≣ True |
A → A ≣ True |
Basic Equivalences
De Morgan's Laws |
¬(𝐴∧𝐵) ≡ ¬𝐴∨¬𝐵 |
¬(𝐴∨𝐵) ≡ ¬𝐴∧¬𝐵 |
Quantifiers
"An equivalence to be careful with" |
∃𝑥(𝑝(𝑥) → 𝑞(𝑥)) ≡ ∀𝑥𝑝(𝑥) → ∃𝑥𝑞(𝑥) |
Quantifiers
Negations of quantifiers |
¬(∀𝑥𝑊) ≡ ∃𝑥¬W |
¬(∃𝑥𝑊) ≡ ∀𝑥¬W |
Quantifiers
Formalize English sentences and entire arguments into FOPC |
∀𝑥 quantifies a conditional |
∃𝑥 quantifies a conjunction |
∀𝑥 with conditional for “all,” “every,” and “only.” |
∃𝑥 with conjunction for “some,” “there is,” and “not all.” |
∀𝑥 with conditional or ¬∃𝑥 with conjunction for “no A is B.” |
∃𝑥 with conjunction or ¬∀𝑥 with conditional for “not all A’s are B.” |
Inference Rules FOPC
UI |
Universal instantiation requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥): |
∀𝑥𝑊(𝑥) / 𝑊(𝑡) |
There are two special cases for UI: |
∀𝑥𝑊(𝑥) / 𝑊(𝑥) |
∀𝑥𝑊(𝑥) / 𝑊(𝑐) |
EI |
Existential generalization requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥) |
𝑊(𝑡) / ∃𝑥𝑊(𝑥) |
EG |
Existential generalization requires that 𝑡 is free to replace 𝑥 in 𝑊(𝑥): |
𝑊(𝑡) / ∃𝑥𝑊(𝑥) |
There are two special cases for EG: |
𝑊(𝑥) / ∃𝑥𝑊(𝑥) |
𝑊(𝑐) / ∃𝑥𝑊(𝑥) |
UG |
Universal Generalization |
∃𝑥𝑊(𝑥) / 𝑊(𝑐) |
UI & EI Add A and E from problem; UG, EG, Take the away A and E in the problem.
CS 310 Lecture 5
Array Traversal Operation |
1. Start |
2. Initialize an Array, LA. // 1. Initialize an array called LA |
3. Initialize, i = 0. // 2. Set i - 0 |
4. Print the LA[i] and increment i. // 3. Repeat Steps 4-5 while i < N |
5. Repeat Step 4 until the end of the array. // 4. Print LA[i] |
6. End // 5. Increment the value of i by one. (Set i = i + 1) |
// represent possible modifications you can do that would still be counted as correct
CS 310 Lecture 5
➢An abstract data type (ADT) in data structure is a data type defined with the help of some attributes and some functions |
➢An abstract data type in the data structure can be |
➢A list data structure |
➢A stack data structure |
➢A queue data structure |
➢Linked List: A LL is a linear data structure constructed like a chain of nodes where |
➢Each node contains a data field |
➢A reference(link/address/array-Indices) to the next node in the list. |
➢Unlike Arrays, Linked List elements are not stored at a contiguous location. |
CS 310 Lecture 5
Doubly-linked list: Operations
➢Insertion: Inserting At the Beginning, at the end, after a given node, and before a
given node.
➢Deletion: Deleting from the Beginning, end, and a specific node of the list
➢Display: This process displays the elements of a doubly LL.
CS 310 Lecture 5
Doubly-linked list: Inserting after a given node
➢ Inserting after a given node can be done by:
➢Firstly create a new node (say new_node).
➢Now insert the data in the new node.
➢Point the next of new_node to the next of prev_node.
➢Point the next of prev_node to new_node.
➢Point the previous of new_node to prev_node.
➢Change the pointer of the new node’s previous pointer to new_node.
|
Created By
Metadata
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets