Last Minute Notes(GATE Important End Minute Notes/Problems -)2019

• Last Minute Notes -C/C++

• In modern systems, size of all pointer types on a given platform is same i.e. whether it is ‘pointer to char’ or ‘pointer to int’ or ‘pointer to pointer to int’ etc., the size of all these pointers is same.
• In C, an identifier (e.g. variable) can consists of letters, digits and underscores only. But it can’t start with a digit e.g. 9var is invalid.
• Unlike ‘long long int’, there’s nothing like ‘long long double’ in C. Besides, real data types (i.e. float, double, long double) can’t be unsigned.
• In C, ‘printf(“%d”,090);‘ is invalid because an octal constant consists of the prefix 0 optionally followed by a sequence of the digits 0 through 7 only.
• Real constants (e.g. 1.414) has data type as double. To convert them to float, we need to suffix them with f or F (e.g. 1.414f or 1.414F).

• Modulus operator (%d) isn’t defined for real types however library functions fmod(), fmodf(), fmodl() from math.h can be used for double, float and long double respectively.
• In C, any of the 3 expressions of for loop i.e. for(exp1 ; exp2 ; exp3) can be empty. Even all of the three can be empty.
• The controlling expression of a switch statement i.e. switch(exp) shall have integer type (i.e. int, char etc.) only.
• When continue statement is hit in while or do-while loops, the next executed statement is controlling expression of while or do-while loops. But when continue statement is hit in for loop, the next executed statement is expression3 which is called increment expression as well.
• As per C standard, continue can be used in loop body only. And break can be used in loop body and switch body only.

• In C, goto statement can be used inside functions only and its label can point to anywhere in the same function only.
• In switch body, two case can’t result in same value though having only one case or only default is okay. In fact, switch body can be empty also.
• As per C standard, a jump statement causes an unconditional jump to another place and all goto, continue, break, return are jump statements.
• In C, typedef is used to create alias of any other type. It can be used to create alias for ‘array’ and ‘function pointer’ as well.
• Multiple aliases of different types can be created using one typedef only. For example, ‘typedef int INT, *INTPTR, ONEDARR[10];’ is completely valid.

• The only storage-class specifier that shall occur in a parameter declaration is register. That’s why even ‘fun(auto int arg)’ is incorrect.
• In C, signed, unsigned, short and long are Type specifiers and when they are used, int is implicitly assumed in all of these. So ‘signed i; unsigned j; short k; long l;’ is valid.
• Though const and volatile look opposite to each other but a variable can be both constand volatile.
• const is a Type qualifier and a variable qualified with const means that the value of variable isn’t modifiable by the program.
• volatile is a Type qualifier and a variable qualified with volatile means that value of variable is subject to sudden change (possibly from outside the program)

• A function can’t have an explicit array as return type i.e. ‘int [5] func(int arg1)’ is invalid. However, indirect methods can be used if array like info needs to be output from a function (e.g. using pointers).
• Though sizeof() looks like a function, it’s actually an operator in C. Also, sizeof() is a compile time operator. That’s why the output of ‘printf(“%d”,sizeof(printf(“GQ”)));’ would be same as ‘printf(“%d”,sizeof(int));’. Basically, operand of sizeof() operator isn’t evaluated at run time. Variable length array (introduced in C99) is exception for this.
• While assigning any function to a function pointer, & (address of) is optional. Same way, while calling a function via function pointer, * (value at address) is optional.
• In C, for macros with arguments, there can’t be any space between macro name and open parenthesis.
• C language doesn’t provide any true support for 2D array or multidimensional arrays. For example, a 2D array is simulated via 1D array of arrays.

• Important point is that array size can be derived from its initialization but that’s applicable for first dimension only. For example, ‘int arr[][2] = {1,2,3,4}’ is valid but ‘int arr[2][] = {1,2,3,4}’ is not valid.
• Dereferencing of void pointer isn’t allowed because void is an incomplete data type.
• In C, initialization of array can be done for selected elements as well. Specific elements in array can be initialized using []. For example, ‘int arr[10] = {100, [5]=100,[9]=100};’ is legal in C. This initializes arr[0], arr[5] and arr[9] to 100. All the remaining elements would be 0.
• As per C standard, if array size is defined using variable, the array can’t be initialized at definition itself. For example, ‘int size = 2, arr[size];’ is valid but ‘int size = 2, arr[size] = {1,2};’ is invalid. Also, an array whose size is specified using variable can’t be defined out any function i.e. this array can’t be global.
• In C, struct members can be initialized even out of order using field name and using dot operator. For example, ‘struct {int i; char c;} myVar = {.c =’A’,.i = 100};’ is valid.

• LMNs-Data Structure(last Minute Notes)

• Arrays 
  An array is collection of items stored at continuous memory locations. The idea is to declare multiple items of same type together. Array declaration: In C, we can declare an array by specifying its and size or by initializing it or by both.

  // Array declaration by specifying size
  int arr[10];
  
  // Array declaration by initializing elements
  int arr[] = {10, 20, 30, 40};
  
  // Array declaration by specifying size and
  // initializing elements
  int arr[6] = {10, 20, 30, 40}

