SOFTWARE LAB (ME-406) - Unit 1 Short Notes

UNIT 1: FUNDAMENTALS OF PROGRAMMING & BASIC ALGORITHMS

[!TIP] Exam Focus: This unit typically forms the foundation. Expect direct questions on syntax, control flow logic, and time complexity analysis (Big O) of simple algorithms. Past papers often include writing pseudo-code and identifying errors.

1.1 Programming Fundamentals & Syntax (C Language Context)

• Program Structure: Preprocessor directives (#include), main() function, statements, comments (//, /* */).

• Data Types & Variables:

  • Primary: int, char, float, double.

  • Derived: Arrays, pointers (introduction).

  • Key Rule: Variable declaration must precede use. Type determines memory size and operations.

• Operators:

  • Arithmetic: +, -, *, /, % (modulus).

  • Relational: ==, !=, >, <, >=, <=.

  • Logical: && (AND), || (OR), ! (NOT).

  • Assignment: =, +=, -= etc.

  • Increment/Decrement: ++, -- (prefix vs. postfix difference).

Common Pitfall: Confusing = (assignment) with == (equality check). Using = in an if condition is a frequent error.

1.2 Control Structures

A. Decision Making (if, if-else, switch)

• if / if-else: Executes based on a boolean expression (non-zero = true, zero = false).

  
  if (condition) {
  
      // true block
  
  } else {
  
      // false block
  
  }
  
  

• switch: Efficient for multi-way branching on integral constant expressions (int, char). break statement is crucial to prevent "fall-through."

  
  switch (expression) {
  
      case const1: ... break;
  
      case const2: ... break;
  
      default: ...
  
  }
  
  

B. Loops (for, while, do-while)

• for(init; condition; increment): Best when iteration count is known.

• while(condition): Pre-test loop. May execute 0 times.

• do { ... } while(condition);: Post-test loop. Executes at least once.

• Loop Control: break (exit loop immediately), continue (skip to next iteration).

Exam Tip: Be prepared to convert a for loop to while and vice-versa. Trace execution for nested loops.

1.3 Functions & Scope

• Function Definition: return_type function_name(parameter_list) { ... }

• Function Call: function_name(arguments);

• Parameter Passing:

  • Call by Value: Copy of argument is passed. Changes inside function do not affect original variable.

  • Call by Reference (using pointers): Address is passed. Changes do affect original variable.

• Scope Rules:

  • Local: Variables declared inside a function/block { }. Exists only within that block.

  • Global: Variables declared outside all functions. Accessible by all functions.

  • Function Prototype: Declaration before main() to inform compiler about function signature.

1.4 Basic Algorithms & Complexity Analysis

A. Searching Algorithms

1. Linear Search:

   • Idea: Sequentially check each element until target is found or end is reached.

   • Pseudo-code:

     
     LINEAR_SEARCH(arr, n, key):
     
       for i = 0 to n-1:
     
         if arr[i] == key:
     
           return i
     
       return -1
     
     

   • Time Complexity:

     • Best Case: $O(1)$ (key is first element).

     • Worst Case: $O(n)$ (key is last or absent).

     • Average Case: $O(n)$.

     \boxed{\text{Time Complexity: } O(n)}

2. Binary Search (Requires Sorted Array):

   • Idea: Repeatedly divide search interval in half.

   • Pseudo-code:

     
     BINARY_SEARCH(arr, low, high, key):
     
       while low <= high:
     
         mid = (low + high) / 2
     
         if arr[mid] == key: return mid
     
         else if arr[mid] < key: low = mid + 1
     
         else: high = mid - 1
     
       return -1
     
     

   • Time Complexity:

     • Best/Worst/Average: $O(\log n)$.

     • Reason: Search space halves each iteration. $$\displaystyle T(n) = T(n/2) + c $$.

     \boxed{\text{Time Complexity: } O(\log_2 n)}

[!TIP] Binary Search Prerequisite: Array must be sorted. If unsorted, you must sort first ($O(n \log n)$) then search ($O(\log n)$), total $O(n \log n)$, which may be worse than linear search $O(n)$ for small n.

B. Sorting Algorithms

1. Bubble Sort:

   • Idea: Repeatedly swap adjacent elements if they are in wrong order. Largest element "bubbles" to end in each pass.

   • Pseudo-code:

     
     BUBBLE_SORT(arr, n):
     
       for i = 0 to n-2:
     
         for j = 0 to n-i-2:
     
           if arr[j] > arr[j+1]:
     
             swap(arr[j], arr[j+1])
     
     

   • Time Complexity:

     • Worst/Average Case: $$\displaystyle O(n^2) $$ (nested loops).

     • Best Case (Optimized with flag): $O(n)$ (already sorted array, 1 pass).

     \boxed{\text{Time Complexity (Worst): } O(n^2)}

2. Selection Sort:

   • Idea: Find minimum element from unsorted part and put it at the beginning.

   • Pseudo-code:

     
     SELECTION_SORT(arr, n):
     
       for i = 0 to n-2:
     
         min_idx = i
     
         for j = i+1 to n-1:
     
           if arr[j] < arr[min_idx]:
     
             min_idx = j
     
         swap(arr[i], arr[min_idx])
     
     

   • Time Complexity: Always $$\displaystyle O(n^2) $$ (nested loops, no early termination).

Comparison: Both Bubble and Selection Sort are in-place (use $O(1)$ extra space) but inefficient ($$\displaystyle O(n^2) $$) for large n. Stable? Bubble Sort is stable; Selection Sort is not (due to swap).

1.5 Arrays & Strings (Basic Operations)

• Array Declaration: type array_name[size]; (Size must be constant/known at compile time in standard C).

• Indexing: Zero-based (arr[0] is first element). Valid indices: 0 to size-1.

• Common Operations:

  • Traversal: Loop through all elements.

  • Insertion/Deletion: Shifting elements required (costly, $O(n)$).

• Strings: Character arrays terminated by '\0'. Use <string.h> functions (strlen, strcpy, strcmp).

Critical Boundary Check: Array Index Out of Bounds causes undefined behavior (crashes, data corruption). Always ensure index < size.

1.6 Memory Addresses & Pointers (Introductory)

• Pointer Variable: Stores memory address of another variable.

  • Declaration: int *ptr;

  • Address-of operator: &var gives address of var.

  • Dereference operator: *ptr gives value at address stored in ptr.

• Pointer Arithmetic: Adding integer n to pointer p moves it by n * (size of datatype) bytes.

• Pointer & Arrays: Array name arr acts as a constant pointer to arr[0]. arr[i] is equivalent to *(arr + i).

Common Pitfall: Uninitialized pointers (wild pointers) point to random locations. Always initialize: int *ptr = NULL; or ptr = &var;.

QUICK RECAP FOR EXAMS

1. Big O Notation: Describes upper bound of growth rate (worst-case). Ignore constants & lower-order terms.

   • $O(1)$: Constant.

   • $O(\log n)$: Logarithmic.

   • $O(n)$: Linear.

   • $$\displaystyle O(n^2) $$: Quadratic.

2. Loop Conversion: Master converting for ↔ while.

3. Search Choice: Unsorted? → Linear Search ($O(n)$). Sorted? → Binary Search ($O(\log n)$).

4. Sort Choice: For learning/conceptual: Bubble/Selection. For practice: Insertion. For efficiency: Quick/Merge (later units).

5. Function Scope: Global variables are accessible everywhere; local variables only within their block.

6. Pointer Essence: & (address), * (value at address). ptr = &x; then *ptr is x.