Data Structures Using C (DSA&C) — Units I–IV

Unit I: Linear Data Structures - Static and Linked Lists

Start here if you are new. This unit builds the vocabulary of algorithms and data structures, then moves from arrays to dynamic memory and linked lists.

11 hours 12 topic blocks 36 viva prompts

A0A1A2A3

10->25->40NULL

Introduction to Algorithms

A recipe for solving a computational problem.

Input: data given to the algorithm.
Output: answer produced by the algorithm.
Finiteness: it must stop after a limited number of steps.
Definiteness: every step must be unambiguous.

Think IPOF: Input, Processing, Output, Finish.

Algorithm Attributes and Design Techniques

How we describe and build algorithms.

Brute force tries straightforward possibilities.
Divide and conquer splits a problem into smaller similar problems.
Greedy chooses the best-looking immediate option.
Dynamic programming stores results of overlapping subproblems.

Design techniques are problem-solving patterns, not programming languages.

Time Space Trade Off

Use more memory to save time, or save memory and spend time.

Lookup tables store answers for reuse.
Caching saves repeated computation.
Sparse matrix representation saves memory but may make some operations more complex.
Sorting first may take time but makes later searching faster.

Extra memory can act like a shortcut.

Data Structures, Classification and Operations

Ways to organize data so operations become easier.

Primitive: int, char, float, pointer.
Linear: array, linked list, stack, queue.
Non-linear: tree, graph.
Static: size fixed before use, like a normal array.

Linear means one-after-another; non-linear means branching or network-like.

Growth of Functions and Master's Theorem

How running time grows when input grows.

O(1): constant time.
O(log n): logarithmic time.
O(n): linear time.
O(n log n): common for efficient sorting.

For Master Theorem, compare f(n) with n^(log_b a).

Arrays: 1D, 2D and Multi-Dimensional

Same-type elements stored in contiguous memory.

Index usually starts from 0 in C-like languages.
Random access is fast: O(1).
Insertion and deletion in the middle can be costly because shifting is needed.
2D arrays can be stored in row-major or column-major order.

Array = apartment building: room number gives direct location.

Memory Representation and Address Calculation

How locations are calculated from base address and index.

Base address is the address of the first element.
Element size depends on data type.
In row-major order, rows are stored one after another.
In column-major order, columns are stored one after another.

Address = starting point + distance.

Sparse Matrices: Types and Representation

Matrices with mostly zero values.

Triplet form stores row, column, value.
Header row often stores rows, columns, and number of non-zero values.
Diagonal matrix, triangular matrix, symmetric matrix, and band matrix are common sparse-like types.
Sparse storage reduces space when non-zero elements are few.

Do not store silence; store only the notes that are played.

Dynamic Memory Allocation

Memory requested while the program is running.

Stack memory is automatic and limited.
Heap memory is manually managed in languages like C.
C functions include malloc, calloc, realloc, and free.
Dynamic allocation supports linked lists, dynamic stacks, dynamic queues, and trees.

Static is booking seats before the event; dynamic is adding chairs as people arrive.

Dynamic Memory versus Static Memory Allocation

Fixed size versus runtime flexibility.

Static allocation can waste memory if size is overestimated.
Dynamic allocation can cause memory leaks if not released.
Arrays are usually static; linked structures are dynamic.
Dynamic memory may be slower due to allocation overhead.

Static = fixed box; dynamic = adjustable box.

Linked List Types

Nodes connected by links instead of contiguous memory.

Singly linked list: each node points to next.
Doubly linked list: each node points to previous and next.
Header linked list: first node stores metadata or simplifies operations.
Circular linked list: last node points back to first.

A linked list is like a treasure hunt: each clue points to the next location.

Linked List Operations

Creation, insertion, deletion, modification, searching, sorting, reversing, merging.

Creation: allocate nodes and connect them.
Insertion: link new node at beginning, end, or position.
Deletion: adjust links and free removed node.
Modification: search a node and change its data.

