Programming for Problem Solving - Complete Notes

Course Overview: Programming for Problem Solving

• Objectives:
  • To relate basics of programming language constructs and problem-solving techniques.
  • To classify and implement control structures and derived data types.
  • To analyze and develop effective modular programming.
  • To construct mathematical problems and real-time applications using C Language.
• Course Outcomes (COs):
  • CO-1: Illustrate the flowchart, algorithm, and pseudo-code for a given problem.
  • CO-2: Execute programs using various data types and operators.
  • CO-3: Implement programs using conditional and iterative statements for a given problem.
  • CO-4: Exercise on programs using arrays, pointers, dynamic memory management, structures, and unions.
  • CO-5: Develop solutions for a given problem using a modular approach and perform file handling.

Unit I: Introduction to Programming and C Language Basics

• Compilers Definition: A compiler is a translator that translates high-level programming language into a machine-understandable format.
• Algorithm: A step-by-step procedure to solve a given problem.
  • Characteristics of an Algorithm:
    1. Finiteness: Terminates after a fixed number of steps.
    2. Definiteness: Each step is precisely defined and unambiguous.
    3. Effectiveness: Operations are basic and can be performed exactly in a fixed duration of time.
    4. Input: Precise inputs or quantities are provided.
    5. Output: One or more results with a specified relation to inputs.
  • Algorithm Exercises:
    1. Swap two numbers without using a temporary variable.
    2. Find roots of a quadratic equation.
    3. Find the largest of three numbers.
    4. Find the sum of the first $N$ numbers.
    5. Find the factorial of a given number.
    6. Generate the first $N$ Fibonacci series values.
• Flowchart: A graphical or pictorial representation of an algorithm showing the sequence in which data are read, computing is performed, decisions are made, and results are obtained.
  • Symbolism:
    • Terminal (Oval): Represents start/end points (BEGIN, START, END, STOP).
    • Input/Output (Parallelogram): Represents making data available for processing or recording processed info.
    • Process (Rectangle): Represents processing operations or assignments; changes or moves data.
    • Flow Direction (Lines/Arrows): Represents the flow of control; normally left to right or top to bottom.
    • Decision Making (Diamond): Represents switching operations determining which alternative path to follow.
    • Connector (Circle): Represents a function in a flow line.
• Pseudocode: An informal way of programming description that represents the implementation of an algorithm without strict syntax or technology considerations.
  • Advantages: Improves readability; acts as a bridge between algorithm and program; explains what each line should do to ease coding.
  • Example Conversion:
    • Source Code: int n = 10; for(i=0; i<n; i++) printf(n);
    • Pseudocode: "The value $10$ is assigned to variable $n$. For value $= 0$ to less than a number, display the numbers."
• History of C:
  1. Structure-oriented language developed at Bell Laboratories in $1972$ by Dennis Ritchie.
  2. Features derived from the "B" language (Basic Combined Programming Language – BCPL).
  3. Invented for implementing the UNIX operating system.
  4. $1978$: Dennis Ritchie and Brian Kernighan published "The C Programming Language" (K&R C).
  5. $1983$: ANSI committee established for a comprehensive definition; "ANSI C" completed late $1988$.
• Characteristics of C:
  • Structured language: divided into multiple blocks/functions.
  • Suitable for both application and system software.
  • Includes derived data types (arrays, structures, pointers, unions) making it simple yet powerful.
  • Highly portable: programs run on different machines without modifications.
  • Rich set of built-in functions.
• Structure of a C Program:
  1. Documentation Section: Set of comment lines (/* ... */) containing details like author and program name. Omitted during compilation.
  2. Link Section: Includes system libraries using #include (e.g., stdio.h, math.h, string.h).
  3. Definition Section: Symbolic constants defined using #define (e.g., #define PI 3.14).
  4. Global Declaration Section: Variables usable in more than one function.
  5. main() function Section: Program entry point. Contains a Declaration part and Executable part within { }. Statements end with a semicolon (;).
  6. Subprogram Section: User-defined functions called from main() or other functions.
• C Character Set:
  • Letters: $a$ to $z$, $A$ to $Z$.
  • Digits: $0$ to $9$.
  • Special Characters: , . ; : ? ' " ! / \ ~ - % & | ^ + _ * < > ( ) [ ] { } # =.
  • White spaces.
• C Tokens: The smallest individual units in a program.
  • Keywords: Fixed-meaning words in lowercase (e.g., auto, break, int, return).
  • Identifiers: User-defined names for variables, arrays, etc.
  • Constants: Fixed values (Integer, Real, Character, String).
    • Decimal Integer: base $10$ ($0-9$).
    • Octal Integer: base $8$ ($0-7$), prefixed by $0$.
    • Hexadecimal: base $16$ ($0-9, A-F$), prefixed by $0X$.
    • Real (Floating Point): numbers with fractional parts; notation: mantissa e exponent (e.g., $3.5E3$).
    • Single Character: enclosed in single quotes (e.g., 'x'). Associated with ASCII (American Standard Code for Information Interchange).
    • String: sequence enclosed in double quotes (e.g., "abcd").
  • Variables: Storage for data values; names consist of letters, digits, and underscores; must begin with letter/underscore; max length $8$ for distinguishability; cannot be a keyword.
