Computer Science G10 S1 (Unit 4 + Chapter 3)

Unit 4 : Computers and Chatper 3 (sorting and searching algorithms)

input

to enter data into a computer

process

to change the meaning or format of some data

output

to display or output data that has been processed or stored

function machine

a metaphor or diagram that represents a machine that takes an input. It applies a rule such as a set of operations and delivers the answer as an output

Sequential Computational Model

Breaks down a process into subtasks and processes the subtask one at a time, in order from start to finish.

Advantage of sequential model

Simple and easy to program

Disadvantage of sequential model

Limited, and not good for large projects (lack of scalability)

Parallel Computational Model

Breaks down a process into subtasks and processes the substasks at the same time. Multiple processing units work on completing the same task.

Advantages of parallel model

Increased performance, Scalability, More efficient use of resources

Disadvantages of parallel processing

Complex, Mork work involved coordinating, costly, less software compatability

Multi-agent Computational Model

Different independent agents work on different independent processes, cooperating and negotiating with each other.

Agent

A computer system that can interpret its environment through its sensors and act autonomously upon that environment

Advantages of multi-agent model

Distributing problem solving, Adaptability, Scalability, Redundancy, Decentralized control

Disadvantages of multi-agent model

Complex, Work involved in coordination, Time spent communicating between agents, security concerns

Von Neumann Architecture

computer design in which the program is stored in the memory with the data

CPU

hardware device that carries out the processing in a computer

Main Memory/ RAM

A temporary store for data and instructions (programs)

Bus

A group of connections between devices in a computer

fetch-decode-execute cycle

sequence of steps carried out repeatedly by a CPU

writing

when the CPU sends data to memory to be stored at a given address

reading

when the CPU retrieves the data stored at a given address

memory address

a number that uniquely identifies a memory storage location

What does the RAM do?

When a CPU stores data into memory, this is called writing. The CPU uses a bus to tell the memory what data to save and where to save it. The reverse process also occurs, called reading where the CPU specifies which part of the memory to read from.

volatile

memory that is erased when the power is turned off

non-volatile

memory that is not lost when the power is turned off

ROM

Memory that cannot be altered and is non-volatile, storing any programs that must run when the computer is first turned on (firmware).

Cache memory

Small, fast, expensive memory used to make up for the difference in speed between two internal components such as the CPU and RAM.

Cache miss

When the data requested for processing by a component or application is not found in the cache memory.

Microprocessor

The central unit that executes and manages the instructions passed to it (inside the CPU)

List the parts of the CPU

Control unit, ALU, Registers, Buses, Clock

Clock

an electronic device in a CPU that 'ticks' at regular intervals and is used to synchronize the actions of the other parts of the CPU

GHz (gigahertz)

a measure of frequency equivalent to 1000 million cycles per second

Control unit

Decodes instructions and executes them

ALU (arithmetic logic unit)

Does math involved in a program

Registers

Fast memory locations in the CPU

Bus width

The number of wires that make up a bus, determining the range of binary numbers that can be communicated

Address bus

Carries memory location

Data bus

Carries values (data)

Control bus

Carries the signal for what to do

List all the registers in the CPU

PC (program counter), MAR (memory address register), MDR (memory data register), CIR (current instruction register), ACC (accumulator)

PC (program counter)

Holds the memory address for the next instruction

MAR (memory address register)

Stores the address of the location currently being written to or read from

MDR (memory data register)/ MBR (memory buffer register)

Stores data that was just read/fetched or is about to be written

CIR (current instruction register)

Holds the memory address for the current instruction

ACC (accumulator)

Holds the value of calculations

Describe the steps in the 'fetch' part of the fetch-decode-execute cycle

1. The memory address of the instruction we need to fetch is in the PC. This memory address is copied from the PC to the MAR via address bus.
2. The memory address of the next instruction is sent along the address bus to the main memory.
3. The instruction at that memory location is copied to the MDR via the data bus.
4. The data is copied to the CIR (so that the MDR is free to be used to store other data during execution)
5. The control unit sends a signal via the control bus to the PC to increment.

Describe what happens in the 'decode' part of the fetch-decode-execute cycle

The control unit decodes the instruction in the CIR to an opcode (the instruction) and operand (the actual value).

Describe what happens in the 'execute' part of the fetch-decode-execute cycle

The opcode is performed upon the operand, where the ALU may be involved. The results are stored in the ACC and possibly send back to the main memory.

Virtual memory

If there is no free memory, the memory manager will swap out some of the data stored in the RAM to an area on the hard disk drive (usually the least recent data) and then the requested data is now swapped in to the free area.

Disadvantages of using virtual memory

1. The read/write speed of a hard disk drive is much slower than of RAM
2. Significant drop in performance
3. Disk thrashing slows down the rate execution of the program

Disk thrashing

a very high rate of hard disk access

List the factors that affect CPU Performance

Clock speed, number of processor cores, size of cache, RAM

How does clocks speed affect processing speed? (3 points)

1. Faster clocks speeds mean more cycles per second, therefore leads to a greater processing speed.
2. However, sometimes the clock speed may be greater than instructions can be processed by transistors.
3. A higher clock speed also requires cooling systems to avoid it from breaking or melting.

How does the number of processor cores affect processing speed?

Each core has its own control unit and ALU, so more cores would increase processing speed, as it enables parallel processing and multitasking. However, not all programs can be run in parallel; some may require sequential processing, so more cores wouldn't increase speed.

How does the size of cache affect processing speed?

The main memory is slower than the CPU, so a larger cache size may allow data to be more quickly accessed or written by the CPU as fewer FDE cycles are required to retrieve data from memory.

