IITIAN1997 STUDIO

Programming for Problem Solving

ES201 · 35 questions with answers

Open this subject studio →

Introduction to Programming

Topics: Components of a computer (disk, memory, processor, OS, compiler); idea of an algorithm; flowcharts and pseudocode; source code, variables, data types, memory locations; syntax and logical errors; object and executable code; arithmetic expressions and precedence.

The computer, the operating system and the compiler

A computer has a processor (CPU) that executes instructions, main memory (RAM) that holds the running program and its data while power is on, and a disk (hard disk or SSD) that stores files permanently. Input and output devices connect it to people. The operating system (Windows, Linux, Android) manages all of these: it loads programs into memory, shares the CPU among them, controls files, and talks to devices.

The CPU understands only machine code, binary instructions specific to its type. People write programs in a high-level language such as C, whose source code is readable text. A compiler translates the whole source file into machine code; this differs from an interpreter (as for Python), which translates and runs one statement at a time.

Building a C program has four stages. The preprocessor handles lines starting with # (including header files and expanding macros). The compiler turns C into assembly language, the assembler turns that into an object file (.o or .obj) of machine code, and the linker joins it with library code (such as printf) into one executable file (a.out or .exe), which the operating system loads and runs.

  • CPU executes; RAM holds the running program; disk stores files
  • OS manages memory, CPU time, files and devices
  • Compiler translates the whole program; interpreter goes line by line
  • Preprocess → compile → assemble → link
  • Object file (.o) + libraries → executable

Example: List what happens when you type gcc hello.c -o hello and then ./hello.

  1. The preprocessor pastes in stdio.h and removes comments.
  2. The compiler and assembler produce machine code in an object file.
  3. The linker adds the library code for printf and writes the executable hello.
  4. Running ./hello asks the OS to load it into memory and start the CPU at main().

Answer: Preprocess, compile, assemble, link; then the OS loads and runs it

Example: Why can a program compiled on Windows not be run directly on an Android phone?

  1. The executable contains machine code for one processor family (usually x86-64 on a PC).
  2. A phone usually has an ARM processor and a different operating system and file format.

Answer: Machine code and executable format differ; the source must be recompiled

Algorithms, flowcharts and pseudocode

An algorithm is a finite, ordered list of clear steps that solves a problem. A good algorithm has defined inputs and outputs, every step is unambiguous and doable, and it always stops after a finite number of steps. Designing the algorithm first, before writing C, separates the thinking from the syntax.

A flowchart draws an algorithm with standard symbols: an oval for start and stop, a parallelogram for input and output, a rectangle for processing, a diamond for a decision with yes and no branches, and arrows for the flow. It shows branching and loops clearly, which helps beginners and helps explain logic to others.

Pseudocode writes the same steps in structured plain English (READ, SET, IF … THEN … ELSE, WHILE, PRINT) without worrying about C syntax. It is quicker to write and change than a flowchart and maps almost line for line onto C. Before coding, trace the algorithm by hand with sample values in a table to catch mistakes early.

  • Algorithm: finite, unambiguous, ordered, with input and output
  • Flowchart: oval, parallelogram, rectangle, diamond, arrows
  • Pseudocode: READ, SET, IF, WHILE, PRINT
  • Trace by hand with a table of variable values
  • Design first, then code

Example: Write an algorithm to find the largest of three numbers and trace it for a = 12, b = 45, c = 30.

  1. 1 Read a, b, c. 2 big ← a. 3 If b > big then big ← b. 4 If c > big then big ← c. 5 Print big.
  2. Trace: big = 12; 45 > 12 so big = 45; 30 > 45 is false.
  3. Print 45.

Answer: 45

Example: Write pseudocode to find the sum of the first n natural numbers, and its result for n = 5.

  1. READ n; SET sum ← 0; SET i ← 1.
  2. WHILE i ≤ n: sum ← sum + i; i ← i + 1.
  3. PRINT sum. For n = 5: 1 + 2 + 3 + 4 + 5.

Answer: 15

Variables, data types and memory

A variable is a named memory location that holds a value which may change. Each variable has a type, a name, a value and an address. A declaration such as int count = 0; reserves memory of the right size and gives it a starting value. Names may use letters, digits and underscores, must not start with a digit, are case-sensitive, and cannot be keywords such as int or while.

The basic types are char (1 byte, a small integer or one character via its ASCII code), int (usually 4 bytes), float (4 bytes, about 7 significant digits) and double (8 bytes, about 15 digits). Modifiers short, long, signed and unsigned change the range. A signed 4-byte int holds −2 147 483 648 to 2 147 483 647; an unsigned char holds 0 to 255. The sizeof operator gives a type’s size in bytes.

Everything in memory is stored in binary. Integers use two’s complement for negative numbers, characters use their codes (‘A’ is 65), and floating-point numbers use a sign, exponent and mantissa, so 0.1 cannot be stored exactly. Going past a type’s range causes overflow: an unsigned value wraps round, while signed overflow is undefined behaviour in C and must be avoided.

  • Variable = name + type + value + address
  • char 1, int 4, float 4, double 8 bytes (typical)
  • signed int: −2³¹ to 2³¹ − 1
  • sizeof(type) gives bytes
  • Binary storage; 0.1 not exact; beware overflow

Example: Show how 25 is stored in one byte, and how the character ‘A’ is stored.

  1. 25 = 16 + 8 + 1 = 00011001₂.
  2. ‘A’ has ASCII code 65 = 64 + 1 = 01000001₂.

Answer: 00011001 and 01000001

Example: An unsigned char holds 250 and 10 is added. What does it hold?

  1. The range is 0 to 255, so 260 does not fit.
  2. Unsigned values wrap round modulo 256: 260 − 256 = 4.

Answer: 4

Errors: syntax, logical and run-time; object and executable code

Syntax errors break the grammar of C: a missing semicolon, unmatched braces, a misspelt keyword, or an undeclared variable. The compiler reports them with a line number (sometimes the line after the real mistake), and no object code is produced until they are fixed. Warnings point to legal but suspicious code and should be taken seriously.

Linker errors appear when the program calls a function that is never defined, or when a library is not linked (for example forgetting -lm for sqrt on some systems). Run-time errors happen while the program runs: division by zero, reading outside an array, using an invalid pointer, or running out of memory. They may crash the program or silently corrupt data.

Logical errors are the hardest: the program compiles and runs but gives wrong answers, because the algorithm or the code is wrong (using = instead of ==, integer division, an off-by-one loop bound). They are found by testing with inputs whose answers are known, tracing values with printf, and using a debugger to step through the code.

  • Syntax error: compiler stops; no object code
  • Linker error: undefined function or missing library
  • Run-time error: divide by zero, bad index or pointer
  • Logical error: runs but wrong answer
  • Fix with test cases, printf tracing, a debugger

Example: Find the errors: int main() { int a = 5 printf("%d", a); return 0 }

  1. A semicolon is missing after int a = 5.
  2. A semicolon is missing after return 0.
  3. #include <stdio.h> is needed for printf.

