Course Description

Introduction

Computers are widely being used in every domain nowadays and in each domain, we have some problems. To Solve the problems of the computer we need to require a program.

A Program consists of two basic components,

1. Algorithm
2. Data Structure

Computer science is a field of study that deals with solving a variety of problems by using computers. To solve a given problem by using computers, you need to design an algorithm for it.

        Multiple algorithms can be designed to solve a particular problem. An algorithm that provides the maximum efficiency should be used for solving the problem. The efficiency of an algorithm can be improved by using an appropriate data structure. Data structures help in creating programs that are simple, reusable, and easy to maintain. This module will enable a learner to select and implement an appropriate data structure and algorithm to solve a given programming problem.

Variables

• Variable is a location in the memory. It has a name and contains a value.

Data Type

• Size of the data in the memory.

• Type of the data in the memory whether it is character or integer, etc.

A Datatype in a programming language is a set of data with the values having predefined characteristics. System/Compiler defined data type is called a primitive data type. Structure in C/C++ and classes in C++/Java are the means to create our own data types known as user-defined data types.

What is Data Structure

Data Structure is a particular way of storing and organizing data in a computer so that it can be used efficiently. A data structure is defined as a way of organizing the various data elements into the memory with respect to each other.

      Data can be organized in many different ways. Therefore, you can create as many data structures as you want. Some data structures that have proved useful over the years are,

• Arrays
• Linked Lists
• Stacks
• Queues
• Trees
• Graphs

Types of Data Structures

Data structures can be classified under the following two categories:

• Static:  Its size cannot be grown or shrank.

                                 Example – Array

• Dynamic: Its size can be grown or shrank.

                                Example – Linked List

Classification

      There are two types of data structures,

• Linear data structure (Link List, stack, queue).
• Non-Linear Data Structure(tree, graph).

Abstract Data Type

• All Primitive data type supports basic operations like addition, subtraction etc.
• The system is providing the implementation for the primitive data types.
• For non-primitive data types, we also need to define the operation.
• Combination of data structure and their operations are called abstract data types.
• So data structure is all about creating abstract data type.
• Any piece of information can be handled by defining the appropriate data type and set of possible operations.

Algorithm

• The word algorithm is derived from the name of the Persian mathematician Al Khwarizmi.
• An algorithm can be defined as a step-by-step procedure for solving a problem.
• An algorithm helps the user arrive at the correct result in a finite number of steps.

An algorithm has five important properties,

• Finiteness: fixed number of steps
• Definiteness: no ambiguity (confusion) in every step.
• Input: an algorithm can take zero or more input
• Output: It definitely gives one output.
• Effectiveness: It specifies the correct result.

Note:  Efficiency is not the property of the Algorithm.

Ex. sum(n) algorithm to add first n natural numbers. Assume s is a variable initialized to 0.

1) if n<=0 return -1.

2) repeat step 3 and 4 while n!=0.

3) s= s+n

4)[decrement n] n--

5) return s.

Analysis of Algorithm

The goal of analysis of algorithm is to compare algorthim mainly in  terms of running time but also in terms of other factors(like memory, efforts etc.)

1- Rate of Growth

The rate at which the running time increases as a function of i/p is called rate of growth.

Types of Analysis

To analyze the given alogrithm we need to know on what inputs the algo is taking less time and on what inputs the algorithm is taking huge time.

• Worst Case
• Average Case
• Best Case

Role of Data Structures

• Different algorithms can be used to solve the same problem.
• Some algorithms may solve the problem more efficiently(correct) than the others.
• An algorithm that provides the maximum efficiency should be used to solve a problem.
• One of the basic techniques for improving the efficiency of algorithms is to use an appropriate data structure.

1. Use of an appropriate data structure, helps improve the efficiency of a program.
2. The use of appropriate data structures also allows you to overcome some other programming challenges, such as:
   • Simplifying complex problems
   • Creating standard, reusable code components
   • Creating programs that are easy to understand and maintain

Just a minute

An array is a ___________ data structure, and a linked list is a ____________ data structure.

Identifying Techniques for Designing Algorithms

• Two commonly used techniques for designing algorithms are:
• Divide and conquer approach
• Greedy approach
• Divide and conquer is a powerful approach for solving conceptually difficult problems.
• Divide and conquer approach requires you to find a way of:
  1. Breaking the problem into sub problems
  2. Solving the trivial cases
  3. Combining the solutions to the sub problems to solve the original problem

Eg. Binary Search , Binary Search Tree , Quick Short , Merge Short etc.

• Algorithms based on greedy approach are used for solving optimization problems, where you need to maximize profits or minimize costs under a given set of conditions.
• Some examples of optimization problems are:
• Finding the shortest distance from an originating city to a set of destination cities, given the distances between the pairs of cities.
• Finding the minimum number of currency notes required for an amount, where an arbitrary number of notes for each denomination are available.
• Selecting items with maximum value from a given set of items, where the total weight of the selected items cannot exceed a given value.

Eg. Graphs

Que.The ___________ technique involves selecting the best available option at each step.

Answer:Greedy

Designing Algorithms Using Recursion

Recursion:

• Refers to the technique of defining a process in terms of itself
• Is used to solve complex programming problems that are repetitive in nature
• Is implemented in a program by using a recursive procedure or function. A recursive procedure or function is a function that invokes itself
• Is useful in writing clear, short, and simple programs

Identify the problem in the following algorithm that attempts to find the sum of the first n natural numbers:

•       Algorithm: Sum (n)
•       1. s = n + Sum(n – 1)
•       2. Return (s)

Answer:

There is no terminating condition in the given recursive algorithm. Therefore, it will call itself infinitely. The correct algorithm would be:?    

•  1. If (n = 1)
•       Return(1)
•   2. s = n + Sum(n – 1)
•   3. Return(s)

Determining the Efficiency of an Algorithm

1. Factors that affect the efficiency of a program include:

• Speed of the machine
• Compiler
• Operating system
• Programming language
• Size of the input

2. In addition to these factors, the way data of a program is organized, and the algorithm used to solve the problem also has a significant impact on the efficiencyof a program.

• The efficiency of an algorithm can be computed by determining the amount of resources it consumes.
• The primary resources that an algorithm consumes are:
• Time: The CPU time required to execute the algorithm.
• Space: The amount of memory used by the algorithm for its execution.
• The lesser resources an algorithm consumes, the more efficient it is.

Time/Space Tradeoff

• Time/Space Tradeoff:
• It refers to a situation where you can reduce the use of memory at the cost of slower program execution, or reduce the running time at the cost of increased memory usage.
• Example is data storage in compressed/uncompressed form.
• Memory is extensible, but time is not. Therefore, time considerations generally override memory considerations.