The total weight age of this subject in GATE is 17 to 20 marks. This subject can be divided into 3 major parts.

Topic |
Weightage in GATE |
No. of hours preparation for an Average student |

Programming Concepts | 6 to 8 marks | 12 |

Data Structures | 5 to 7 marks | 10 |

Algorithms | 6 to 8 marks | 16 |

Approximate time to be spent for 1 mark question: 1.5 minutes

Approximate time to be spent for 2 marks question: 3 minutes

The preparation method in each topic is given below.

**PROGRAMMING CONCEPTS:**

**Basics and programming constructs: **The questions from this topics are asked to find the output of a simple code. Need to concentrate on below sub topics.

- C – operators and their functioning
- Sequential constructs and their functioning: if, if..else, else if ladder, switch
- Loop constructs and their functioning: while, do..while, for

**Functions: **The questions from this topics are asked to find the output of a simple code. Need to concentrate on below sub topics.

- Recursion: Practice tracing of different recursive programs.
- Storage classes: Understand the behavior of variables based on their storage classes. Also concentrate on the questions on recursion when combined with static and auto variables.
- Static and Dynamic scope: Practice tracing of programs based on the scope of variables.
- Parameter passing techniques: Understand different types of parameter passing techniques from different languages and trace some of the programs. Also concentrate on questions with combination of scope of variables and parameter passing techniques.

**Arrays, Pointers, Structures: **The questions from this topics are asked to find the output of a simple code.

- Arrays: Understand row major and column major order storage and finding address of a particular element. Also trace different programs based on arrays
- Pointers: Understand the concepts of Pointer, pointer to pointer, Pointer to function, Array of pointers, Pointers of different types, Dynamic memory allocation.
- Structures: Understand structure and union and the memory needed for each of them.

**DATA STRUCTURES:**

**Stacks and Queues:**

- Understand Push, Pop in Stacks and EnQueue, DeQueue in Queues
- Concentrate on the applications of stacks and queues: Infix to prefix, infix to postfix conversion, postfix expression evaluation, implementation Queues using stacks etc.

**Linked Lists:**

- Understand the self referential structures.
- Trace different algorithms on different types of Linked lists and analyze the time complexities of such lists.

**Trees:**The most important topic of Data Structures.

- Go through properties of Binary trees, BST, Complete binary trees.
- Tree traversals, construction of binary tree when in-order, pre-order (or) in-order, post-order are given.
- Construction of BST when pre-order or post-order are given, Insert, delete, search operations on BST, the possible sequences when we search for an element in BST.
- Types of heap trees, insert, delete operations.
- AVL tree construction, insert, delete operations.

**ALGORITHMS:**

**Asymptotic Notations:**Concentrate on these sub topics.

- Understand the definitions of different Asymptotic notations, Properties of those notations.
- Comparing different functions to find relation between them.
- Finding time complexities of algorithms with loops.
- Finding time complexities of Recursive algorithms i.e. writing recurrence relations and solve them by different methods.

**Divide and Conquer:** Concentrate on these sub topics.

- Master’s theorem.
- Different problems solved based on D & C: Finding max and min in array, Matrix multiplication, Binary search, Quick sort, Merge sort.
- The time complexities of these algorithms and study of their behavior in best, worst case.

**Sorting:**

- Understand the process of different sorting algorithms, number of iterations and number of comparisons.
- The time complexities of these algorithms and study of their behavior in best, worst case.

**Hashing:**

- Different hash functions, Collision resolution techniques.
- Also concentrate on hashing questions when combined with probability.

**Graph Theory:**

- Graph traversals: DFS, BFS, their applications
- Finding Connected components, Cut vertices and edges, Strongly connected components, Topological sorting.
- Time complexities of these algorithms.

**Greedy Method:**

- Different problems solved based on Greedy: Fractional Knapsack, Job assignment, Job sequencing, Finding MST (Kruskal’s and Prim’s algorithms), Single source shortest path, Huffman coding algorithms.
- Time complexities of these algorithms.

**Dynamic Programming:**

- Different problems solved based on DP: 0/1 Knapsack, Travelling Sales man, All pairs shortest path, Longest common subsequence, Matrix chain multiplication, Optimal Binary search tree.
- Time complexities of these algorithms.

By

**Mrs.Navatha**

M.tech, Gold Medalist in Master’s degree

**For Details Contact**

navatha@icegateinstitute.com