Computer Science 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 including start/end, process, sub-program, input/output
  • Uses a diamond for selection decisions
• Abstraction


  Removing unnecessary detail from a problem
• Decomposition


  Breaking down a problem into sub-problems
• Structure diagram


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


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


  • Go through every line of code
  • Only add to a column when that value changes
  • Generally move to a new row when moving to a new block of code
• Linear search


  Looks for a target by comparing each item in a list one by one
• 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 pairs 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 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


  Determine how data is stored in the computer and the operations it can do
• 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 must be true)
  • Or (only one side needs to be true)
• Substring

  Extracts part of a string
• Concatenation


  Joins 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


  Obtained using an input statement, always a string
• Random function


  Generates a random number
• Sequence


  • Lines of code executed one after the other
• Selection


  • If statements, including if-elif-else and switch statements
• Iteration


  • Loops that repeat a set number of times (for loop) or until a condition is met (while loop, do-while loop)
• While loop


  1. Repeat until a condition is broken

  2. Useful when you don't know how many times the loop needs to repeat
• Do until loop (do while loop)

  1. Repeat until a condition is met

  2. Runs at least once even if condition is false
• Subprogram (subroutine)


  Named out-of-line block of code
• Procedure


  Type of subprogram
• Function


  Type of subprogram that has a return value
• Parameter


  Variable used as an input to a subprogram
• Return value


  Output from a subprogram
• Local variable


  Variable that only exists when the subprogram is executing and is only accessible inside the subprogram