Introduction To Algorithms

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. Algorithms need to be unambiguous, finite, feasible, independent and provide proper output in proper input. Algorithms are either incremental or divide and conquer type. Analysis of algorithms can be done for the worst case, average case or the best case. Complexity of algorithms are measured using theta, big-oh or big-omega notations.

Summary

Things to Remember

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output.
Algorithms need to be unambiguous, finite, feasible, independent and provide proper output in proper input.
Algorithms are either incremental or divide and conquer type.
Analysis of algorithms can be done for the worst case, average case or the best case.
Complexity of algorithms are measured using theta, big-oh or big-omega notations.

MCQs

No MCQs found.

Subjective Questions

Q1:

Write short notes on epithelial cells.

Type: Short Difficulty: Easy

Show/Hide Answer

Answer: <h3>CELLS AND TISSUE</h3>
<h4> Tissue</h4>
 The tissue is a group or layer (organization) of similarly specialized cells that together perform the certain special functions. OR the collection of cells that frequently have the similar morphological characteristics and functions.Tissue are formed by cells.Body organs are then formed by the functional grouping of the multiple tissues. The study of the tissue is known as Histology.
<h4>Types of Tissues</h4>
 Primarily there are four basic types of tissues, they are: 1. Epithelial Tissue 2. Connective Tissue 3. Muscle Tissue 4. Nervous Tissue
<h4> Function</h4>
<ul>
<li>Covers body surface,</li>
<li>lines body cavities</li>
<li>Binds and support body parts</li>
<li>Enables movement of structures within the body movement</li>
<li>Enables response to stimuli and coordinates bodily function</li>
</ul>
<h3> 1. Epithelial Tissue</h3>
 Epithelial tissue is the outer covering cells that it covers the outside of the body and lines of organs, vessels blood and lymph) and body cavities.Epithelial tissue is made up of epithelial cells, which are vastly different from muscle cells. In addition, the principal function of epithelial tissue is protective function and covering(e.g skin), specialized to function in secretion(e.g epithelial cells of glands) and absorption(e.g intestine).The skin is an organ made up of epithelial tissue which protects the body from dirt, dust, bacteria and other microbes that may be harmful. There are other functions of epithelial tissue: 1. Epithelial tissue helps to protect organs from microorganisms, injury, and fluid loss. 2. It helps in the absorption of water and nutrient. 3. It helps in elimination of waste. 4. It helps in the secretion of enzymes and /or hormones in the form of glands.
<h4> Classification of Epithelial Tissue</h4>
 Epithelia are commonly classified based on the shape of the cells on the free surface, as well as the number of cell layers.
 1. By the shape of cells
<ul>
<li>Squamous epithelial</li>
<li>Cuboidal/Cubical epithelial</li>
<li>Columnar epithelial</li>
<li>Ciliated epithelial</li>
</ul>
 2. Number of cells layer
<ul>
<li>Simple epithelial tissue</li>
<li>Simple squamous epithelial</li>
<li>Simple cuboidal epithelial</li>
<li>Simple columnar epithelial/Nonciliated</li>
<li>Ciliated simple columnar epithelial</li>
<li>Stratified or compound epithelia</li>
<li>Stratified squamous epithelial</li>
<li>Transitional epithelial</li>
<li>Stratified columnar epithelial</li>
<li>Stratified cuboidal epithelial</li>
</ul>
 
<h4>Simple Epithelial Cells</h4>
 It contains the single layer of cells(found where absorption,secretion, and filtration takes place). • Squamous epithelial-It is composed of the single layer of flattened cells and close fitting.They are found where filtration takes place(kidney and lungs).Its main function is to provide a thin, smooth and inactive lining to the heart, the blood vessels and the alveoli and the lymph nodes. • Cuboidal epithelial-It is cube shaped cells and box shape cells( having same height and width) fitting closely together lying on the basement membrane.Functions include secretion and absorption (located in small ducts of glands and kidney tubules)
 
