Data Structures and Algorithms (ITE1004)

Credits : 4

NOTE:

This subject will not leave you for the rest of your life, till you are there in the Tech industry. The level of difficulty asked in VIT exams is fairly easy, provided you practice the concepts regularly. If you do this subject right, and build the right foundation, it will help you a lot in the long run.

This subject is like Mathematics, there is no limit to the questions solved, you will find a plethora of great DSA questions.

The god of all the material is GeeksforGeeks (GFG) –

https://www.geeksforgeeks.org/fundamentals-of-algorithms/ https://www.geeksforgeeks.org/data-structures/

The playlists which we will be using are :

Jenny’s Lectures
Abdul Bari (Algorithms) : Personal Favourite

MODULE 1

Introduction to Data structures and Algorithms

Topics Included: Overview and importance of algorithms and data structures, Stages of algorithm development for solving a problem: Describing the problem, identifying a suitable technique, Design of an Algorithm, Proof of Correctness of the Algorithm, Computing the time complexity of the Algorithm

Videos to watch: According to the playlist

1.0 to 1.5.3

Faculty’s slides will do wonders for this module

MODULE 2

Analysis of Algorithms

Topics Included: Asymptotic notations and their significance, Running time of an algorithm, Time-complexity of an algorithm, Performance analysis of an algorithm, Analysis of iterative and recursive algorithms, Master theorem (without proof)

Videos to watch: According to the playlist

1.8.1 to 2.5

MODULE 3

Data Structures:

Topics Included: Importance of data structures, Arrays, Stacks, Queues, Linked list, Trees, Hashing table, Binary Search Tree, Heaps.

Videos to watch: According to the playlist

1.1 to 5.12

MODULE 4

Algorithm Design Paradigms

Topics Included: Divide and Conquer, Brute force, Greedy, Recursive Backtracking and Dynamic programming

Videos to watch:

Jenny’s Lectures (for Greedy): 7.1 to 8.3

Divide and Conquer covered in Module 2

Brute Force: https://www.youtube.com/watch?v=uUUsmu-uNnQ

Dynamic Programming: https://www.youtube.com/playlist?list=PLxCzCOWd7aiHcmS4i14bI0VrMbZTUvlTa (watch video 28 and 29)

Backtracking: 6.1 to 6.4

MODULE 5

Graph Algorithms

Topics Included: Breadth First Search (BFS), Depth First Search (DFS), Minimum Spanning Tree (MST), Single Source Shortest Paths

Videos to watch: According to the playlist

6.1 to 6.15

MODULE 6

Computational Complexity classes

Topics Included: Tractable and Intractable Problems, Decidable and Undecidable problems, Computational complexity Classes: P, NP and NP complete - Cooks Theorem ( without proof),3-CNF-SAT Problem, Reduction of 3-CNF-SAT to Clique Problem, Reduction of 3-CNF-SAT to Subset sum problem

Videos to watch:

Tractable and Intractable Problems –

https://www.youtube.com/watch?v=26zyR6NevdY

Decidable and Undecidable problems –

https://www.youtube.com/watch?v=RiDzt22KUd8

P, NP and NP complete - Cooks Theorem (without proof) and rest topics:

8.0 to 9.2

MODULE 7

Recent Trends

Topics Included: Algorithms related to Search Engines

Faculty’s slides will do wonders for this module

MODULE 8