Other pages in this set

Page 2

Preview of page 2

Here's a taster:

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 of an operating system
4.2 Operating system classification
(Read on Device, SMARTPHONES and Personal digital ASSISTANTS) on page 145+
6.0 Communications and networking
Communication methods
Asynchronous serial data transmission
6.…read more

Page 3

Preview of page 3

Here's a taster:

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 standard interface.
So what exactly is it that needs to be hidden or kept secret? It is the internal design of such system ­
how they operate that is kept secret for a very obvious reason.…read more

Page 4

Preview of page 4

Page 5

Preview of page 5

Here's a taster:

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 ideas and can solve the
problem with dramatically different speeds.…read more

Page 6

Preview of page 6

Here's a taster:

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 is doubled then the order of
growth of the problem is quadratic.
Exponential growth is used to
measure problems which grow very
quickly.…read more

Page 7

Preview of page 7

Here's a taster:

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
time algorithm that executes in O(n)
Finite state machines are used
extensively in applications in
computer science.…read more

Page 8

Preview of page 8

Here's a taster:

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 of a state must be unique
Nondeterministic FSM: an FSM that may have several possible next state for each pair of state and
input symbol.…read more

Page 9

Preview of page 9

Here's a taster:

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 set of input symbols (input symbol alphabet); if it produces an output, it has a
set of output symbols (output symbol alphabet)
3.…read more

Page 10

Preview of page 10

Here's a taster:

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 reasonable (polynomial) time solution has yet been
Heuristic: describes an approach that uses knowhow and experience to make informed guesses that
assist in finding a polynomial time solution to an intractable algorithmic problem.…read more


No comments have yet been made

Similar Computing resources:

See all Computing resources »See all resources »