Notes on Algorithms, Pseudocode, and Basic Program Design

Algorithm foundations

• An algorithm is a step-by-step set of instructions that tell how to accomplish a task.
  • It is not written in a programming language.
  • It can be written in English or in pseudocode (a mix of natural language and programming-like statements).
• Key questions when analyzing an algorithm:
  • What data does the program need to work on?
  • How will the data be provided or read (input format)? Will data come from user input or a data file?
  • What is the format of each value? How much data is in the file?
  • What calculations are performed and what are the constraints on inputs or results?
  • How will the output be presented (screen vs. data file)?
• Basic design considerations include anticipating user mistakes (input validation) and handling exceptions when invalid data is read.
  • Example of a potential exception: if a user is asked for a decimal number and types a non-numeric string, an exception can terminate the program.
• Real-world example concept: developing a simple calculator algorithm (discount price) to avoid mental math at the store.

Pseudocode: purpose, form, and conventions

• Pseudocode is a non-formal, hybrid notation that expresses an algorithm without tying it to a specific language.
• It should be understandable and implementable in any language (C, Java, C++, JavaScript, etc.).
• The speaker proposes a personal, modified form of pseudocode for classroom use.
• Common elements in pseudocode (as used in the lecture):
  • Input from the user and saving values (e.g., read from user input, save as itemPrice).
  • Output to the screen (e.g., write/output text or values to the screen).
  • Variable naming conventions: typical guidance is that names begin lowercase and use camelCase for multi-word names (e.g., itemPrice, discountRate).
  • Flow control:
  • Conditional: if condition then action else alternativeAction. Example: testScore >= 90 yields an A, else if testScore >= 80 yields a B, etc.
  • Nested and chained conditions (else if) are allowed.
  • Repetition: while condition doSomething (loop while there are more inputs, etc.).
• Important note: there is no single standard for pseudocode; it’s meant to express the algorithm’s intent, not to be a runnable program.
• Rationale for pseudocode: once you have an algorithm, you can implement it in any language; pseudocode serves as a language-agnostic blueprint.
• Emphasis on explicit prompts and input handling:
  • Be explicit about what you’re asking for (e.g., input the original price, input the discount).
  • Distinguish between data to collect, how to collect it, what calculations to perform, and what to display.
• Memory and memory management concept:
  • A computer doesn’t remember anything until you store a value in a variable,
  • Memory is allocated during program execution and is not preserved after the program ends.
• Typographic emphasis in the lecture:
  • Bold capitalization is used to highlight keywords; it’s not required, but helps to identify core actions (e.g., Read, Write).

Example: a simple discount calculator (data, process, output)

• Data needed:
  • Original price of an item
  • Discount value (as a decimal, e.g., 0.25 for 25%)
• Data source:
  • Prompt the user for inputs, then read from keyboard (console input).
• Calculations (conceptual):
  • Discounted price = originalPrice × (1 − discount)
• Output:
  • Display the discounted price on the screen.
• Constraints and validation:
  • Prices should be non-negative; discount should be greater than or equal to 0 and less than 1 (depending on input convention).
• Pseudocode example (conceptual):
  • Write: "Enter original price:" to screen
  • Read: originalPrice from user
  • Write: "Enter discount (as decimal, e.g., 0.25):" to screen
  • Read: discount from user
  • discountedPrice = originalPrice × (1 − discount)
  • Write: discountedPrice to screen
• Notes on language-specific implementation:
  • The same algorithm can be implemented in Java, C, JavaScript, etc. The lecture shows a Java example using a Scanner to read input and println to display output, with variables like itemPrice and discount.

Key programming concepts highlighted

• Variables and data storage:
  • You must declare and store inputs and results in variables to allow the program to perform calculations and to remember them during execution.
• Input validation and exceptions:
  • If input is not of the expected type (e.g., a string where a number is required), the program can throw an exception or handle the error gracefully.
• Language-agnostic perspective:
  • An algorithm is independent of a specific language; it focuses on the steps to solve a problem.
• Naming and style:
  • Consistent naming aids readability; camelCase is suggested for multi-word variable names.

Practical example: cell phone usage charges (HW prompt and calculation)

• Given: minutes used, base charge, overage rate, and tax rate.
• Rules described in the transcript:
  • If minutes exceed 300, there is an overage charge at $0.45 per minute for the extra minutes.
  • A base charge of $29.95 is added.
  • A sales tax of 12.5% (0.125) is applied to the subtotal.
