CS201 Introduction to Programming Comprehensive Study Guide

Introduction to Programming (CS201): Lectures 1 to 18

Fundamental Programming Definitions and Skills

• Definition of Coding: "A program is a precise sequence of steps to solve a particular problem."
• Steve Summit's Perspective: At its most basic level, programming simply means telling a computer what to do. The mechanisms (artificial languages) are chosen either for programmer convenience or computer interpretability.
• Importance of Programming: It is a creative activity that develops analytical thinking, critical reading, and creative synthesis. It allows for the expression of abstract ideas.
• Essential Programming Skills:
  • Paying Attention to Detail: Precise problem analysis is required. Logic must be sound even if grammar/syntax is correct. Example: The Lewis Carroll poem "Through the Looking Glass" contains grammatically correct but meaningless lines like "'Twas brillig, and the slithy toves / Did gyre and gimble in the wabe."
  • Thinking about Reusability: Write code that can solve related problems. Example: Using a circle area function to calculate the area of a ring by subtracting the inner circle from the outer.
  • User Interface (UI): Do not assume user literacy; provide self-explanatory interfaces.
  • Understanding Computer Limitation: Computers are "stupid" and follow instructions verbatim; they lack human intuition regarding context (e.g., asking "Time?" vs. "What is the time?").
  • Liberal Commenting: Comments are ignored by the compiler and do not affect performance or memory but are vital for human understanding.

The Program Design Recipe

• Analogies: Programming is compared to architecture, composing music, or playing soccer—it requires honing basic drills (ball handling, scales, sketching) to achieve instinctive creativity.
• The Recipe Steps:
  1. Analyze the problem statement (typically word problems).
  2. Express the essence abstractly with named examples.
  3. Formulate statements/comments in precise language.
  4. Evaluate through testing and checks.
  5. Refine and revise iteratively.
• Payroll Example Application: Divide the system into categories (Permanent, Contractual, Hourly, Per Unit). Use pseudo-code or flowcharts before coding.

Software Categories and History of C

• Software Classification:

  • System Software: Controls hardware (OS, Device Drivers, Utilities).
    • OS: Foundations for applications; manages resources ($CPU$, memory, disk).
    • Drivers: Communication bridges (e.g., TWAIN for scanners).
    • Utilities: Specific tasks like Disk Compression or Defragmentation.
  1. Application Software: End-user programs (Accounting, Payroll, GPS).

• Evolution of C Language:

  • $1967$: Martin Richards developed BCPL for writing OS and compilers.
  • $1970$: Ken Thompson developed B (typeless language).
  • Early $70s$: Dennis Ritchie at Bell Labs created C by adding data typing to B and BCPL.
  • $1989$: ANSI/ISO standardization to create a machine-independent definition.

• Development Tools:

  • Editor: Simple text editor (vs. Word Processor which adds hidden formatting).
  • Compiler vs. Interpreter: Compilers translate the whole program to machine language and require zero syntax errors to generate an executable. Interpreters translate line-by-line (easier for debugging but slower).
  • Debugger: Traces logical errors by stopping execution to check variable values.
  • Linker: Combines relevant routines/libraries into a standalone executable.
  • Loader: Loads the program from disk into primary memory for $CPU$ execution.

Basic C Syntax and Data Types

• Structure of a C Program:

  • #include : Pre-processor directive to include I/O library.
  • $main()$: The starting point of execution.
  • $\{ \}$: Braces defining a block of code.
  • $cout$: Output stream; $<<$ indicates data direction.
  • $cin$: Input stream; $>>$ indicates data direction.

• Variables: Labeled memory locations. Properties include Name, Type, Size, and Value.

• Integer Types:

  • $int$: Typically $4$ bytes ($32$ bits).
  • $short$: Typically $2$ bytes (range $-32768$ to $32767$).
  • $long$: For very large whole numbers.

• Real Number (Floating Point) Types:

  • $float$: $4$ bytes for decimal values.
  • $double$: Usually $8$ bytes for larger/more precise decimals.

• Character Type:

  • $char$: For single characters (e.g., $'a'$). Enclosed in single quotes.

• Arithmetic Operators:

  • Addition ($+$), Subtraction ($-$), Multiplication ($*$), Division ($/$), Modulus ($$ - returns remainder).
  • Integer Division: Truncates the fractional part (e.g., $5 / 2 = 2$).

