PAPER DOS

• Algorithm

  A sequence of steps that can be followed to complete a task
• Algorithmic thinking

  Solving problems by defining steps and the sequence needed
• Program code is just implementing an algorithm
• Algorithms

  • Can be represented in pseudocode
  • Can be represented in flowcharts
• Pseudocode

  Resembling code but more relaxed
• Flowchart

  • Has a set group of symbols like start/end, process box, sub-program, input/output, selection, loops
• Abstraction

  Removing unnecessary detail from a problem
• Decomposition

  Breaking down a problem into sub-problems that each represent a specific task
• Structure diagram

  Represents decomposition of a large problem into sub-problems
• Trace table

  Shows how values change when an algorithm is carried out
• Trace tables

  • Go through every line of code and follow it
  • Only add to a column when that value changes
  • Generally only move to a new row when moving to a new block of code
• Algorithms to know

  • Linear search
  • Binary search
  • Bubble sort
  • Merge sort
  • Insertion sort
• Linear search

  Compares each item in a list one by one until the target is found
• Binary search

  Compares the middle item to the target, discards half the list, and repeats until the target is found or the list is exhausted
• Bubble sort

  Does a series of passes, swapping each pair if needed, until a full pass happens with no swaps
• Merge sort


  Divides the list continuously by two until each list has one item, then merges the lists back together keeping them in order
• Insertion sort

  Starts with one item in a sorted part and moves items one by one from the unsorted part to the sorted part, keeping the order
• Data types to know

  • Integer
  • Real (float)
  • String
  • Boolean
  • Character
• Casting

  Converting between data types
• Arithmetic operations


  • Addition
  • Subtraction
  • Multiplication
  • Division (real and integer)
  • Exponentiation
• Comparison operators

  Used in if statements and loops
• Boolean operators

  • And (both sides need to be true)
  • Or (only one side needs to be true)
• Substring

  Extracting part of a string
• Concatenation

  Joining two strings together
• Variables

  Identifiers that hold a value that can be changed
• Constants

  Identifiers that hold a value that cannot be changed
• User input

  Getting input from the user, which is always a string
• Printing

  Outputting information to the screen
• Random function

  Generates a random number
• Constructs

  • Sequence (lines executed in order)
  • Selection (if/elif/else statements)
  • Iteration (loops)
• For loop

  Repeats a set number of times, using a counter variable
• While loop

  Repeats until a condition is broken
• Do-until loop

  Repeats until a condition is met
• Looping a set number of times

  1. Use a counter variable like I

  2. Put a numerical sequence

  3. Use it in some other output
• Do until loop (do while loop)

  Repeats until a condition is met
• Condition control loops are used when you don't know how many times the loop needs to repeat
• While loop example


  1. While password not equals one two three

  2. Ask for the password again
• Do until loop (do while loop) example

  1. Condition comes after the body of the loop

  2. Loops always run at least once

  3. Condition is the opposite of a while loop
• Subprogram (subroutine)


  • Named out of line block of code
  • Can be a procedure or a function
• Calling a subprogram


  1. Execute the subprogram

  2. Can have parameters as inputs

  3. Can have a return value as output