Fundamentals of Problem Solving and C Programming

Von Neumann Architecture

• Origins: The Von Neumann Architecture was created by John von Neumann. It represents the first written description of how an electronic computer should store and process information.

• Publication: It was published on June 30, 1945, as part of the ‐‐First Draft of a Report on the EDVAC (Electronic Discrete Variable Automatic Computer).‐‐

• Core Components: The architecture comprises five fundamental elements:

  • ALU (Arithmetic Logic Unit): Performs mathematical and logical operations.

  • Single Shared Memory: Used for storing both programs and data.

  • Single Memory Bus: A shared path for data transfer.

  • Input/Output: Systems for interacting with the external environment.

  • Control Unit: Manages the computer's resources and coordinates tasks.

• Legacy: This design remains the fundamental basis for all modern computers and most electronic devices.

Central Processing Unit (CPU) and Registers

• Primary Components:

  • Control Unit

  • Arithmetic Logic Unit (ALU)

  • Registers

  • Memory Unit

• Registers Definition: Registers are small, high-speed storage areas located within the CPU. They are used to hold data and instructions temporarily during processing.

• Key Registers and Functions:

  • Program Counter (PC): Holds the memory address of the next instruction to be fetched from memory.

  • Current Instruction Register (CIR): Holds the specific instruction currently being decoded and executed.

  • Accumulator (ACC): Used by the ALU to hold data currently being processed as well as the results of calculations.

  • Memory Address Register (MAR): Holds the address of the data or instruction to be fetched from memory, or the destination address in memory for data transfer.

  • Memory Data Register (MDR): Stores the actual instructions or data being fetched from or written to the memory address specified in the MAR.

Communication Systems and the System Bus

• System Bus: A communication system where only one device can transmit data at any given time. It consists of three specific types of buses:

  • Data Bus: Transfers actual data between components. This bus is bidirectional.

  • Address Bus: Carries the memory or I/O controller addresses to be accessed. This bus is unidirectional from the CPU to other components.

  • Control Bus: Transmits control signals (like read/write signals or interrupt requests) from the CPU to components and sends status signals back to the CPU. This bus is bidirectional.

Fetch-Decode-Execute Cycle

• Concept: Programs are stored in memory as instructions alongside data.

• Process: The processor periodically fetches instructions from the main memory, decodes what the instruction means, and subsequently executes the required operations.

Memory Hierarchy and Caches

• Hierarchical Structure (from fastest/most expensive to slowest/cheapest):

  1. Registers: Smallest capacity, highest speed, highest price, located in the CPU.

  2. Cache: Small, fast memory located on the CPU chip or very close to it. It stores frequently accessed data.

  3. Main Memory (DRAM): Larger and slower than cache; used for currently running programs and data.

  4. Flash Memory / Solid State Drives / Hard Drives: Large capacity, slow speed, lowest price. Non-volatile storage for long-term data preservation.

• Calculated Cache Levels:

  • L1 Cache: The smallest and fastest, typically on the CPU core. Often split into Instruction Cache ($L1i$) and Data Cache ($L1d$).

  • L2 Cache: Larger and slightly slower than L1.

  • L3 Cache: The largest and slowest of the CPU caches, but still significantly faster than main memory.

Parallelism vs. Concurrency

• Parallelism: Involves using multiple processing units to perform tasks simultaneously and independently.

• Concurrency: Refers to managing multiple tasks on even a single CPU core by switching between tasks before they are necessarily completed.

• Design: Programs can be parallel, concurrent, both, or neither.

Number Systems in Computing

• Decimal (Base-10): Standard system for everyday calculations using digits $0$ through $9$.

• Binary (Base-2): The foundation of digital systems using digits $0$ and $1$.

• Octal (Base-8): Uses digits $0$ through $7$ to simplify binary representation.

• Hexadecimal (Base-16): Uses digits $0-9$ and letters $A-F$ to represent values $10-15$. Essential for simplifying large binary data.

• Duodecimal (Base-12): A less common system with specific niche applications.

Number System Conversions

• Decimal to Binary ($10.25_{10}$ to Binary):

  • Integer Part ($10$):

    • $10 \div 2 = 5$ (Remainder $0$)

    • $5 \div 2 = 2$ (Remainder $1$)

    • $2 \div 2 = 1$ (Remainder $0$)

    • $1 \div 2 = 0$ (Remainder $1$)

    • Read remainders bottom-up: $1010$.

  • Fractional Part ($0.25$):

    • $0.25 \times 2 = 0.5$ (Integer $0$)

    • $0.5 \times 2 = 1.0$ (Integer $1$)

    • Read integers top-down: $01$.

  • Result: $(1010.01)_2$.