•  Length of Array = UB - LB + 1 
  
  Given the address of first element, address of any other element is calculated using the formula:-
     Loc (arr [k]) = base (arr) + w * k
     w = number of bytes per storage location 
         of for one element 
     k = index of array whose address we want 
         to calculate
  
  Elements of two-dimensional arrays (mXn) are stored in two ways:-
  
  Column major order: Elements are stored column by column, i.e. all elements of first column are stored, and then all elements of second column stored and so on.
  
     Loc(arr[i][j]) = base(arr) + w (m *j + i)
  
  Row major order: Elements are stored row by row, i.e. all elements of first row are stored, and then all elements of second row stored and so on.
  
     Loc(arr[i][j]) = base(arr) + w (n*i + j)
  
  Stacks
  
  Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).
  

• Basic operations :
  Push: Adds an item in the stack. If the stack is full, then it is said to be an Overflow condition. (Top=Top+1) Pop: Removes an item from the stack. The items are popped in the reversed order in which they are pushed. If the stack is empty, then it is said to be an Underflow condition.(Top=Top-1)
  Peek: Get the topmost item.
  Infix, prefix, Postfix notations
  Infix notation: X + Y – Operators are written in-between their operands. This is the usual way we write expressions. An expression such as

     A * ( B + C ) / D

  Postfix notation (also known as “Reverse Polish notation”): X Y + Operators are written after their operands. The infix expression given above is equivalent to

   
     A B C + * D/

  Prefix notation (also known as “Polish notation”): + X Y Operators are written before their operands. The expressions given above are equivalent to

   
     / * A + B C D

  Converting between these notations: Click here
  Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:
• 1) Only one disk can be moved at a time.
  2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
  3) No disk may be placed on top of a smaller disk.

  For n disks, total 2n – 1 moves are required 
  Time complexity : O(2n) [exponential time]

  Queues
  Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO).  A good example of queue is any queue of consumers for a resource where the consumer that came first is served first. Stack :  Remove the item the most recently added Queue: Remove the item the least recently added Operations on Queue:
  Enqueue: Adds an item to the queue. If the queue is full, then it is said to be an Overflow condition.
  Dequeue: Removes an item from the queue. The items are popped in the same order in which they are pushed. If the queue is empty, then it is said to be an Underflow condition.
  Front: Get the front item from queue.
  Rear: Get the last item from queue.
  Linked Lists
  Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at contiguous location; the elements are linked using pointers.
  Advantages over arrays
  1) Dynamic size
  2) Ease of insertion/deletion
  Drawbacks:
  1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists.
  2) Extra memory space for a pointer is required with each element of the list. Representation in C: A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL.
  Each node in a list consists of at least two parts: 
  1) data
  2) pointer to the next node In C, we can represent a node using structures. Below is an example of a linked list node with an integer data.

  // A linked list node
  struct node
  {
    int data;
    struct node *next;
  };

Last Minute Notes – DBMS

E-R Diagram: The most common asked questions in ER diagram is minimum number of tables required for a given ER diagram. Generally, following criteria are used

Cardinality	Minimum No. of tables
1:1 cardinality with partial participation of both entities	2
1:1 cardinality with total participation of atleast 1 entity	1
1:n cardinality	2
m:n cardinality	3

Note: This is a general observation. Special cases need to be taken care. We may need extra table if attribute of a relationship can’t be moved to any entity side.

Keys of a relation: There are various types of keys in a relation which are:

• Candidate Key: The minimal set of attributes which can determine a tuple uniquely. There can be more than 1 candidate key of a relation and its proper subset can’t determine tuple uniquely and it can’t be NULL.
• Super Key: The set of attributes which can determine a tuple uniquely. A candidate key is always a super key but vice versa is not true.
• Primary Key and Alternate Key: Among various candidate keys, one key is taken primary key and others are alternate keys.

Normal Forms

• First Normal Form: A relation is in first normal form if it does not contain any multi-valued or composite attribute.
• Second Normal Form: A relation is in second normal form if it does not contain any partial dependency. A dependency is called partial dependency if any proper subset of candidate key determines non-prime (which are not part of candidate key) attribute.
• Third Normal Form: A relation is in third normal form if it does not contain any transitive dependency. For a relation to be in Third Normal Form, either LHS of FD should be super key or RHS should be prime attribute.
• Boyce-Codd Normal Form: A relation is in Boyce-Codd Normal Form if LHS of every FD is super key. The relationship between Normal Forms can be represented as:1NF⊃2NF⊃3NF⊃BCNF

Relational Algebra: Procedural language with basic and extended operators.

Basic Operator	Semantic
σ (Selection)	Select rows based on given condition
∏ (Projection)	Project some columns
X (Cross Product)	Cross product of relations, returns m*n rows where m and n are number of rows in R1 and R2 respectively.
U (Union)	Return those tuples which are either in R1 or in R2. Max no. of rows returned= m+n andMin no. of rows returned = max(m,n)
– (Minus)	R1-R2 returns those tuples which are in R1 but not in R2. Max no. of rows returned = m and Min no. of rows returned = m-n
ρ (Rename)	Renaming a relation to other relation.

