ENGINEERING BLOG

Posts

Showing posts from June, 2021

Storing values in arrays

STORING VALUES IN ARRAYS When we declare an array, we are just allocating space for its elements; no values are stored in the array. There are three ways to store values in an array. First, to initialize the array elements during declaration; second, to input values for individual elements from the keyboard; third, to assign values to individual elements. This is shown in below fig. Figure: Storing values in an array Initializing Arrays during Declaration The elements of an array can be initialized at the time of declaration, just as any other variable. When an array is initialized, we need to provide a value for every element in the array. Arrays are initialized by writing, type array_name[size]={list of values}; Note that the values are written within curly brackets and every value is separated by a comma. It is a compiler error to specify more values than there are elements in the array. When we write, int marks[5]={90, 82, 78, 95, 88}; An ar...

Declaration of Arrays

DECLARATION OF ARRAYS We have already seen that every variable must be declared before it is used. The same concept holds true for array variables. An array must be declared before being used. Declaring an array means specifying the following: * Data type—the kind of values it can store, for example, int, char, float, double. * Name—to identify the array. * Size—the maximum number of values that the array can hold. Arrays are declared using the following syntax: type name[size]; The type can be either int, float, double, char, or any other valid data type. The number within brackets indicates the size of the array, i.e., the maximum number of elements that can be stored in the array. For example, if we write, int marks[10]; then the statement declares marks to be an array containing 10 elements. In C, the array index starts from zero. The first element will be stored in marks[0], second element in marks[1], and so on. Therefore, the last element, that is the 10th element, will be ...

Accessing the elements of the array

ACCESSING THE ELEMENTS OF AN ARRAY Storing related data items in a single array enables the programmers to develop concise and efficient programs. But there is no single function that can operate on all the elements of an array. To access all the elements, we must use a loop. That is, we can access all the elements of an array by varying the value of the subscript into the array. But note that the subscript must be an integral value or an expression that evaluates to an integral value. As shown in above Fig., the first element of the array marks[10] can be accessed by writing marks[0]. Now to process all the elements of the array, we use a loop as shown in Fig. below. // Set each element of the array to –1 int i, marks[1 ]; for(i= ;i<1 ;i++) marks[i] = –1; Fig: Code to initialize each element of the array to –1 The code accesses every individual element of the array and sets its value to –1. In the for loop, first the value of marks[0] is set to –1, then...

Array

ARRAY INTRODUCTION We will explain the concept of arrays using an analogy. Consider a situation in which we have 20 students in a class and we have been asked to write a program that reads and prints the marks of all the 20 students. In this program, we will need 20 integer variables with different names, as shown in Fig. below. Figure: Twenty variables for 20 students Now to read the values of these 20 variables, we must have 20 read statements. Similarly, to print the value of these variables, we need 20 write statements. If it is just a matter of 20 variables, then it might be acceptable for the user to follow this approach. But would it be possible to follow this approach if we have to read and print the marks of students, * in the entire course (say 100 students) * in the entire college (say 500 students) * in the entire university (say 10,000 students) The answer is n...

Points to Remember

• A data structure is a particular way of storing and organizing data either in computer’s memory or on the disk storage so that it can be used efficiently. • There are two types of data structures: primitive and non-primitive data structures. Primitive data structures are the fundamental data types which are supported by a programming language. Non-primitive data structures are those data structures which are created using primitive data structures. • Non-primitive data structures can further be classified into two categories: linear and non-linear data structures. • If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. However, if the elements of a data structure are not stored in sequential order, then it is a non-linear data structure. • An array is a collection of similar data elements which are stored in consecutive memory locations. • A linked list is a linear data structure consisting of a grou...

Omega, Theta notation

OMEGA NOTATION (Ω) The Omega notation provides a tight lower bound for f(n). This means that the function can never do better than the specified value but it may do worse. Ω notation is simply written as, f(n) ∈ Ω(g(n)), where n is the problem size and Ω(g(n)) = {h(n): ∃ positive constants c > 0, n0 such that 0 ≤ cg(n) ≤ h(n), ∀ n ≥ n0}. Hence, we can say that Ω(g(n)) comprises a set of all the functions h(n) that are greater than or equal to cg(n) for all values of n ≥ n0. If cg(n) ≤ f(n), c > O, ∀ n ≥ nO, then f(n) ∈ Ω(g(n)) and g(n) is an asymptotically tight lower bound for f(n). Examples of functions in Ω(n2) include: n2, n2.9, n3+ n2, n3 Examples of functions not in Ω(n3) include: n, n2.9, n2 To summarize, • Best case Ω describes a lower bound for all combinations of input. This implies that the function can never get any better than the specified value. For example, when sorting an array the best case is when the array is already correctly s...

Big O Notation

BIG O NOTATION In today’s era of massive advancement in computer technology, we are hardly concerned about the efficiency of algorithms. Rather, we are more interested in knowing the generic order of the magnitude of the algorithm. If we have two different algorithms to solve the same problem where one algorithm executes in 10 iterations and the other in 20 iterations, the difference between the two algorithms is not much. However, if the first algorithm executes in 10 iterations and the other in 1000 iterations, then it is a matter of concern. We have seen that the number of statements executed in the program for n elements of the data is a function of the number of elements, expressed as f(n). Even if the expression derived for a function is complex, a dominant factor in the expression is sufficient to determine the order of the magnitude of the result and, hence, the efficiency of the algorithm. This factor is the Big O, and is expressed as O(n). The Big O notation, where O sta...