• Precedence Table:

  1. $( )$ Parentheses (Highest).
  2. `$*$, $/$, $$ Multiplication, Division, Modulus.
  3. `$+$, $-$ Addition, Subtraction (Lowest).

Control Structures: Decisions and Loops

• Relational Operators: $==$ (equal to), $!=$ (not equal), $>$, $<$, $>=$, $<=$.

• Logical Operators:

  • && (AND): Both must be true.
  • $||$ (OR): At least one must be true.
  • $!$ (NOT): Reverses the truth value.

• If/Else Structure: Allows branching execution based on a condition.

• Switch Statement: Multi-way decision for discrete integer/character values. Uses $case$, $break$, and $default$. Missing a break causes "fall through."

• While Loop: Executes zero or more times based on a condition.

• Do-While Loop: Executes at least once (condition check is at the end).

• For Loop: Combines (Initialization; Condition; Increment) in one statement.

• Increment/Decrement: $x++$ (post-increment), $++x$ (pre-increment), $x--$,$--x$. Compound assignments like $x += 5$ ($x = x + 5$).

Functions and Scope

• Top-Down Design: Breaking complex tasks into smaller, manageable sub-tasks.
• Structure: $return \_ type \text{ } function \_ name ( \text{argument list} ) \text{ } \{ \text{body} \}$.
• Prototype (Declaration): Notifies the compiler of the function signature (return type, name, and parameters) before its call.
• Call by Value: Passes a copy of the variable; original remains unchanged.
• Call by Reference: Uses pointers; allows the function to modify the original variable.
• Scope:
  1. Block Scope: Variables local to braces $\{ \}$.
  2. Function Scope: Variables local to the function.
  3. File/Global Scope: Variables declared outside all functions, accessible everywhere.
• Recursion: A function calling itself. Examples: Factorial ($n! = n \times (n-1)!$) or Power functions ($x^n = x \times x^{n-1}$). Requires a base case to terminate.

Arrays and Matrices

• Definition: A collection of identical data types in contiguous memory locations.
• Indexing: Starts at $0$. An array of size $n$ has indices $0$ to $n - 1$.
• Character Arrays (Strings): Terminated by a null character '\0'. $char \text{ name } [10] = \text{ "Amir" }$ automatically adds '\0'.
• Two-Dimensional Arrays: Represented as $type \text{ name } [rows][cols]$. Access as $matrix[i][j]$. Stored in row-major order.
• Passing Arrays to Functions: Default is Call by Reference (passing the starting address).
• Algorithms:
  1. Linear Search: Checks every element sequentially.
  2. Binary Search: Divides a sorted array in half repeatedly. Max comparisons for $2^n$ elements is $n$.
  3. Bubble Sort: Repeatedly swaps adjacent elements to move the largest to the end.
  4. Transpose: Interchanging rows and columns ($A(i,j) \rightarrow A(j,i)$).

Pointers and Memory Management

• Pointer: A variable storing a memory address.
• Operators:
  • & (Address operator): Returns the memory address of a variable.
  • $*$ (Dereferencing operator): Accesses the value stored at the address pointed to.
• Pointer Arithmetic: Adding $1$ to a pointer jumps memory by the size of the data type (e.g., incrementing an $int$ pointer jumps $4$ bytes).
• Pointer to Pointer: Declared as $type **ptr$. Used in command-line arguments ($char **argv$).
• Constant Pointers:
  • $int *const \text{ ptr}$: Value of the pointer is constant (cannot point elsewhere).
  • $const int * \text{ ptr}$: Value at the address is constant (cannot change the integer).

File Handling and String Libraries

• Header Files:

  • $<ctype.h>$: Character tests ($isdigit$, $isalpha$, $tolower$).
  • $<string.h>$: String manipulation ($strlen$, $strcpy$, $strcat$, $strcmp$, $strtok$).
  • $<stdlib.h>$: Conversion functions ($atoi$, $atof$) and $rand()$.
  • $<fstream.h>$: File handling.

• File Stream Classes:

  • $ifstream$: Input file stream.
  • $ofstream$: Output file stream.

• Opening Modes:

  • $ios::in$: Open for reading.
  • $ios::out$: Open for writing (truncates existing).
  • $ios::app$: Append to the end.

• I/O Methods:

  • $get()$ / $put()$: Single character processing.
  • $getline(char \text{ array}, \text{ size})$: Efficiency-focused line processing; reads up to new line character.
  • $eof()$: Returns true when the end of the file is reached.