• Binary to Decimal ($1010.01_2$ to Decimal):

  • Calculations: $(1 \times 2^3) + (0 \times 2^2) + (1 \times 2^1) + (0 \times 2^0) + (0 \times 2^{-1}) + (1 \times 2^{-2})$

  • Sum: $8 + 0 + 2 + 0 + 0 + 0.25 = 10.25_{10}$.

• Decimal to Octal ($10.25_{10}$ to Octal):

  • Integer Part ($10$):

    • $10 \div 8 = 1$ (Remainder $2$)

    • $1 \div 8 = 0$ (Remainder $1$)

    • Result: $12_8$.

  • Fractional Part ($0.25$):

    • $0.25 \times 8 = 2.0$ (Integer $2$)

    • Result: $0.2_8$.

  • Final: $12.2_8$.

• Octal to Decimal ($12.2_8$ to Decimal):

  • Calculations: $(1 \times 8^1) + (2 \times 8^0) + (2 \times 8^{-1})$

  • Sum: $8 + 2 + 0.25 = 10.25_{10}$.

• Decimal to Hexadecimal ($10.25_{10}$ to Hexadecimal):

  • Integer Part ($10$): $10 \div 16 = 0$ Remainder $10$ (which is $A_{16}$).

  • Fractional Part ($0.25$): $0.25 \times 16 = 4.0$ (Integer $4$).

  • Result: $A.4_{16}$.

• Hexadecimal to Decimal ($A.4_{16}$ to Decimal):

  • Calculations: $(A \times 16^0) + (4 \times 16^{-1}) = (10 \times 1) + (4 \times 0.0625) = 10.25_{10}$.

• Hexadecimal to Binary ($3A_{16}$):

  • $3_{16} = 0011_2$

  • $A_{16} = 1010_2$

  • Result: $00111010_2$.

• Binary to Hexadecimal ($1111011011_2$):

  • Group by 4 bits from right: $0011$ ($3$), $1101$ ($D$), $1011$ ($B$).

  • Result: $3DB_{16}$.

• Binary to Octal ($111101101_2$):

  • Group by 3 bits: $111$ ($7$), $101$ ($5$), $101$ ($5$).

  • Result: $755_8$.

• Octal to Binary ($153_8$):

  • $1_8 = 001_2$, $5_8 = 101_2$, $3_8 = 011_2$.

  • Result: $001101011_2$.

Practice Problems: Number Systems

• Easy Level:

  • Convert $(101101)_2$ to Decimal.

  • Convert $(57)_8$ to Decimal.

  • Convert $(3A)_{16}$ to Decimal.

  • Convert $(45)_{10}$ to Binary.

  • Convert $(83)_{10}$ to Octal.

• Medium Level:

  • Convert $(11010110)_2$ to Decimal.

  • Convert $(256)_{10}$ to Binary.

  • Convert $(175)_{10}$ to Octal.

  • Convert $(255)_{10}$ to Hexadecimal.

  • Convert $(764)_8$ to Binary.

• Advanced Level:

  • Convert $(110111101)_2$ to Octal.

  • Convert $(527)_8$ to Binary.

  • Convert $(111100101101)_2$ to Hexadecimal.

  • Convert $(A9F)_{16}$ to Binary.

  • Convert $(372)_8$ to Hexadecimal.

  • Convert $(2F5)_{16}$ to Octal.

  • Convert $(110110101011)_2$ to Decimal.

  • Convert $(1023)_{10}$ to Binary, Octal, and Hexadecimal.

  • Convert $(7B9)_{16}$ to Decimal.

Types of Programming Languages

• Classification by Abstraction:

  • High-Level Languages: Human-readable, portable, and requires a compiler or interpreter (e.g., Python, Java, JavaScript).

  • Low-Level Languages: Close to machine code, provides high hardware control but is difficult to write (e.g., Machine code).

  • Assembly Languages: Uses symbolic instructions. An assembler converts it to machine code.