• Columnar epithelial-
It is a single layer of tall,closely packed cells that line the digestive tract from the stomach to the rectum. It is rectangular in shape with cylindrical in the basement. Functions include absorption and secretion.
• Ciliated epithelial-
It is a single layer columnar cells which have fine hair like process, known as cilia.The cilia contain microtubules inside the plasma membrane that extends from the free border of columnar cells.It is found in the lining of uterine tubes where cilia propel ova towards the uterus and respiratory tract where they propel mucus towards the throat.
<ul>
<li>Stratified or compound epithelial</li>
</ul>
It contains multiple layers of cells. The superficial layers grow up from below and the basement membrane is usually absent. The main function of compound epithelial is to protect underlying structure. • Stratified squamous epithelial-
It is the most widespread stratified epithelia. It’s composed of several layers of cells of different shapes and is perfect for its protective role. In deep surface it is either columnar or cuboidal shape, grow towards the surface and become flattened. Stratified squamous forms the external part of the skin and extends into everybody opening that’s continuous with the skin.It can be divided into two according to its lining and they are: • The outer layer of the skin (epidermis) is keratinized (contains keratin, a protective protein. • Other stratified squamous in the body is non-keratinized.
 
 • Transitional epithelial-It is a type of tissue consisting of multiple layers of epithelial tissue which are composed of several layers of pear-shaped cells and is found in the lining of the urinary bladder, pelvis, kidney, and ureters and the superior urethra and gland ducts of the prostate. Stratified columnar epithelial-It is a type of epithelial tissue composed of column-shaped cells arranged in multiple layers.It is found in the ocular conjunctiva of the eye, in the parts of the pharynx and anus, the female's uterus, the male urethra, and vas deference,also found in lobular ducts in salivary glands.If forms the lining of the respiratory tract ,ureter, and oviduct etc.
 • Stratified cuboidal epithelial-It is a type of epithelial tissue composed of multiple layers of cube-shaped cells.It is made up of two or more layers of cells.It has several locations in the body: sweat gland ducts; egg-producing vesicles, or follicles, in the ovaries; and sperm-producing ducts, or seminiferous tubules, of the testis.It main function is sweat secretion, aiding in sperm production and secretion of ovarian hormones
 
<h4> </h4>

Videos

Epithelial tissue and types

Introduction To Algorithms

An algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output.

We can also view an algorithm as a tool for solving a well-specified computational problem. The statement of the problem specifies in general terms the desired input/output relationship. The algorithm describes a specific computational procedure for achieving that input/output relationship.

For example, we might need to sort a sequence of numbers into nondecreasing order. This problem arises frequently in practice and provides fertile ground for introducing many standard design techniques and analysis tools. Here is how we formally define the sorting problem:

Input: A sequence of n numbers (a₁, a₂,…,a_n)

Output: A permutation (reordering) (a1’,a2’,…,a_n’) of the input sequence such that a1’ <= a2’ <= … <= a_n’.

For example, given the input sequence (31, 41, 59, 26, 41, 58), a sorting algorithm returns as output the sequence (26, 31, 41, 41, 58, 59). Such an input sequence is called an instance of the sorting problem. In general, an instance of a problem consists of the input (satisfying whatever constraints are imposed in the problem statement) needed to compute a solution to the problem.

Many of the algorithms we’ll discuss apply directly to specific data structures. For most of the data structures, the following tasks are to be performed:

Insert a new data item
Search for a specific item
Delete a specified item
Traverse through all the items
Sort the items

Characteristics of an Algorithm

Not all procedures can be called an algorithm. An algorithm should have the following characteristics:

Unambiguous− Algorithm should be clear and unambiguous. Each of its steps (or phases), and their input/outputs should be clear and must lead to only one meaning.

Input− An algorithm should have 0 or more well-defined inputs.

Output− An algorithm should have 1 or more well-defined outputs, and should match the desired output.

Finiteness− Algorithms must terminate after a finite number of steps.

Feasibility− Should be feasible with the available resources.

Independent− An algorithm should have step-by-step directions which should be independent of any programming code.

Algorithms are two different types:

Incremental Algorithms
In incremental algorithms, the input is processed from the starting element and the steps are followed moving forward step by step until the last element of the input is reached. An example is insertion sort.

INSERTION-SORT (A)

1 for j = 2 to A.length

2 key = A[j]

3 // Insert A[j] into the sorted sequence A[1...j-1]

4 i = j – 1

5 while I > 0 and A[i] > key

6 A[i+1] = A[i]

7 i = i – 1

8 A[i+1] = key

fig: Insertion Sort
Array indices appear above the rectangles, and values stored in the array positions appear within the rectangles. (a)–(e) The iterations of the for loop of lines 1–8. In each iteration, the black rectangle holds the key taken from A[j], which is compared with the values in shaded rectangles to its left in the test of line 5. Shaded arrows show array values moved one position to the right in line 6, and black arrows indicate where the key moves to in line 8. (f) The final sorted array.
Divide and Conquer Algorithms

In dividing and conquer algorithms, the input is divided into smaller fragments and each fragment is processed with the same steps. Once the fragments are in the required output form, they are combined together to get the final output.

Divide the problem into a number of subproblems that are smaller instances of the same problem.

Conquer the subproblems by solving them recursively. If the subproblem sizes are small enough, however, just solve the subproblems in a straightforward manner.

Combine the solutions to the subproblems into the solution for the original problem.

An example is the Merge Sort.

Divide the array repeatedly into two halves

Stop dividing when there is a single element left.

By fact, single element is already sorted.

Merge two already sorted sub arrays into one.

Above figure shows the operation of merge sort on the array A(5, 2, 4, 7, 1, 3, 2, 6). The lengths of the sorted sequences being merged increase as the algorithm progresses from bottom to top.

Analysis of Algorithms

It is the measure of the efficiency of an algorithm by checking

the correctness of the algorithm
implementation of the algorithm
the simplicity of the algorithm
the execution time of the algorithm
memory requirements of the algorithm

Types of Analysis

1.Worst Case Analysis

The worst-case running time of an algorithm gives us an upper bound on the running time for any input. Knowing it provides a guarantee that the algorithm will never take any longer. We need not make some educated guess about the running time and hope that it never gets much worse.

2.Average Case Analysis

The average case analysis gives the expected behaviour when the input is randomly drawn from a given distribution. It provides an estimate of the running time for an average input.

3.Best Case Analysis

The best case analysis is used when the input is already in order, eg in sorting, if the elements are already sorted. It rarely occurs in practice.

Algorithm Performance

The performance evaluation of an algorithm is obtained by totalling the number of occurrences of each operation when running the algorithm. It is done as a function of the input size ‘n’ and is said to be considered modulo a multiplicative constant.

The following notations are commonly used in performance analysis and used to characterize the complexity of an algorithm:

Theta Notation ( Tightly Bound )
Big – Oh Notation ( Upper Bound )
Big – Omega Notation ( Lower Bound )

These notations will be covered in detail in chapter 8.

References:

1. Y. Langsam, M. J. Augenstein and A. M Tenenbaum, “Data Structures using C and C++”

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, “Introduction toAlgorithms”

3. G. Brassard and P. Bratley, “Fundamentals of Algorithms”

4. R. L. Kruse, B. P. Leung, C. L. Tondo, “Data Structure and Program design in C”

Lesson

Concept of data structure

Subject

Computer Engineering

Grade

Engineering

Recent Notes

No recent notes.

Related Notes

No related notes.