IB Computer Science SL Unit 4

Variable & Constants

Variables are unique identifiers that retrieve values from the memory addresses at which they are stored

The value of a variable can change while value of a constant does not change during program execution

What is a sub procedure?

A sub-program is a named section of code that performs a specific task and can be called by the identifier when needed; without knowing the details (of code and data structures) users can access this information as these are wrapped/hidden within the sub-program

Benefits of Subprograms?

Sub-programs contain reusable code (for use in other programs)

A large programming project can be divided into sub-programs

Different sub-programs can be constructed by different programmers

Future maintenance is easier due to the organization of the large program (into sub-programs)

Types of loops?

Post condition/Pre condition are constraints the loop, and before and at the end

Established conditions may also need exceptions or further considerations.

What is Concurrent processing?

Concurrent processing is a computing model/system in which multiple processors execute instructions simultaneously or different stages (of programming) run simultaneously (rather than consecutively);

this decreases product development time / and decreases the time to market; leading to improved productivity/reduced costs; however, it requires more resources/more software developers;

Sequential Search

Sequential search also known as linear search is an algorithmn to find an item in a list.

It starts at the first element and compares it to each element to the ones its looking for until find

Binary Search

Binary sort is an algorithmn to find an item in an already sorted list.

It compares the value it is looking for with the middle value and eliminates the lower/upper half depending on the result of the comparison

Sorting Algorithm?

A sorting algorithm is a method for reorganizing a number of items;

into a specific order (such as alphabetical order, highest-to-lowest value);

Bubble Sort

A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order, to sort the list in ascending/descending order. This process is repeated until no swaps came be made.

Selection Sort

A sort algorithm that repeatedly scans for the smallest item in the list and swaps it with the element at the current index. The index is then incremented, and the process repeats until the last two elements are sorted.

Possible Tests?

Normal data that would be accepted as it is within the required range(meets the requirements) and produces expected results. Test for correct data types (e.g. currency, integer, floating point)

extreme - Extreme data is the largest/smallest acceptable value

boundary - Boundary data is the largest/smallest acceptable value and the corresponding smallest/largest rejected value; test for valid ranges and boundary conditions

abnormal - erroneous data, data that should be rejected by the algorithm

Types of errors?

syntax errors: mistakes in the grammar of your coderuntime error: errors detected when your program runs such as erroneous user inputlogic error: errors that allow the code to run correctly but with an unexpected or incorrect output

Flowchart symbols

Oval - Begin or end

Rectangle - Process

Parrelelogram - Input/Output

Diamond - Decision

Arrow - Direction of Flow

Input devices

When you transfer data from the source in the outside world to the computer

Process

The program being executed.

Output devices

When you take data produced by a computer and turn it into a human-readable form (such as an image on a screen)

What is Complexity?

complexity of an algorithmn, is a measure of the amount of time and space requried by algorithmn for an input of a given size

we can review these by worst case, best case, rarely use the best case

What do we measure when measuring effciency?

Algorithm efficiency refers to the resources required by an algorithm, typically measured in time and space complexity. Efficient algorithms can handle larger datasets and perform operations faster, improving software application performance.

Methods to improve efficiency:

1. Use of loops: To remove the necessity to process extra lines of code

2. Use of arrays/data structures ; So data can be stored/re-used/re-ente

basic loop complexity?

A single loop that repeats n times takes n time to run

A nested loop that repeats n times takes n x n times to run

conditional loop on runs the minimum number of times required

What are effects a programs effciency?

1. Computer used; the hardware

2. representation of abstract data types

3. effciency of compiler

4. competence of programmer

5. complexity of algorithm

6. Input size

What is Big O notation?

Big O notation is used in Computer Science to describe the performance or complexity of an algorithm in the worst-case scenario, and can be used to describe the execution time required or the space used (e.g. in memory or on disk) by an algorithm.

Rules of the Big O notation?

1. Focusing on the dominant term: Only the term with the largest growth rate is considered.

2. Ignoring constant factors: Multiplicative constants are ignored when determining the Big O complexity.

what is a iteration?

The number of times a step is performed in a algorithm.

Trace table/dry run?

Rules?

1. interation per row

What are the Fundamental operations of a computer?

The four most fundamental operations are:

ADD

COMPARE

RETRIEVE (sometimes called LOAD)

STORE (sometimes called SAVE)

fundamental operations?