• Classification by Paradigm:

  • Procedural: Follows step-by-step commands (e.g., Java, Pascal, BASIC).

  • Functional: Based on mathematical functions (e.g., Scala, Haskell, F#, Lisp, Erlang).

  • Object-Oriented (OOP): Programs are collections of objects (e.g., Python, Ruby, C++, Java, C#, Swift, Kotlin, Objective-C).

  • Scripting: Interpreted at runtime without pre-compilation (e.g., Python, Perl, PHP, Bash, JavaScript, PowerShell).

  • Logic: Uses logical statements and relationships (e.g., Prolog, Alma-0, Absys, Mercury).

Language Processors

• Compiler: Reads the entire high-level source program as a whole and translates it into machine language in one go (e.g., C, C++, C#).

• Interpreter: Translates and executes one statement at a time immediately before moving to the next line.

• Assembler: Translates assembly language into machine code.

Structure of a C Program

• Six Basic Sections:

  1. Documentation: Contains descriptions, programmer name, and creation date using comments (// or /* ... */).

  2. Preprocessor Section: Includes header files (e.g., #include <stdio.h>).

  3. Definition: Defines symbolic constants (e.g., #define PI 3.14).

  4. Global Declaration: Contains global variables, static variables, and function prototypes accessible throughout the program (e.g., int num = 18;).

  5. Main() Function: The mandatory starting point for every C program, enclosed in braces { }.

  6. Sub Programs: Where user-defined functions are implemented.

C Preprocessors and Macros

• Purpose: Modifies source code before compilation begins.

• Macro Directives:

  • Constant Macros: Replaces identifiers with values (e.g., #define LIMIT 5).

  • Macros with Arguments: Function-like macros that expand into reusable snippets without function call overhead (e.g., #define AREA(l, b) (l * b)).

Data Types in C

• Primary / Basic Data Types:

  • Integer (int): Represents decimal integers; further classified as signed or unsigned.

  • Character (char): Represents characters; size is $8$ bits.

  • Real: Represents decimal or integer numbers on the number line (Float, Double).

  • Void: Represents the absence of type.

  • Pointer: Holds the memory address of another variable using operators & and *.

• User-Defined Data Types:

  • Typedef: Creates an identifier for an existing type (e.g., typedef int numbers;).

  • Enumerated (enum): Assigned a value from a specific set of values.

• Derived Data Types:

  • Array: A collection of homogeneous data types stored in contiguous memory.

  • Structure (struct): A collection of non-homogeneous (different) data types.

  • Union: Similar to structures but shares the same memory space for all members.

Variables and Constants in C

• Variable Features: Named memory locations, stored in RAM, whose value can change at runtime. Syntax: data_type variable_name = value;.

• Variable Types:

  • Local: Declared inside a function.

  • Global: Declared outside functions.

  • Static: Retains its value between multiple function calls.

  • External (extern): Shared across multiple source files.

  • Automatic: Default for local variables within a block.

• Constants: Fixed values that cannot be modified after definition.

  • Literal Constants: Direct values like $10$, $3.14$, or "Hello".

  • Const Keyword: Variables defined with const (e.g., const int MAX = 100;).

  • Preprocessor Constants: Defined using #define PI 3.14159.

Operators and Bitwise Logic

• Operator Groups: Arithmetic, Assignment, Comparison, Logical, and Bitwise.

• Order of Operations (Highest to Lowest):

  1. () - Parentheses

  2. *, /, % - Multiplicative

  3. +, - - Additive

  4. >, <, >=, <= - Comparison

  5. ==, != - Equality

  6. && - Logical AND

  7. || - Logical OR

  8. = - Assignment

• Bitwise Operators:

  • & (Binary AND): Copies a bit to the result if it exists in both operands. (e.g., $60 \, \& \, 13 = 12$).

  • | (Binary OR): Copies a bit if it exists in either operand. (e.g., $60 \, | \, 13 = 61$).

  • ^ (Binary XOR): Copies a bit if it is set in one operand but not both. (e.g., $60 \, \wedge \, 13 = 49$).

  • ~ (Binary One's Complement): Unary operator that flips bits. (e.g., ~60 yields bits representing $-61$).

  • << (Binary Left Shift): Moves bits left by a specified number of positions (e.g., $60 \ll 2 = 240$).

  • >> (Binary Right Shift): Moves bits right (e.g., $60 \gg 2 = 15$).

Storage Classes in C

• auto:

  • Scope: Local.

  • Lifetime: Block exit.

  • Default Value: Garbage.

  • Storage: Stack memory.

• register:

  • Scope: Local.

  • Lifetime: Block exit.

  • Storage: CPU register (for speed).

  • Note: Cannot use the & address operator on register variables.

• static:

  • Scope: Local to block or global to file.

  • Lifetime: Entire program execution.

  • Default Value: Zero.

  • Storage: Data segment.

• extern:

  • Scope: Global (cross-file).

  • Lifetime: Entire program execution.

  • Default Value: Zero.

  • Storage: Data segment.