Dr. R.

Manimegalai, (PhD - IIT Madras)

Professor and Head,
Department of Computer Science and Engineering
PSG Institute of Technology and Applied Research
Coimbatore – 641 062.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 1

• Facts GATE exam

• Higher Education Opportunities

- Details of Fellowships and Scholarships for Higher Education

• Solving of few Data Structure GATE questions (2016-2020)

• Sharing 25 years CSE GATE questions

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 2

• GATE – Graduate Aptitude Test in Engineering
• Conducted annually during the month of February every year

• Tests the comprehensive understanding of various undergraduate subjects in

engineering and science for admission into the Masters Program and Jobs in
Public Sector Companies

• Conducted jointly by the Indian Institute of Science (IISc) and seven Indian
Institutes of Technologies at Roorkee, Delhi, Guwahati, Kanpur, Kharagpur,
Chennai (Madras) and Mumbai (Bombay) on behalf of the National Coordination
Board – GATE, Department of Higher Education, Ministry of Education (MoE),
Government of India

• Conducted in neighboring countries as well – Nepal, Ethiopia, Srilanka,

Singapore, UAE and Bangladesh

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 3

• http://gate.iitm.ac.in/ - IIT Madras,
Chennai

• http://gate.iisc.ac.in/ - IISc, Bangalore

• http://gate.iitd.ac.in/ - IIT Delhi

• https://appsgate.iitb.ac.in/ - IIT Mumbai

• https://jam.iitk.ac.in/ - IIT Kanpur

• http://jam.iitkgp.ac.in/ - IIT Kharagpur

• http://gate.iitg.ac.in/ - IIT Guwahati

• https://www.iitr.ac.in/gate/ - IIT Roorkee

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 4

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 6
• Direct PhD option in almost all 23 IITs with valid GATE score and more than
8.0 CGPA, Stipend  30K to 50K
• https://www.primeministerfellowshipscheme.in/about-the-scheme
A special scheme for 100 'Doctoral Research Fellowships' every year as announced during
the Inception Ceremony of the Indian Science Congress Association, in June 2012 in
Kolkata, stipend ~ 75K per month
• PM Fellowship Scheme for Doctoral Research is a Public-Private Partnership (PPP)
between SERB, which is an autonomous body under DST, Government of India, and
Confederation of Indian Industry (CII)
Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 8
Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 9
 IBM PhD Fellowship Awards ~ 45K

Infosys Fellowship for PhD Students

Other Companies such as Microsoft,

Intel , L&T and Siemens fund
program specific fellowships

PMRF ~ 75K

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 10

• GATE  M.Tech at IITs/IISC and Aided institutions
• GRE  MS at leading abroad universities
• CAT/GMAT  M.B.A at IIMs and abroad
• Scholarships / Fellowships for doing ME / MTech / PhD (Partial List)
• L&T- IIT Scholarship for M.Tech Structural Engineering
• IBM and Infosys Scholarships for doing MS / PhD
• HTRA Schemes in IITs, DAAD Fellowship Programmes with Germany
• The Jawaharlal Nehru Memorial Fund
• K.C. Mahindra Scholarships for Post-Graduate Studies Abroad
• Chevening Scholarships from UK government, Fulbright Scholar Program
• Endeavour Research Fellowship to study at Australia
• National Scholarships (All States), National Talent Search Scholarship (NTS)
• Aditya Birla scholarship, Lucent Scholarships, GE Fund Scholarships,
• Inlaks Foundation Scholarships, Tata Mellanium Scholarship, Jindal Foundation
Scholarship, DAE, DGFS Scholarship by DRDO, AERB scholarship, GE Fund
Scholarship, IEEE / CSI Fellowships, TCS-TRDC Fellowships, Foundation for
Excellence (FEE) Scholarships, Foundation for Excellence Scholarships, Department
of Higher Education, MHRD
Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 11
• Through knowledge in Basics and Strong Fundamentals

• Willingness to learn new things – continuous and life-long

learning
• The right attitude and aptitude towards learning
• Learn-unlearn-relearn

• Soft-skills which include verbal, written, and people skills

• Ability to work in a team
• Basic programming / Computer skills
• Leadership qualities and taking initiatives in day-to-day
activities
Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 12
 Answer : The solution has optimal substructure
We use dynamic programming approach when the solution
has an optimal substructure.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 13

 Answer : (B)
OBST is built using a dynamic programming table that
requires cubic time due to nested loops over subproblems.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 14

 Answer : (C)
Multistage graph problems are solved using optimal
substructure by solving smaller subproblems and combining
their results.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 15

 Answer : Distances will not converge correctly, and a
negative cycle can be detected when the distance of a vertex
to itself becomes negative.
The algorithm's key property is that it cannot handle graphs
with negative cycles but can detect them.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 16

 Answer : B
The DP table has dimensions based on the number of items
(n) and knapsack capacity (W).

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 17

 Answer : A
The solution involves processing each stage once, leading to
a linear time complexity relative to the number of vertices.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 18

 Answer : B
The algorithm iteratively considers each vertex as an
intermediate node for all pairs of vertices.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 19

 Answer : B
The DP approach solves the problem efficiently in O(nW)
time, where n is the number of items and W is the capacity.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 20

 Answer : C
The DP approach calculates the maximum value by
considering the inclusion or exclusion of items. The optimal
solution includes items 2 and 3.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 21

 Answer : A
The algorithm computes all-pairs shortest paths iteratively.
The shortest path from 1 to 3 is via vertex 2.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 22

 Answer : C
Using dynamic programming, the OBST minimizes the
expected search cost. The cost for these probabilities is 1.6.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 23

 Answer : B
The shortest path is computed stage by stage using DP. The path
1→2→3→61 → 2 → 3 → 61→2→3→6 gives a total weight of 9.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 24

 Answer : B
Floyd-Warshall is designed to calculate all-pairs shortest
paths in a weighted graph using dynamic programming.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 25

 Answer : A
Using dynamic programming, the shortest path 1→3→4→5
has a total weight of 2 + 2 + 3 = 7.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 26

 Answer : B
If a vertex i has a negative distance to itself after execution,
it indicates the presence of a negative cycle.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 27

 Answer : B
Using dynamic programming to calculate the OBST, the
minimum cost for the given probabilities is found to be 2.3.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 28

 Answer : B
The optimal selection is to take items with weights 3 and 4,
yielding a total value of 30+20=50.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 29

 Answer : C
Time complexity of Bellman-Ford is O(VE) where V is
number of vertices and E is number of edges. For a complete
graph with n vertices, V = n, E = O(n2). So overall time
complexity becomes O(n3)

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 30

 Answer : B
As the mentioned approach uses the memorization technique
it always stores the previously calculated values. Due to this,
the time complexity is decreased but the space complexity is
increased.

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 31

• Websites of IITs and IISc
• Previous year GATE questions
• https://www.btechguru.com/
• https://www.noticebard.com/
• https://en.wikipedia.org/wiki/
Graduate_Aptitude_Test_in_Engineering

• Textbooks
• Horowitz, Sahni – all titles, Anany Levitin, Weiss

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 32

 Thank You!
and
Best Wishes for Bright Future!!

Cracking GATE Exam – Data Structures, RM / CSE-PSGiTech 33