Unit 1: Foundational Concepts - Subjective Questions

C is a general-purpose, procedural programming language developed by Dennis Ritchie. It is widely used for operating systems, embedded systems, compilers, and other performance-critical software.

C++ was developed by Bjarne Stroustrup as an extension of C. It supports procedural programming as well as object-oriented and generic programming.

Major differences:

• Programming paradigm: C is primarily procedural, whereas C++ is multi-paradigm.
• Data abstraction: C uses structures and functions; C++ provides classes and objects.
• Encapsulation: C does not provide access specifiers, while C++ supports private, protected, and public members.
• Inheritance and polymorphism: These are directly supported in C++ but not in C.
• Input/output: C commonly uses scanf and printf; C++ commonly uses cin and cout.
• Memory management: C uses functions such as malloc and free; C++ additionally provides new and delete.
• Compatibility: Much C code can be compiled as C++, although the languages are not completely identical.

Both languages provide efficient execution, low-level memory access, functions, control structures, and a rich set of operators.

A data type specifies the kind of value a variable can store, the operations permitted on it, and typically the amount of memory allocated to it.

1. Fundamental data types:

• char: stores a character or small integer.
• int: stores an integer.
• float: stores a single-precision real number.
• double: stores a double-precision real number.
• bool: stores true or false in C++.
• void: represents the absence of a value.

Type modifiers such as short, long, signed, and unsigned modify certain fundamental types.

2. Derived data types:

• Array: collection of elements of the same type, such as int marks[5];.
• Pointer: stores an address, such as int *ptr;.
• Reference: provides an alias in C++, such as int &ref = value;.
• Function type: describes a function's return and parameter types.

3. User-defined data types:

• struct: groups related members.
• class: combines data and operations with access control.
• enum: defines named integral constants.
• union: allows multiple members to share storage.
• Type aliases can be created with typedef or using.

The exact size of many data types is implementation-dependent and can be checked with sizeof.

• A variable is a named memory location whose value can change during execution. Example: int count = 1;.
• A constant object is a named value that cannot be modified after initialization. Example: const double rate = 0.05;.
• A literal is a fixed value written directly in source code, such as 25, 3.14, 'A', or true.
• A symbolic constant gives a meaningful name to a fixed value. It may be created with const, constexpr, an enumeration, or a C preprocessor macro such as #define MAX_SIZE 100.

Declaration and initialization:

A declaration introduces a name and its type. Initialization supplies its initial value. For example, in int total = 0;, total is declared and initialized.

Scope:

• Block or local scope: A name declared inside a block is accessible from its declaration to the end of that block.
• Function parameter scope: A parameter is available within its function.
• Global or namespace scope: A name declared outside functions can be used by functions subject to visibility and linkage rules.
• Class scope: A class member is associated with its class.

constexpr is preferable when a C++ value must be evaluable at compile time. Typed constants are generally safer than preprocessor macros because they follow language scope and type-checking rules.

scanf reads formatted input, while printf produces formatted output. Both are declared in <stdio.h>.

Example:

int age;
double salary;
scanf("%d %lf", &age, &salary);
printf("Age: %d, Salary: %.2f\n", age, salary);

Common format specifiers:

• %d: int
• %u: unsigned int
• %f: floating-point output in printf; float * input in scanf
• %lf: double * input in scanf
• %c: character
• %s: character string
• %p: pointer value

In scanf, the address operator & is normally placed before scalar variables so that the function can store the input. An array name used with %s already represents an address, so & is normally unnecessary.

Safety considerations:

• The format specifier must match the argument type; a mismatch can cause undefined behavior.
• Check the return value of scanf, which reports how many items were successfully assigned.
• Limit string input width, for example scanf("%19s", name); for a 20-character array.
• %s stops at whitespace and therefore does not read a full line.
• Use suitable line-input functions when spaces or stronger validation are required.

Formatting controls such as %.2f specify precision, while %8d specifies a minimum field width.

C++ provides stream-based input and output through <iostream>.

#include <iostream>
#include <string>
using namespace std;

int main() {
    int age;
    string name;
    getline(cin, name);
    cin >> age;
    cout << "Name: " << name << ", Age: " << age << '\n';
}

• cin is the standard input stream and commonly uses the extraction operator >>.
• cout is the standard output stream and commonly uses the insertion operator <<.
• getline(cin, text) reads an entire line, including spaces.
• Stream state can be tested with expressions such as if (cin) or if (cin.fail()).