Answer: Two missing semicolons and a missing header

Example: int a = 7, b = 2; float avg = (a + b) / 2; prints 4.000000, not 4.5. Why, and how is it fixed?

  1. a + b and 2 are both int, so 9/2 is integer division, giving 4, which is then stored as 4.0.
  2. Make one operand floating: (a + b) / 2.0.

Answer: A logical error from integer division; use 2.0

Arithmetic expressions and precedence

C evaluates expressions by precedence and associativity. Unary operators (++, −−, !, unary minus, casts) bind tightest; then *, / and %; then + and −; then relational operators (<, <=, >, >=), then equality (==, !=), then && and ||, and finally assignment. Operators of equal precedence are applied left to right, except assignment and unary operators, which go right to left. Brackets override everything.

Integer division drops the fraction (7/2 is 3), and % gives the remainder (7 % 2 is 1); with negative numbers C truncates towards zero, so −7/2 is −3 and −7 % 2 is −1. When an int meets a float or double in an expression, it is converted to the wider type first (implicit conversion). A cast such as (float)a forces a conversion explicitly.

The increment operator ++ adds one. Prefix ++i increases i and then gives the new value; postfix i++ gives the old value and then increases i. Never change the same variable twice in one expression (as in i = i++ + ++i): the result is undefined. Compound assignments such as x += 5 are shorthand for x = x + 5.

  • Order: unary → * / % → + − → relational → == != → && → || → =
  • Integer division truncates towards zero
  • % is the remainder; −7 % 2 = −1
  • int with float → float; casts force conversion
  • i++ uses then increments; ++i increments then uses

Example: Evaluate 10 + 3 * 4 / 2 − 5 % 3 in C.

  1. *, / and % first, left to right: 3 * 4 = 12, 12 / 2 = 6, 5 % 3 = 2.
  2. Then 10 + 6 − 2.

Answer: 14

Example: With int a = 7, b = 2, find a / b, a % b and (float)a / b.

  1. a / b is integer division: 3.
  2. a % b = 1.
  3. (float)a / b converts a to 7.0 first: 3.5.

Answer: 3, 1 and 3.5

Example: What do 5 / 2 * 2.0 and 5 * 2.0 / 2 give?

  1. 5 / 2 is evaluated first as ints: 2, then 2 * 2.0 = 4.0.
  2. 5 * 2.0 = 10.0, then / 2 = 5.0.

Answer: 4.0 and 5.0: order changes the answer

Example: int i = 5; int j = i++ + 2; What are i and j?

  1. i++ supplies the old value 5 to the expression.
  2. j = 5 + 2 = 7, and afterwards i becomes 6.

Answer: i = 6, j = 7

A program is stored on disk, loaded into main memory and executed by the processor under the operating system. An algorithm is a finite, unambiguous sequence of steps that solves a problem; it is expressed as a flowchart or pseudocode before coding. A C compiler translates source code (.c) into object code (.o), and the linker joins it with libraries to form an executable. Variables are named memory locations with a data type (int, float, double, char) that fixes their size and range. Syntax errors are caught by the compiler; logical errors give wrong results and must be found by testing.

  • Algorithm properties: input, output, definiteness, finiteness, effectiveness.
  • Flowchart symbols: oval (start/stop), parallelogram (input/output), rectangle (process), diamond (decision), arrows (flow).
  • Typical sizes: char 1 byte, int 4 bytes, float 4, double 8 (machine dependent).
  • Precedence: () > unary > * / % > + − > relational > == != > && > || > = ; * / % associate left to right.
  • Integer division truncates: 7/2 = 3, 7 % 2 = 1, 7.0/2 = 3.5.
  • Compile → link → load → execute; gcc prog.c -o prog.

Key formulas

  • 7 / 2 = 3 (int), 7 % 2 = 1
  • a + b * c evaluates b * c first

Practice questions

The value of 2 + 3 * 4 in C is

  1. 20
  2. 14
  3. 24
  4. 9
Show the answer

Answer: B. 14 Multiplication first: 2 + 12.

A diamond symbol in a flowchart represents

  1. input
  2. process
  3. decision
  4. start
Show the answer

Answer: C. decision Yes/no branch.

Which converts C source into object code?

  1. linker
  2. compiler
  3. loader
  4. editor
Show the answer

Answer: B. compiler Compilation.

17 % 5 equals

  1. 3
  2. 2
  3. 3.4
  4. 5
Show the answer

Answer: B. 2 Remainder.

Theory questions

What is an algorithm? List its characteristics. (2 marks)

Show the model answer

A finite sequence of well-defined steps to solve a problem; input, output, definiteness, finiteness, effectiveness.

Draw a flowchart and write pseudocode to find the largest of three numbers. (5 marks)

Show the model answer

Read a, b, c; if a > b and a > c then max = a, else if b > c then max = b else max = c; print max. Flowchart with two decision diamonds.

Explain the steps from writing a C program to its execution, with syntax and logical errors, and the precedence and associativity of operators. (10 marks)

Show the model answer

