paper 2

• 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
• 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 move to a new row when moving into a new block of code
• Searching algorithms


  • Linear search
  • Binary search
• Linear search


  Compares each item in a list one by one until the target is found, list does not need to be ordered
• Binary search


  Compares the middle item to the target, discards half the list, repeats until target is found, list must be ordered
• Sorting algorithms


  • Bubble sort
  • Merge sort
  • Insertion sort
• Bubble sort


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


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


  Starts with one item in a sorted part, moves items one by one from the unsorted part to the sorted part
• In section A, you can answer algorithm questions in your own way, while in section B the questions will be more restricted
• Data types


  • 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)
• String operations


  • Substring (extract part of a string)
  • Concatenation (join strings)
• Variables


  Identifiers that hold a value that can be changed
• Constants


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


  Assigned to a variable, always a string so may need to be cast
• Printing


  Outputting to the screen, can concatenate strings
• Random function


  Generates a random number
• Programming constructs


  • Sequence (lines executed in order)
  • Selection (if/elif/else statements)
  • Iteration (for loops, while loops, do-while loops)
• Selection


  If statements are always checked, elif statements are only checked if previous conditions were false, else statements cover all other possibilities
• Switch statement


  An alternative to multiple if/elif statements, based on the value of a variable
• Count-controlled loop (for loop)


  Repeats a set number of times, uses a counter variable
• Condition-controlled loop (while, do-while)

  Repeats until a condition is met (or broken), don't know how many times in advance
• 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
• While loop


  Repeats until a condition is broken
• 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