DS102 - DATA STRUCTURE 2

Counting

A basic mathematical tool that has uses in the most diverse circumstances

Product and Sum Rules

Represent the most intuitive notions of counting

Product Rule

Suppose there are n(A) ways to perform task A, and regardless of how task A is performed, there are n(B) ways to perform task B

Product Rule Formula

n(A) · n(B)

Sum Rule

Suppose there are n(A) ways to perform task A, and distinct from these, there are n(B) ways to perform task B

Sum Rule Formula

n(A) + n(B)

Sum Rule for Multiple Tasks

n(A) + n(B) + n(C)

Inclusion and Exclusion Principle

A counting principle used when sets overlap. It prevents elements that belong to more than one set from being counted more than once

Inclusion and Exclusion Principle For two sets formula

|A ∪ B| = |A| + |B| − |A ∩ B|

Inclusion and Exclusion Principle For three sets formula

|A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|

Pigeonhole Principle

If (k + 1) or more objects are placed into k boxes, then there is at least one box containing two or more of the objects

Permutation

An ordered arrangement of distinct objects

r-permutation

The arrangement of r-elements of a set

Permutation Formula

P(n,r) = n! / (n − r)!

Combination

An r-combination of elements of a set is an unordered selection of r elements from the set

Pascal’s Triangle

A triangular array constructed by summing adjacent elements in preceding rows. It is named after the French mathematician Blaise Pascal

Pascal’s Triangle Rule

Each number is the sum of the numbers to its upper left and upper right

Binomial Coefficient

The number of ways of picking unordered outcomes from possibilities, also known as a combination or combinatorial number

Algorithms

A topic included in the lecture before Cryptography

Cryptography

The subject of transforming information so that it cannot be easily recovered without special knowledge

Classical Cryptography

Cryptography involving traditional methods of transforming messages into secret forms

Encryption

The process of making a message secret

Caesar’s Cipher / Shift Cipher

f(p) = (p + n) mod 26

Julius Caesar’s Cipher / Shift Cipher

Uses two aligned alphabets. A shift parameter is used as the key

Caesar’s Cipher

Each letter of the message in the "plain" line is matched with the corresponding letter in the "cipher" line

Caesar’s Encryption

Can be represented using modular arithmetic by transforming letters into numbers

Encryption Formula

f(p) = (p + n) mod 26

Decryption

The process of determining the original message from the encrypted message

Decryption Formula

f⁻¹(p) = (p − n) mod 26

Caesar’s Decryption

Uses the same letter-to-number system

Decryption Formula

f⁻¹(p) = (p − n) mod 26

Trees

In 1857, English mathematician Arthur Cayley used trees to count certain types of chemical compounds

Tree

A connected undirected graph with no simple circuits

Theorem

An undirected graph is a tree if and only if there is a unique simple path between any of its vertices

Node

In tree data structure, every individual element is called

Root

In a tree data structure, the first node is called

Edge

In a tree data structure, the connecting link between any two nodes is called

Parent

In a tree data structure, the node which is predecessor of any node is called

Child

In a tree data structure, the node which is descendant of any node is called

Siblings

In a tree data structure, nodes which belong to same Parent are called

Leaf

In a tree data structure, the node which does not have a child is called

Internal Nodes

In a tree data structure, the node which has at least one child is called

Degree

In a tree data structure, the total number of children of a node is called

Level

In a tree data structure, the root node is said to be at Level 0. The children of the root node are at Level 1, and the children of the nodes at Level 1 are at Level 2, and so on

Height

In a tree data structure, the total number of edges from a leaf node to a particular node in the longest path is called

Depth

In a tree data structure, the total number of edges from root node to a particular node is called

Path

In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as ____ between those two Nodes

Sub tree

In a tree data structure, each child from a node forms a subtree recursively. Every child node will form a subtree on its parent node

Leftmost Derivation

The derivation proceeds by replacing the leftmost nonterminal first

Rightmost Derivation

The derivation proceeds by replacing the rightmost nonterminal first