IB CS HL Topic 4 - Computational thinking, problem-solving and programming

Pseudo Code

Conditions

Concurrent Programming

Concurrent Processing System - 1 job uses several processors to execute sets of instructions in parallel.

• Increases computation speed and complexity of the programming language and hardware.

Sequential

Refers to processes that are executed one after the other, without overlap in execution.

GANTT charts

Useful way to track the order of events

Pre conditions

Constraints the state of the system before the use case can start.

Post conditions

Constraints the state of the system after the use case has executed.

Abstraction

A technique for managing complexities of computer systems by removing some characteristics to focus on the essential ones.

Why use abstraction?

• Convenient way to deal with complexity

• Enables a person to concentrate on the essential aspects, while ignoring distracting details.

Successive Decomposition

A method of breaking down complex problems into simpler, more manageable sub-problems to better understand and solve them.

Collections

• Unordered lists of unknown length

• Dynamic size = efficient use of RAM

• Can store any data type

• Methods

  • addItem(item) - Adds an item to the end

  • getNext() - Returns the first item in the collection when first called, and subsequently gets the next item

  • resetNext() - Goes back to the start of the collection and restarts the iteration

  • hasNext() - Returns ‘TRUE‘ if there are

    one or more elements in the collection

  • isEmpty() - Returns TRUE if the collection does not contain any elements.

Sequential search

• To find an item in an ordered/unordered list

• Starts at the first element and compares each element to the target until it finds it.

• Pros: Can be performed on both sorted & unsorted lists

• Cons: Slower than binary search

Binary Search

• Half-interval search

• Only applies to sorted arrays

• Finds the position of a target value by repeatedly dividing the interval in half and comparing the target value to the middle element of the array

• If they are unequal, the lower or upper half of the array is eliminated, depending on the result, and the search is repeated in the remaining sub-array until it is successful.

• Pros: Faster than sequential search

• Cons: Can only be performed on sorted lists

Bubble sort

• Repeatedly steps through the list to be sorted, compares each pair of adjacent items, and swaps them if they are in the wrong order.

• Pros: Can finish faster if no/less swaps are made

• Cons: Makes a lot of swaps; complex

Selection sort

• Divides the input list into a sorted and an unsorted region.

• Initially, the sorted sublist is empty, and the unsorted sublist is the entire input list.

• Repeatedly selects the smallest/largest element from the unsorted region and moves it to the end of the sorted region.

• Moves the sublist boundaries 1 element to the right

• Pros: Max of n swaps (fewer than bubble sort); simple when memory is limited

• Cons: Inefficient on large lists; must always perform n swaps - cannot finish early; complex

Flowcharts

Shapes and Meanings

Factors affecting algorithm’s run time…

• computer used, the hardware platform

• representation of abstract data types

• efficiency of compiler

• competence of programmer

• complexity of underlying algorithm

• size of the input

Complexity

A measure of the amount of time [t(n)] and/or space required by an algorithm for an input of a given size (n).

Iteration

• Number of times a step is performed in an algorithm

• Often in loops/recursive methods

Fundamental operations of a computer

• CPU’s set of instructions

  • Add

  • Compare

  • Retreive

  • Store

Compound operations of a computer

• A large number of sub-operations

• Involves multiple stages/operations

Features of a computer language

• Computer languages

  • High level - Java, Python, C++

  • Low level - Assembly, Machine Code

• Fixed vocabulary

• Unambiguous meaning

• Consistent grammar & syntax

Need of high level languages…

• Similar to human language = easier to understand

• Allows for quicker development and debugging

• Abstracts basic operations of a computer

• Takes less time to type compared to low level languages

Compiler

The translator translates a high level language into a lower level language (done in a batch)

Interpreter

Translator translates a high level language into an intermediate code which will be immediately executed by the CPU (done line by line)

Assembler

Translator translates assembly language to machine code (mnemonics to binary)

Variable

• Storage location for data

• Represents a value

• Naming a memory location for later usage

• Has a pre-determined, fixed name and data type

Constant

• An identifier with an unalterable associated value

• Value cannot be changed during run-time

Operator

• A character/set of characters that represents an action

• Types

  • Boolean

  • Arithmatic

  • Assignment

  • Relational

Object

• An instance of a class

• Holds data (attributes - variables) and ways to manipulate the data (behaviors - methods)

Modular Programming

• Breaking down a programming project into modules

• Pros

  • Usefulness of reusable code

  • Manageable modules - easier to design, implement, test, and update/fix

  • Distributed development - Parallel work on different modules - less development time

  • Program readability increases

  • Eases program organization