Extended Operator	Semantic
∩ (Intersection)	Returns those tuples which are in both R1 and R2. Max no. of rows returned = min(m,n) and Min no. of rows returned = 0
⋈c (Conditional Join)	Selection from two or more tables based on some condition (Cross product followed by selection)
⋈c(Equi Join)	It is a special case of conditional join when only equality condition is applied between attributes.
⋈(Natural Join)	In natural join, equality condition on common attributes hold and duplicate attributes are removed by default. Note: Natural Join is equivalent to cross product if two relations have no attribute in common and natural join of a relation R with itself will return R only.
/(Division Operator)	Division operator A/B will return those tuples in A which is associated with every tuple of B.Note:Attributes of B should be proper subset of attributes of A. The attributes in A/B will be Attributes of A- Attribute of B.

SQL: As opposed to Relational Algebra, SQL is a non-procedural language.

Operator	Meaning
Select	Selects columns from a relation or set of relations.Note: As opposed to Relational Algebra, it may give duplicate tuples for repeated value of an attribute.
From	From is used to give input as relation or set of relations from which data needs to be selected.
where	Where is used to give condition to be used to filter tuples
Group By	Group By is used to group the tuples based on some attribute or set of attributes like counting the no. of students group by department.
Aggregate functions	Find the aggregated value of an attribute. Used mostly with group by. e.g.; count, sum, min max. select count(*) from student group by dept_idNote: we can select only those columns which are part of group by.
Nested Queried	When one query is a part of other query. Solving nested queries questions can be learnt in http://quiz.geeksforgeeks.org/nested-queries-sql/

Conflict serializable and Conflict Equivalent: A schedule is conflict serializable if it is conflict equivalent to a serial schedule.

Checking for Conflict Serializability

To check whether a schedule is conflict serializable or not, find all conflicting operations pairs of a schedule and draw precedence graph ( For all conflicting operation pair, an edge from Ti to Tj if one operation of conflicting pair is from Ti and other from Tj and operation of Ti occurs before Tjin schedule). If graph does not contain cycle, the schedule is conflict serializable else it is not conflict serializable.

Schedules are said to be conflict equivalent if 1 schedule can be converted into another by swapping non conflicting operations.

Note: Two phase locking protocol produce conflict serializable schedule but may suffer from deadlock. On the other hand, Time-Stamp based protocols are free from deadlock yet produce conflict serializable schedule.
View Serializable and View Equivalence: Two schedules S1 and S2 are said to be view-equivalent if all conditions are satisfied for all objects:

• If the transaction Ti in S1 reads an initial value for object X, in S2 also, Ti must read the initial value of X.
• If the transaction Ti in S1 reads the value written by transaction Tj in S1 for object X, same should be done in S2.
• If the transaction Ti in S1 is the final transaction to write the value for an object X, in S2 also,Ti must write the final value of X.

A schedule is view serializable if it is view equivalent to any serial schedule.

Irrecoverable Schedules: For a transaction pair < Ti, Tj >, if Tj is reading the value updated by Ti and Tj is committed before commit of Ti, the schedule will be irrecoverable.

Recoverable Schedules: For a transaction pair < Ti, Tj >, if Tj is reading the value updated by Ti and Tj is committed after commit of Ti, the schedule will be recoverable.

Cascadeless Recoverable Schedules: For a transaction pair < Ti, Tj >, if value updated by Ti is read by Tj only after commit of Ti, the schedule will be cascadeless recoverable.

Strict Recoverable: For a transaction pair < Ti, Tj >, if value updated by Ti is read or written by Tj only after commit of Ti, the schedule will be strict recoverable. The relationship between them can be represented as:

Strict ⊂ Cascadeless Recoverable ⊂ recoverable ⊂ all schedules

File structures :

Primary Index : A primary index is an ordered file, records of fixed length with two fields. First field is same as primary key as data file and second field is a pointer to data block, where the key is available.

The average number of block accesses using index = log2 Bi + 1, where Bi = number of index blocks.

Clustering Index : Clustering index is created on data file whose records are physically ordered on a non-key field (called Clustering field).

Secondary Index : Secondary index provides secondary means of accessing a file for which primary access already exists.

 Number of index entries = Number of records

B Trees :
At every level , we have Key and Data Pointer and data pointer points to either block or record.

Properties of B-Trees :
Root of B-tree can have children between 2 and P, where P is Order of tree.

Order of tree – Maximum number of children a node can have.

Internal node can have children between ⌈ P/2 ⌉ and P 
Internal node can have keys between ⌈ P/2 ⌉ – 1 and P-1

B+ Trees :
In B+ trees structure of leaf and non-leaf are different, so their order is. Order of non-leaf will be higher as compared to leaf nodes.

Searching time will be less in B+ tress, since it doesn’t have record pointers in non-leaf because of which depth will decrease.