These are operations that do not require the processor to go through a large number of sub operations to reach a result.

compound (complex) operations?

A compound operation is an operation that involves a number of stages/other operations. Think of it as a group of operations that combine together to form an operation.

Comparing Fundamental and compound operations?

Fundamental operation requires one machine instruction cycle/do not require the processor to go through many machine instruction cycles to reach a result

A compound operation is complex / it is an operation that involves a number of other operations to reach the result

For example, find the largest number in an array/ sort the array in ascending order etc.

What is High-level language?

It uses natural language so it is easier for humans to understand, has high abstraction by hiding system complexities, and is easier to develop (easier debugging, better readability); machine independent

What is low level language?

Low Level Languages are programming languages that sit close to a computer's instruction set and machine code.

What is assembly language?

Assembly is a low-level languague that is intended to communicate directly with the hardware; The code is written using mnemonics, abbreviated text commands such as LDA (Load), STO(Store

Assembler

Translates assembly language to machine code (mnemonics to binary)

Why use assembly code?

You can directly manipulate individual bits & bytes and hardware, control programs in embedded system and perform real time responses

Machine code?

Each different type of processor has its own set of machine code instructions; they execute tasks in binary. Only the language computers can directly understand, and it is harder to understand and debug. It is system specific.

Why do we need translators?

The program written in HLL must be translated into machine code so that the computer can execute the program;

as the computer only understands machine language / as code written in HLL can only be understood by humans and cannot be interpreted by the computers (which work in binary);

Compiler

Translates a high level language into a lower level language in a full batch; soucre code to object code, unless an error is discovered

also performs(Lexical analysis;Parsing;)

Interpreter

Translates a high level language into an intermediate code which will be immediately executed by the CPU (line by line), it checks for error after translating each line and displays where the error is

Interpreter Vs compiler

Compiler requires all errors to be corrected before running, interpreter allows you to execute some parts which may be beneficial for development

Compiler executes faster, interpreter takes longer

Once compiled object code can be transfered to other computers; interpreteurs are required to run the code

What is a collection?

A Collection is a framework/data structure to store and manipulate a group of objects; Collections provide built-in methods for common operations: (Adding/removing elements, storing, retrieving, and manipulating data).

Collections reduce programming effort/increase performance, because of these built-in methods optimize common operations

Standard collection operations

.addItem( data ) = add data item to the collection

.resetNext() = start at the beginning

.hasNext() → tells whether there is another item in the list .getNext() → retrieves a data item from the collection .isEmpty() → check whether collection is empty

Paramter & argument

PAR: A variable in a function definition that acts as a placeholder for input values.

ARG: The actual value passed to a function when it is called.

Conditional statement requirements?

test/condition;

action/consequence;

alternative action/consequence;

Advantages and Disadvantages of Linear vs Binary Search

1. Linear: Simple to implement, works on unsorted arrays, and is memory efficient. However, it is slow for large datasets, has O(n) time complexity, and is inefficient compared to other search algorithms.

2. Binary: More efficient on sorted arrays, faster search time with O(log) time compelxity. However requires sorted data, not suitable for datasets that frequently change, not suitable for small datasets because of sorting overhead.

Advantages and Disadvantages of Bubble vs Sequential Sort

1. Bubble sort: Easy to implement and stable, but has O(n^2) time complexity, making it inefficient for large datasets.

2. Sequential sort: Generally faster than bubble sort, works well with small arrays, but requires additional memory for storing data.

Linear Search Algorithm Logic

1. Start from the first element

2. Compare each element with the search value

3. If a match is found, return the index

4. If not found, return -1 or null

Binary Search Algorithm Logic

1. Find middle element If target = middle, return index

2. If target < middle, search left half

3. If target > middle, search right half

4. Repeat until found or subarray empty

Bubble Sort Algorithm Logic

1. Start with the first element (i=0).

2. Compare the current element (arr[j]) with the next element (arr[j+1]).

3. If arr[j] > arr[j+1], swap them.

4. Move to the next element (increment j), and repeat until end of array(j < n-i-1).

Sequential Search Algorithm Logic

1. Initialize i to 0 (the starting index)

2. While i is less than the length of the array:

- Set j to i (the current element index)

- Compare the element at arr[j] with the target value.

- If arr[j] equals the target, return j.

- Increment i by 1.

3. If no match is found after checking all elements, return a value indicating the target is not present.