Fundamentals of Programming and Algorithm Design Study Guide

What is Computer Programming?

• Computer programming is the process of giving computers instructions on what to do next.

• These instructions are written in code by programmers to solve problems or perform tasks.

• Programming languages enable humans to interact with machines and make them perform necessary operations, bridging the communication gap.

A Brief History of Computer Programming

• $1883$ (Ada Lovelace & Charles Babbage): The first computer program was created for the mechanical Analytical Engine. Lovelace realized that numbers could represent more than just raw quantities and wrote an algorithm to compute Bernoulli numbers.

• $1949$ (Assembly Language): This language was developed to simplify machine code instructions into readable symbols.

• $1957$ (FORTRAN): Created by John Backus specifically for scientific, mathematical, and statistical applications.

• $1972$ (C): Created by Dennis Ritchie as a high-level programming language that is closer to human expression.

• $1983$ (C++): Created by Bjarne Stroustrup as an object-oriented extension of the C language.

• $1991$ (Python): Developed by Guido van Rossum with a primary focus on code readability and simplicity.

• $1995$ (Java): Developed by Sun Microsystems, originally targeted at handheld devices.

• $2000$ (C#): Developed by Microsoft as an object-oriented language combining features of C++ and Visual Basic.

• $2014$ (Swift): Created by Apple to modernize development for iOS and macOS systems.

Types of Languages and Classification

• Low-Level Languages:

  • Machine Language: Consists purely of binary ($0s$ and $1s$). It is executed directly by hardware without the need for translation. Example: Machine Code.

• Middle-Level Languages:

  • Assembly Language: Uses short text symbols called mnemonics (e.g., $ADD \text{ A, B}$). It must be converted to binary using an Assembler.

• High-Level Languages:

  • High-Level: Features human-readable syntax using English keywords and strict rules known as Syntax. It is converted using a Compiler or Interpreter. Examples include C, C++, Java, Python, and FORTRAN.

Translators and Development Tools

• Assembler:

  • Definition: Converts Assembly language instructions into raw machine code ($0s$ and $1s$).

  • How it Works: Converts human-readable mnemonics like $ADD$, $MOV$, and $SUB$ directly into binary instructions for the CPU.

  • Key Feature: Translates code on a $1-to-1$ basis, meaning one line of assembly equals one line of machine code.

• Compiler:

  • Definition: Translates the entire high-level program into machine code at once before running it.

  • How it Works: Reads all source code, checks for syntax errors, optimizes it, and outputs an executable file (e.g., $.exe$).

  • Key Feature: Programs execute faster, but all syntax errors must be fixed before the program can run. Examples include compilers for C, C++, and Rust.

• Interpreter:

  • Definition: Translates and executes high-level source code line-by-line at runtime.

  • How it Works: Reads one line of code, translates it to machine code, runs it, and then moves to the next line.

  • Key Feature: Execution is slower, but debugging is easier because the program stops exactly at the line containing the error. Examples include interpreters for Python, JavaScript, and Ruby.

• IDE (Integrated Development Environment):

  • Definition: A single software application that combines all development tools into one window.

  • Components Included:

    • Code Editor with syntax highlighting and auto-completion.

    • Compiler/Interpreter buttons to run code instantly.

    • Debugger to step through code line-by-line.

  • Examples: Visual Studio Code, CLion, Eclipse, and PyCharm.

Structured Programming and the C Language

• Structured programming enforces clear logical control structures to make source code readable, modular, and maintainable.

• Fundamentals of C Program Structure:

  • #include <stdio.h>: Header file inclusion. Header files ($.h$) are libraries containing standard pre-defined functions. They are loaded using #include <filename.h> directives. For example, <stdio.h> provides standard input/output operations like printf and scanf.

  • int main(void): The exact execution entry point for the program. It is equivalent to the "trigger event" in block-based programming (such as "when green flag clicked").

  • Curly Braces ({ }): Define code blocks and the scope of execution.

  • Statements & Semicolons (;): Every command line must terminate with a semicolon.

  • printf("hello, world\n");: A statement that prints text to the screen.

  • return 0;: A statement indicating the function has completed successfully.

• Key Programming Components:

  • Functions: Modular, reusable blocks of code that perform specific operations.

  • Arguments: Values passed into functions as inputs inside parentheses (e.g., "hello, world\n" in printf()).

  • Variables & Data Types: Memory locations used to store changeable values. Example of integer declaration: int age;.

  • Assignment: The process of setting a value, such as counter = counter + 1;.

Logic Formulation & Data Representation

• Logic formulation is the systematic, step-by-step approach to analyzing and designing solutions to problems before writing executable code.

• Representing Numbers:

  • Decimal System: Human-standard counting using $10$ digits ($0-9$).

  • Binary System: Computer-standard counting using $2$ digits ($0$ and $1$).

  • Bit: A single binary digit ($0$ or $1$).

  • Hardware Implementation: Computers use electricity. Bits are represented physically using tiny switches called transistors, which are turned $ON$ for $1$ and $OFF$ for $0$.

  • Byte: A sequence of $8$ bits. Example: $00000011$ represents the number $3$.

  • Decimal to Binary Examples:

    • $0 = 0000$

    • $1 = 0001$

    • $2 = 0010$

    • $3 = 0011$

    • $4 = 0100$

    • $5 = 0101$

    • $6 = 0110$

• Representing Text:

  • Text is represented by mapping numbers to characters.

  • ASCII (American Standard Code for Information Interchange): Standard numerical mapping for basic characters, uppercase/lowercase letters, and punctuation.

    • 'A' is $65$ ($01000001$ in binary).

    • 'B' is $66$ ($01000010$ in binary).

    • Example message "HI!": ASCII Decimal: $72$, $73$, $33$. Binary: $01001000$, $01001001$, $00100001$.

  • Unicode: An expanded standard using more bits than ASCII to accommodate international symbols, accented characters, and emojis. Example: "Face with medical mask" emoji (
    f637 ) is represented by $4$ bytes: $11110000$, $10011111$, $10011000$, $10110111$.

• Representing Media:

  • Images: Displays consist of tiny square dots called pixels. Colors are represented using the RGB (Red, Green, Blue) standard, requiring $3$ bytes (one per channel with values from $0 - 255$).

    • Black: $R=0, G=0, B=0$

    • White: $R=255, G=255, B=255$

    • Red: $R=255, G=0, B=0$

    • Green: $R=0, G=192, B=0$

    • Blue: $R=0, G=32, B=255$

  • Video: A sequence of many image frames changing rapidly every second to create the perception of motion.

  • Sound: Audio formats like MIDI represent music digitally by mapping numbers to musical notes, duration, and volume.

Algorithms and Efficiency

• An algorithm is a step-by-step set of instructions for solving a problem.

• Phone Book Search Example:

  • Algorithm 1 (Linear Search): Flip $1$ page at a time from start to end. Correctness: Correct. Efficiency: Up to $n$ steps.

  • Algorithm 2: Flip $2$ pages at a time. Correctness: Incorrect (might accidentally skip the target page). Efficiency: Up to $\frac{n}{2}$ steps.

  • Algorithm 3 (Binary Search): Open to the middle, check if the name is in the left or right half, discard the unused half, and repeat. Correctness: Correct. Efficiency: $\text{log}_2(n)$ steps.

Pseudocode Standards and Rules

• Pseudocode is a plain English representation of an algorithm specifying logical flow and operations.

• Building Blocks of Pseudocode:

  • Functions (Actions/Verbs): Commands like PICK UP, OPEN TO, LOOK AT, CALL.

  • Conditionals (Branches): Paths based on conditions, such as IF, ELSE IF, ELSE.

  • Boolean Expressions (Questions): Statements evaluating strictly to TRUE/FALSE or YES/NO (e.g., "person is on page").

  • Loops (Cycles): Constructs that repeat specific execution sequences (e.g., GO TO line 3).

• Core Formatting Rules:

  • Capitalized Control Keywords: Keep control structures uppercase (IF, THEN, ELSE, WHILE, FOR, FUNCTION, RETURN, START, END).

  • Capitalized I/O: Write input/output operations in uppercase (READ, PRINT, INPUT, OUTPUT).

  • Indentation: Use indentation to define blocks inside IF, WHILE, or FOR structures.

  • One Action Per Line: Avoid multi-step statements on a single line.

• Pseudocode Operators:

  • Assignment: = (e.g., total = 0).

  • Comparison: ==, !=, <, >, <=, >=.

Pseudocode Examples

• Example 1: Product of Two Numbers

  • START

  • $1$ READ num1, num2

  • $2$ answer = num1 * num2

  • $3$ PRINT answer

  • END

• Example 2: Check Specific Input Values

  • START

  • $1$ READ userInput

  • $2$ IF userInput == 5 THEN

  • $3$ PRINT "Your number is 5"

  • $4$ ELSE IF userInput == 6 THEN

  • $5$ PRINT "Your number is 6"

  • $6$ ELSE

  • $7$ PRINT "Your number is not 5 or 6"

  • $8$ ENDIF

  • END

• Example 3: Range Check & Color Mapping

  • START

  • $1$ PRINT "Please enter a number"

  • $2$ READ colornum

  • $3$ IF colornum > 0 AND colornum <= 10 THEN

  • $4$ PRINT "Blue"

  • $5$ ELSE IF colornum > 10 AND colornum <= 20 THEN

  • $6$ PRINT "Red"

  • $7$ ELSE IF colornum > 20 AND colornum <= 30 THEN

  • $8$ PRINT "Green"

  • $9$ ELSE

  • $10$ PRINT "Not a correct color option"

  • $11$ ENDIF

  • END

• Example 4: Print Multiples of 5 (Loop)

  • START

  • $1$ x = 1

  • $2$ WHILE x <= 20

  • $3$ PRINT x * 5

  • $4$ x = x + 1

  • $5$ ENDWHILE

  • END

Flowchart Standards

• Flowcharts are graphical diagrams representing execution flow through standardized geometric symbols.

• Flowchart Symbols:

  • Terminal (Oval): Marks the START and END points.

  • Input / Output (Parallelogram): Represents taking data in or writing data out.

  • Process (Rectangle): Indicates internal calculations, actions, or variable assignments.

  • Decision (Diamond): Evaluates a conditional expression returning TRUE/FALSE or YES/NO.

  • Flow Line (Arrow): Defines the execution progression path between symbols.

  • Connector (Circle): Connects separate flow path segments on a single page.

Practice Exercises

• Question 1: Check Odd or Even Number

  • Task: Write pseudocode and describe a flowchart that prompts for an integer, checks if it is even or odd, and displays the result.

• Question 2: Find the Greatest of Two Numbers

  • Task: Write pseudocode and describe a flowchart that takes two numbers and prints the larger value. If equal, display a message stating equality.

• Question 3: Calculate Student Pass/Fail Status

  • Task: Write pseudocode prompting for marks ($0 - 100$). If marks $\ge 50$, print "Pass"; otherwise, print "Fail". Include validation for the range $0 - 100$.

• Question 4: Sum of Numbers from 1 to N

  • Task: Write pseudocode and describe a flowchart to calculate and print the sum of all positive integers from $1$ up to a user-entered number $N$.