Edit source (.c) → preprocess (#include, #define) → compile to object code → link with libraries → load into memory → execute. Syntax errors: violations of grammar (missing ;), reported by compiler. Logical errors: wrong algorithm, found by testing/debugging. Precedence table with examples (a = 10 − 4/2*3 = 4).

Conditional Branching, Loops, Arrays and Strings

Topics: Writing and evaluating conditions and branching; iteration and loops; 1-D and 2-D arrays; character arrays and strings.

Conditions and branching

A condition is an expression that C treats as true if it is non-zero and false if it is zero. Relational operators (<, >, <=, >=, ==, !=) give 1 or 0, and logical operators combine them: && (and), || (or), ! (not). && and || short-circuit: the right side is not evaluated if the left already decides the result, so (n != 0 && x / n > 2) is safe.

The if statement runs a block when its condition is true; if … else chooses between two blocks; and an else-if ladder tests several conditions in order and runs only the first one that is true. Always use braces for clarity, and remember that = assigns while == compares: if (x = 5) is always true and changes x.

The switch statement compares one integer or character expression with constant case labels and jumps to the match. Each case normally ends with break; without it, execution falls through into the next case, which is sometimes useful (several labels sharing code) but usually a bug. A default label handles anything else. The conditional operator c ? a : b gives a compact two-way choice inside an expression.

  • Non-zero is true; zero is false
  • &&, || short-circuit; ! negates
  • if, if-else, else-if ladder
  • switch with case, break, default; beware fall-through
  • c ? a : b; never confuse = with ==

Example: Write the leap-year condition and test 1900, 2000, 2023 and 2024.

  1. (y % 4 == 0 && y % 100 != 0) || y % 400 == 0.
  2. 1900: divisible by 100 but not 400 → not leap. 2000: divisible by 400 → leap.
  3. 2023: not divisible by 4 → not leap. 2024: divisible by 4, not 100 → leap.

Answer: Leap: 2000 and 2024 only

Example: Marks ≥ 80 get A, ≥ 65 B, ≥ 50 C, else F. Write the ladder and find the grade for 78.

  1. if (m >= 80) g = 'A'; else if (m >= 65) g = 'B'; else if (m >= 50) g = 'C'; else g = 'F';
  2. 78 ≥ 80 is false; 78 ≥ 65 is true.

Answer: B

Example: What does this print for n = 2? switch (n) { case 1: printf("one "); case 2: printf("two "); case 3: printf("three "); break; default: printf("other"); }

  1. Execution jumps to case 2 and prints "two ".
  2. There is no break, so it falls through into case 3 and prints "three ", then breaks.

Answer: two three

Loops: while, do-while and for

A loop repeats a block. The while loop tests its condition first and may run zero times. The do-while loop runs the block first and tests afterwards, so it always runs at least once; it suits menus and input checks. The for loop gathers initialisation, condition and update in one line, for (i = 0; i < n; i++), and suits counting loops.

break leaves the innermost loop (or switch) at once; continue skips the rest of the current pass and goes to the next test. A loop whose condition never becomes false is infinite; this is sometimes deliberate (for (;;) with a break) but usually a bug, such as forgetting to update the loop variable.

Loops can be nested: an inner loop runs completely for each pass of the outer one, which is how tables, patterns and matrices are processed. Common loop patterns are counting, summing, finding a maximum, digit extraction with % 10 and / 10, and searching with an early break.

  • while: test first (0 or more passes)
  • do-while: at least one pass
  • for (init; test; update)
  • break leaves the loop; continue skips to the next pass
  • Digit tricks: n % 10, n / 10

Example: Find the sum of digits of 4729 with a while loop.

  1. while (n > 0) { sum += n % 10; n /= 10; }
  2. Digits taken: 9, 2, 7, 4.
  3. sum = 9 + 2 + 7 + 4.

Answer: 22

Example: Reverse 1234 with a loop.

  1. while (n > 0) { r = r * 10 + n % 10; n /= 10; }
  2. r: 4, 43, 432, 4321.

Answer: 4321

Example: Is 91 prime? Use a loop from 2 to √91.

  1. for (d = 2; d * d <= 91; d++) if (91 % d == 0) break;
  2. d = 7 divides: 91 = 7 × 13.

Answer: Not prime

Example: How many times does the body run? int i = 10; do { i++; } while (i < 5);

  1. The body runs before the test: i becomes 11.
  2. 11 < 5 is false, so the loop ends.

Answer: Once

One-dimensional arrays

An array stores many values of one type under one name, in consecutive memory locations: int a[6] reserves six ints, a[0] to a[5]. The index starts at 0, so the last element of an n-element array is a[n − 1]. Arrays can be initialised as int a[] = {7, 3, 9, 4, 6, 2}; the size is then counted for you.

C does not check indices. Writing a[6] in a six-element array reads or overwrites whatever lies next in memory, a classic source of crashes and security holes, so loop bounds must be exactly i = 0 to i < n. The size of an array is fixed when it is declared (variable-length arrays exist in C99 but dynamic memory is often better).

Because elements are consecutive, the address of a[i] is base + i × sizeof(element). Typical array tasks are reading and printing, sum and average, maximum and minimum with their positions, counting values that satisfy a condition, reversing, and searching.

  • int a[n]: elements a[0] … a[n − 1]
  • No bounds checking: stay within 0 ≤ i < n
  • Address of a[i] = base + i × size
  • Initialise: int a[] = {…}
  • Patterns: sum, max, count, reverse, search

Example: For int a[] = {7, 3, 9, 4, 6, 2}, find the maximum and the average.

  1. max starts at a[0] = 7 and is replaced by 9 at index 2; nothing larger follows.
  2. Sum = 7 + 3 + 9 + 4 + 6 + 2 = 31.
  3. Average = 31/6.0 = 5.17.

Answer: Max 9; average ≈ 5.17

Example: int a[10] starts at address 1000 and int is 4 bytes. Where is a[5]?

  1. a[5] is 5 elements after a[0], and each takes 4 bytes.
  2. Address = 1000 + 5 × 4 = 1020.

Answer: 1020

Example: What is wrong with for (i = 1; i <= 6; i++) sum += a[i]; for a six-element array?

  1. It skips a[0].
  2. It reads a[6], which is outside the array.

Answer: Off by one at both ends; use i = 0; i < 6

Two-dimensional arrays and matrices

A two-dimensional array such as int a[3][4] is a table of 3 rows and 4 columns, a[i][j] being row i, column j. It is processed with nested loops: the outer over rows, the inner over columns. Initialise with nested braces, int m[2][2] = {{1, 2}, {3, 4}}.

C stores a 2-D array in row-major order: all of row 0, then row 1, and so on, in one strip of memory. For an array with C columns, the address of a[i][j] is base + (i × C + j) × size. This is why, when an array is passed to a function, the number of columns must be given.

Matrix operations are natural with 2-D arrays. Addition adds matching elements. Transpose swaps rows and columns, t[j][i] = a[i][j]. Multiplication of an m × n by an n × p matrix needs three nested loops: c[i][j] = Σₖ a[i][k] × b[k][j], and is defined only when the inner dimensions match.

  • a[i][j]: row i, column j
  • Nested loops: rows outside, columns inside
  • Row-major: address = base + (i × C + j) × size
  • Transpose t[j][i] = a[i][j]
  • Product c[i][j] = Σ a[i][k] b[k][j]

Example: Multiply [[1, 2], [3, 4]] by [[5, 6], [7, 8]].

  1. c[0][0] = 1×5 + 2×7 = 19; c[0][1] = 1×6 + 2×8 = 22.
  2. c[1][0] = 3×5 + 4×7 = 43; c[1][1] = 3×6 + 4×8 = 50.

Answer: [[19, 22], [43, 50]]

Example: int a[4][5] begins at 2000 (int = 4 bytes). Find the address of a[2][3].

  1. Elements before it: 2 full rows of 5 plus 3 = 13.
  2. Address = 2000 + 13 × 4.

Answer: 2052

Character arrays and strings

C has no separate string type: a string is an array of char ending with the null character ‘\0’, which marks where it stops. char s[] = "hello" uses 6 bytes, five letters plus the terminator. Strings are read with scanf("%s", s) (which stops at a space) or fgets(s, size, stdin) (which reads a whole line safely), and printed with printf("%s", s) or puts.

The header string.h provides strlen (length without the null), strcpy (copy), strcat (join), strcmp (compare: 0 if equal, negative if the first comes earlier in dictionary order, positive otherwise) and others. Strings cannot be copied with = or compared with ==; those operate on addresses, not contents. The destination must be large enough, or memory beyond it is overwritten.

Many string tasks are simple loops that stop at ‘\0’: finding the length, counting vowels or words, changing case (‘a’ − 32 gives ‘A’ in ASCII), reversing, and checking for a palindrome by comparing characters from both ends towards the middle.

  • String = char array ending in '\0'
  • Size = length + 1
  • fgets for whole lines; scanf %s stops at spaces
  • strlen, strcpy, strcat, strcmp (string.h)
  • Never use = or == on strings

Example: Count the vowels in "programming".

  1. Loop until '\0', testing each letter against a, e, i, o, u.
  2. Vowels found: o, a, i.

Answer: 3

Example: What is the sign of strcmp("apple", "apricot")?

  1. Compare letter by letter: a = a, p = p, then p versus r.
  2. 'p' (112) is less than 'r' (114).

Answer: Negative: "apple" comes first

Example: Check whether "madam" is a palindrome.

  1. Compare s[0] with s[4] (m, m) and s[1] with s[3] (a, a).
  2. The middle s[2] needs no partner; all pairs match.

Answer: Yes

Decisions use if, if-else, else-if ladders and switch; loops repeat code with while (test first), do-while (test after, runs at least once) and for (counter-controlled). break exits a loop and continue skips to the next iteration. An array stores many values of one type in contiguous memory, indexed from 0; a 2-D array (matrix) is stored row by row. A string is a char array ending in the null character ‘\0’; <string.h> provides strlen, strcpy, strcat and strcmp.

  • Relational operators return 1 (true) or 0 (false); any non-zero value is true.
  • switch works on integer/char constants; remember break in each case.
  • for (i = 0; i < n; i++) runs n times.
  • int a[5] has elements a[0]…a[4]; out-of-range access is undefined behaviour.
  • char s[10] = "hello" uses 6 bytes including ‘\0’.
  • Matrix product: c[i][j] = Σₖ a[i][k]·b[k][j]; needs columns of A = rows of B.

Key formulas

  • for (init; condition; update)
  • c[i][j] = Σ a[i][k]·b[k][j]
  • strlen("hello") = 5

Practice questions

A do-while loop executes its body at least

  1. 0 times
  2. once
  3. twice
  4. n times
Show the answer

Answer: B. once Condition checked after the body.

The last element of int a[10] is

  1. a[10]
  2. a[9]
  3. a[1]
  4. a[0]
Show the answer

Answer: B. a[9] Indices 0–9.

Strings in C end with

  1. \n
  2. \0
  3. .
  4. EOF
Show the answer

Answer: B. \0 Null terminator.

How many times does for (i = 1; i <= 10; i += 3) run?

  1. 3
  2. 4
  3. 10
  4. 9
Show the answer

Answer: B. 4 i = 1, 4, 7, 10.

Theory questions

Differentiate while and do-while loops. (2 marks)

Show the model answer

while tests the condition before the body (may run zero times); do-while tests after (runs at least once) and ends with a semicolon.

Write a C program to find the sum of digits of a number. (5 marks)

Show the model answer

int n, s = 0; scanf("%d", &n); while (n > 0) { s += n % 10; n /= 10; } printf("%d", s);

Write a C program to multiply two matrices after checking compatibility, and explain how 2-D arrays are stored in memory. (10 marks)

Show the model answer

Read r1, c1, r2, c2; if c1 != r2 print error; read A and B; triple loop: for i, for j, c[i][j] = 0, for k c[i][j] += a[i][k]*b[k][j]; print C. Storage: row-major — a[i][j] is at base + (i × columns + j) × size.

Basic Algorithms

Topics: Searching; bubble, insertion and selection sort; finding roots of equations; order of complexity through example programs.

Searching: linear and binary search

Linear search checks the elements one by one until the key is found or the array ends. It works on any array, sorted or not, but in the worst case needs n comparisons, so it is O(n).

Binary search works only on a sorted array. It compares the key with the middle element; if they are equal the search ends, if the key is smaller it continues in the left half (high = mid − 1), otherwise in the right half (low = mid + 1). Each step halves the range, so at most about log₂n + 1 comparisons are needed: O(log n). For a million elements that is about 20 instead of a million.

Write mid as low + (high − low)/2 rather than (low + high)/2 for very large arrays to avoid integer overflow, and stop when low exceeds high (the key is absent). The extra cost of sorting first pays off when the same data is searched many times.

  • Linear: any order, O(n)
  • Binary: sorted only, O(log n)
  • mid = low + (high − low)/2
  • key < a[mid] ⇒ high = mid − 1; key > a[mid] ⇒ low = mid + 1
  • Stop when low > high: not found

Example: Search for 23 in {2, 5, 8, 12, 16, 23, 38, 56, 72, 91} by binary search.

  1. low 0, high 9, mid 4: a[4] = 16 < 23, so low = 5.
  2. low 5, high 9, mid 7: a[7] = 56 > 23, so high = 6.
  3. low 5, high 6, mid 5: a[5] = 23. Found.

Answer: Index 5 after 3 comparisons

Example: What is the most comparisons binary search needs for 1000 sorted elements? And linear search?

  1. Binary: ⌈log₂(1001)⌉ = 10.
  2. Linear: up to 1000.

Answer: 10 versus 1000

Bubble sort

Bubble sort compares neighbouring elements and swaps them if they are in the wrong order. After the first pass the largest value has bubbled to the end; after the second, the second largest is in place, and so on. Each pass can therefore stop one place earlier.

In the worst case (reverse order) it makes n(n − 1)/2 comparisons and as many swaps, so it is O(n²). A flag that records whether any swap happened lets it stop early: if a whole pass makes no swaps, the array is sorted. With that flag an already sorted array needs only one pass, O(n).

Bubble sort is simple and stable (equal elements keep their order) but slow for large data. Its code shows the basic pattern of nested loops and swapping through a temporary variable: temp = a[j]; a[j] = a[j + 1]; a[j + 1] = temp;.

  • Swap neighbours that are out of order
  • Largest moves to the end each pass
  • Worst case n(n − 1)/2 comparisons: O(n²)
  • Swap flag: stop early; sorted input O(n)
  • Swap with a temporary variable

Example: Bubble-sort {5, 1, 4, 2, 8}, with the early-stop flag, showing each pass.

  1. Pass 1: 1 4 2 5 8 (5 moved past 1, 4 and 2).
  2. Pass 2: 1 2 4 5 8.
  3. Pass 3: no swaps, so stop.

Answer: 1 2 4 5 8 after 3 passes

Example: How many comparisons does plain bubble sort make for 10 elements in the worst case?

  1. Pass k compares n − k pairs: 9 + 8 + … + 1.
  2. Total = n(n − 1)/2 = 10 × 9/2 = 45.

Answer: 45

Selection and insertion sort

Selection sort finds the smallest element of the unsorted part and swaps it into the next position. It always makes n(n − 1)/2 comparisons (O(n²)) but at most n − 1 swaps, which helps when writing to memory is expensive. It is not stable in its usual form.

Insertion sort works like arranging playing cards in the hand: take the next element (the key), shift larger sorted elements one place right, and drop the key into the gap. It is O(n²) in the worst case but O(n) for nearly sorted data, is stable, and is often used for small arrays or as the final stage of faster sorts.

All three simple sorts are O(n²). Faster algorithms such as merge sort and quicksort reach O(n log n), but the simple ones teach the loop patterns and are adequate for a few hundred elements.

  • Selection: pick the minimum, swap into place; ≤ n − 1 swaps
  • Insertion: shift larger elements, insert key
  • Insertion is O(n) on nearly sorted data, and stable
  • All three O(n²) worst case
  • Merge sort and quicksort: O(n log n)

Example: Selection-sort {64, 25, 12, 22, 11}, showing each pass.

  1. Pass 1: minimum 11 swaps with 64: 11 25 12 22 64.
  2. Pass 2: minimum 12 swaps with 25: 11 12 25 22 64.
  3. Pass 3: 22 swaps with 25: 11 12 22 25 64. Pass 4: no change.

Answer: 11 12 22 25 64

Example: Insertion-sort {12, 11, 13, 5, 6}, showing the array after each insertion.

  1. Insert 11: 11 12 13 5 6. Insert 13: unchanged.
  2. Insert 5: 5 11 12 13 6.
  3. Insert 6: 5 6 11 12 13.

Answer: 5 6 11 12 13

Finding roots of equations: bisection and Newton–Raphson

Many equations f(x) = 0 cannot be solved by algebra, so programs approximate the root. If f is continuous and f(a), f(b) have opposite signs, a root lies between a and b. The bisection method takes the midpoint c = (a + b)/2, keeps the half in which the sign changes, and repeats until the interval is smaller than the tolerance. It always converges, halving the error each step, so it is reliable but slow.

Newton–Raphson uses the tangent line: x_(n+1) = xₙ − f(xₙ)/f′(xₙ). Near a simple root it converges very fast, roughly doubling the number of correct digits each step, but it needs the derivative and can fail if f′(x) is near zero or the start is poor.

In C both are loops with a stopping test such as fabs(b − a) < 1e-6 or fabs(f(x)) < 1e-6, plus a maximum number of iterations so that a bad case cannot loop forever. The function is usually written as a separate C function, double f(double x) { return x*x*x - x - 2; }.

  • Bisection: c = (a + b)/2; keep the sign-change half
  • Always converges; error halves each step
  • Newton: x_(n+1) = xₙ − f(xₙ)/f′(xₙ)
  • Very fast near a root; may fail if f′ ≈ 0
  • Stop on tolerance or a maximum number of iterations

Example: Apply three bisection steps to f(x) = x³ − x − 2 on [1, 2].

  1. f(1) = −2, f(2) = 4. c = 1.5: f = −0.125 < 0, so the root is in [1.5, 2].
  2. c = 1.75: f = 1.609 > 0, so [1.5, 1.75].
  3. c = 1.625: f = 0.666 > 0, so [1.5, 1.625].

Answer: Root in [1.5, 1.625] (true root 1.5214)

Example: Use Newton–Raphson for √10 (f(x) = x² − 10) starting at x₀ = 3.

  1. x₁ = 3 − (9 − 10)/6 = 3.166667.
  2. x₂ = 3.166667 − (10.027778 − 10)/6.333333 = 3.162281.
  3. x₃ = 3.162278.

Answer: √10 ≈ 3.162278 in three steps

Order of complexity

The time a program takes grows with the size of its input n. Big-O notation describes that growth, ignoring constant factors and smaller terms: a loop over n elements is O(n), two nested loops over n are O(n²), and halving the range each step is O(log n). The same idea applies to the extra memory a program uses.

To find the order, count how many times the innermost statement runs. A loop for (i = 0; i < n; i++) runs n times; for (i = 1; i < n; i *= 2) runs about log₂n times; a nested loop where j goes from 0 to i runs 0 + 1 + … + (n − 1) = n(n − 1)/2 times, still O(n²).

Usual classes from fast to slow are O(1), O(log n), O(n), O(n log n), O(n²), O(n³) and O(2ⁿ). For small n any method works, but for large n a better algorithm beats a faster computer: replacing an O(n²) sort by an O(n log n) one turns hours into a fraction of a second.

  • Count the innermost operation
  • Single loop O(n); nested O(n²); halving O(log n)
  • Σ i for i < n = n(n − 1)/2 ⇒ O(n²)
  • O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)
  • Algorithm choice beats hardware