• Data Types:
  • Primary/Fundamental:
    • Integer (int): Keyword int. Size: $2$ bytes (standard range $-32768$ to $32767$). Unsigned int size: $2$ bytes ($0$ to $65535$). Long int size: $4$ bytes.
    • Float: Keyword float. Size: $4$ bytes ($6$ digits precision). Range: $3.4e-38$ to $3.4e+38$.
    • Double: Extension of floating point. Size: $8$ bytes ($14$ digits precision). Long double: $10$ bytes.
    • Character: Keyword char. Size: $1$ byte ($8$ bits). Range: $-128$ to $+127$ (signed).
    • Void: No value; used for functions that return nothing.
  • User-defined:
    • typedef: Creates an identifier for an existing data type (e.g., typedef int marks;).
    • enum: Enumerated data type (e.g., enum day {Monday, Tuesday...};).
  • Derived: Arrays, functions, structures, pointers.
• Operators:
  • Arithmetic: +, -, *, /, % (Modulo). Modulo cannot be used with floating point.
  • Relational: <, <=, >, >=, ==, !=. Return $1$ (True) or $0$ (False).
  • Logical: && (AND), || (OR), ! (NOT).
  • Assignment: =, and shorthand forms like +=, -=, *=, /=, %=.
  • Increment/Decrement: ++ and --. Prefix (++m) increments then assigns; Postfix (m++) assigns then increments.
  • Conditional (Ternary): exp1 ? exp2 : exp3. If exp1 is true, execute exp2, else exp3.
  • Bitwise: Operate at bit level (AND, OR, XOR, NOT, Left shift, Right shift). Left shift multiply by $2$; Right shift divide by $2$.
  • Special: Comma (evaluates left-to-right), sizeof() (returns bytes occupied).
• Precedence and Associativity:
  • Highest: () [] -> . ++ -- (Post), then Unary, then Multiplicative, then Additive.
  • Lowest: Comma operator.
• Storage Classes: Define scope (visibility) and lifetime (longevity).
  • Auto: Default; local to block; stored in stack memory; initial value is garbage.
  • Extern (Global): Stored in data segment; active throughout program; default value is $0$.
  • Static: Persists until end of program; initialized once; internal static scope is block; default value is $0$.
  • Register: Stored in machine registers for fast access (usually int or char); initial value is garbage.
• Type Conversion:
  • Implicit: Automatic conversion from lower to higher types.
  • Explicit (Type Casting): Manual conversion using syntax (type) expression (e.g., (int) 7.5).
• Input and Output:
  • Formatted I/O:
    • scanf(): Reads data from standard input (stdin). Syntax: scanf("format-string", Address). Specifiers: %d (int), %f (float), %c (char), %s (string).
    • printf(): Writes data to standard output (stdout). Supports field width (e.g., %10d) and precision (e.g., %.2f).
  • Unformatted I/O:
    • Input: getchar(), getch() (no echo), getche() (echo), gets() (reads string with spaces), getc() (file reading).
    • Output: putchar(), putch(), puts(), putc() (file writing).
• Decision Making and Branching:
  • if statement: Simple if, if...else, nested if...else, and else-if ladder.
  • switch statement: Tests a variable against case labels (integer or character only). Needs break to prevent fall-through.
  • goto statement: Unconditional jump. Forward jump skips code; Backward jump forms a loop.

Unit II: Loops, Arrays, and Strings

• Looping Statements (Iteration):
  • Entry Controlled (Pre-checking): Condition checked before body (while, for).
  • Exit Controlled (Post-checking): Condition checked after body (do-while).
  • For Loop Structure: for(initialization; test; update). Popular because all three components are in one line.
  • While Loop: Evaluation happens first. If false initially, body never runs.
  • Do-While: Body executes at least once before checking the condition.
  • Break vs Continue:
    • break: Terminates loop enclosure entirely.
    • continue: Terminates current iteration and jumps to the next test.
• Arrays: Group of similar data elements stored in contiguous memory locations.
  • Declaration: data_type name[size];. Range is $0$ to $size-1$.
  • Initialization Types:
    • Compile-time: int a[5]={1,2,3,4,5};. Partial: int a[5]={1,2}; (remaining are $0$).
    • Run-time: Using loops and scanf().
  • Two-Dimensional Arrays: Represented as a table with rows and columns. Syntax: data_type name[row_size][col_size];. Stored row by row.
• Strings: Group of characters ending with a null character (\0).
  • Initialization: char s[6] = "Hello"; (size includes the null character).
  • String Functions (string.h):
    • strlen(s): Returns length excluding null character.
    • strcpy(s1, s2): Copies s2 to s1.
    • strcmp(s1, s2): Compares strings; returns $0$ if equal, negative if $s1 < s2$, positive if $s1 > s2$.
    • strcat(s1, s2): Appends s2 to the end of s1.
    • strrev(s): Reverses the string.
  • 2D Strings: Array of strings (e.g., char city[5][10]; for $5$ names of max $10$ chars).