Comparison:

• cin and cout are type-aware, whereas scanf and printf rely on format strings.
• C++ streams support operator overloading, so user-defined types can provide natural input/output behavior.
• C formatted I/O is often concise for strict formatting, but an incorrect format specifier can cause undefined behavior.
• C++ output formatting can be controlled with manipulators from <iomanip>, such as fixed, setprecision, and setw.

When operator>> is followed by getline, the remaining newline may need to be consumed, for example with cin.ignore().

Conditional statements select a block of code according to whether a condition is true or false.

• Simple if: Executes a block only when its condition is true.
• if-else: Selects one of two alternative blocks.
• Nested if: Places one conditional statement inside another.
• else-if ladder: Checks several conditions in order; the first true branch is executed.

if (marks >= 90) {
    cout << "Grade A";
} else if (marks >= 75) {
    cout << "Grade B";
} else if (marks >= 50) {
    cout << "Grade C";
} else {
    cout << "Fail";
}

Logical operators:

• && means logical AND; both conditions must be true.
• || means logical OR; at least one condition must be true.
• ! negates a condition.

For example, age >= 18 && citizen checks two requirements. The && and || operators use short-circuit evaluation, so the second operand is evaluated only when necessary.

Braces should be used consistently to avoid ambiguity. In a nested conditional without braces, an else is associated with the nearest unmatched if.

for loop: Best suited when initialization, condition, and update can be expressed together, often when the number of iterations is known.

for (int i = 0; i < 5; ++i) {
    cout << i << ' ';
}

while loop: Checks its condition before every iteration. It may execute zero times and is useful when repetition depends on an event or input.

while (value > 0) {
    value /= 10;
}

do-while loop: Checks its condition after the body, so its body executes at least once.

do {
    cin >> choice;
} while (choice < 1 || choice > 3);

Loop control statements:

• break immediately terminates the nearest loop.
• continue skips the remainder of the current iteration.
• return exits the entire function and therefore any loop inside it.

An infinite loop occurs when the termination condition never becomes false, often because an update is omitted, the wrong comparison is used, or a floating-point value never reaches an exact target. Proper initialization, progress toward termination, and boundary testing help prevent such errors.

A function is a named, reusable block of code that performs a specific task. Functions improve modularity, readability, reuse, testing, and maintenance.

int add(int, int);              // Declaration

int add(int a, int b) {         // Definition
    return a + b;
}

int result = add(4, 6);         // Call

• A declaration or prototype tells the compiler the function's name, return type, and parameter types before it is used.
• A definition supplies the function body and implements its behavior.
• A call transfers control to the function and supplies arguments.
• Formal parameters are names in the declaration or definition, such as a and b.
• Actual arguments are expressions supplied by the caller, such as 4 and 6.
• The return type specifies the type of result. A void function returns no value.

The declaration and definition must have compatible signatures. In C++, functions may be overloaded when they have different parameter lists, but functions cannot be overloaded solely by changing the return type.

In call by value, each parameter receives a copy of an argument. Changes affect only the local copies. In call by reference, reference parameters become aliases for the caller's variables, so changes affect the original values.

void swapByValue(int a, int b) {
    int temp = a;
    a = b;
    b = temp;
}

