COMP 3

Get Started. It's Free
COMP 3

4. Problem Solving

4.1. Info Hiding and Abstraction

4.1.1. Interface

4.1.2. Abstraction

4.1.3. Data Representation

4.2. Comparing Algorithms

4.2.1. Algorithms

4.2.1.1. (Series of unambiguous instructions)

4.2.2. Computational complexity of an algorithm

4.2.3. Time Complexity Of An Algorithm

4.2.4. Space Complexity Of An Algorithm

4.2.5. Order Of Growth

4.2.6. Asymptotic Behaviour

4.2.7. Order Of Complexity

4.2.7.1. Exponential Growth

4.2.7.1.1. Formula: k^n

4.2.7.2. Exponential Time Algorithm

4.2.7.3. Polynomial Growth

4.2.7.3.1. Formula: n^k

4.2.7.4. Polynomial Time Algorithm

4.2.7.5. Linear Time Algorithm

4.2.7.5.1. Formula: O(n)

4.3. Finite State Machines

4.3.1. FSMs and FSAs Are represented by State Transition Diagrams.

4.3.1.1. FSM: Can produce outputs whilst processing; Output based on the inputs and/or change of states.

4.3.1.1.1. Example Uses: - Spell checking - Grammar checking - Recognizing Speech

4.3.1.2. FSA: Does not output while processing. Solves Yes / No problems.

4.3.1.2.1. Deterministic FSA: All transition criteria must be unique and link only to 1 state.

4.3.1.2.2. Non-Deterministic FSA: Same Criteria can lead to multiple new states.

4.4. Turing Machines

4.4.1. It is a finite state machine that controls one or more tapes where at least one of the tape is of unbounded length.

4.4.3. Transition Diagram

4.4.4. Transition Rules

4.4.4.1. Transition Function(current state, input symbol)= (next state, output symbol, movement)

4.4.5. Equivalent Turing Machines

4.4.6. Power Of A Turing Machine

4.4.7. Universal Turing Machine

4.4.8. Interpreter

4.4.9. Principle Of Universitality

4.5. Intractable Problems

4.5.1. Non-Computable

4.5.2. Decision Problem

4.5.3. Decidable/Undecidable

4.5.4. Tractable

4.5.4.1. Has reasonable time solution as the size of input increase

4.5.5. Intractable

4.5.5.1. Describes a problem which has no reasonable time solution

4.6. Regular Expressions

4.6.1. Notation.

4.6.1.1. X* = Zero or more of X. X+ = One or more of X. XX? = X or XX. X | Y = X or Y.

5. Programming concepts

5.1. Recursion

5.1.1. The mechanism of recursive routines

5.1.2. Writing a recursive routine

5.1.3. The Tower of Hanoi

5.2. Lists and Pointers

5.2.1. Abstract data types

5.2.2. Linear Lists

5.2.4. Use of free memory, the heap and pointers

5.3.1. Stacks

5.3.2. Queues

5.4. Graphs and Trees

5.4.1. Graphs

5.4.1.1. Labelled graph

5.4.1.2. Directed graph

5.4.1.3. Data representation of a graph

5.4.1.4. Directed/Undirected graph

5.4.1.5. Connectivity

5.4.1.6. Path

6. Real numbers

6.1. Floating point numbers

6.1.1. Precision

6.1.2. Errors

6.1.2.1. Rounding errors

6.1.2.2. Absolute errors

6.1.2.3. Relative error

6.1.2.4. Cancellation error

6.1.2.5. Underflow

6.1.2.6. Overflow

6.1.3. Normalisation

7. Operating systems

7.1. types of operating system

7.1.1. Interactive

7.1.2. Network

7.1.3. Real Time

7.1.4. Device

7.1.5. Embedded

7.1.6. Desktop

7.1.7. Server

7.2. Role of OS

7.2.1. To hide the complexities of hardware from user.

7.2.1.1. Provide Interfaces such as GUI and can also provide virtual machine

7.2.2. Manage resources.

7.2.2.1. Hard to make OS flexible enough to run hardware produced by different manufacturers

7.2.2.1.1. Embedded systems do not require an operating system as they have a very simple function of being controllers.

7.2.2.2. allocation of processor time

7.2.2.3. allocation of hard drive space (storage locations)

7.2.2.4. Controls input/output devices

7.2.2.5. Deals with data file management

7.2.3. Manage software

7.3. Virtual Machine

7.3.1. Application Programming Interface

7.3.2. The apparent machine that the OS presents to the user, achieved by hiding the hardware behind layers of operating system software.

7.4. User Interface

7.4.1. Command Line

7.4.2. Graphical user interface

9. Communication & networking

9.1.1. ring

9.1.2. bus

9.1.3. star

9.1.4. Mesh

9.1.5. hybrid

9.3. security

9.3.1. threat

9.3.2. protection

9.4.1. Gateway

9.4.2. Switch

9.4.3. Router

9.4.4. Hub

9.5. Data Transmission

9.5.1. movement of data from one place to another

9.5.2. Occurs between a transmitter and receiver over a transmission medium

9.5.3. connection between transmitter and receiver is called communication channel

9.5.4. transmission media

9.5.4.1. Guided

9.5.4.1.1. electromagnetic wave, guided along a physical path such as twisted pair, coaxial cables and fiber optic.

9.5.4.2. ungided

9.5.4.2.1. electromagnetic wave are transmitted through vacuums, solids, liquids and gases using methods such as radio waves or microwave.

9.6. serial data transmission

9.6.1. single bits are