Example: How many times does x++ run? for (i = 0; i < n; i++) for (j = 0; j < i; j++) x++;

  1. For each i the inner loop runs i times.
  2. Total = 0 + 1 + … + (n − 1) = n(n − 1)/2.

Answer: n(n − 1)/2, so O(n²)

Example: Sorting 10⁶ numbers at 10⁸ simple steps per second: compare O(n²) with O(n log n).

  1. n² = 10¹² steps ⇒ 10⁴ s, almost 3 hours.
  2. n log₂n ≈ 10⁶ × 20 = 2 × 10⁷ steps ⇒ 0.2 s.

Answer: About 3 hours versus 0.2 seconds

Linear search checks elements one by one (O(n)); binary search halves a sorted array each step (O(log n)). Bubble sort repeatedly swaps adjacent out-of-order pairs, selection sort picks the minimum of the unsorted part, insertion sort inserts each element into the sorted part; all three are O(n²) in the worst case. Roots of f(x) = 0 are found numerically by bisection (halve an interval where f changes sign) or Newton–Raphson (x_{n+1} = xₙ − f(xₙ)/f′(xₙ)). Complexity describes how running time grows with input size.

  • Binary search needs sorted data; ≈ log₂ n comparisons.
  • Bubble sort: after pass k the k largest elements are in place; at most n − 1 passes.
  • Insertion sort is fast (O(n)) on nearly sorted data.
  • Bisection: always converges if f(a)f(b) < 0; error halves each step.
  • Newton–Raphson: fast (quadratic) convergence near the root but needs f′ and a good guess.
  • Growth: O(1) < O(log n) < O(n) < O(n log n) < O(n²).

