Algorithms and Problem Solving

Algorithms and Problem Solving

• Algorithms are procedures for solving a problem.
• Algorithms specify actions and their order.
• Software development follows a method.
• Steps in the method include:
  • Problem analysis
  • Program design
  • Program coding
  • Testing and documentation
  • Maintenance and updates
• The software development method can be expanded to include:
  • Specify the problem requirements.
  • Analyze the problem.
  • Design the algorithm to solve the problem.
  • Implement the algorithm.
  • Test and verify the program.
  • Maintain and update the program.
• Polya's problem-solving steps, applied to program development:
  • Understand the problem.
  • Get an idea of how an algorithmic function might solve the problem.
  • Formulate the algorithm and represent it as a program.
  • Evaluate the solution for accuracy and its potential as a tool for solving other problems.

Software

• Programs are sets of instructions for a computer.
• Software is a collection of programs.
• Two types of software:
  • System software: manages hardware enabling execution of application programs. Examples: Operating Systems, Compilers, Programming Languages.
  • Application software: solves user problems. Examples: Word processors, database management.

Computer Languages

• Machine language: a collection of binary numbers directly understood by the computer.
• Assembly language: uses symbolic names to represent machine operations and memory locations, making it easier to use than machine language. An assembler converts this language to machine language.
• High-level language: combines algebraic expressions and symbols (like English commands) used by programmers. Compilers or interpreters translate these languages into machine language. Examples: C, Pascal, FORTRAN, Python.

High-Level to Low-Level Languages

• High-level languages (e.g., Python) express the addition of numbers more naturally.
• To execute high-level language programs, they need to be translated into machine language using a compiler or interpreter.
• A compiler translates the entire program into machine language at once.
• An interpreter translates and executes the program line by line.

Compilers

• Compilers are complex software programs.
• They take a high-level language program and translate it into an equivalent program in machine language.
• The machine language version of the program is called the object code.
• The input is the high-level language and the output is the machine code, which can then be run by the computer.

Interpreters

• Interpreters analyze and execute source code instruction by instruction.
• High-level languages like Python use interpreters.
• Interpreters are less efficient than compilers in terms of execution speed because they analyze and translate each instruction every time it's encountered.

Meter to Yard Conversion Example

• A program is needed to convert square meters to square yards. -Input is the size in square meters (decimal). -Output is the size in square yards (decimal). -Formula: square yards = 1.196 * square meters

Polya's Problem Solving Steps

• Understand the problem.
• Generate ideas for algorithmic solutions.
• Formulate the algorithm as a program representation.
• Evaluate the solution for accuracy and its use in other problem contexts

Ages of Children Problem

• Person A is tasked to determine the ages of B's three children.
• B provides clues:
  • Product of their ages is 36
  • Sum of their ages required additional clues
  • Oldest child plays piano
• The solution is to find integer combinations of ages that multiply to 36, whose sums satisfy B's givens.

Algorithm

• An algorithm is a procedure—a set of actions and the order in which these actions should be performed—used to solve a problem.

Pseudocode

• Pseudocode is an informal, English-like language for describing algorithms.
• Pseudocode is not specific to any computer language.
  • Example: Get out of bed, take a shower, get dressed, eat breakfast, drive to work

Diagrams

• Flowcharts: graphical representations of algorithms using predefined symbols for start/stop input/output, processing, and flow control

Algorithm Representation

• Algorithms require well-defined primitives, basic operations, to be effectively implemented as computer programs.

Control Structures

• Programs execute instructions in a specific order, and this order is controlled by control structures.
• There are three main control flows:
  • Sequence
  • Selection
  • Iteration

Pseudocode Primitives

• Assignment statements (e.g., name = expression).
• Conditional statements (e.g., if condition: activity).
  • Also including "else" statements for alternate conditions.
• Repeated statements (e.g., while condition: body).

Flowchart Examples

• Flowcharts illustrate the steps and logic of algorithms visually.
  • Showing input, output, processing, decision points, and the order of execution.
• Provide visualizations of algorithms using established symbols.