Unit 1: Foundational Concepts

I. Orientation — Programming, Abstraction, and Efficiency

Computing systems solve problems by representing data, applying precisely defined operations, and managing computational resources. C (1972) emphasizes procedural programming and direct memory control, while C++ (first released in 1985) extends these foundations with object-oriented and generic programming.

• Core model: Input is transformed by an algorithm to produce output.
• Program construction: Data types, variables, control structures, and functions express algorithms in executable form.
• Abstraction: Structures, classes, and data structures organize complex data while hiding unnecessary implementation details.
• Correctness: Syntax must follow language rules, while logic must produce the intended result.
• Efficiency: Time and space complexity describe how resource usage grows with input size.

II. C/C++ Programming Foundations — Language, Data, and Input/Output

A. Introduction to C/C++

C and C++ are compiled, statically typed languages used for systems, application, and performance-sensitive programming.

• C characteristics: C is procedural, supports pointers and manual memory management, and commonly uses source files ending in .c.
• C++ characteristics: C++ supports procedural, object-oriented, and generic programming, usually in .cpp files.
• Compilation process: Source code passes through preprocessing, compilation, assembly, and linking to create an executable.
• Basic program:

#include <iostream>
int main() {
    std::cout << "Hello";
    return 0;
}

• Entry point: Execution begins at main; returning 0 conventionally indicates successful termination.

B. Data types

A data type determines the kind of value stored, valid operations, and approximate memory requirements.

• Integral types: char, short, int, long, and long long store whole numbers; signedness affects their range.
• Floating-point types: float, double, and long double represent real numbers with finite precision.
• Boolean type: C++ bool stores true or false; C commonly uses _Bool or <stdbool.h>.
• Void type: void represents no value, as in a function that returns nothing.
• Modifiers: signed, unsigned, short, and long alter numeric ranges or representation.
• Size check: sizeof(int) returns the implementation-defined storage size in bytes.

C. Variables

A variable is a named memory location whose value can change during program execution.

• Declaration: int count; associates the identifier count with type int.
• Initialization: int count = 5; gives the variable an initial value before use.
• Assignment: count = 8; replaces its current value.
• Scope: A local variable belongs to its enclosing block, while a global variable is declared outside all functions.
• Lifetime: Automatic local variables normally exist until their block finishes; static variables persist for the program’s duration.

D. Constants

A constant is a value that cannot be modified through its declared name.

• Literal constants: Examples include 25, 3.14, 'A', and "C++".
• C++ constant: const double PI = 3.14159; prevents assignment to PI.
• Compile-time constant: constexpr int SIZE = 100; requires a value evaluable at compile time.
• Macro constant: C supports #define SIZE 100, but typed constants are generally safer because they obey scope and type rules.

E. Reading and writing data using scanf, printf, cin and cout

C uses formatted library functions, whereas C++ commonly uses type-aware stream operators.

• C input/output: scanf reads according to format specifiers; printf formats output.
• C example:

int age;
scanf("%d", &age);
printf("Age: %d\n", age);

• Address requirement: &age supplies the address where scanf stores the integer; incorrect specifiers can cause undefined behavior.
• C++ input/output: cin >> age extracts a typed value, while cout << age inserts it into an output stream.
• C++ example:

int age;
std::cin >> age;
std::cout << "Age: " << age << '\n';

• Common specifiers: %d represents int, %f reads float, %lf reads double, and %s handles a C-style string.

III. Program Flow and Functions — Decisions, Repetition, and Reuse

A. Control structures: if-else and loops

Control structures determine which statements execute and how often they execute.

• Selection: if executes a block when its condition is true; else supplies an alternative.
• Conditional chain: else if distinguishes several mutually exclusive cases.
• for loop: Best suited to count-controlled repetition, as in for (int i = 0; i < 5; ++i).
• while loop: Tests its condition before each iteration and may execute zero times.
• do-while loop: Tests after the body, guaranteeing at least one execution.
• Loop control: break exits the nearest loop; continue skips to its next iteration.

if (score >= 50) std::cout << "Pass";
else std::cout << "Fail";

B. Functions: declaration and definition

A function packages a named operation so it can be reused, tested, and understood independently.

• Declaration: A prototype states the interface before use: int add(int, int);.
• Definition: The definition supplies the body: int add(int a, int b) { return a + b; }.
• Parameters and arguments: Parameters are local names in the function; arguments are values supplied by the caller.
• Return type: int promises an integer result, while void specifies no returned value.
• Signature: In C++, the function name and parameter types support function overloading.

C. Call by value and call by reference

Parameter-passing determines whether a function operates on a copy or on the caller’s original object.

1. Call by value: void f(int x) copies the argument into x; changing x does not change the caller’s variable.
2. Call by reference: C++ void f(int& x) makes x an alias, so assignments modify the original variable.
   • C pointer equivalent: C passes an address by value, as in void f(int *x) { *x = 10; }, called with f(&n).
   • Trade-off: Value passing provides isolation; references efficiently modify or avoid copying large objects.

D. Recursion

Recursion occurs when a function solves a problem by calling itself on a smaller instance.

• Base case: A terminating condition prevents unlimited calls.
• Recursive case: Each call must progress toward the base case.
• Example:

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

• Evaluation: factorial(4) computes (4 \times 3 \times 2 \times 1 = 24).
• Cost: Each unfinished call occupies stack space; excessive depth may cause stack overflow.

IV. Object-Oriented Foundations — Types, Objects, and Lifetimes

A. Introduction to object-oriented programming

Object-oriented programming models software as interacting objects that combine state with behavior.

