Vidyarthi AIStudent Career Compass

BCS304VTU · Sem 3

Data Structures and Applications

VTU 2022 scheme (B.E. CSE and allied, from 2023-24) · 100 marks: 50 SEE + 50 CIE. SEE is a 3-hour paper of 100 marks scaled to 50: 10 questions of 20 marks (2 per module, up to 3 sub-questions each), answer 5 full questions choosing one from each module. CIE 50 = 25 from two internal tests + 25 from assignments/other methods. Minimum 18/50 in SEE, 20/50 in CIE, 40/100 overall. Lab BCSL305 is a separate 1-credit course (50 CIE + 50 SEE).

Official syllabus

Revised 0 of 105 high-repeat questions

One-Night Pass Pack

Stack is a LIFO list where insertion and deletion happen only at the top. push: if top == MAX - 1, print 'Stack Full'; else s[++top] = item. pop: if top == -1, print 'Stack Empty' and return; else return s[top--]. display: print s[top] down to s[0]. All operations are O(1) except display (O(n)).
Full-marks tip: Write #define MAX, the global array and int top = -1, then the three functions. Draw the stack after a few pushes and pops. Mention the dynamic array version (realloc to double size) for extra marks.

Exam kal hai? Send this Pass Pack to your batch group.

Unit-wise syllabus

U1Introduction to Data Structures, Arrays, Structures and Stacks

Weightage: Equal share: 1 of 5 modules (~20%), 2 questions per module in SEE

Classification of data structures (primitive and non-primitive), operationsPointers and dynamic memory allocation (malloc, calloc, realloc, free)Arrays, dynamically allocated arrays, structures and unionsPolynomials, sparse matrices, multidimensional arrays, strings and pattern matching (KMP)Stacks, stacks using dynamic arraysEvaluation and conversion of expressions (infix, postfix)

U2Queues and Linked Lists

Weightage: Equal share: 1 of 5 modules (~20%), 2 questions per module in SEE

Queues, circular queues, queues using dynamic arraysMultiple stacks and queuesSingly linked lists and chains, representing chains in CLinked stacks and queuesPolynomial representation and addition using linked lists

U3Linked Lists (contd.) and Trees

Weightage: Equal share: 1 of 5 modules (~20%), 2 questions per module in SEE

Additional list operations (invert, concatenate, circular lists)Sparse matrices using linked listsDoubly linked listsBinary trees: properties and representationBinary tree traversals: inorder, preorder, postorder, level orderThreaded binary trees

U4Trees (contd.) and Graphs

Weightage: Equal share: 1 of 5 modules (~20%), 2 questions per module in SEE

Binary search trees: insert, delete, searchSelection trees (winner and loser trees)Forests and conversion to binary treesDisjoint sets: union and find, weighted union, collapsing findCounting binary trees, constructing a tree from traversalsGraph ADT, representations, DFS, BFS, connected components

U5Hashing, Priority Queues and Efficient BSTs

Weightage: Equal share: 1 of 5 modules (~20%), 2 questions per module in SEE

Static hashing: hash tables, hash functions, overflow handling (linear probing, chaining)Dynamic hashing (with and without directories)Single and double ended priority queuesLeftist trees (min leftist tree, melding)Optimal binary search trees

Curated video lectures

Free lectures from well-known educators, matched to units. Videos load only when you tap “Watch here”, to save data.

Data Structures (arrays, stacks, queues, linked lists, trees)

Neso Academy · Playlist · 144 videos · English

C Programming and Data Structures (pointers, dynamic memory, structures)

Neso Academy · Playlist · 314 videos · English · Unit 1

Data Structures and Algorithms full course

Jenny's Lectures CS IT · Playlist · 122 videos · English

Linked lists, stacks, queues and binary trees in C

mycodeschool · Playlist · 42 videos · English · Unit 2

Algorithms: hashing, BFS/DFS and optimal BST

Abdul Bari · Playlist · 84 videos · English · Unit 5

Exam Guide Radar

Standard textbook

Ellis Horowitz, Sartaj Sahni and Susan Anderson-Freed, Fundamentals of Data Structures in C, 2nd Edition, Universities Press, 2014

Exam guide students buy

Sunstar Exam Scanner for VTU 3rd semester CSE (2022 scheme) or a Technical Publications Data Structures and Applications book written for VTU

Pick the 2022-scheme edition: question banks are arranged module-wise with solved VTU papers.

Local market tip

Pick the edition that prints code BCS304 and the 2022 scheme on the cover, not 21CS32 or 18CS32 books, and buy before the first IA test in your college's book stall or near your campus.

Lab Viva Survival

BCSL305 Programs 3, 4, 5: Stack menu program, infix to postfix, postfix evaluation and Tower of Hanoi

Q. How do you check a palindrome using a stack?: → Push all characters, then pop and compare with the original string from the start; all must match.
Q. What is the postfix of A + B * C?: → A B C * +, because * has higher precedence than +.
Q. How many moves does Tower of Hanoi need for n disks?: → 2^n - 1 moves, so 7 moves for 3 disks.
Q. Which header and function did you use for dynamic memory?: → stdlib.h with malloc or calloc to allocate and free to release memory.

BCSL305 Programs 6 to 9: Circular queue, SLL of students, DLL of employees, circular list polynomial

Q. How do you detect a full circular queue?: → When (rear + 1) % MAX equals front.
Q. How can a doubly linked list work as a double-ended queue?: → Insert and delete at both the front and the end, since each node has left and right links.
Q. Why use a header node in the polynomial program?: → The list is never empty, so insertion and traversal code need no special case for NULL.

BCSL305 Programs 10 to 12: BST, graph reachability with DFS/BFS, hashing with linear probing

Q. What is the time to search in a BST?: → O(h): O(log n) for a balanced tree, O(n) for a skewed tree.
Q. Why did you use an adjacency matrix for the cities graph?: → It is easy to code and checking an edge is O(1); lists save space for sparse graphs.
Q. What happens in linear probing when the slot is occupied?: → The next slot (index + 1) % m is checked until an empty slot is found.