void swapByReference(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

If x = 10 and y = 20, calling swapByValue(x, y) leaves them unchanged because only copies are exchanged. Calling swapByReference(x, y) changes x to 20 and y to 10.

Comparison:

• Call by value protects the original object from direct modification.
• Copying a large object may consume additional time and memory.
• A non-constant reference permits the function to modify the caller's object.
• A const reference, such as const Record &r, avoids a potentially expensive copy while preventing modification through that reference.
• C uses pass-by-value only, but pointer parameters can be used to modify caller-owned data, for example void swap(int *a, int *b).

The parameter style should communicate intent: value for an independent copy, const reference for read-only access to a potentially large object, and non-constant reference when mutation is intended.

Recursion is a technique in which a function solves a problem by calling itself on a smaller instance of that problem. Every correct recursive solution requires progress toward at least one terminating base case.

For a non-negative integer , factorial is defined as:

long long factorial(unsigned int n) {
    if (n == 0) {
        return 1;                 // Base case
    }
    return n * factorial(n - 1); // Recursive case
}

• The base case n == 0 returns directly and stops recursion.
• The recursive case reduces the problem from n to n - 1.
• Each call waits for the next call's result, so activation records accumulate on the call stack.

The recurrence is , which gives . The recursion depth is , so the auxiliary stack space is .

A missing or unreachable base case can cause unbounded recursion and stack overflow. Factorial values also grow quickly and can overflow fixed-width integer types.

Object-oriented programming (OOP) organizes software around objects that combine state and behavior.

• Encapsulation: Bundles data and methods within a class and controls access to implementation details. For example, a BankAccount can keep balance private and modify it only through validated methods.
• Abstraction: Presents essential operations while hiding unnecessary implementation details. A user may call withdraw() without knowing how transactions are recorded internally.
• Inheritance: Creates a new class from an existing class. For example, SavingsAccount may inherit common account operations from BankAccount and add interest-related behavior.
• Polymorphism: Allows one interface to represent multiple implementations. A virtual draw() function can behave differently for Circle and Rectangle objects.

Benefits:

• Better modularity and separation of responsibilities
• Reuse of well-designed behavior
• Easier maintenance and extension
• Protection of class invariants
• Flexible substitution through polymorphic interfaces

OOP should not be treated merely as placing functions inside classes. Effective OOP assigns each class a clear responsibility and exposes a small, meaningful public interface while protecting its internal state.

In C++, both struct and class can contain data members, member functions, constructors, destructors, static members, access specifiers, and inheritance.

C++ differences:

• Members of a struct are public by default.
• Members of a class are private by default.
• Base-class inheritance is public by default for a struct and private by default for a class.

struct Point {
    int x;
    int y;
    void move(int dx, int dy) {
        x += dx;
        y += dy;
    }
};

class Counter {
    int value;
public:
    void increment() { ++value; }
};

By convention, a C++ struct is often used for simple records with public data, while a class is used when invariants and implementation details must be encapsulated. This is a convention rather than a major language restriction.

A C structure groups data members but cannot directly contain C++-style member functions, constructors, destructors, access specifiers, or inheritance. Operations on a C structure are normally implemented as separate functions that receive a pointer to the structure.

A class is a user-defined type that specifies data and operations. An object is an instance of that class with its own state.

class Rectangle {
private:
    double width;
    double height;

public:
    Rectangle(double w, double h) : width(w), height(h) {}

    double area() const {
        return width * height;
    }

    bool setWidth(double w) {
        if (w <= 0) return false;
        width = w;
        return true;
    }
};

Objects can be created and used as follows:

Rectangle first(4.0, 3.0);
Rectangle second(10.0, 2.0);

double a1 = first.area();
double a2 = second.area();
first.setWidth(5.0);

Explanation:

• width and height are private and cannot be accessed directly by ordinary external code.
• The constructor initializes each object's state.
• area() is a const member function because it does not modify the object.
• setWidth() validates a proposed value before changing the state.
• first and second have the same behavior but store independent values.

Data hiding prevents arbitrary changes and allows the class to preserve rules such as requiring positive dimensions.

Constructors and destructors are special manager functions that control an object's initialization and cleanup.

• A constructor has the same name as its class and no return type. It runs when an object is created.
• A default constructor can be called without arguments.
• A parameterized constructor accepts values used for initialization.
• A copy constructor creates an object from another object of the same class and commonly has the form Type(const Type &other).
• A destructor has the form ~Type() and runs when an object's lifetime ends.

class Buffer {
    int size;
public:
    Buffer() : size(0) {}
    explicit Buffer(int s) : size(s) {}
    Buffer(const Buffer &other) : size(other.size) {}
    ~Buffer() {
        // Release owned resources if necessary.
    }
};

An initializer list initializes members directly before the constructor body runs. It is required for reference members, const members, and base classes, and is usually more efficient than assignment in the body.

Members are initialized in the order in which they are declared in the class, not the textual order of the initializer list. During destruction, the destructor body runs and then members and base classes are destroyed in the reverse of their construction order.

Constructors can establish class invariants, while destructors support RAII, where resources are tied to object lifetime. A class that manually owns a resource may need carefully defined copy, move, and destruction behavior.

A data structure is a method of organizing and storing data so that operations such as access, insertion, deletion, searching, and traversal can be performed effectively.

Primitive and non-primitive:

• Primitive types are basic language-provided types such as int, char, and double.
• Non-primitive structures combine or organize values, such as arrays, linked lists, stacks, queues, trees, graphs, structures, and classes.

Static and dynamic:

• A static data structure has a size that is normally fixed before or at creation. A fixed-size array is a common example.
• A dynamic data structure can grow or shrink during execution. Linked lists and dynamically resized containers are examples.

Homogeneous and non-homogeneous:

• A homogeneous structure stores elements of the same type, such as an array of integers.
• A non-homogeneous structure stores logically related values of different types, such as a Student structure containing an integer ID, a string name, and a floating-point grade.

The best structure depends on the required operations, memory constraints, ordering requirements, and expected amount of data.

In a linear data structure, elements are arranged in a sequence. In a non-linear data structure, an element may be related to several other elements, creating hierarchical or network relationships.

Linear structures:

• Array: Stores same-type elements in contiguous memory. It supports fast indexed access and is used for tables, matrices, and fixed collections.
• Linked list: Stores nodes connected through links. It supports flexible growth and efficient insertion or deletion when the relevant node position is already known.
• Stack: Follows last-in, first-out order. Principal operations are push, pop, and top. Applications include function calls, expression evaluation, and undo systems.
• Queue: Follows first-in, first-out order. Principal operations are enqueue, dequeue, and front access. Applications include scheduling, buffering, and breadth-first search.

Non-linear structures:

• Tree: Represents hierarchical relationships using parent-child connections. Operations include insertion, deletion, searching, and traversal. Applications include file systems, syntax trees, and search indexes.
• Graph: Represents vertices connected by edges. Operations include adding vertices or edges, traversal, connectivity testing, and path finding. Applications include maps, communication networks, and dependency analysis.

Common operations across structures include creation, traversal, access, search, update, insertion, deletion, sorting, and merging. Their costs vary with the representation and algorithm used.

Linear search examines elements sequentially until the target is found or all elements have been checked.

• Best-case time: when the first element matches.
• Worst-case time: when the target is absent or appears last.
• Average-case time: under typical uniform-position assumptions.
• Iterative auxiliary space: .

Binary search compares the target with the middle element and repeatedly discards half of the remaining search interval.

Its recurrence can be expressed as:

After reductions, the remaining size is . Setting it to gives:

Therefore:

• Best-case time: when the middle element matches immediately.
• Worst-case and average-case time: .
• Iterative auxiliary space: .
• Recursive auxiliary space: because of call-stack frames.

Binary search requires data sorted according to the same ordering used by comparisons. Its standard efficient form also assumes random access, as provided by arrays or vectors. Sorting solely to perform one search may cost and may not be worthwhile.

A time-space trade-off occurs when execution time can be reduced by using more memory, or memory usage can be reduced by performing additional computation.

Examples:

• Memoization: A recursive algorithm stores previously computed results. This consumes memory but prevents repeated computation. For example, a naive recursive Fibonacci implementation takes exponential time, while memoization can reduce it to time using additional space.
• Lookup tables: Precomputed values allow fast queries but require storage.
• Hash tables: Extra table space can provide expected search time, compared with a sequential search taking time.
• Compression: Keeping data compressed saves storage but requires time to compress and decompress it.
• In-place algorithms: An in-place sort saves auxiliary memory, while some algorithms using temporary arrays may be simpler or faster.

An algorithm may intentionally use more memory to improve response time, avoid repeated work, support caching, or process many queries efficiently. Conversely, embedded devices and memory-limited systems may accept additional computation to reduce storage.

The correct choice depends on input size, memory limits, latency requirements, number of repeated operations, implementation complexity, and hardware characteristics.

Asymptotic notations describe growth for sufficiently large input sizes while ignoring constant factors and lower-order terms.

Big-O upper bound:

if there exist constants and such that:

Big-Omega lower bound:

if there exist constants and such that:

Big-Theta tight bound:

if there exist constants and such that:

For and :

The left inequality establishes , and the right inequality establishes . Hence:

Although the function is also and , gives its tight asymptotic growth rate.

The function examines every unordered pair of distinct array positions satisfying . It increments count whenever the two positions contain equal values. Therefore, it returns the number of equal-value index pairs, not merely the number of distinct duplicated values.

For a fixed index , the inner loop executes times. The total number of comparisons is:

Since the number of comparisons grows quadratically, the running time is:

This bound is the same in the best, average, and worst cases because both loops perform the same number of iterations regardless of the array values. Only the number of increments changes.

The function uses a fixed number of scalar variables and allocates no data structure that grows with . Its auxiliary space complexity is therefore:

More time-efficient alternatives are possible. Sorting can support a approach, while a hash table can provide expected time at the cost of additional space, demonstrating a time-space trade-off.