Problem solving, algorithms and the C environment notes — Unit 1

⇒What problem solving means here

• A computer has no judgement; it repeats instructions exactly as written.
• Problem solving is the human half — deciding the method before touching a keyboard.
• The method must be finite, unambiguous and produce a result for every valid input.
• The same method can then be written in C, Python or Java without change of logic.

⇒Stages of solving a problem

Split every problem into what enters, what happens and what leaves. It exposes a missing requirement in seconds and mirrors how marks are distributed in a programming answer.

Row three has no single formula — it has cases. Problems with cases are where careless answers lose marks, because the special case (D = 0, or a = 0) is quietly skipped.

An algorithm is a finite sequence of well-defined steps that transforms a given input into the required output.

⇒Algorithm: area of a circle

1. 1.Start.
2. 2.Read radius r.
3. 3.If r ≤ 0, print "invalid radius" and go to step 6.
4. 4.area ← 3.14159 × r × r.
5. 5.Print area.
6. 6.Stop.

⇒Algorithm: largest of three numbers

1. 1.Start. Read a, b, c.
2. 2.big ← a.
3. 3.If b > big then big ← b.
4. 4.If c > big then big ← c.
5. 5.Print big. Stop.

The second version scales: with the same pattern you can find the largest of a hundred numbers, while a chain of if-else comparisons cannot be extended.

• Every decision diamond has exactly one entry and two exits.
• Flow normally runs top to bottom; label any upward arrow (that is a loop).
• One Start and one Stop per flowchart, however many branches exist.

⇒Even or odd

⇒Sum of first N natural numbers

Pseudocode sits between an algorithm and a program: structured like code, readable like English, free of syntax rules.

BEGIN
  READ n
  fact <- 1
  FOR i <- 1 TO n DO
      fact <- fact * i
  ENDFOR
  PRINT fact
END

• Keywords in capitals: READ, PRINT, IF, WHILE, FOR, ENDIF, ENDWHILE.
• Use ← or <- for assignment, = only for comparison.
• Indent the body of every decision and loop; indentation is the structure.

1. 1.Problem definition — write down what the program must do, in one sentence.
2. 2.Analysis — identify inputs, outputs, formulae and invalid cases.
3. 3.Design — algorithm, flowchart, and how data will be stored.
4. 4.Coding — translate into C, one logical block at a time.
5. 5.Testing and debugging — normal, boundary and invalid inputs.
6. 6.Documentation and maintenance — comments, and later corrections.

C is called a middle-level language because it offers 3GL structure with 2GL access to memory addresses through pointers.

• Assembler: assembly language → machine code.
• Linker: joins your object code with library code into one executable.
• Loader: places the executable in memory and starts it.

• Developed by Dennis Ritchie at Bell Laboratories, 1972, to write the UNIX operating system.
• Standardised as ANSI C (C89), then C99, C11 and C17.
• Descended from BCPL and B, which is where the name comes from.

/* 1. Documentation: purpose, author, date */
#include <stdio.h>        /* 2. Link section  */
#define PI 3.14159        /* 3. Definition    */
float radius;             /* 4. Global declaration */
float area(float r);      /* prototype */

int main(void) {          /* 5. main function */
    printf("%.2f\n", area(2.0f));
    return 0;
}

float area(float r) {     /* 6. subprograms */
    return PI * r * r;
}

• Only main() is compulsory; execution always begins there.
• #include and #define are preprocessor directives — no semicolon.
• return 0 reports success to the operating system.

⇒Rules for identifiers

• Start with a letter or underscore, never a digit.
• Letters, digits and underscore only — no space, no hyphen.
• Case sensitive: total, Total and TOTAL are three variables.
• A keyword can never be used as an identifier.

A variable names a storage location whose value may change; a constant's value is fixed at compile time. Every variable must be declared before use — C will not guess a type.

int count;               /* declaration only, value is garbage */
int marks = 78;          /* declaration with initialisation   */
const float PI = 3.14f;  /* value cannot be changed later     */
#define MAX 100          /* preprocessor constant, no memory  */
char grade = 'A';        /* single quotes for a character     */

• Qualifiers: short, long, signed, unsigned change range, not meaning.
• unsigned int cannot hold a negative value; it wraps to a large positive one.
• Sizes are implementation defined — quote sizeof(), not a memorised number, if asked to prove it.

⇒Implicit versus explicit conversion

• Implicit (promotion): the compiler widens the smaller type — char → int → float → double.
• Explicit (cast): you force it, e.g. (float) a / b.
• 5 / 2 is 2, but (float) 5 / 2 is 2.5 — the cast applies before the division.

• Formatted: printf() and scanf() — need a format specifier per value.
• Unformatted: getchar(), putchar(), gets() (unsafe, use fgets()), puts().
• scanf() needs the address operator: scanf("%d", &n).

#include <stdio.h>

int main(void) {
    float p, r, t, si;
    printf("Enter principal, rate, time: ");
    scanf("%f %f %f", &p, &r, &t);
    si = (p * r * t) / 100;
    printf("Simple interest = %.2f\n", si);
    return 0;
}

Compile with gcc si.c -o si and run ./si. For 5000 8 2 the output is 800.00. Declare the variables as int instead and 5000 7.5 2 silently loses the fractional rate — the whole point of the exercise.

• Can you list the stages of program development with one line each?
• Can you write an algorithm and draw the matching flowchart for the same problem?
• Can you state four differences between a compiler and an interpreter?
• Can you predict output for a mixed-type expression with integer division?
• Can you name the six sections of a C program in order?