• Encapsulation: Data and related functions are bundled inside a class.
• Abstraction: A public interface exposes essential operations while hiding implementation details.
• Inheritance: A derived class can reuse and specialize a base class.
• Polymorphism: One interface can invoke different implementations, such as overridden virtual functions.
• Purpose: These principles support modularity, reuse, and controlled change in large systems.

B. User-defined data types: struct and class

Structures and classes let programmers create types containing related members.

1. struct: Members are public by default in C++; C structures contain data but not C++-style member functions.
2. class: Members are private by default and commonly enforce encapsulation.
   • Concrete definition:

struct Point {
    int x;
    int y;
};

• Use: Point p{2, 3}; creates a value whose members are accessed as p.x and p.y.
• C++ equivalence: Apart from default access and inheritance access, struct and class have the same language capabilities.

C. Classes and objects

A class is a blueprint defining members, while an object is a concrete instance of that class.

• State: Data members store each object’s values.
• Behavior: Member functions operate on the object’s state.
• Access control: private, protected, and public regulate member visibility.
• Instance creation: Counter c; allocates an object named c.
• Member access: c.increment() uses the dot operator; a pointer uses ptr->increment().
• Identity: Separate objects have independent state even when created from the same class.

D. Manager functions: constructors and destructors

Constructors initialize objects, while destructors release resources when objects cease to exist.

1. Constructor: Has the class name and no return type; it runs automatically at object creation.
2. Destructor: Uses ~ClassName() and runs automatically at object destruction.
   • Example:

class Box {
    int width;
public:
    Box(int w) : width(w) {}
    ~Box() {}
};

• Initialization list: width(w) initializes the member directly.
• Resource management: Destructors may release dynamic memory, files, or locks; automatic cleanup underlies the RAII technique.

V. Data Structures — Organizing Information

A. Introduction to data structures

A data structure is a systematic representation of data designed to support particular operations efficiently.

• Core operations: Common operations include insertion, deletion, traversal, searching, sorting, and updating.
• Choice criterion: The best structure depends on required operations; an array offers direct indexed access, while a linked list supports flexible node insertion.
• Abstract data type: An ADT specifies behavior independently of implementation; a stack, for example, requires last-in, first-out operations.
• Implementation: Data structures use primitive values, pointers, structures, classes, and memory-management mechanisms.

B. Types of data structures

Data structures can be classified by organization, size behavior, and element relationships.

• Primitive structures: Built-in forms such as integers, characters, floating-point values, and pointers.
• Linear structures: Arrays, linked lists, stacks, and queues arrange elements sequentially.
• Non-linear structures: Trees model hierarchies, while graphs represent general networks of vertices and edges.
• Static structures: Fixed-size arrays normally reserve capacity before execution or allocation.
• Dynamic structures: Linked structures can grow or shrink through runtime allocation.
• Homogeneous versus heterogeneous: Arrays hold one element type; structures and classes can combine different member types.

VI. Algorithmic Efficiency — Growth and Resource Bounds

A. Time and space complexity analysis

Complexity analysis measures how an algorithm’s resource requirements grow with input size (n).

• Time complexity: Counts dominant elementary operations rather than clock seconds.
• Space complexity: Includes auxiliary memory such as temporary arrays and recursion stacks.
• Input size: (n) may denote the number of array elements, nodes, or input symbols.
• Dominant growth: For (T(n)=3n^2+2n+5), the quadratic term dominates as (n) increases.
• Cases: Best, average, and worst cases describe different inputs of the same size.

B. Time-space trade-off

A time-space trade-off improves execution speed by using additional memory, or saves memory by performing more computation.

1. More space, less time: A lookup table stores precomputed results so repeated retrieval can approach constant time.
2. Less space, more time: Recomputing values avoids storing them but repeats operations.
   • Memoization: Caching recursive Fibonacci results changes repeated subproblem evaluation from exponential growth to linear time while requiring (O(n)) storage.
   • Decision factors: Available memory, input scale, latency requirements, and frequency of repeated operations determine the suitable balance.

C. Big-O notation

Big-O gives an asymptotic upper bound on a function’s growth.

• Formal condition: (f(n)=O(g(n))) if constants (c>0) and (n_0) exist such that (0\le f(n)\le c\,g(n)) for every (n\ge n_0).
• Symbols: (f(n)) is the measured cost, (g(n)) is the comparison function, (c) is a constant multiplier, and (n_0) is the threshold.
• Example: (3n+2=O(n)), because for (n\ge1), (3n+2\le5n).
• Use: Big-O often expresses worst-case growth, but mathematically it is any valid upper bound.

D. Big-Omega notation

Big-Omega gives an asymptotic lower bound on growth.

• Formal condition: (f(n)=\Omega(g(n))) if constants (c>0) and (n_0) exist such that (0\le c\,g(n)\le f(n)) whenever (n\ge n_0).
• Interpretation: Beyond the threshold, (f) grows at least as quickly as a constant multiple of (g).
• Example: (3n+2=\Omega(n)), since (3n+2\ge3n) for (n\ge1).
• Distinction: Omega is a growth lower bound, not automatically an algorithm’s best-case running time.

E. Big-Theta notation

Big-Theta provides a tight asymptotic bound by combining upper and lower bounds.

• Formal condition: (f(n)=\Theta(g(n))) if positive constants (c_1), (c_2), and (n_0) satisfy
  (0\le c_1g(n)\le f(n)\le c_2g(n)) for all (n\ge n_0).
• Meaning: (f) and (g) have the same asymptotic order of growth.
• Example: (3n^2+2n+5=\Theta(n^2)); constants and lower-order terms do not alter the growth class.
• Common classes: (\Theta(1)), (\Theta(\log n)), (\Theta(n)), (\Theta(n\log n)), (\Theta(n^2)), and (\Theta(2^n)) represent increasingly rapid growth.