In linked lists, order is made by links, not by memory addresses.

Focus Topic

Introduction to Algorithms

A recipe for solving a computational problem.

Beginner Explanation

An algorithm is a finite, ordered set of steps that converts input into output. For example, a recipe that tells you how to search a name in a list is an algorithm.

Good algorithms are clear, correct, finite, and efficient. We judge them by how much time and memory they use as input size grows.

Example

To find the largest number: keep a variable max, compare every item with max, update max when a bigger item appears.

largest(A, n)
  max = A[0]
  for i = 1 to n-1
    if A[i] > max
      max = A[i]
  return max

Flashcards

Flip the cards until the answer feels obvious.

Differentiation Tables

Fast contrasts for exams and viva answers.

Array vs Linked List

Point	Array	Linked List
Memory	Contiguous memory	Non-contiguous nodes connected by links
Size	Usually fixed	Can grow or shrink dynamically
Access	Direct O(1) by index	Sequential O(n)
Insertion/Deletion	Costly in middle due to shifting	Efficient if position pointer is known
Extra Space	No link field	Needs pointer fields

Static vs Dynamic Memory Allocation

Point	Static	Dynamic
Time	Before or at compile/load time	During runtime
Size	Fixed	Flexible
Memory Area	Stack/static area commonly	Heap
Risk	May waste space	Memory leak or dangling pointer
Example	int A[100]	malloc/new node

Linear Search vs Binary Search

Point	Linear Search	Binary Search
Data Requirement	Sorted or unsorted	Sorted only
Method	Check one by one	Check middle and halve range
Worst Time	O(n)	O(log n)
Best Use	Small or unsorted data	Large sorted arrays
Linked List	Works naturally	Not efficient without random access

Selection vs Bubble vs Insertion Sort

Point	Selection	Bubble	Insertion
Main Idea	Select minimum	Adjacent swaps	Insert into sorted part
Best Time	O(n^2)	O(n) with early stop	O(n)
Worst Time	O(n^2)	O(n^2)	O(n^2)
Stable	Usually no	Yes	Yes
Good For	Few swaps	Teaching basics	Small or nearly sorted data

Merge Sort vs Quicksort

Point	Merge Sort	Quicksort
Technique	Divide and merge	Partition around pivot
Average Time	O(n log n)	O(n log n)
Worst Time	O(n log n)	O(n^2)
Space	O(n) for arrays	O(log n) average stack
Stability	Stable if implemented carefully	Usually not stable

Stack vs Queue

Point	Stack	Queue
Principle	LIFO	FIFO
Insertion	Top	Rear
Deletion	Top	Front
Operations	Push, pop, peek	Enqueue, dequeue, front
Example	Undo, recursion	Scheduling, BFS

Linear Queue vs Circular Queue vs Deque vs Priority Queue

Point	Linear Queue	Circular Queue	Deque	Priority Queue
Shape	Straight line	Ring	Both ends active	Priority-based
Deletion	Front only	Front only	Front or rear	Highest/lowest priority
Insertion	Rear only	Rear with wrap	Front or rear	By priority rule
Main Benefit	Simple	Reuses space	Flexible ends	Important items first
Example	Print queue	Buffer	Sliding window	Emergency room

Chaining vs Double Hashing

Point	Chaining	Double Hashing
Collision Handling	Stores collided keys in bucket/list	Finds another table slot using second hash
Memory	Extra links/buckets	Uses table slots
Deletion	Usually simpler	Needs care with deleted markers
Load Factor	Can exceed 1	Must stay below 1
Clustering	Less sensitive	Reduces clustering compared with linear probing

BFS vs DFS

Point	BFS	DFS
Data Structure	Queue	Stack or recursion
Order	Level by level	Depth first
Shortest Path	Yes for unweighted graph	Not guaranteed
Memory	Can store many frontier nodes	Stores path/recursion depth
Uses	Shortest unweighted path	Cycle detection, components

