Short Notes on Computer Science topics

For page specific messages
For page author info

These are single line facts on the various topic of Computer Science. Might be useful for revision.

Computer Networks

  • Protocols are agreements on how communication components and DTE's are to communicate.
  • Simplex Communication in one direction.
  • Half duplex communication in both directions but only in one direction at a time.
  • Full duplex communication in both direction simultaneously.
  • Error detection at data link layer is achieved by "cyclic redundancy codes" (CRC).
  • Example of Network Layer protocol:- 
    Internet Protocol (IP) - ARPANET 
    X.25 packet level protocol (PLP) - ISO
    Source routing & domain naming using USENET
  • Mesh topology has the highest reliability. 
  • Baud means the rate at which the signal changes.
  • Start and stop bits are used in serial communication for "Synchronization".
  • "Baseband signals" are the unmodulated signal coming from a transmitter. 
  • Manchester line encoding is a "non return to zero code" & "Unipolar code".
  • A switched circuit is a dial-up circuit that may encounter blockage (busy signal).
  • Pertain to error transmission used in continuous ARQ method.
  • Selective Repeat involves complex login than Go-back-N.
  • Selective Repeat has better line utilization.
  • In carrier sense network, if the prevailing condition is a "channel busy" then,
    If technique used is non-persistent then it results in randomized wait and sense.
    If technique used is 1-persistent then the channel continually sensed.
  • Non-polling system:- TDMA, Xon/Xoff
  • Carrier sense and Token passing systems that can be used in both priority and non-priority modes.
  • BSC is a character-oriented protocol, half-duplex protocol.     
  • HDLC --> Bit-oriented and code transparent.
  • Bit stuffing refers to inserting '0' (zero) in user data stream to differentiate it with the flag.
  • Baseband uses analog technology.
  • Broadband uses digital technology.
  • The adaptive and dynamic directory used in packet routing changes within each user session and at system generation time only. Example:- TYMNET and ARPANET.
  • The method of network routing where every possible path between transmitting and receiving DTE is used is called directory routing.
  • MultiPlexer vs Statistical Multiplexer
    Uses TDMUses FDM
    Waste Output link CapacityOptimize output link capacity
    Don't need buffersneed buffers
  • Flooding --> A type of isolated routing.
    A method in which every incoming packet is sent out on every outgoing line except the one by which it arrived.
  • Selective flooding is a type in which the packets are sent to those lines that are going approximately in the right direction.
  • Resilience parameter which gives the probability of the transport layer itself spontaneously terminating a connection due to internal problems.
  • The Residual error rate measures the number of lost or garbled messages as a fraction of the total sent in the sampling period.
  • In session layer, during data transfer, the data stream responsible for the control purpose (i.e. control of the session layer itself) is "capability data".
  • DNS uses the UDP as the transport protocol.
  • The address of a class B host is to be split into subnets with a 6 - bit subnet number. Then, maximum number of subnets = 26 -2 =62 and maximum number of hosts = 210 - 2 = 1022.

Computer Graphics

Subdivision method of clipping, DDA Algorithm and Clipping algorithm of Cohen and Sutherland using region codes, Sutherland-Hodgman algorithm for polygon clipping.

  • A perspective projection produces "realistic view".
  • A parallel projection preserves "realistic dimension".
  • Oblique projection with an angle of 450 to the horizontal plane is called "cavalier projection".
  • Random-scan monitors draw a picture one line at the time.
  • The perspective anomaly in which the object behind the center of projection is projected upside down and backward onto the view plane is called as "view confusion".
  • Beam penetration for producing color display is used with random-scan monitors.
  • The phenomenon of having a continuous glow of beam on the screen even after it is removed is called as "Phosphorescences".
  • A CRT with raster scan monitor is best suited for CAD system.
  • When the computer is not able to maintain operation and display, bright slots occur in the screen is called "snowing".
  • "Depth buffer", "Scan line", "Depth sort hidden" surface methods employ image space approach except back face removal.
  • The "anti-aliasing" technique which allows the shift of 1/4, 1/2 and 3/4 of a pixel diameter enabling a closer path of aline is "pixelPhasing".
  • The subcategories of orthographic projection are isometric, dimetric, trimetric.
  • The clarity of a displayed image depends on the resolution, floating point precision of the system and associated software.
  • In multiple "transformation" following are communicative:-  
    Successive transformation of the same kind.
    Uniform scaling and rotation.
  • In raster scan for transformation, a 900 rotation can be performed by copying each row of the block into a column in the new frame buffer location.
  • Random scan monitors are also referred as "Vector Display", "Stroke Writing Display" and "Calligraphic Display".
  • Picture start flickering below the refresh rate of 25.
  • When several types of O/P devices are available in graphic installation, it is convenient to use "bundle attributes".
  • Raster systems display a picture from the definition in a "frame buffer".
  • Backface removal is an example of object space method.
  • Basic ray tracing technique: 
    Rays are cast from the eyepoint through every pixel on the screen.
    Viewing transformations are not applied to the scene prior to rendering.
    Removes hidden surfaces (Best for non polygon, nonplanar surface).
  • The hue of the color is related to its wavelength.
  • The best-hidden surface removal algorithm depends on the application.
  • Engineering drawing commonly applies orthographic projection.
  • The basic elements of a picture in volume graphics are "Voxel".
  • "Vanishing point" is a point at which a set of projected parallel lines appears to converge.
  • A viewgraph is an oversized slide designed for presentation on an overhead projector. 

