Computer Programming Languages and Algorithmic Problem Solving

Course Overview and Computer Basics

• Computer systems consist of two primary components: hardware and software.
• A program is a defined set of instructions executed by a computer to carry out specific tasks.
• Software serves as the collective term for all the various programs used to instruct computer hardware.
• The Central Processing Unit (CPU), or processor, executes the instructions contained within a program.
• Computer memory stores data for processing and holds intermediate calculation results.
• Memory capacity is measured in bytes. For example, $1\text{ Gigabyte (GB)}$ of RAM corresponds to approximately $10^9\text{ bytes}$ (1 billion bytes) of memory.

Memory Organization and Addressing

• Main memory is structured as a long, continuous list of numbered bytes.
• The unique number assigned to a specific byte is defined as its address.
• A byte is the smallest addressable unit of memory in a computer architecture.
• Data of all types (numbers, characters, and text strings) is binary-encoded as sequences of $0\text{s}$ and $1\text{s}$ and stored directly in memory.
• Memory locations can span multiple contiguous bytes depending on the data type (e.g., 1-byte, 2-byte, or 3-byte memory locations).

Programming Languages and Classification

• Software programs convert high-level human logic into low-level instructions that computer hardware can execute.
• Programming languages fall into three primary categories based on abstraction level:
  • Machine Language: Low-level binary code consisting of $0\text{s}$ and $1\text{s}$ executed directly by the CPU (e.g., 1101101010011010).
  • Assembly Language: Low-level language using symbolic mnemonics to represent machine operations (e.g., add 2, 3, result).
  • High-Level Language: High-abstraction language providing readable syntax close to human logic and math (e.g., result = 2 + 3).

Overview of Major High-Level Programming Languages

• Ada: Named after Ada Lovelace, who worked on early mechanical general-purpose computing. Developed for the U.S. Department of Defense and used predominantly in defense projects.
• BASIC: Beginner's All-purpose Symbolic Instruction Code. Designed to be easy to learn and use for introductory programming.
• C: Developed at Bell Laboratories. Combines the speed and direct hardware control of assembly language with the portability and ease of use of high-level languages.
• C++: An object-oriented programming language built as an extension of C.
• C#: Pronounced "C Sharp". A hybrid language combining features of Java and C++, developed by Microsoft.
• COBOL: COmmon Business Oriented Language. Designed specifically for commercial business applications.
• FORTRAN: FORmula TRANslation. Highly popular for scientific, engineering, and mathematical calculations.
• Java: Developed by Sun Microsystems (now Oracle). Designed for creating platform-independent internet and enterprise applications.
• Pascal: Named after 17th-century calculating machine pioneer Blaise Pascal. A simple, structured, general-purpose language used primarily for teaching programming fundamentals.
• Python: A simple, general-purpose scripting language optimized for high readability and rapid development.
• Visual Basic: Developed by Microsoft to enable rapid development of graphical user interfaces (GUIs).

Programming Paradigms

• A paradigm is a system of concepts and practices reflecting the structural design and style of programming.
• A programming paradigm classifies languages based on how program execution and structure are organized.

Imperative vs. Declarative Programming

• Imperative Programming: The programmer explicitly gives sequential commands/instructions telling the machine how to change its state step-by-step. Examples include C, C++, Java, PHP, Python, and Ruby.
  • Imperative snippet in C: cpp void main() { int d; int a, b; a = 1; b = 1; d = a / b; cout << "division" << d; } &nbsp;&nbsp;&nbsp;&nbsp;
• Declarative Programming: The programmer specifies what result is required without defining the explicit control flow or step-by-step algorithm to achieve it. Examples include SQL and Prolog.
  • Declarative snippet in SQL: sql select upper(name) from people where length(name) > 5 order by name     

Specific Programming Paradigms

Structured Programming

• A subcategory of imperative programming.
• Control flow is strictly defined using three core control structures:
  1. Sequence: Executing statements sequentially. java x = 5; y = 11; z = x + y; System.out.println(z);      
  2. Selection: Conditional branching based on boolean evaluation. java if (x % 2 == 0) { System.out.println("The number is even."); }      
  3. Repetition: Iterative looping constructs. java while (x < 100) { System.out.println(x); x = x * x; } &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;

Procedural Programming

• Derived from structured programming and centered on procedural calls (functions, routines, or subroutines).
• Employs a top-down design approach where a program breaks down into smaller sub-functions.
• Programs begin execution from a central entry point function (e.g., main()).
• Examples include COBOL, BASIC, Pascal, FORTRAN, and C.

• Example of Procedural C Program:

  #include <stdio.h>

  // Function to add two numbers
  int add(int a, int b) {
      return a + b;
  }

  int main() {
      int num1, num2;
      printf("Enter two numbers: ");
      scanf("%d %d", &num1, &num2);
      int sum = add(num1, num2);
      printf("Sum: %d\n", sum);
      return 0;
  }
