MajorYear 2 Sem 1

TIT2201

Data Structures and Algorithms

Covers fundamental data structures (arrays, linked lists, trees, graphs, hash tables) and core algorithms including sorting, searching, and graph traversal.

Maintained by @sufikai

Topics Covered

  1. Arrays, dynamic arrays, and memory layout
  2. Linked lists — singly, doubly, circular
  3. Stacks and queues (array-backed and linked)
  4. Recursion and the call stack
  5. Sorting — bubble, insertion, merge, quick, heap
  6. Searching — linear search, binary search
  7. Trees — binary trees, BST, AVL, heaps
  8. Hash tables — collision handling, load factor
  9. Graphs — representation, BFS, DFS
  10. Algorithm complexity — Big-O, time vs space trade-offs

Study Guide

Where to start

Get comfortable with recursion before anything else — trees, graphs, merge sort, and quicksort all depend on it. If recursion feels shaky, spend a day tracing call stacks on paper before moving on.

Arrays and linked lists

Know the time complexity for insert, delete, and access on both. Interviewers and exam questions love asking you to pick one and justify why. Arrays win on random access (O(1)); linked lists win on insert/delete at a known node (O(1) with pointer).

Sorting algorithms

You need to be able to trace merge sort and quicksort by hand. For exams, memorise the worst/average/best cases and whether each is stable. Merge sort is O(n log n) guaranteed; quicksort degrades to O(n²) on a sorted input with naive pivot selection.

Trees and BSTs

Practice in-order, pre-order, and post-order traversals until they are muscle memory. BST insert and delete are common exam questions — draw the tree state after each operation.

Big-O analysis

Drop constants, drop lower-order terms. Focus on the dominant term. Practice deriving complexity from nested loops — each level of nesting multiplies. A loop inside a loop over the same n is O(n²).

Exam Tips

  • Draw diagrams for every linked list and tree question — pointer manipulation is almost impossible to reason about in your head.
  • For sorting, practice tracing the algorithm on a small array (5–7 elements) by hand; exam questions almost always require this.
  • Hash table questions often involve showing collision resolution — know both chaining and open addressing (linear probing).
  • BFS uses a queue; DFS uses a stack (or recursion). Getting these mixed up is the most common graph mistake.
  • Past papers repeat Big-O derivation questions — practise deriving complexity for code snippets with 2–3 nested loops.

External Resources