STUDENT HELPLINE : 08888484828

HOW TO PREPARE FOR DATA STRUCTURES AND ALGORITHMS FOR GATE-2017
May 20, 2018

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