Data Structure and Algorithms
Semester III · BCA 201 · 3 credits
0 / 11
chapters done
-
The syllabus asks for
- Data, data structure and algorithm
- Abstract Data Type
- Why data structures matter
- Measuring cost in one page
- Conventions in this book
- Seeing the ideas: algorithms, structures and cost
Key points
- A data structure organises data for efficient operations; an algorithm is a finite, unambiguous procedure.
- Structures are classified as primitive/non-primitive, linear/non-linear, static/dynamic.
- An ADT specifies behaviour only, so implementations can be swapped.
- The right structure changes cost from linear to logarithmic or constant; Big-O is the common yardstick.
-
The syllabus asks for
- Stack as an ADT
- A complete stack program
- Application 1: balanced brackets
- Expression notations
- Program: infix → postfix → value
- Other applications
- Seeing the ideas: the stack in pictures
Key points
- A stack restricts access to the top, giving LIFO behaviour with O(1) operations.
- Overflow and underflow must be checked in the array implementation.
- Postfix and prefix remove the need for brackets; stacks convert and evaluate them.
- Stacks power bracket matching, recursion, undo and DFS.
-
The syllabus asks for
- Queue as an ADT
- Program: circular queue and priority queue
- Priority queue and deque
- Applications of queues
- Seeing the ideas: queues in life and in memory
Key points
- A queue gives first-come-first-served access with O(1) operations.
- The linear array queue wastes cells; the circular queue reuses them with modulo arithmetic.
- Priority queues break FIFO by priority; deques allow both ends.
- Queues drive scheduling, buffering and BFS.
-
The syllabus asks for
- The List ADT
- Static and dynamic list structures
- Array implementation of a list
- Queue as a list
- Seeing the ideas: the list as an ordered collection
Key points
- A list allows insertion, deletion and access at any position.
- Array lists are fast to index but slow to change in the middle; linked lists are the reverse.
- Shifting is the cost of contiguity; it explains why Unit 5's pointers are needed.
- Queues and stacks are lists with restricted access points.
-
The syllabus asks for
- Singly linked list
- Program: singly linked list
- Linked stack and linked queue
- Doubly and circular linked lists
- Array versus linked list
- Seeing the ideas: nodes, links and pointer changes
Key points
- Linked lists trade O(1) indexing for O(1) structural change and dynamic size.
- The order of pointer assignments is the main source of bugs; always free removed nodes.
- Stacks and queues become capacity-free and O(1) when linked.
- Doubly linked lists add back-links for flexible deletion and two-way traversal.
-
The syllabus asks for
- Principle of recursion
- Programs: factorial, Fibonacci, GCD, power, binary search
- Towers of Hanoi
- Recursion versus iteration
- Applications and the search tree: backtracking
- Seeing the ideas: recursion in objects, calls and trees
Key points
- Recursion solves a problem through smaller versions of itself and needs a reachable base case.
- The call stack stores pending calls; deep or repeated recursion costs memory and time.
- Hanoi needs 2ⁿ − 1 moves; naive Fibonacci recomputes subproblems; iteration or memoisation removes the waste.
- Backtracking explores a search tree and prunes dead branches (N-queens).
-
The syllabus asks for
- Basic terms
- Binary search tree (BST)
- Height, level, depth and tree counting facts
- AVL balanced trees
- B-trees
- The Huffman algorithm
- Game trees and minimax
- Seeing the ideas: trees, balance and compression
Key points
- Trees model hierarchy; binary trees limit each node to two children.
- A BST gives ordered storage and O(h) operations, and inorder traversal gives sorted output.
- AVL rotations keep the height logarithmic; B-trees keep it tiny for disk-based data.
- Huffman builds optimal prefix codes greedily; game trees with minimax and pruning choose moves.
-
The syllabus asks for
- Introduction
- Big-O notation
- The elementary sorts
- Quick sort
- Merge sort
- Heap sort
- Radix sort
- Programs: all the sorts
- Efficiency of sorting
- Seeing the ideas: sorting by machine and by method
Key points
- Elementary sorts are O(n²) but simple; insertion sort is the best of them for small or nearly sorted input.
- Quick, merge and heap sort reach O(n log n); quick is fastest on average but has an O(n²) worst case, merge is stable, heap is in place.
- Radix sort is linear for fixed-width keys; external sort merges sorted runs from disk.
- Big-O describes how cost grows, not exact time.
-
The syllabus asks for
- Introduction to searching
- Sequential (linear) search
- Binary search
- Tree search and the general search tree
- Hashing
- Efficiency comparison
- Seeing the ideas: finding things fast
Key points
- Sequential search is general but O(n); binary search is O(log n) but needs sorted, indexable data.
- Trees add O(log n) updates; multiway trees suit disks.
- Hashing gives O(1) average by computing the address; collisions are handled by chaining or probing.
- Choose by data order, update rate and whether ordered or range queries are needed.
-
The syllabus asks for
- Graphs as an ADT; types of graph
- Representations
- Transitive closure and Warshall's algorithm
- Traversal and spanning forests
- Minimum spanning trees (Kruskal and round-robin)
- Shortest paths: the greedy method and Dijkstra
- Programs: BFS, DFS, Dijkstra, Kruskal, Warshall
- Seeing the ideas: graphs of bridges, roads and routes
Key points
- Graphs generalise trees; representation decides the cost of each operation.
- Warshall's algorithm computes reachability; BFS and DFS traverse in O(n + e) and produce spanning trees or forests.
- Kruskal and round-robin build minimum spanning trees greedily; Dijkstra computes shortest paths greedily.
- Greedy works only when the greedy-choice property holds.
-
The syllabus asks for
- Deterministic and non-deterministic algorithms
- Divide and conquer
- Series (serial) and parallel algorithms
- Heuristic algorithms
- Approximate algorithms
- Seeing the ideas: many ways to design an algorithm
Key points
- Deterministic algorithms follow one path; non-deterministic ones guess and verify, which defines NP.
- Divide and conquer splits, solves and combines; recurrences and the Master theorem give the cost.
- Parallel algorithms speed up only the parallelisable fraction (Amdahl's law).
- For hard problems we accept heuristics (no guarantee) or approximation algorithms (guaranteed ratio).
No chapter matches. Try another word.
The paper
TU assessment: 60% final examination set by the university, 40% internal (assignments, lab work, attendance). Confirm the split in your college's notice.
Where the hours go
Teaching hours are the board's guide to how much of the paper each part carries.
- Unit 5 · Linked Lists5 h
- Unit 7 · Trees5 h
- Unit 8 · Sorting5 h
- Unit 9 · Searching5 h
- Unit 10 · Graphs5 h
- Unit 11 · Algorithms5 h
- Unit 6 · Recursion4 h
- Unit 2 · The Stack3 h
- Unit 3 · Queue3 h
- Unit 1 · Introduction to Data Structure2 h
- Unit 4 · List2 h