Unit III: Searching, Sorting, and Functions

• Searching Techniques:
  • Linear Search (Sequential): Systematic check from start to end; O(n) average/worst case; works on sorted/unsorted data.
  • Binary Search: Quick divide-and-conquer approach; data must be sorted. Compare key to middle element. Complexity: O(log n).
• Sorting Algorithms (Internal Sorts):
  • Bubble Sort (Exchange Sort): Compares adjacent elements and swaps if out of order. Largest element "bubbles" to the end each iteration.
  • Insertion Sort: Scans elements and inserts each into its proper position in a pre-sorted subarray. Effective for small $N$.
  • Selection Sort: Repeatedly finds the smallest element and interchanges it with the current position ($A[0], A[1]...A[k]$).
• Functions: Block of code performing a specific task; name-based reusability.
  • Advantages: Reduces redundancy; modular debugging/testing; memory efficiency; allows collaborative programming.
  • Elements:
    1. Declaration (Prototype): Informs compiler of the function (e.g., int sum(int, int);).
    2. Call: Executes the function using actual parameters.
    3. Definition: Contains the code (Header + Body). Uses formal parameters.
  • Categories:
    1. No arguments, no return value.
    2. With arguments, no return value.
    3. No arguments, with return value.
    4. With arguments, with return value.
• Parameter Passing Mechanism:
  • Call by Value: Copies value; changes in function do not affect the calling variable.
  • Call by Reference: Passes memory addresses (pointers); changes in function affect actual variables.
• Recursion: A function calling itself. Requires a base case to terminate. Successive calls must work on smaller versions of the problem (e.g., Factorial $N! = N \times (N-1)!$; Fibonacci $F(n) = F(n-1) + F(n-2)$).

Unit IV: Structures, Unions, and Pointers

• Structures (struct): A user-defined collection of logically related data items of different data types under a single name.
  • Members/Elements: Fields within the structure.
  • Accessing: Using the dot operator (s.member) or arrow operator (p->member for pointers).
  • Array of Structures: Example: struct student class[100];.
  • Structure within Structure (Nesting): Members can be structures (e.g., emp.allowance.DA).
• Unions: Similar to structures but all members share the same memory location. Size of union = size of its largest member. Only one member can be used at a time.
• Pointers: A derived data type that stores the address of another variable.
  • Symbolism: & is address-of; * is indirection/dereference.
  • Pointer Arithmetic: Incrementing a pointer (p++) moves it by the size of the data type (i.e., Scale Factor).
    • Scale Factors: char ($1$), int ($2$), float ($4$), double ($8$).
  • Chain of Pointers: A pointer to another pointer (e.g., int **p2;).
  • Array of Pointers: Used for efficiency in ragged arrays (varying length strings).
• Dynamic Memory Allocation (Heap): Allocating memory at runtime.
  • malloc(size): reserves block of bytes; returns void pointer.
  • calloc(n, size): reserves $n$ blocks; initializes all to $0$.
  • realloc(ptr, new_size): modifies size of existing block.
  • free(ptr): releases memory back to the system.
• Self-referential Structure: A structure containing a pointer member pointing to the same structure type (essential for Linked Lists).

Unit V: File Handling and Preprocessor commands

• Files: A location on a disk for group data storage.
  • Text File: Stores alphanumeric data; human-readable; requires binary conversion.
  • Binary File: Stores raw bytes; machine-readable; faster; no conversion needed.
• Opening Modes:
  • r (read): returns NULL if non-existent.
  • w (write): creates new or erases existing contents.
  • a (append): keeps existing content; adds to end.
  • r+, w+, a+: combination modes for both reading and writing.
• File I/O Functions:
  • Character based: getc(), putc().
  • Integer based: getw(), putw().
  • Mixed data: fscanf(), fprintf().
  • Binary block: fread(), fwrite().
• Error Handling: feof() (checks end-of-file), ferror() (detects errors during processing).
• Random Access:
  • ftell(fp): current position index.
  • rewind(fp): resets position to start ($0$).
  • fseek(fp, offset, position): moves pointer. Position values: $0$ (Begin), $1$ (Current), $2$ (End).
• Command Line Arguments: Parameters passed to main() during program invocation (int argc, char *argv[]).
• Preprocessor Directives: Commands beginning with # processed before compilation.
  • File Inclusion: #include <filename> (system) or #include "filename" (user-defined).
  • Macro Substitution: #define identifier string.
    • Simple constants (e.g., #define M 5).
    • Argumented/Macros with parameters (e.g., #define SQUARE(x) (x*x)).
  • Conditional Compilation: #if, #else, #elif, #endif, #ifdef, #ifndef. Enables logic-based inclusion/exclusion of code blocks.
  • Special commands: #line (resets line counter), #error (generates custom compile-error message), #pragma (compiler-specific actions).