• Key numerical references (as stated):
  • Overage rate: $0.45$ per minute
  • Threshold: $300$ minutes
  • Base charge: $29.95$
  • Tax rate: $0.125$ (12.5%)
• Formulas (as derived from the lecture’s workflow):
  • Overages: $ext{overage} = ext{max}(0, ext{minutesUsed} - 300) imes 0.45$
  • Subtotal before tax: $ext{subtotal} = ext{overage} + 29.95$
  • Total cost with tax: $ext{cost} = ext{subtotal} imes (1 + 0.125) = ext{subtotal} imes 1.125$
• Notes:
  • If minutesUsed ≤ 300, overage is 0 and cost is simply 29.95 × 1.125 (tax applied to the base charge).
  • The calculation illustrates applying a conditional workflow, accumulation, and tax on a subtotal.
  • The homework prompt asks students to implement this as an algorithm, including input prompts and the calculation steps.

Practical example: painting a bedroom (geometry and rounding up cans)

• Data to collect:
  • Wall dimensions: width and height of one wall (the room is assumed square so all four walls have the same height and width)
  • Door dimensions (height, and possibly width as discussed)
  • Window dimensions: height and width
  • Paint coverage: square feet per can (provided by the paint can)
• Area calculations described in the transcript:
  • Area of walls: $ext{wallArea} = 4 imes ext{wallHeight} imes ext{wallWidth}$
  • Door area (as stated): $ext{doorArea} = 4 imes ext{doorHeight}$
  • Window area: $ext{windowArea} = ext{windowHeight} imes ext{windowWidth}$
• Combined area to paint:
  • The transcript moves from individual areas to a combined area to paint; the typical intended formula is:
  • $ext{areaToPaint} = ext{wallArea} - ext{doorArea} - ext{windowArea}$
  • (Note: the speaker implies combining these areas to determine how much surface must be painted; the minus terms account for openings, though the exact wording in the talk is a bit ambiguous about the subtraction.)
• Can calculation (rounding up):
  • Number of cans: $ext{cansNeeded} = \left\lceil \frac{\text{areaToPaint}}{\text{coverage}} \right\rceil$
• Data prompts and non-language specifics:
  • Prompt: "Please input height and width of the bedroom" (and then read wall height and wall width)
  • The speaker notes that paint coverage is provided by the can and that the calculation is not language-specific; this is an opportunity to practice translating a real-world problem into an algorithm.
• Practical considerations:
  • The problem demonstrates breaking a task into data, calculations, and final output, and the need to round up since you cannot buy a fraction of a can.

Additional notes and classroom context

• The instructor refers to a delayed reward: a homework problem will be assigned (paint calculation scenario) with a due date later in the week; help will be available if questions arise.
• The algorithm design approach presented includes: identifying data needs, where data comes from, what calculations occur, and what the output should be.
• Emphasis on problem-solving framing: describe the problem in terms of inputs, processing, and outputs, rather than diving straight into code.
• Philosophical/practical takeaway: an algorithm communicates what to do (the steps), while the programming language specifies how to do it (syntax and implementation).

Key takeaways

• Algorithms are language-agnostic blueprints for solving problems; pseudocode helps bridge the idea to code.
• Always analyze data requirements, input sources, data formats, and constraints before coding.
• Use clear, consistent variable naming and explicit prompts to improve usability and robustness.
• Use control structures (if/else, else-if, while) to model decisions and repetition in your problems.
• Remember that a computer only computes what you tell it to; values must be stored in variables to be used later.
• Common real-world examples (discount calculator, phone charges, painting project) illustrate how to translate a spoken problem into a structured algorithm with concrete formulas and rounding rules.

Note: The formulas use standard mathematical notation converted to LaTeX for precise representation, as requested. For example:

• $ext{discountedPrice} = ext{originalPrice} \times (1 - \text{discount})$
• $ext{areaToPaint} = \text{wallArea} - \text{doorArea} - \text{windowArea}$
• $ext{cansNeeded} = \left\lceil \dfrac{\text{areaToPaint}}{\text{coverage}} \right\rceil$
• $ext{subtotal} = ext{overage} + 29.95$
• $ext{cost} = \text{subtotal} \times 1.125$