COMP100 Lecture Two Notes

COMP100: Lecture Two Study Notes

Algorithm

• An algorithm is a well-defined, step-by-step procedure to solve a problem or achieve a specific goal.
  • It is a mathematical and computer science concept that specifies:
  • A series of actions to be executed.
  • Typical components include:
    • Conditions
    • Loops
    • Termination rules
  • Example and applications:
  • Algorithms are essential for programming and are the basis for writing effective code.

Program

• A program is an implementation of one or more algorithms in a specific programming language.
  • Defined as:
  • A set of instructions written to perform a specific task on a computer.
  • Represents a practical realization of algorithms.
  • Key differences from algorithms:
  • An algorithm is conceptual and general.
  • A program is language-specific and executable.

High Level Languages

• High-level languages are more convenient for humans to express algorithms compared to low-level languages.
  • Example of high-level language statement:
  • x = 26 - 5 (equivalent assembler code in one statement).
  • Important point:
  • Statements in high-level languages need to be translated into machine code for execution.

Interpreters and Compilers

Interpreters

• Interpreters are programs that take high-level programs as input and produce machine code or intermediate programs.
  • They process statements:
  • Typically one or a few statements at a time:
    1. Read a statement
    2. Translate it into machine code
    3. Execute the translated statement

Compilers

• A compiler reads and translates the entire program before it starts executing.
  • Definitions:
  • The high-level program before compilation is called source code.
  • The output generated is called object code or executable.
  • Once compiled, a program can be executed repeatedly without further translation.

Elements of Programming I

• All programming languages provide the following elements:
  1. Literals:
  • Actual data that the algorithms manipulate, like actual numbers and characters (e.g., "42", "Hello!").
  1. Variables:
  • Represents particular values, requiring the ability to create and assign variables for naming values.
  1. Arithmetic Expressions:
  • The language must provide operators to form arithmetic expressions. Example: $(v * 0.5 * (a / t))$.

Elements of Programming II

• Continuation of the essential elements:
  1. Logic Expressions:
  • Comparison operators to form boolean expressions that evaluate to true or false. Example: (x + y) >= 0.
  1. Input Functions:
  • To read input values from the user.
  1. Output Functions:
  • To write results to the screen.
  1. Control Structures:
  • Allow control over the execution flow of the algorithm.

What is a Programming Language?

1. Syntax:
   • Refers to how to correctly express statements in the language and the rules of grammar.
2. Semantics:
   • The meaning of the statements, specifically what happens when the statement is executed.
   • Typically involves how memory changes as a result of the execution.

Example of GCD Algorithm Implementations

In Assembler

section .text
global _start
_start:
    mov eax, 270  ; a value
    mov ebx, 192  ; b value
loop:
    cmp ebx, 0    ; compare b with zero
    je end        ; if zero, end the loop
    xor edx, edx  ; clear the edx
    idiv ebx      ; divide eax by ebx, remainder in edx
    mov eax, ebx  ; a becomes b
    mov ebx, edx  ; b becomes remainder
end:
; here eax contains the gcd

In Python

def gcd(a, b):  # loop until b is zero
    while b != 0:
        a, b = b, a % b  # replace a, b with b, a mod b
    return a

In Java

public class Main {
    public static int gcd(int a, int b) {  // loop until b is zero
        while (b != 0) {
            int temp = a;
            a = b;
            b = temp % b;
        }
        return a;  // return gcd
    }
}

In Julia

function gcd(a, b)
    while b != 0  # loop until b is zero
        a, b = b, a % b  # replace a, b with b, a mod b
    end
    return a  # return gcd
end

In Lisp

(defun gcd (a b)
    (loop until (zerop b)  ; loop until b is zero
        do
            (setf a b)
            (setf b (mod a b)))
    a)  ; return gcd

In C

#include <stdio.h>
int gcd(int a, int b) {  // loop until b is zero
    while (b != 0) {
        int temp = a;
        a = b;
        b = temp % b;
    }
    return a;  // return gcd
}