Key formulas

  • x_{n+1} = xₙ − f(xₙ)/f′(xₙ)
  • c = (a + b)/2 (bisection)
  • Comparisons (bubble) ≤ n(n − 1)/2

Practice questions

Binary search requires the array to be

  1. unsorted
  2. sorted
  3. of even length
  4. of strings
Show the answer

Answer: B. sorted Halving relies on order.

Worst-case complexity of bubble sort is

  1. O(n)
  2. O(log n)
  3. O(n²)
  4. O(1)
Show the answer

Answer: C. O(n²) Nested passes.

Newton–Raphson uses

  1. only f(x)
  2. f(x) and f′(x)
  3. two brackets
  4. random numbers
Show the answer

Answer: B. f(x) and f′(x) Tangent line step.

Maximum comparisons for binary search in 1024 sorted items are about

  1. 1024
  2. 512
  3. 10
  4. 100
Show the answer

Answer: C. 10 log₂ 1024 = 10 (11 in the worst case).

Theory questions

What is the time complexity of linear and binary search? (2 marks)

Show the model answer

Linear O(n); binary O(log n).

Write a C program for bubble sort and show its passes on 5, 1, 4, 2, 8. (6 marks)

Show the model answer

for i in 0..n−2, for j in 0..n−2−i: if a[j] > a[j+1] swap. Pass 1: 1 4 2 5 8; pass 2: 1 2 4 5 8; pass 3: no swaps (sorted).

