Programming in C

Arrays

• Array — collection of elements of the same type in contiguous memory.
• One-dimensional: declaration int a[10];, indices 0..9.
• Two-dimensional: matrix declaration int m[3][4];. C uses row-major order.
• Multidimensional: extend the same idea, e.g. int t[2][3][4];.
• Static init: int a[3] = {1,2,3};
• Dynamic allocation: use malloc and free for runtime sizes.

// static
int a[5] = {0};

// dynamic
int *b = malloc(n * sizeof(int));
if (b == NULL) { /* handle error */ }
free(b);

Character Arrays and Strings

• Character array: char s[6] = {'H','i','\0'};
• String literal: char s[] = "Hello"; (null-terminated).
• Common functions: strlen, strcpy, strcmp, strcat.
• Comparison: use strcmp(a,b), not the == operator.
• Safety: always ensure space for the terminating '\0' and prefer bounded input.

char s[6] = "Hello";
printf("%s
", s);
if (strcmp(s, "Hello") == 0) { /* equal */ }

Functions (User-defined)

• Prototype / declaration: e.g. int add(int, int);
• Definition: code body, e.g. int add(int a, int b) { return a + b; }
• Call: sum = add(x, y);
• Parameter passing: C passes by value. To modify caller data, pass a pointer (pass-by-reference style), e.g. void inc(int *p).
• Passing arrays/strings: arrays decay to pointers; use signatures like void f(int a[], int n) or void f(char s[]).
• Scope: local variables have block scope; globals have file or external linkage; static affects lifetime/linkage.

void inc_val(int x) { x = x + 1; }     // caller not changed
void inc_ref(int *p) { *p = *p + 1; }  // caller changed

int a = 5;
inc_val(a);    // a still 5
inc_ref(&a);   // a becomes 6

Recursion

• Recursive function: a function that calls itself.
• Base case: required for termination; always identify it.
• Tail recursion: recursive call is the last action; can be optimized in some compilers.
• Analysis: formulate recurrence (e.g., T(n)=T(n-1)+O(1)) and solve for complexity.
• Recursion tree: visualize calls and costs per level for complexity analysis.

// recursive
int fact(int n) {
  if (n <= 1) return 1;
  return n * fact(n-1);
}

// iterative
int fact_iter(int n) {
  int r = 1;
  for (int i = 2; i <= n; i++) r *= i;
  return r;
}

Searching and Sorting — Basics

• Linear search: scan sequentially; O(n) worst-case.
• Binary search: requires sorted array; O(log n).
• Sorting (intro): be familiar with bubble, insertion, selection; know their basic complexities.

int linear_search(int a[], int n, int key) {
  for (int i = 0; i < n; i++)
    if (a[i] == key) return i;
  return -1;
}

Debugging Exercise

#include <stdio.h>

int sum_rows(int m[][3], int r) {
  int s = 0;
  for (int i = 0; i <= r; i++) {   // error: loop bounds (<=) incorrect
    for (int j = 0; j < 3; j++)
      s += m[i][j];
  }
  return s;
}

Programming Exercise

• Write a function to search for a string in an array of strings and return index or -1.
• Implement insertion sort on an integer array and state its time complexity.