static RAM (SRAM)

memory that retains data bits in its memory as long as power is being supplied and does not have to be refreshed

List the disadvantages of cache memory (4 points)

1. Increasing cache size has diminishing returns
2. Cache misses
3. Cache is more expensive than RAM
4. Cache generates more heat than RAM

How does the size of RAM affect CPU performance?

Larger RAM improved processing speeds by reducing the need for virtual memory.

Secondary storage

any kind of permanent storage to which the contents of ROM/RAM are copied (usually a hard disk, optical or solid-state device)

Magnetic storage

secondary storage that works by making parts of a substance behave like a magnet, with north and south poles to represent 0s and 1s

Explain how magnetic storage works

Inside a hard disk drive is a stack of disks called platters with magnetic coating on each surface. When data is read, the arm moves across to be above the right track, and the required sector comes around under the head. The surface behaving like a magnet causes a tiny current in the head, where the disk controller translates this into 1s and 0s. To write data, the arm magnetizes and demagnetizes the section of the disk spinning under it.

platters

rigid, rapidly rotating, magnetically coated disks within a hard disk drive

latency

refers to any kind of delay that data travelling through a network might encounter

Advantages of using magnetic secondary storage

Cheap, high capacity, reliable

Disadvantages of using magnetic secondary storage

Susceptible to damage if dropped, latency due to moving parts, vulnerable to magnetic fields

What is magnetic storage best for?

Devices that process a lot of data but are not moved. Long term storage due to their high reliability.

Optical storage

Secondary storage that works using differences in light reflection from a material

Explain how optical storage works

1. A disk contains pits and lands which are stored in the long spiral tracks on a disk
2. The optical drive uses a laser to reflect light off the surface of the disk
3. When the laser beam hits the curved start or end of a pit, the light is reflected and a 1 is recorded. Where the light is reflected from the flat bottom of a pit, or from an area with no pit (a land), a 0 is recorded

When writing, a laser heats the recording material, creating reflective pits on the surface of the disk. This is slow because the heating and cooling of the surface takes time.

Advantages of using optical storage

Portable, reliable if cared properly

Disadvantages of optical storage

Slow access to data, can be easily scratched or damaged

What is optical storage best for?

Distributing high quality video or audio, storing backups of data

solid-state storage

Secondary storage that works by storing charge (electrons)

Explain how solid-state storage works

Solid state storage consists of billions of transistors that fit on a chip, that pool electrons. To read data, control signals apply a small voltage onto a specific bit and a 1 is read out if the pool is empty whereas a 0 is read out if the pool if full. To write data, a bit is found and a high voltage is applied to pull electrons into pools, creating 0s or 1s. Because of the voltage applied solid-state storage can only be rewritten around 1 million times before failing.

Advantages of using solid-state storage

Fast, durable (robust), portable, not much electricity needed

Disadvantages of using solid-state storage

Expensive, reading and writing break down chip

What is solid-state storage best for?

Being portable, and transferring small amounts of data between devices

cloud storage

secondary storage, often belonging to a third party, that is accessed via a network, usually the Internet, and so is not in the same physical place as the machine's main memory. Files stored 'in the cloud' can be accessed anywhere via an Internet connection

Virtualisation

any process that hides the true physical nature of a computing resource, making it look different, usually to simplify the way it is accessed

Explain how cloud storage works

When files and data are sent to the cloud, they are actually being sent to server(s) connected to the internet. The cloud company maintains and manages the facilities (servers and the network) the cloud company needs.

Advantages of cloud storage

Data accessed from anywhere with an internet connection.
You can view data on multiple devices without transferring.
Cloud storage manages security and backup.
Additional storage accessed without physical components

Disadvantages of cloud storage

Vulnerable to hackers
Requires internet connection
Reliant on third party

What is cloud storage best for?

Large organizations that need to access large amounts of data across multiple devices

Embedded system

An embedded system is one that is designed to do a specific job, part of a bigger system.

How are embedded systems different from general purpose computers?

Cheap, low-power, simple technology, limited memory

Internet of Things (IoT)

the interconnection of digital devices embedded in everyday objects

peripherals

Input and output devices of a computer

bubble sort

Algorithm that starts at one end of the list and compares pairs of data items, swapping ones that are in wrong order until 1 transversal is completed. This process is repeated until there have been no swaps in a pass.

merge sort

Sorting algorithm that divides a list into two smaller lists and divides these until the size of each list is one. Then, by repeatedly combining lists and sorting each item in the list, the list eventually becomes sorted.

recursion

a process that is repeated until a condition is met

brute force

an algorithm design that does not include any techniques to improve performance, but instead relies on computing power to try all possibilities until the solution to a problem is found

divide and conquer

an algorithm design that works by dividing a problem into smaller and smaller sub-problems, until they are easy to resolve. The solutions to these are then combined to give a solution to the complete problem

bubble sort vs merge sort (about bubble sort)

much slower, uses less memory, simple and easy to code

bubble sort vs merge sort (about merge sort)

much faster, more complex to code and debug, uses more memory as many lists are created

linear search

Simple algorithm that checks each item in the list from start to end until the target is found. (brute force)

binary search

Uses ‘divide and conquer’ method to search the median item of a list, then reduce the size of the list to the searched by eliminating items too high/low.

linear search vs binary search (about linear search)

sorts both sorted and unsorted, much slower, easier to program

worst case scenario for linear search

target item is last, item not in list

linear search vs binary search (about binar search)

only works on sorted list, much faster, more complex to code and debug

worst case scenario for binary search

n items are searched if list length 2^n

API (application programming interface)

code that allows two programs to communicate with each other