Write a C program to find a root of x³ − x − 2 = 0 by the bisection method correct to 4 decimal places, and explain the algorithm. (10 marks)

Show the model answer

f(1) = −2, f(2) = 4 ⇒ root in [1, 2]. Loop: c = (a + b)/2; if f(a)·f(c) < 0, b = c else a = c; stop when (b − a) < 0.0001. Root ≈ 1.5214. Code with a function float f(float x) { return x*x*x - x - 2; } and a while loop.

Functions and Recursion

Topics: Functions (including library functions), parameter passing, call by value, passing arrays (idea of call by reference); recursion; examples: factorial, Fibonacci, Ackermann.

Functions and library functions

A function is a named block of code that does one job, can be called from many places, and may return a value. Splitting a program into functions makes it shorter, easier to test, and easier to read. Every C program starts at main(), which calls other functions as needed.

A function has a return type, a name, a parameter list and a body: double area(double r) { return 3.14159 * r * r; }. If it is defined after main, a prototype such as double area(double r); must appear before its first use, so the compiler can check the arguments. A function that returns nothing has type void.

Library functions come with C and are declared in headers: printf and scanf in stdio.h; sqrt, pow, sin, fabs in math.h; strlen, strcpy in string.h; rand, malloc, exit in stdlib.h; toupper, isdigit in ctype.h. Use them instead of rewriting standard tasks: they are tested and fast.

  • Function: return type, name, parameters, body
  • Prototype before use if defined later
  • void for no return value
  • return sends a value back and ends the function
  • Headers: stdio.h, math.h, string.h, stdlib.h, ctype.h

Example: Write a function for the area of a circle and find area(5.0).

  1. double area(double r) { return 3.14159 * r * r; }
  2. area(5.0) = 3.14159 × 25.

Answer: 78.54

Example: What do pow(2, 10), sqrt(144) and fabs(−3.5) return?

  1. pow(2, 10) = 2¹⁰ = 1024.0.
  2. sqrt(144) = 12.0; fabs(−3.5) = 3.5.

Answer: 1024.0, 12.0 and 3.5 (all double)

Parameter passing: call by value and the idea of call by reference

C passes arguments by value: the function receives copies in its own parameters, so changing a parameter does not change the caller’s variable. This protects the caller’s data, and it is why a naive swap function does not work.

To let a function change the caller’s variables, pass their addresses and use pointers. A function void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } called as swap(&a, &b) works on a and b themselves. This is how C gives the effect of call by reference, and it is also how a function can return more than one result.

scanf("%d", &n) needs the & for exactly this reason: scanf must store into n, so it is given n’s address. Local variables live only while their function runs; never return the address of a local variable.

  • C copies arguments (call by value)
  • Changing a parameter does not change the caller’s variable
  • Pass &var and use *ptr to change the original
  • scanf needs addresses: &n
  • Never return the address of a local variable

Example: void swap(int x, int y) { int t = x; x = y; y = t; } What happens to a = 3, b = 7 after swap(a, b)?

  1. x and y receive copies 3 and 7 and are swapped inside.
  2. The copies vanish when swap returns.

Answer: a = 3, b = 7: unchanged

Example: Repeat with void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; } and swap(&a, &b).

  1. x points to a and y to b.
  2. *x and *y are a and b themselves, so they are exchanged.

Answer: a = 7, b = 3

Passing arrays to functions

When an array is passed to a function, C passes the address of its first element, not a copy of all elements. The parameter int a[] is really a pointer int *a, so a function can read and change the caller’s array directly.

Because only an address arrives, the function cannot tell how long the array is (sizeof gives the pointer size inside it), so the length is passed as a separate parameter: int sum(int a[], int n). For 2-D arrays the column count must be part of the parameter type, as in void show(int m[][4], int rows).

Mark array parameters const when the function only reads them, int sum(const int a[], int n), so the compiler stops accidental changes. Returning results through the array itself is common: sorting functions rearrange the caller’s array in place.

  • An array argument passes the address of a[0]
  • int a[] in a parameter means int *a
  • Pass the length separately
  • 2-D: column count required, m[][4]
  • Use const for read-only arrays

Example: void twice(int a[], int n) { for (int i = 0; i < n; i++) a[i] *= 2; } What is x after int x[3] = {1, 2, 3}; twice(x, 3);?

  1. The function receives x’s address, not a copy.
  2. Each a[i] *= 2 changes x itself: 1, 2, 3 become 2, 4, 6.

Answer: {2, 4, 6}

Example: Inside int f(int a[]) { return sizeof(a); } on a 64-bit system, what is returned for an array of 10 ints?

  1. a is a pointer inside the function.
  2. A pointer is 8 bytes on a 64-bit system, not 40.

Answer: 8 (so pass the length separately)

Recursion: factorial, Fibonacci and GCD

A recursive function calls itself on a smaller version of the problem. It needs a base case that stops the recursion and a recursive step that moves towards it. Factorial is the classic example: fact(0) = 1, fact(n) = n × fact(n − 1). Each call waits on the call stack until the smaller call returns.

Recursion often mirrors a mathematical definition directly and simplifies problems that split into similar parts (trees, Towers of Hanoi, divide-and-conquer sorting). Its costs are memory for each stack frame and time for each call; very deep recursion can overflow the stack.

Naive recursive Fibonacci, fib(n) = fib(n − 1) + fib(n − 2), recomputes the same values again and again, so its number of calls grows exponentially: fib(30) makes about 2.7 million calls. An iterative loop, or remembering computed values (memoisation), reduces it to O(n). Euclid’s GCD, gcd(a, b) = gcd(b, a % b) with gcd(a, 0) = a, is recursion that is both short and efficient.

  • Base case + recursive step towards it
  • fact(n) = n × fact(n − 1), fact(0) = 1
  • Each call has its own stack frame
  • Naive Fibonacci is exponential; use a loop or memoise
  • gcd(a, b) = gcd(b, a % b)

Example: Trace fact(5).

  1. fact(5) = 5 × fact(4) = 5 × 4 × fact(3) = … = 5 × 4 × 3 × 2 × 1 × fact(0).
  2. fact(0) = 1, and the calls return in reverse order.

Answer: 120

Example: How many calls does naive fib(5) make, and what does it return?

  1. Calls C(n) = C(n − 1) + C(n − 2) + 1 with C(0) = C(1) = 1.
  2. C(2) = 3, C(3) = 5, C(4) = 9, C(5) = 15.
  3. fib(5) = 5.

Answer: 15 calls; returns 5

Example: Find gcd(48, 18) recursively.

  1. gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0).
  2. The base case returns 6.

Answer: 6

The Ackermann function

The Ackermann function is defined by A(0, n) = n + 1; A(m, 0) = A(m − 1, 1); A(m, n) = A(m − 1, A(m, n − 1)). It is total (always finishes) but grows extraordinarily fast, faster than any function built only from loops of fixed nesting depth, which made it a famous example in the theory of computation.