Prim vs Kruskal

Point	Prim	Kruskal
Growth	One tree grows	Forest joins components
Choice	Minimum edge from tree to outside	Minimum global edge avoiding cycle
Needs Sorting	Not necessarily with priority queue	Yes, sort edges
Cycle Check	Avoided by tree/outside rule	Uses union-find
Good For	Dense graphs with matrix	Sparse graphs with edge list

Dijkstra vs Bellman-Ford

Point	Dijkstra	Bellman-Ford
Problem	Single-source shortest path	Single-source shortest path
Negative Edges	Not allowed	Allowed
Negative Cycle Detection	No	Yes
Speed	Faster with priority queue	Slower
Method	Greedy nearest vertex	Repeated relaxation of all edges

BST vs AVL Tree vs B-Tree

Point	BST	AVL Tree	B-Tree
Balance	May be unbalanced	Strictly height-balanced	Balanced multi-way
Children	At most 2	At most 2	Many children
Worst Search	O(n)	O(log n)	O(log n)
Main Use	Simple ordered data	Fast in-memory search	Databases and disks
Maintenance	Simple	Rotations	Split/merge nodes

Quiz

1. What does the Master Theorem commonly solve?

Pick an answer to see the explanation.

Short Notes

Unit I: Introduction to Algorithms

A recipe for solving a computational problem.
Think IPOF: Input, Processing, Output, Finish.
Input: data given to the algorithm.
Output: answer produced by the algorithm.

Unit I: Algorithm Attributes and Design Techniques

How we describe and build algorithms.
Design techniques are problem-solving patterns, not programming languages.
Brute force tries straightforward possibilities.
Divide and conquer splits a problem into smaller similar problems.

Unit I: Time Space Trade Off

Use more memory to save time, or save memory and spend time.
Extra memory can act like a shortcut.
Lookup tables store answers for reuse.
Caching saves repeated computation.

Unit I: Data Structures, Classification and Operations

Ways to organize data so operations become easier.
Linear means one-after-another; non-linear means branching or network-like.
Primitive: int, char, float, pointer.
Linear: array, linked list, stack, queue.

Unit I: Growth of Functions and Master's Theorem

How running time grows when input grows.
For Master Theorem, compare f(n) with n^(log_b a).
O(1): constant time.
O(log n): logarithmic time.

Unit I: Arrays: 1D, 2D and Multi-Dimensional

Same-type elements stored in contiguous memory.
Array = apartment building: room number gives direct location.
Index usually starts from 0 in C-like languages.
Random access is fast: O(1).

Unit I: Memory Representation and Address Calculation

How locations are calculated from base address and index.
Address = starting point + distance.
Base address is the address of the first element.
Element size depends on data type.

Unit I: Sparse Matrices: Types and Representation

Matrices with mostly zero values.
Do not store silence; store only the notes that are played.
Triplet form stores row, column, value.
Header row often stores rows, columns, and number of non-zero values.

Unit I: Dynamic Memory Allocation

Memory requested while the program is running.
Static is booking seats before the event; dynamic is adding chairs as people arrive.
Stack memory is automatic and limited.
Heap memory is manually managed in languages like C.

Unit I: Dynamic Memory versus Static Memory Allocation

Fixed size versus runtime flexibility.
Static = fixed box; dynamic = adjustable box.
Static allocation can waste memory if size is overestimated.
Dynamic allocation can cause memory leaks if not released.

Unit I: Linked List Types

Nodes connected by links instead of contiguous memory.
A linked list is like a treasure hunt: each clue points to the next location.
Singly linked list: each node points to next.
Doubly linked list: each node points to previous and next.

Unit I: Linked List Operations

Creation, insertion, deletion, modification, searching, sorting, reversing, merging.
In linked lists, order is made by links, not by memory addresses.
Creation: allocate nodes and connect them.
Insertion: link new node at beginning, end, or position.

