Concepts Archives - Page 12 of 14

Decidability of Languages 6

Apr

4

2013

Click the below image to view it in readable form

Closure Properties of Languages

Apr

4

2013

Click the above image to view it in readable form

Types of Delays 1. Nodal processing delay 2. Queuing delay 3. Transmission delay 4. Propagation delay (1-2)Processing delay a. The time required to examine the packets header and determine where to direct the packet. b. Other factors include, the time needed to check for bit level errors in the packet that occurred in transmitting the ...

Theory of Automata

Apr

4

2013

Definition of Automaton: An Automaton is a “self-acting” system that operates on a set of input symbols (one at a time) and decides whether or not to accept the given input sequence. Sometimes it may optionally produce some output sequence as well. Formally an Automaton may be defined to consist of the following: 1. Input: A ...

The Havel Hakimi Algorithm 3

Apr

4

2013

The Havel Hakimi algorithm gives a systematic approach to answer the question of determining whether it is possible to construct a simple graph from a given degree sequence. Take as input a degree sequence S and determine if that sequence is graphical That is, can we produce a graph with that degree sequence? ...

Tech Jargon

Apr

4

2013

Words Explanation Context A context is the contents of a CPU’s registers and program counter at any point in time. Process A process (also sometimes referred to as a task) is an executing/ running instance of a program. Threads Threads are lightweight processes that can run in parallel and share an address space (i.e., a ...

TCP Congestion control algorithm 1

Apr

4

2013

Re-transmissions, Timeouts and Duplicate Acknowledgements TCP is relegated to rely mostly upon implicit signals it learns from the network and remote host. TCP must make an educated guess as to the state of network and trust the information from the remote host in order to control the rate of data flow. A sender’s implicit ...

Spanning Trees

Apr

4

2013

Let G = (V, E) be a connected graph in which each edge (u, v) E has an associated cost C(u, v). A Spanning Tree for G is a subgraph of G that it is a free tree connecting all vertices in V. The cost of a spanning tree is the sum of costs on its edges. Minimum Spanning Tree An MST of G is a spanning tree of G having a minimum cost. ...

Serializability

Apr

4

2013

Basic Assumption – Each transaction preserves database consistency Thus, serial execution of set of transactions preserves database consistency. A (possibly concurrent) schedule is serializable if it os equivalent to serial schedule (say, Transaction T1 follows Transaction T2 or T2 follows T1) Different form of schedule equivalence gives rise to the notions of 1. ...

Recoverable and Cascadeless Schedules 36

Apr

4

2013

Recoverability A recoverable schedule is one where, for each pair of Transaction Ti and Tj such that Tj reads data item previously written by Ti the commit operation of Ti appears before the commit operation Tj . Suppose that the system allows T9 to commit immediately after execution of read(A) instruction.Thus T9 commit before T8 does. Now suppose that T8 fails ...