# Topic division and how to prepare for Gate 2018 (Full list in next 3 days)

#1

Topic division and way to approach -

1. C programming.

Make hello world program straight away ,make sure it runs.

Learn variables,make programs on signed,unsigned and output,make addition program.

Make prime number program.

Learn loops,make bubble sort,make pattern printing programs.

Learn pointers,practice a lot on them as question most likely to come from this topic.

2.Data structure and algorithms -

1.Learn sorting.

-a)Insertion sort -
open wikipedia,take pencil and paper,do an example by your own.
Try to understand the correctness of insertion sort.
Try to understand the change in no of comparisions needed in insertion sort of array is partially sorted.
Best case occurs when ? Worst case occurs when ? Complexities ?
Recursive version of insertion sort.Derive recurrence relation for it.Compare it with iterative version of insertion sort.
Can we use binary search inside insertion sort where it scans linearly to find out the correct place to where to put element.If yes why?If not,why not ?
Describe a nlogn time algorithm that, given a set S of n integers and another integer x , determines whether or not there exist two elements in S whose sum is exactly x .
.

-b)Merge sort -
Work out an example by your own.
How much space needed to sort n intergers in merge sort.
How do you write merge procedure without using sentinels(Merging two sorted arrays to form one sorted arrays).Read the questions based on merge procedure.
Best case occurs when ? Worst case occurs when ? Complexities ?
Give an algorithm that determines the number of inversions in any permutation on n elements in n lg n worst-case time. (Modify merge sort )

-c) Heap sort
Work out an example using pencil and paper.
Where exactly we are saving in number of comparisions ?
What help building a max heap does,we can still find max of array by O(n) algorithm each time and then swap it with last.
What are the minimum and maximum numbers of elements in a heap of height ?
Where in a max-heap might the smallest element reside, assuming that all elements are distinct?
Is an array that is in sorted order a min-heap?

-d) Quick sort
Work out an example.
Modify quicksort to sort in non increasing order?
Partition function.Quickselect algorithm.
Complexities and worst,best and average case.

Binary Search trees

What is the difference between the binary-search-tree property and the min-heap
property )? Can the min-heap property be used to print out the keys
of an n-node tree in sorted order in O.n time? Show how, or explain why not.

Give a nonrecursive algorithm that performs an inorder tree walk.

Show that if a node in a binary search tree has two children, then its successor has
no left child and its predecessor has no right child.