Hey guys, thought i should share the notes i made for comp3. 
Enjoy and make sure you use other resources also to revise!

Good Luck!

Word Document 4.21 Mb

Pages in this set

Page 1

Preview of page 1


Page 2

Preview of page 2
1.1 Problem SOLVING: Information hiding and Abstraction
Data representation
1.2 Comparing alogirthms
1.3 Finite state machines
Types of FSM
1.4 Turing machines(Read book)
1.5 Intractable problems(read book)
1.6 regular expressions, BNF and RPN
2.0 Programming Concepts
3.1 Real Numbers
Formats of floatingpoint numbers
4.0 Operating system
4.1 Role…

Page 3

Preview of page 3
Interface: a boundary between the implementation of a system and the world that uses it.
It provides an abstraction of the entity behind the boundary thus separating the methods of eternal
communication from internal operation.

Information hiding means hiding design details behind a…

Page 4

Preview of page 4
to the pigeonhole with their number of hairs on t, there must be at least wo people with the same
number of hairs on their head "

Representation abstraction is applied to problem solving. It is also known as problem abstraction or
reduction. Details are removed until it…

Page 5

Preview of page 5
Different problems may solve the same problems;

Each step in any algorithm must be unambiguous.
The range of inputs for which an algorithm works has to be specified carefully.
Several algorithms for solving the same problem may exist
Algorithms for the same problem can be based on a very different…

Page 6

Preview of page 6

Order of growth: assesses by what
factor execution time increases when
the size of the input in increased.
A problem has a linear order of growth
when an algorithm takes twice as long
to run if the input is doubled. If the
execution time increases by 4 when
the input…

Page 7

Preview of page 7
Exponential growth: growth that has the form k(^n).
Exponential time algorithm: an algorithm whose execution grows exponentially with input size.

Polynomial growth: a growth that has the form n(^k),
Polynomial time algorithm: an algorithm those execution time grown as a polynomial of input size

Linear time algorithm: a polynomial

Page 8

Preview of page 8

Transition Function : maps (input symbol, current state) to (output system, next state).
Transition table: tabulates that mappings (input symbol, current state) to (output symbol,
next state).

Deterministic finite state machine: an FSM that has just one next state for each pair of state and
input symbol. Each outgoing transition…

Page 9

Preview of page 9

1. FSMs can be used to control traffic lights, as recognizer that specify a language and check if a
given string is in the language, to search for words in a large piece of text, and for party
2. An FSM has a…

Page 10

Preview of page 10
Decision problem: A yes/no algorithmic problem.

Decidable: a decision problem that has a yes/no answer.

Undecidable: describes a decision type algorithmic problem that is noncomputable.

Tractable: describes a problem that has a reasonable (polynomial) time solution as the size of the
input increases.

Intractable: describes a problem for which no…




this is for the old spec (2510)

Similar Computing resources:

See all Computing resources »