Software Engineering

Program Graph, Coupling and Cohesion, Cyclomatic Complexity, Cyclomatic Number

  • Good Software requirement specification (SRS) document has:-
    Functional Requirement 
    Non-Functional Requirement
    Goals of Implementations
  • Design phase includes:- Data, Architectural, Interface and procedural designs.
  • Data structure suitable for the application is discussed in "Data Design".
  • The design phase will usually be "top-down".
  • Assertions are conditions which are always true at the point of execution.
  • Assuming the existence of a start and end nodes for a program graph, the total no. of the path is equivalent to the minimum set of test data required to test the software.
  • Structured programming codes include sequencing, alteration, iteration.
  • Perfective maintenance takes the maximum chunk of the total maintenance effort in a typical life cycle of a software product.
  • Avoid goto statements, names variables and functions according to their use, modularize the program improve readability in coding.
  • The data flow model of an application mainly shows "processing requirement and flow of data".
  • Content coupling in a module is desirable.
  • Logical cohesion in a module is desirable.
  • Stamp coupling is preferred over functional coupling.
  • Configuration management is concerned with "Controlling changes to the source code", "Controlling documentation changes" and "maintaining versions of software".
  • The cyclomatic number of graph theory concept will be used in software testing.
  • The context diagram should depict the system as a single bubble.
  • External entities should be identified clearly at all levels of DFDs.
  • Control information should not be represented in a DFD.
  • The functional testing method is normally used as the acceptance test for a software system.
  • Software testing techniques are more effective if applied immediately after design.
  • In the object-oriented design of software, objects have "attributes, names, and operations".      

Principles of Compiler Design

  • CFG      --> Context-free grammar
  • DFSA    --> Deterministic finite state automata 
  • NDFSA  --> Non-deterministic finite state automata
  • Cross compiler is a compiler that runs on one machine and produces object code for another machine.  
  • In a compiler, keywords of a language are recognized during the lexical analysis of the programme.
  • A interpreter is prefered over a compiler when
    • the initial stage of programme development.
    • Debugging can be faster and easier.
  • The cost of developing compiler is proportional to 
    • the complexity of the source language.
    • the complexity of the architecture of the target machine. 
    • The flexibility of the available instruction set.
  • An ideal compiler should be 
    • be smaller in size
    • take less time for compilation
    • be written in the high level
    • produce object code that is smaller in size and executes faster.
  • In a compiler, the grouping of characters into token is done by the "lexical analyzer".
  • A given pattern constitutes a token or not depends on the source language.
  • A grammar will be meaningless if the terminal set and the non-terminal set are not disjoint.
  • A grammar will be meaningless if left-hand side of production is a single terminal, left-hand side of production has no non-terminal.   
  • In context free grammar, terminal symbols can't be present on the left-hand side of any production. 
  • CFG (Context Free Grammar) can be recognized by a "push-down automata" and "2-way linear bound automata".
  • CSG (Context Sensitive Grammar) can be recognized by "2-way linear bounded automata".
  • Sentence of a grammar should be derivable from the "start" state.
  • Sentence of grammar should be frontier of a derivation tree in which the root node has the "start" state as a label.
  • A grammar can have a non-terminal A that can't derive any string of terminals.
  • A grammar can have a non-terminal A that can be present in any sentential form.
  • A top-down parser generates left-most derivation.
  • A bottom-up parser generates right-most derivation in reverse.
  • A given grammar is said to be ambiguous if there is a sentence with more than one derivation tree corresponding to it.    

Automata Theory


  • 3NF is considered adequate for relational database design.
  • A functinal dependency of the form X $ \rightarrow $ Y is trivial if Y $\subseteq $ X.
  • In 3NF, every non-key attribute is functionally dependent on the primary key.
  • The column of a table is referred to as the attribute.
  • Every relation in BCNF is also in 3NF.
  • An index is clustered, if the data records of the file are organized in the same order as the data entries of the index.
  • A data model is a collection of conceptual tools for describing data, data relationship, data semantics and consistency constraints.
  • MAX, COUNT and SUM functions ignore NULL values.  

Operating System

Data Structures & Algorithms


MCQs in Computer Science by Timothy Williams, Fifth Edition.


Exclude node summary :