It is a good test of understanding recursion and the call stack, because the inner call A(m, n − 1) must finish before its result becomes the second argument of the outer call. Small cases follow patterns: A(1, n) = n + 2, A(2, n) = 2n + 3, and A(3, n) = 2^(n+3) − 3.

Even A(4, 1) = 65 533 needs an enormous number of calls and a very deep stack, so in C it is only practical for tiny arguments. Its C code is a direct transcription of the three cases using if-else and return.

  • A(0, n) = n + 1
  • A(m, 0) = A(m − 1, 1)
  • A(m, n) = A(m − 1, A(m, n − 1))
  • A(1, n) = n + 2; A(2, n) = 2n + 3; A(3, n) = 2^(n+3) − 3
  • Grows explosively; deep stack

Example: Evaluate A(1, 2) step by step.

  1. A(1, 2) = A(0, A(1, 1)); A(1, 1) = A(0, A(1, 0)); A(1, 0) = A(0, 1) = 2.
  2. A(1, 1) = A(0, 2) = 3.
  3. A(1, 2) = A(0, 3) = 4.

Answer: 4

Example: Use the patterns to find A(2, 2) and A(3, 3).

  1. A(2, n) = 2n + 3: A(2, 2) = 7.
  2. A(3, n) = 2^(n+3) − 3: A(3, 3) = 64 − 3.

Answer: 7 and 61

Functions break a program into reusable units with a prototype, definition and call. C passes arguments by value — the function gets copies, so changes do not affect the caller — but an array argument passes its base address, so the function can modify the original elements (the idea of call by reference; pointers make it explicit). A recursive function calls itself on a smaller problem and must have a base case; each call gets its own stack frame. Classic examples: n! = n·(n − 1)!, Fibonacci F(n) = F(n − 1) + F(n − 2), and the very fast-growing Ackermann function.

  • Prototype: int max(int, int); definition with body; call max(a, b).
  • Library functions: printf, scanf (stdio.h), sqrt, pow (math.h), strlen (string.h).
  • Call by value: swap(a, b) does not swap the caller’s variables; swap(&a, &b) with pointers does.
  • Recursion needs a base case to stop; otherwise stack overflow.
  • Naive recursive Fibonacci is O(2ⁿ); iterative is O(n).
  • Ackermann A(m, n): A(0, n) = n + 1; A(m, 0) = A(m − 1, 1); A(m, n) = A(m − 1, A(m, n − 1)).

Key formulas

  • fact(n) = n · fact(n − 1), fact(0) = 1
  • fib(n) = fib(n − 1) + fib(n − 2)

Practice questions

In C, scalar arguments are passed by

  1. reference
  2. value
  3. name
  4. pointer automatically
Show the answer

Answer: B. value Copies are passed.

A recursive function must have

  1. a loop
  2. a base case
  3. global variables
  4. no parameters
Show the answer

Answer: B. a base case To stop recursion.

fact(4) computed recursively equals

  1. 10
  2. 16
  3. 24
  4. 4
Show the answer

Answer: C. 24 4 × 3 × 2 × 1.

When an array is passed to a function, the function receives

  1. a copy of all elements
  2. the base address
  3. only the first element value
  4. nothing
Show the answer

Answer: B. the base address Changes affect the original array.

Theory questions

What is recursion? (2 marks)

Show the model answer

A function calling itself to solve a smaller instance of the same problem, with a base case that ends the calls.

Explain call by value and call by reference with a swap program. (5 marks)

Show the model answer

void swap(int x, int y) swaps copies only — caller unchanged. void swap(int *x, int *y){ int t = *x; *x = *y; *y = t; } called as swap(&a, &b) swaps the caller’s variables.

Write recursive C functions for factorial and the nth Fibonacci number, trace fib(4), and compare recursion with iteration. (10 marks)

Show the model answer

long fact(int n){ return n <= 1 ? 1 : n*fact(n-1); } int fib(int n){ return n < 2 ? n : fib(n-1)+fib(n-2); } Trace fib(4) = fib(3) + fib(2) = (fib(2) + fib(1)) + (fib(1) + fib(0)) = 3. Recursion: elegant, uses stack, may be slower/repeat work; iteration: loops, less memory, often faster.

Pointers, Structures and Linked Lists

Topics: Idea of pointers; defining pointers; pointers in self-referential structures; linked list; applications.

The idea of pointers

Every variable lives at a memory address. A pointer is a variable that stores an address. int *p; declares p as a pointer to int; p = &x; makes it hold x’s address (& is the address-of operator); and *p (the dereference or indirection operator) means the int stored at that address, so *p = 20; changes x.

Pointers have types so that C knows how many bytes to read and how far to step. Pointer arithmetic moves in units of the pointed-to type: if p points to an int at 1000 and an int is 4 bytes, p + 1 is 1004 and p + 3 is 1012. A pointer that points nowhere should be set to NULL and checked before use.

Dereferencing an uninitialised, NULL or freed pointer is a run-time error that may crash the program or corrupt memory. Pointers are what make call-by-reference, dynamic memory, efficient array and string handling, and linked data structures possible in C.

  • int *p; p = &x; *p is x
  • & gives the address; * follows it
  • p + k moves k elements, not k bytes
  • Initialise to NULL; check before use
  • Never dereference a wild or freed pointer

Example: int x = 10, *p = &x; *p = *p + 5; What is x?

  1. p holds x’s address, so *p is x.
  2. x = 10 + 5.

Answer: 15

Example: int a[5] starts at 1000 (int = 4 bytes) and int *p = a;. Find p + 3 and explain *(a + 2).

  1. p + 3 = 1000 + 3 × 4 = 1012, the address of a[3].
  2. *(a + 2) is the element two places after a[0], that is a[2].

Answer: 1012; *(a + 2) is the same as a[2]

Pointers with arrays and strings

An array name used in an expression becomes a pointer to its first element, so a[i] is defined as *(a + i). A pointer can therefore walk through an array: for (p = a; p < a + n; p++) sum += *p;. Unlike a pointer variable, the array name itself cannot be reassigned.

Strings are handled the same way. char *s = "ASTU"; points to a string literal (which should not be modified), while char t[] = "ASTU"; is a modifiable array. Loops such as while (*s) { s++; } step through the characters until the null terminator.

An array of pointers, char *names[] = {"Ram", "Rita", "Babu"};, stores strings of different lengths without wasting space, and is how command-line arguments arrive in main(int argc, char *argv[]). A pointer to a pointer (char **) holds the address of a pointer.

  • a[i] ≡ *(a + i)
  • Walk an array with p++
  • String literal via char * is read-only; char[] is editable
  • Array of pointers for strings of different lengths
  • main(int argc, char *argv[])

Example: Count the characters of "ASTU" with a pointer loop.

  1. char *s = "ASTU"; int n = 0; while (*s) { n++; s++; }
  2. The loop stops at the null after U.

Answer: 4