Time and space complexity

TIME AND SPACE COMPLEXITY Analysing an algorithm means determining the amount of resources (such as time and memory) needed to execute it. Algorithms are generally designed to work with an arbitrary number of inputs, so the efficiency or complexity of an algorithm is stated in terms of time and space complexity. The time complexity of an algorithm is basically the running time of a program as a function of the input size. Similarly, the space complexity of an algorithm is the amount of computer memory that is required during the program execution as a function of the input size. In other words, the number of machine instructions which a program executes is called its time complexity. This number is primarily dependent on the size of the program’s input and the algorithm used. Generally, the space needed by a program depends on the following two parts: * Fixed part : It varies from problem to problem. It includes the space needed for storing instructions, constants, variables, and struc...

Different approach to designing an algorithm

DIFFERENT APPROACHES TO DESIGNING AN ALGORITHM Algorithms are used to manipulate the data contained in data structures. When working with data structures, algorithms are used to perform operations on the stored data. A complex algorithm is often divided into smaller units called modules. This process of dividing an algorithm into modules is called modularization. The key advantages of modularization are as follows: * It makes the complex algorithm simpler to design and implement. * Each module can be designed independently. While designing one module, the details of other modules can be ignored, thereby enhancing clarity in design which in turn simplifies implementation, debugging, testing, documenting, and maintenance of the overall algorithm. There are two main approaches to design an algorithm—top-down approach and bottom-up approach, Fig : Different approaches of designing an algorithm Top-down approach A top-down design approach starts by dividing the comple...

Control statement used in algorithms

CONTROL STRUCTURES USED IN ALGORITHMS An algorithm has a finite number of steps. Some steps may involve decision-making and repetition. Broadly speaking, an algorithm may employ one of the following control structures: (a) sequence, (b) decision, and (c) repetition. Sequence By sequence, we mean that each step of an algorithm is executed in a specified order. Let us write an algorithm to add two numbers. This algorithm performs the steps in a purely sequential order, as shown in below. Fig : Algorithm to add two numbers Decision Decision statements are used when the execution of a process depends on the outcome of some condition. For example, if x = y, then print EQUAL. So the general form of IF construct can be given as: IF condition Then process A condition in this context is any statement that may evaluate to either a true value or a false value. In the above example, a variable x can be either equal to y or not equal to y. However, it cannot be bo...

Abstract data type

ABSTRACT DATA TYPE An abstract data type (ADT) is the way we look at a data structure, focusing on what it does and ignoring how it does its job.For example, stacks and queues are perfect examples of an ADT. We can implement both these ADTs using an array or a linked list. This demonstrates the ‘abstract’nature of stacks and queues. To further understand the meaning of an abstract data type, we will break the term into ‘data type’ and ‘abstract’, and then discuss their meanings. Data type Data type of a variable is the set of values that the variable can take. We have already read the basic data types in C include int, char, float, and double. When we talk about a primitive type (built-in data type), we actually consider two things: a data item with certain characteristics and the permissible operations on that data. For example, an int variable can contain any whole-number value from –32768 to 32767 and can be operated with the operators +, –, *, and /. In other words, the operations...

Algorithm

ALGORITHMS The typical definition of algorithm is ‘a formally defined procedure for performing some calculation’. If a procedure is formally defined, then it can be implemented using a formal language, and such a language is known as a programming language. In general terms, an algorithm provides a blueprint to write a program to solve a particular problem. It is considered to be an effective procedure for solving a problem in finite number of steps. That is, a well-defined algorithm always provides an answer and is guaranteed to terminate. Algorithms are mainly used to achieve software reuse. Once we have an idea or a blueprint of a solution, we can implement it in any high-level language like C, C++, or Java. An algorithm is basically a set of instructions that solve a problem. It is not uncommon to have multiple algorithms to tackle the same problem, but the choice of a particular algorithm must depend on the time and space complexity of the algorithm. Introduction to data structure...

Operations on data structures

OPERATIONS ON DATA STRUCTURES This section discusses the different operations that can be execute on the different data structures before mentioned. Traversing It means to process each data item exactly once so that it can be processed. For example, to print the names of all the employees in a office. Searching It is used to detect the location of one or more data items that satisfy the given constraint. Such a data item may or may not be present in the given group of data items. For example, to find the names of all the students who secured 100 marks in mathematics. Inserting It is used to add new data items to the given list of data items. For example, to add the details of a new student who has lately joined the course. Deleting It means to delete a particular data item from the given collection of data items. For example, to delete the name of a employee who has left the office. Sorting Data items can be ordered in some order like ascending order or descending order depending ...

Classification of data structures

CLASSIFICATION OF DATA STRUCTURES Data structures are generally categorized into two classes: primitive and non-primitive data structures. Primitive and Non-primitive Data Structures Primitive data structures are the fundamental data types which are supported by a programming language. Some basic data types are integer, real, character, and boolean. The terms ‘data type’, ‘basic data type’, and ‘primitive data type’ are often used interchangeably. Non-primitive data structures are those data structures which are created using primitive data structures. Examples of such data structures include linked lists, stacks, trees, and graphs. Non-primitive data structures can further be classified into two categories: linear and non-lineardata structures. Linear and Non-linear Structures If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. Examples include arrays, linked lists, stacks, and queues. Linear data s...