&nbsp;&nbsp;```

### Object-Oriented Programming (OOP)
- Structured around **objects** containing both state (data fields) and behavior (methods).
- Core concepts include **Classes** (blueprints) and **Objects** (instances of classes).
- Examples include C++, C#, Java, and Python.

| Class | Object Instances |
| :--- | :--- |
| Fruit | Apple, Banana, Mango |
| Car | Volvo, Audi, Toyota |
| Student | Ali, Hamza, Ahmad |

- Example Object-Oriented Java Program:

java public class Car { String carReg; int carModel; String carClass;

  public Car(String num) {
      carReg = num;
  }

  public String getReg() {
      return carReg;
  }

  public static void main(String[] args) {
      Car Audi = new Car("AX-7865");
      System.out.println(Audi.getReg());
  }

}   ```

Functional Programming (FP)

• Programs are constructed entirely by composing short, pure mathematical functions.

• Computation is driven by function applications rather than state changes and mutable variable assignments.

• All code and variables are strictly scoped within functions.

• Examples include Haskell, Lisp, JavaScript, Python, and C++.

• Comparison: Summing integers $1$ to $10$:

  • Imperative approach (Java):

  int total = 0;
  for (int i = 1; i <= 10; i++)
      total = total + i;
  &nbsp;&nbsp;&nbsp;&nbsp;```
  - Functional approach (Haskell):
  

  haskell sum [1..10]     ```

• Declarative/Functional vs. Imperative comparison in Java:

  import java.util.Arrays;
  import java.util.List;

  public class Functional {
      public static void main(String[] args) {
          List<Integer> numbers = Arrays.asList(11, 22, 33, 44, 55, 66, 77, 88, 99, 100);
          final int factor = 2;

          // Declarative / Functional Stream API
          numbers.stream()
                 .filter(number -> number % 2 == 0)
                 .forEach(System.out::println);

          // Imperative Loop Construct
          for (int number : numbers) {
              if (number % 2 == 0) {
                  System.out.println(number);
              }
          }
      }
  }
&nbsp;&nbsp;```

# Program Development Cycle

- Effective programming mandates planning algorithm design prior to writing source code.
- Large computational problems must be broken down into smaller sub-tasks.

![Seven-step program development lifecycle flowchart](https://assets.knowt.com/pdf-flow-prod/344cedc3-78d6-4909-b39d-0dc8215f8be9-figures/5.png)

## The Seven Steps of Program Development
1. **Step 1–4**: Devise Algorithm (identifies and resolves Algorithmic Problems).
2. **Step 5**: Translate to Code (identifies and resolves Implementation Problems).
3. **Step 6**: Test Program (verifies program execution correctness).
4. **Step 7**: Debug Program (routes algorithmic defects back to Steps 1–4 and syntax/implementation defects back to Step 5).

## Algorithmic Tools

### Algorithm
- A set of well-defined, ordered logical steps taken to perform a task.
- Example: Gross Pay Algorithm for an hourly employee:
  1. Obtain hours worked.
  2. Obtain hourly pay rate.
  3. Multiply hours worked by pay rate.
  4. Display the resulting gross pay calculation.

### Pseudocode
- An informal design language without strict syntax rules.
- Cannot be compiled or executed directly; serves as a language-agnostic blueprint for implementation.
- Example Pseudocode:

text Display "Enter the number of hours the employee worked." Input hours Display "Enter the employee's hourly pay rate." Input payRate Set grossPay = hours * payRate Display "The employee's gross pay is $", grossPay   ```

Flowcharts

• Diagrams graphically depicting algorithm flow using standardized symbols:
  • Ovals: Terminal symbols (Start / End).
  • Parallelograms: Input and Output operations (e.g., GET, PUT).
  • Rectangles: Processing operations (computations and variable assignments).
  • Arrows: Show execution flow path.

The 4-Step Algorithm Design Framework

1. Step 1: Work an Instance Yourself.
2. Step 2: Write Down Exactly What You Just Did.
3. Step 3: Generalize Your Steps.
4. Step 4: Test Your Algorithm.

Worked Example 1: Exponentiation ($x^y$)

• Problem statement: Calculate $x$ raised to the power $y$ ($x^y$).

Step 1: Work an Instance

• Choose concrete values $x = 3$ and $y = 4$. The mathematical target is $3^4 = 81$.

Step 2: Write Down Steps

• Multiply $3$ by $3$ $\rightarrow$ yields $9$.
• Multiply $3$ by $9$ $\rightarrow$ yields $27$.
• Multiply $3$ by $27$ $\rightarrow$ yields $81$.
• $81$ is the final answer.

Step 3: Generalize

• Replace static base $3$ with variable $x$:
  • Multiply $x$ by $3$ $\rightarrow$ yields $9$.
  • Multiply $x$ by $9$ $\rightarrow$ yields $27$.
  • Multiply $x$ by $27$ $\rightarrow$ yields $81$.