Viva Question Bank

Use Random to practice one Unit I viva question aloud.

Introduction to Algorithms

What is an algorithm?
Why should an algorithm be finite?
What is the difference between an algorithm and a program?

Algorithm Attributes and Design Techniques

Name any three algorithm design techniques.
Where is divide and conquer used?
What does greedy choice mean?

Time Space Trade Off

Define time-space trade off.
Give one example where extra memory reduces time.
Why is sparse matrix storage a space-saving method?

Data Structures, Classification and Operations

What is a data structure?
Classify arrays and graphs.
List common operations on data structures.

Growth of Functions and Master's Theorem

What is Big O notation?
What is the recurrence of merge sort?
State the basic idea of Master's Theorem.

Arrays: 1D, 2D and Multi-Dimensional

What is an array?
Why is array access O(1)?
What is row-major order?

Memory Representation and Address Calculation

What is base address?
Differentiate row-major and column-major order.
Calculate address when base, index, and element size are given.

Sparse Matrices: Types and Representation

What is a sparse matrix?
What is triplet representation?
Name types of sparse matrices.

Dynamic Memory Allocation

What is dynamic memory allocation?
Differentiate malloc and calloc.
Why must dynamically allocated memory be freed?

Dynamic Memory versus Static Memory Allocation

Differentiate static and dynamic memory allocation.
What is a memory leak?
Why is dynamic memory more flexible?

Linked List Types

What is a linked list?
Differentiate singly and doubly linked lists.
What is a circular linked list?

Linked List Operations

What is the time complexity of searching in a linked list?
How do you insert a node after a given node?
Why is pointer order important during deletion?

Unit I: Linear Data Structures - Static and Linked Lists

Flashcards

What are the main attributes of an algorithm?

Input, output, definiteness, finiteness, effectiveness, and correctness.

Why do we analyze algorithms?

To predict time and memory needs before implementing or running them on large input.

Which design technique is used by merge sort?

Divide and conquer.

What is a greedy algorithm?

An algorithm that repeatedly selects the locally best choice hoping it leads to a global optimum.

Give one time-space trade off example.

Hash table search uses more memory than a plain list but gives average O(1) search.

Does every program need minimum memory?

No. Sometimes using extra memory gives much better speed and is worth it.

Differentiation Tables

Array vs Linked List

Static vs Dynamic Memory Allocation

Linear Search vs Binary Search

Selection vs Bubble vs Insertion Sort

Merge Sort vs Quicksort

Stack vs Queue

Linear Queue vs Circular Queue vs Deque vs Priority Queue

Chaining vs Double Hashing

BFS vs DFS

Prim vs Kruskal

Dijkstra vs Bellman-Ford

BST vs AVL Tree vs B-Tree

Quiz

Short Notes

Unit I: Introduction to Algorithms

Unit I: Algorithm Attributes and Design Techniques

Unit I: Time Space Trade Off

Unit I: Data Structures, Classification and Operations

Unit I: Growth of Functions and Master's Theorem

Unit I: Arrays: 1D, 2D and Multi-Dimensional

Unit I: Memory Representation and Address Calculation

Unit I: Sparse Matrices: Types and Representation

Unit I: Dynamic Memory Allocation

Unit I: Dynamic Memory versus Static Memory Allocation

Unit I: Linked List Types

Unit I: Linked List Operations

Viva Question Bank

Introduction to Algorithms

Algorithm Attributes and Design Techniques

Time Space Trade Off

Data Structures, Classification and Operations

Growth of Functions and Master's Theorem

Arrays: 1D, 2D and Multi-Dimensional

Memory Representation and Address Calculation

Sparse Matrices: Types and Representation

Dynamic Memory Allocation

Dynamic Memory versus Static Memory Allocation

Linked List Types

Linked List Operations