Example: Sum int a[] = {4, 1, 6} with a pointer.

  1. for (p = a; p < a + 3; p++) sum += *p;
  2. sum = 4 + 1 + 6.

Answer: 11

Structures and self-referential structures

A structure groups related variables of different types into one new type: struct student { char name[20]; int roll; float marks; };. Members are reached with the dot operator, s.roll, and through a pointer with the arrow operator, ptr->roll, which means (*ptr).roll. Arrays of structures hold records such as a class list.

Structures can be assigned as a whole, passed to and returned from functions (by value, which copies every member, or by pointer, which is faster for big structures), and nested inside each other. typedef gives a shorter name: typedef struct student Student;.

A self-referential structure contains a pointer to its own type: struct node { int data; struct node *next; };. It cannot contain a whole struct node (that would be infinitely large), but it can point to one. This single idea builds linked lists, trees and graphs, where each element knows where the next one is.

  • struct groups mixed types
  • s.member; ptr->member ≡ (*ptr).member
  • Arrays of structures for records
  • typedef for short names
  • struct node { int data; struct node *next; }

Example: A student has marks 78.5, 82 and 91 stored in a structure. Write the average and its value.

  1. avg = (s.m[0] + s.m[1] + s.m[2]) / 3.0;
  2. (78.5 + 82 + 91)/3 = 251.5/3.

Answer: ≈ 83.83

Example: Why can struct node contain struct node *next but not struct node next?

  1. A member of the same struct type would itself contain another, without end, so its size could not be fixed.
  2. A pointer has a fixed size (8 bytes on 64-bit), whatever it points to.

Answer: A pointer has a fixed size; a nested copy would be infinite

Linked lists

A linked list is a chain of nodes, each holding data and a pointer to the next node; the last points to NULL, and a head pointer records the first. Nodes are created one at a time with malloc, so the list grows and shrinks while the program runs, without a fixed size and without shifting elements.

Traversal follows the pointers: for (p = head; p != NULL; p = p->next) printf("%d ", p->data);. To insert at the beginning, make the new node point to the old head and then set head to it. To insert after a node q, set new->next = q->next and then q->next = new (in that order). To delete the node after q, save it, set q->next = q->next->next, then free the saved node.

Compared with arrays, linked lists allow O(1) insertion and deletion once the position is known, but reaching the k-th element takes O(k) steps and each node uses extra memory for its pointer. Variants include doubly linked lists (pointers both ways) and circular lists.

  • Node = data + next pointer; last next = NULL
  • Traverse: p = p->next until NULL
  • Insert at front: new->next = head; head = new
  • Delete after q: q->next = q->next->next; free the old node
  • Fast insert/delete; slow random access

Example: The list is 20 → 30 → NULL. Show the steps to insert 10 at the front.

  1. new = malloc(sizeof(struct node)); new->data = 10;
  2. new->next = head (the node 20).
  3. head = new.

Answer: 10 → 20 → 30 → NULL

Example: Delete 30 from 10 → 20 → 30 → 40.

  1. Walk until q is the node 20 (q->next->data == 30).
  2. Save t = q->next; set q->next = t->next (node 40); free(t).

Answer: 10 → 20 → 40

Dynamic memory and applications of linked structures

malloc(n) reserves n bytes on the heap and returns their address (or NULL if memory is short); calloc also clears them to zero; realloc resizes a block; and free returns it. Memory obtained this way lasts until it is freed, so it can outlive the function that made it, unlike local variables.

Forgetting free causes a memory leak, which slowly uses up memory in long-running programs. Using memory after freeing it, or freeing it twice, causes hard-to-find bugs. A safe habit is: check malloc’s result for NULL, free each block exactly once, and set the pointer to NULL afterwards.

Linked structures built this way implement stacks (push and pop at the head, last in first out), queues (add at the tail, remove at the head, first in first out), polynomials (one node per term), sparse matrices, and the adjacency lists of graphs used in maps and networks.

  • malloc, calloc, realloc, free (stdlib.h)
  • Check for NULL; free once; set to NULL
  • Leak: memory never freed
  • Stack: LIFO via the head of a list
  • Queue: FIFO; also polynomials, graphs

Example: Allocate an array of n ints at run time and release it.

  1. int *a = malloc(n * sizeof(int)); if (a == NULL) { /* report and stop */ }
  2. Use a[0] … a[n − 1] as usual.
  3. free(a); a = NULL;

Answer: malloc(n * sizeof(int)), check, use, then free

Example: Push 1, 2, 3 onto a linked-list stack, then pop twice. What comes out, and what remains?

  1. Each push adds at the head: the list becomes 3 → 2 → 1.
  2. Pops remove from the head: 3, then 2.

Answer: Pops 3 then 2; 1 remains

A pointer stores the address of a variable: & gives an address and * dereferences it. Pointer arithmetic moves by the size of the pointed type, and an array name acts as a pointer to its first element. A structure groups related data of different types (e.g. a student’s roll, name and marks); an array of structures stores many records. A self-referential structure contains a pointer to its own type, which links nodes into a linked list that can grow and shrink at run time using malloc and free.

  • int x = 5; int *p = &x; *p = 7 changes x.
  • p + 1 points to the next int (address + 4 bytes typically).
  • struct student { int roll; char name[20]; float marks; } s; access s.roll, via pointer p->roll.
  • struct node { int data; struct node *next; };
  • Insertion at the head: new->next = head; head = new;
  • Always check malloc’s result and free memory you no longer need.

Key formulas

  • *(a + i) ≡ a[i]
  • p->x ≡ (*p).x

Practice questions

If int x = 10, *p = &x; then *p is

  1. address of x
  2. 10
  3. garbage
  4. 0
Show the answer

Answer: B. 10 Dereference gives the value.

Structure members are accessed through a pointer with

  1. .
  2. ->
  3. *
  4. &
Show the answer

Answer: B. -> Arrow operator.

A linked-list node contains

  1. data only
  2. data and a pointer to the next node
  3. only pointers
  4. an array
Show the answer

Answer: B. data and a pointer to the next node Self-referential structure.

malloc allocates memory from the

  1. stack
  2. heap
  3. register
  4. disk
Show the answer

Answer: B. heap Dynamic allocation.

Theory questions

What is a pointer? How is it declared? (2 marks)

Show the model answer

A variable holding the memory address of another variable; declared with *, e.g. int *p;

Write a program using an array of structures to store and display details of 5 students. (5 marks)

Show the model answer

struct student { int roll; char name[30]; float marks; } s[5]; loop to scanf each field; loop to printf; optionally find the topper.

Explain self-referential structures and write functions to create, insert at the beginning and display a singly linked list. (10 marks)

Show the model answer

struct node { int data; struct node *next; }; struct node *head = NULL; void insert(int x){ struct node *n = malloc(sizeof *n); n->data = x; n->next = head; head = n; } void display(){ for (struct node *p = head; p; p = p->next) printf("%d -> ", p->data); printf("NULL"); } Advantages over arrays: dynamic size, easy insert/delete; disadvantages: no random access, extra memory for pointers.

Open this subject studio →