• Identify repetitive loop behavior:
  • Start with running result variable $n = x$
  • Loop count from $1$ to $y - 1$ (inclusive):
  • Update $n = \text{Multiply } x \text{ by } n$
  • Output $n$

Step 4: Test and Refine Algorithm

• Handle edge case $y = 0$:

  If y is 0 then
      1 is your answer
  Otherwise:
      Start with n = x
      Count up from 1 to y - 1 (inclusive), for each number you count:
          n = Multiply x by n
      n is your answer.
  ```
- Simplified unified form (initializing $n = 1$):

text Start with n = 1 Count up from 1 to y (inclusive), for each number you count: n = Multiply x by n n is your answer.   ```

Worked Example 2: Nearest Point Search Problem

• Problem statement: Given a target point $P$ and a set of candidate points $S$, find the point in $S$ closest to $P$.

Step 1: Work an Instance

• Input target point $P = (1, -1)$.
• Input candidate set $S = \{(2,7), (10,5), (8,-2), (7,-6), (-3,-5), (-8,0), (-5,6)\}$.
• Domain formula (Euclidean Distance):   $\text{distance} = \sqrt{\Delta x^2 + \Delta y^2} = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
• Step-by-step evaluations:
  1. Point $(2,7)$: $\text{distance} = \sqrt{(2-1)^2 + (7-(-1))^2} = \sqrt{1^2 + 8^2} = \sqrt{65} \approx 8.06$. Set current minimum distance = $8.06$.
  2. Point $(10,5)$: $\text{distance} = \sqrt{(10-1)^2 + (5-(-1))^2} = \sqrt{9^2 + 6^2} = \sqrt{117} \approx 10.82$. Compare $10.82$ to $8.06$ ($8.06$ is smaller; retain $(2,7)$).
  3. Point $(8,-2)$: $\text{distance} = \sqrt{(8-1)^2 + (-2-(-1))^2} = \sqrt{7^2 + (-1)^2} = \sqrt{50} \approx 7.07$. Compare $7.07$ to $8.06$ ($7.07$ is smaller; update best candidate to $(8,-2)$).
  4. Point $(7,-6)$: $\text{distance} = \sqrt{(7-1)^2 + (-6-(-1))^2} = \sqrt{6^2 + (-5)^2} = \sqrt{61} \approx 7.81$. Compare $7.81$ to $7.07$ ($7.07$ is smaller; retain $(8,-2)$).
  5. Point $(-3,-5)$: $\text{distance} = \sqrt{(-3-1)^2 + (-5-(-1))^2} = \sqrt{(-4)^2 + (-4)^2} = \sqrt{32} \approx 5.66$. Compare $5.66$ to $7.07$ ($5.66$ is smaller; update best candidate to $(-3,-5)$).
  6. Point $(-8,0)$: $\text{distance} = \sqrt{(-8-1)^2 + (0-(-1))^2} = \sqrt{(-9)^2 + 1^2} = \sqrt{82} \approx 9.06$. Compare $9.06$ to $5.66$ ($5.66$ is smaller; retain $(-3,-5)$).
  7. Point $(-5,6)$: $\text{distance} = \sqrt{(-5-1)^2 + (6-(-1))^2} = \sqrt{(-6)^2 + 7^2} = \sqrt{85} \approx 9.22$. Compare $9.22$ to $5.66$ ($5.66$ is smaller; retain $(-3,-5)$).
• Final Result: Closest point is $(-3,-5)$.

Step 2: Write Down Log of Actions

• Document distance calculations and compare each result against the ongoing minimal distance, recording best candidate updates whenever a smaller distance is encountered.

Step 3: Generalize

• Define calculation for point $S_i$ in set $S$:   $\text{currentDistance} = \sqrt{(S_i.x - P.x)^2 + (S_i.y - P.y)^2}$
• Define state tracking variables:
  • bestChoice: Point coordinates yielding the minimum distance.
  • bestDistance: Numerical value of the minimum distance found.
• Establish initialization:
  • Set bestChoice = $S_0$
  • Set bestDistance = $\sqrt{(S_0.x - P.x)^2 + (S_0.y - P.y)^2}$
• Iterative step rule:
  • Loop index $i$ from $1$ to length of $S - 1$ (exclusive of total point count):
  • Calculate currentDistance for point $S_i$.
  • If currentDistance < bestDistance, set bestChoice = $S_i$ and bestDistance = currentDistance.

Step 4: Final Generalized Pseudocode

Compute sqrt((S[0].x - P.x)^2 + (S[0].y - P.y)^2), call it bestDistance
Start with bestChoice of S[0]
Count from 1 to the number of points in S exclusive, call each number i:
    Compute sqrt((S[i].x - P.x)^2 + (S[i].y - P.y)^2), call it currentDistance
    If currentDistance is smaller than bestDistance:
        Update bestChoice to S[i] and bestDistance to currentDistance
Return bestChoice