Questions on Algorithms

1. What are the complexities of some famous algorithms?

Ans: Some famous algorithms are:

i) Binary Search : O(log n)

ii) Merge Sort : O(n log n)

iii) Insertion Sort : O(n * n)

iv) Quick Sort : O(n log n)

v) Selection Sort : O(n * n)

2. What are the most important types of algorithms?

Ans: There are five important basic designs for algorithms.

i) Divide and Conquer: This is top-down technique for designing algorithms that consists dividing the problem into smaller sub-problems that are similar to the original problem but smaller in size, solve the sub-problems recursively and then combine these solutions to create a solution to the original problem. An example of this approach is "binary search".

ii) Greedy Method: The greedy method suggests that one can devise an algorithm that works in stages, considering on input at a time. At each stage, a decision is made regarding whether a particular input is an optimal solution. An example of this approach is "knapsack problem". Greedy algorithms attempt not only to find a solution, but to find the idle solution to any given problem.

iii) Dynamic Programming: This can be used when the solution to a given problem can be viewed as the result of a sequences of decisions. An example of this approach is "multi stage graph". This class remembers older results and attempts to use this to speed the process of finding new results.

iv) Back Tracking: If we reach a dead-end, we use the stack to pop-off the dead end and try something else we had not tried before. An example of this approach is "8-queens problem". Back tracking tests a solution, if one is found the algorithm has solved, if not it recurs once and tests again, continuing until a solution is found.

v) Branch and Bound: This algorithm form a tree of sub-problems to the primary problem, following each branch until it is either solved or lumped in with another branch.

Questions on Compiling and Linking

1. What is meant by compiling and linking?

Ans: Creating an executable is a multistage process divided into two components.

Compiling: This refers to the processing of source code files (.c or .cpp) and the creation of an object file. This step doesn't create executable file. Instead, the compiler produces the machine language instructions that corresponding to the source file that was compiled. For example, you we compile three source files then we will have three object files created as output, each with name .o .

Linking: This refers to the creation of single executable file from multiple object files. In this step, it is common that the linker will complain about undefined functions. During compilation, if the compiler couldn't find the definition for a particular function, it would just assume that the function was defined in another file. Compiler doest look one file at a time. On other hand, the linker may look multiple files and try to find references for the functions that weren't mentioned.

Compiler errors are usually syntactic in nature -- a missing semicolon, an extra parenthesis. Linking errors usually have to do with missing or multiple declarations.

2. What are the steps of compilation?

Ans: Following are the steps that compiler does:

i) Lexical Analysis

ii) Syntactic Analysis

iii) Semantic Analysis

iv) Pre-Optimization of internal representation

v) Code Generation

vi) Post Optimization

3. What is static linkage and dynamic linkage?

Ans: If every program uses the standard C library, it means the each program would normally have a unique copy of that particular library present within it. This leads wasted of resources, degrade the efficiency and performance. Since C library is common, it is better to have each program reference the common one instance of the library, instead if having each program contain a copy of the library.

This implementation during the linking process where some objects are linked during the link time(static linkage) whereas some done during the run time(dynamci linkage).

Static Linkage: Static linkage means the the program and the particular library are combined together by the linker at link time. Programs that are linked statically are linked against archives of objects(libraries) that typically have the extension of .a.

For gcc, the -static option can be used during the compilation/linking of the program.

gcc -static filename.c -o filename

The drawback of this technique is that the executable is quite big in size.

Dynamic Linkage: Dynamic linkage means that the program and the particular library are not combined together at link time. Instead, the linker places information to the executable that tells the loader which shared object module the code is in and which run time linker should be used to find and bind the references. This means that the binding between the program and the shared object is done at run time that is before the program starts, the appropriate shared objects are found and bound. Programs that are linked dynamically that typically have the extension of .so.

4. What are the types of linkages?

Ans: The linkage determines whether identifiers that have identical names refers to the same object, function. The linkage of an identifier depends on how it was declared. There are three types of linkages:

i) Internal Linkage: Identifiers can only be seen within a translation unit(file). Ex: static

ii) External Linkage: Identifiers can be seen in other translation units(files). Ex: extern

iii) No Linkage: Identifiers can only be seen in the scope in which they are defined.