Unit 1 algorithms

Algorithms

specific set of instructions for solving a problem or completing a task

abstraction

removing unnecessary details from a problem to focus on essential components

decomposition

breaking down a large problem into smaller sub-problems

Arithmetic operators

+ addition

- subtraction

/ division

* multiply

^ exponent

MOD remainder

DIV integer division

Arithmetic operators in c#

+ addition

- subtraction

/ division

* multiply

^ exponent

% remainder

/ integer division

Flowchart symbols

program structures

sequence, selection, iteration

what is selection?

ability to choose different paths through a program

what is sequence?

series of steps are completed one after the other

what is iteration?

repeating a part of a program, referred to as repetition/looping in flowcharts show through arrows that repeats a part of the flowchart

Pseudo code symbol for less than

< less than

Pseudo code symbol for less than or equal to

Pseudo code symbol for greater than

>

Pseudo code symbol for greater than or equal to

Pseudo code symbol for equal to

=

Pseudo code symbol for assignment

<--

Pseudo code symbol for not equal to

Pseudo code symbol for multiply

*

Pseudo code symbol for addition

+

Pseudo code symbol for division

/

Pseudo code symbol for subtraction

-

Pseudo code symbol for exponent

^

what is IF ELSE?

Branching depending on the condition

USER INPUT

Get user to input

OUTPUT

Outputs to user

FOR

Repeat a set number of times

WHILE

Repeat while a condition is true

REPEAT UNTIL

Do a loop until a condition is true

INT_TO_STRING

converts an integer to a string

STRING_TO_INT

converts a string to an integer

THEN

Executes if condition is true

Iteration is pseudocode

FOR... ENDFOR

WHILE... ENDWHILE

REPEAT... UNTIL

Types of searches

Binary search, linear search

Binary search

Only works on sorted lists, middle item of the list is checked first.

If the item searched for is less than this item, the right side of the list is discarded, and a binary search executed on the left side of the list.

Linear search

If list is not sorted. Items are examined in order

Time tables

The variables can be traced as a program is run, done using a trace table

Types of sorts

Bubble sort, merge sort

Bubble sort

Starts with the left item, compare it with the next item nearest, swap if one item is lower than another, repeat for other items, this is the first pass.

Repeat in second pass until all items are in order.

Merge sort

Divide list into two, continue dividing mini lists until there is 1 item in each list.

Merge each list and order them until there is only one fully merged list remaining.

Merge sort is faster than bubble sort.