System Calls and System Programs

System Calls and System Programs

System calls provide an interface between the process an the operating system. System calls allow user-level processes to request some services from the operating system which process itself is not allowed to do. In handling the trap, the operating system will enter in the kernel mode, where it has access to privileged instructions, and can perform the desired service on the behalf of user-level process. It is because of the critical nature of operations that the operating system itself does them every time they are needed. For example, for I/O a process involves a system call telling the operating system to read or write particular area and this request is satisfied by the operating system.
System programs provide basic functioning to users so that they do not need to write their own environment for program development (editors, compilers) and program execution (shells). In some sense, they are bundles of useful system calls.

EXAMAPERS123.BLOGSPOT.COM

Interprocess CommunicatioN

Interprocess Communication

Since processes frequently needs to communicate with other processes therefore, there is a need for a well-structured communication, without using interrupts, among processes.

Race Conditions
In operating systems, processes that are working together share some common storage (main memory, file etc.) that each process can read and write. When two or more processes are reading or writing some shared data and the final result depends on who runs precisely when, are called race conditions. Concurrently executing threads that share data need to synchronize their operations and processing in order to avoid race condition on shared data. Only one ‘customer’ thread at a time should be allowed to examine and update the shared variable.
Race conditions are also possible in Operating Systems. If the ready queue is implemented as a linked list and if the ready queue is being manipulated during the handling of an interrupt, then interrupts must be disabled to prevent another interrupt before the first one completes. If interrupts are not disabled than the linked list could become corrupt.


Critical Section
How to avoid race conditions?


The key to preventing trouble involving shared storage is find some way to prohibit more than one process from reading and writing the shared data simultaneously. That part of the program where the shared memory is accessed is called the Critical Section. To avoid race conditions and flawed results, one must identify codes in Critical Sections in each thread. The characteristic properties of the code that form a Critical Section are
• Codes that reference one or more variables in a “read-update-write” fashion while any of those variables is possibly being altered by another thread.
• Codes that alter one or more variables that are possibly being referenced in “read-updata-write” fashion by another thread.
• Codes use a data structure while any part of it is possibly being altered by another thread.
• Codes alter any part of a data structure while it is possibly in use by another thread.

Here, the important point is that when one process is executing shared modifiable data in its critical section, no other process is to be allowed to execute in its critical section. Thus, the execution of critical sections by the processes is mutually exclusive in time.


Mutual Exclusion


A way of making sure that if one process is using a shared modifiable data, the other processes will be excluded from doing the same thing.
Formally, while one process executes the shared variable, all other processes desiring to do so at the same time moment should be kept waiting; when that process has finished executing the shared variable, one of the processes waiting; while that process has finished executing the shared variable, one of the processes waiting to do so should be allowed to proceed. In this fashion, each process executing the shared data (variables) excludes all others from doing so simultaneously. This is called Mutual Exclusion.
Note that mutual exclusion needs to be enforced only when processes access shared modifiable data - when processes are performing operations that do not conflict with one another they should be allowed to proceed concurrently.


Mutual Exclusion Conditions
If we could arrange matters such that no two processes were ever in their critical sections simultaneously, we could avoid race conditions. We need four conditions to hold to have a good solution for the critical section problem (mutual exclusion).
• No two processes may at the same moment inside their critical sections.
• No assumptions are made about relative speeds of processes or number of CPUs.
• No process should outside its critical section should block other processes.
• No process should wait arbitrary long to enter its critical section.


Proposals for Achieving Mutual Exclusion

The mutual exclusion problem is to devise a pre-protocol (or entry protocol) and a post-protocol (or exist protocol) to keep two or more threads from being in their critical sections at the same time. Tanenbaum examine proposals for critical-section problem or mutual exclusion problem.
Problem
When one process is updating shared modifiable data in its critical section, no other process should allowed to enter in its critical section.


Proposal 1 -Disabling Interrupts (Hardware Solution)
Each process disables all interrupts just after entering in its critical section and re-enable all interrupts just before leaving critical section. With interrupts turned off the CPU could not be switched to other process. Hence, no other process will enter its critical and mutual exclusion achieved.
Conclusion
Disabling interrupts is sometimes a useful interrupts is sometimes a useful technique within the kernel of an operating system, but it is not appropriate as a general mutual exclusion mechanism for users process. The reason is that it is unwise to give user process the power to turn off interrupts.


Proposal 2 - Lock Variable (Software Solution)
In this solution, we consider a single, shared, (lock) variable, initially 0. When a process wants to enter in its critical section, it first test the lock. If lock is 0, the process first sets it to 1 and then enters the critical section. If the lock is already 1, the process just waits until (lock) variable becomes 0. Thus, a 0 means that no process in its critical section, and 1 means hold your horses - some process is in its critical section.
Conclusion
The flaw in this proposal can be best explained by example. Suppose process A sees that the lock is 0. Before it can set the lock to 1 another process B is scheduled, runs, and sets the lock to 1. When the process A runs again, it will also set the lock to 1, and two processes will be in their critical section simultaneously.


Proposal 3 - Strict Alteration
In this proposed solution, the integer variable 'turn' keeps track of whose turn is to enter the critical section. Initially, process A inspect turn, finds it to be 0, and enters in its critical section. Process B also finds it to be 0 and sits in a loop continually testing 'turn' to see when it becomes 1.Continuously testing a variable waiting for some value to appear is called the Busy-Waiting.
Conclusion
Taking turns is not a good idea when one of the processes is much slower than the other. Suppose process 0 finishes its critical section quickly, so both processes are now in their noncritical section. This situation violates above mentioned condition 3.
Using Systems calls 'sleep' and 'wakeup'
Basically, what above mentioned solution do is this: when a processes wants to enter in its critical section , it checks to see if then entry is allowed. If it is not, the process goes into tight loop and waits (i.e., start busy waiting) until it is allowed to enter. This approach waste CPU-time.
Now look at some interprocess communication primitives is the pair of steep-wakeup.
• Sleep
o It is a system call that causes the caller to block, that is, be suspended until some other process wakes it up.
• Wakeup
o It is a system call that wakes up the process.

Both 'sleep' and 'wakeup' system calls have one parameter that represents a memory address used to match up 'sleeps' and 'wakeups' .


The Bounded Buffer Producers and Consumers
The bounded buffer producers and consumers assumes that there is a fixed buffer size i.e., a finite numbers of slots are available.
Statement
To suspend the producers when the buffer is full, to suspend the consumers when the buffer is empty, and to make sure that only one process at a time manipulates a buffer so there are no race conditions or lost updates.
As an example how sleep-wakeup system calls are used, consider the producer-consumer problem also known as bounded buffer problem.
Two processes share a common, fixed-size (bounded) buffer. The producer puts information into the buffer and the consumer takes information out.
Trouble arises when
1. The producer wants to put a new data in the buffer, but buffer is already full.
Solution: Producer goes to sleep and to be awakened when the consumer has removed data.
2. The consumer wants to remove data the buffer but buffer is already empty.
Solution: Consumer goes to sleep until the producer puts some data in buffer and wakes consumer up.
Conclusion
This approaches also leads to same race conditions we have seen in earlier approaches. Race condition can occur due to the fact that access to 'count' is unconstrained. The essence of the problem is that a wakeup call, sent to a process that is not sleeping, is lost.

Semaphores


E.W. Dijkstra (1965) abstracted the key notion of mutual exclusion in his concepts of semaphores.
Definition
A semaphore is a protected variable whose value can be accessed and altered only by the operations P and V and initialization operation called 'Semaphoiinitislize'.
Binary Semaphores can assume only the value 0 or the value 1 counting semaphores also called general semaphores can assume only nonnegative values.

The P (or wait or sleep or down) operation on semaphores S, written as P(S) or wait (S), operates as follows:
P(S): IF S > 0
THEN S := S - 1
ELSE (wait on S)

The V (or signal or wakeup or up) operation on semaphore S, written as V(S) or signal (S), operates as follows:
V(S): IF (one or more process are waiting on S)
THEN (let one of these processes proceed)
ELSE S := S +1

Operations P and V are done as single, indivisible, atomic action. It is guaranteed that once a semaphore operations has stared, no other process can access the semaphore until operation has completed. Mutual exclusion on the semaphore, S, is enforced within P(S) and V(S).
If several processes attempt a P(S) simultaneously, only process will be allowed to proceed. The other processes will be kept waiting, but the implementation of P and V guarantees that processes will not suffer indefinite postponement.
Semaphores solve the lost-wakeup problem.
Producer-Consumer Problem Using Semaphores
The Solution to producer-consumer problem uses three semaphores, namely, full, empty and mutex.
The semaphore 'full' is used for counting the number of slots in the buffer that are full. The 'empty' for counting the number of slots that are empty and semaphore 'mutex' to make sure that the producer and consumer do not access modifiable shared section of the buffer simultaneously.
Initialization
• Set full buffer slots to 0.
i.e., semaphore Full = 0.
• Set empty buffer slots to N.
i.e., semaphore empty = N.
• For control access to critical section set mutex to 1.
i.e., semaphore mutex = 1.
Producer ( )
WHILE (true)
produce-Item ( );
P (empty);
P (mutex);
enter-Item ( )
V (mutex)
V (full);
Consumer ( )
WHILE (true)
P (full)
P (mutex);
remove-Item ( );
V (mutex);
V (empty);
consume-Item (Item)

EXAMAPERS123.BLOGSPOT.COM

'Definition of Process

SUCCESS FOR CAREER

Definition of Process

The notion of process is central to the understanding of operating systems. There are quite a few definitions presented in the literature, but no "perfect" definition has yet appeared.

Definition
The term "process" was first used by the designers of the MULTICS in 1960's. Since then, the term process, used somewhat interchangeably with 'task' or 'job'. The process has been given many definitions for instance
• A program in Execution.
• An asynchronous activity.
• The 'animated sprit' of a procedure in execution.
• The entity to which processors are assigned.
• The 'dispatchable' unit.
and many more definitions have given. As we can see from above that there is no universally agreed upon definition, but the definition "Program in Execution" seem to be most frequently used. And this is a concept are will use in the present study of operating systems.
Now that we agreed upon the definition of process, the question is what is the relation between process and program. It is same beast with different name or when this beast is sleeping (not executing) it is called program and when it is executing becomes process. Well, to be very precise. Process is not the same as program. In the following discussion we point out some of the difference between process and program. As we have mentioned earlier.
Process is not the same as program. A process is more than a program code. A process is an 'active' entity as oppose to program which consider to be a 'passive' entity. As we all know that a program is an algorithm expressed in some suitable notation, (e.g., programming language). Being a passive, a program is only a part of process. Process, on the other hand, includes:
• Current value of Program Counter (PC)
• Contents of the processors registers
• Value of the variables
• The process stack (SP) which typically contains temporary data such as subroutine parameter, return address, and temporary variables.
• A data section that contains global variables.
A process is the unit of work in a system.
In Process model, all software on the computer is organized into a number of sequential processes. A process includes PC, registers, and variables. Conceptually, each process has its own virtual CPU. In reality, the CPU switches back and forth among processes. (The rapid switching back and forth is called multiprogramming).




Process State


The process state consist of everything necessary to resume the process execution if it is somehow put aside temporarily. The process state consists of at least following:
• Code for the program.
• Program's static data.
• Program's dynamic data.
• Program's procedure call stack.
• Contents of general purpose registers.
• Contents of program counter (PC)
• Contents of program status word (PSW).
• Operating Systems resource in use.

A process goes through a series of discrete process states.
• New State: The process being created.
• Running State: A process is said to be running if it has the CPU, that is, process actually using the CPU at that particular instant.
• Blocked (or waiting) State: A process is said to be blocked if it is waiting for some event to happen such that as an I/O completion before it can proceed. Note that a process is unable to run until some external event happens.
• Ready State: A process is said to be ready if it use a CPU if one were available. A ready state process is runable but temporarily stopped running to let another process run.
• Terminated state: The process has finished execution.






Process State


The process state consist of everything necessary to resume the process execution if it is somehow put aside temporarily. The process state consists of at least following:
• Code for the program.
• Program's static data.
• Program's dynamic data.
• Program's procedure call stack.
• Contents of general purpose registers.
• Contents of program counter (PC)
• Contents of program status word (PSW).
• Operating Systems resource in use.

A process goes through a series of discrete process states.
• New State: The process being created.
• Running State: A process is said to be running if it has the CPU, that is, process actually using the CPU at that particular instant.
• Blocked (or waiting) State: A process is said to be blocked if it is waiting for some event to happen such that as an I/O completion before it can proceed. Note that a process is unable to run until some external event happens.
• Ready State: A process is said to be ready if it use a CPU if one were available. A ready state process is runable but temporarily stopped running to let another process run.
• Terminated state: The process has finished execution.







Process Control Block


A process in an operating system is represented by a data structure known as a process control block (PCB) or process descriptor. The PCB contains important information about the specific process including
• The current state of the process i.e., whether it is ready, running, waiting, or whatever.
• Unique identification of the process in order to track "which is which" information.
• A pointer to parent process.
• Similarly, a pointer to child process (if it exists).
• The priority of process (a part of CPU scheduling information).
• Pointers to locate memory of processes.
• A register save area.
• The processor it is running on.
The PCB is a certain store that allows the operating systems to locate key information about a process. Thus, the PCB is the data structure that defines a process to the operating systems.

EXAMAPERS123.BLOGSPOT.COM

C LANGUAGE PROGRAMS BITS

C LANGUAGE PROGRAMS BITS

1. The recurrence relation that arises in relation with the complexity of binary search is
a. T(n)=T(n/2)+k, where k is constant
b. T(n)=2T(n/2)+k, where k is constant
c. T(n)=T(n/2)+log(n)
d. T(n)=T(n/2)+n
2. The running time T(n), where `n' is the input size of a recursive algorithm is given as followsT(n)=c+T(n-1),if n>1
d, if n≤ 1
The order of this algorithm is
a. n2
b. n
c. n3
d. nn
3. The concept of order(Big O) is important because
a. it can be used to decide the best algorithm that solves a given problem
b. It determines the minimum size of a problem that can be solved in a given system, in a given amount of time
c. It is the lower bound of the growth rate of the algorithm
d. It is the average bound of the growth rate of the algorithm
4. The concept of order(Big O) is important because
a. it can not be used to decide the best algorithm that solves a given problem
b. It determines the maximum size of a problem that can be solved in a given system, in a given amount of time
c. It is the lower bound of the growth rate of the algorithm
d. It is the average bound of the growth rate of the algorithm
5. The time complexity of an algorithm T(n), where n is the input size is given byT(n)=T(n-1)+/n, if n>1
=1 otherwise
The order of the algorithm is
a. log n
b. n
c. n2
d. nn
6. The running time of an algorithm is given byT(n)=T(n-1)+T(n-2)-T(n-3), if n>3
= n otherwise
The order of this algorithm is
a. n
b. log n
c. nn
d. n2
7. If n=4,then the value of O(log n) is
a. 1
b. 2
c. 4
d. 8
8. If n=4,then the value of O( n2) is
a. 4
b. 16
c. 64
d. 512
9. The average time complexity of insertion sort is
a. O(n2)
b. O(n)
c. O(1)
d. O(log n)
10. The running time of an algorithm is given byT(n)=T(n-1)+T(n-2)-T(n-3), if n>3
= n otherwise
What should be the relation between T(1),T(2) and T(3) so that its order is constant.
a. T(1)=T(2)=T(3)
b. T(1)+T(3)=2T(2)
c. T(1)-T(3)=T(2)
d. T(1)+T(2)=T(3)
11. The order of the algorithm that finds a given Boolean function of `n' variables , produces a is
a. constant
b. linear
c. non-linear
d. exponential
12. If n=16, then the value of O(n log n) is
a. 16
b. 32
c. 64
d. 128


13. How many memory management functions are there in C
a. 4
b. 3
c. 2
d. 1
14. Which of the following is not a C memory allocation function
a. alloc( )
b. calloc( )
c. free
d. malloc()
15. If n= 8, then the value of O(1) is
a. 1
b. 2
c. 4
d. 8
16. If n=4, then the value of O(n3) is
a. 4
b. 16
c. 64
d. 512
17. If n=2, then the value of O(n) is
a. 2
b. 3
c. 4
d. 5
18. All memory management functions are found in
a. stdlib.c
b. stdio.h
c. conio.h
d. math.h
19. The function that returns memory to the heap is
a. alloc( )
b. free( )
c. malloc( )
d. realloc( )
20. Which of the following statement about the releasing memory allocation is false?
a. It is an error to dereference a pointer to allocated memory after the memory has been released
b. It is an error to free memory with a pointer to other than the first element of an allocated array
c. Memory should be freed as soon as it is no longer needed
d. To ensure that it is released , allocated memory should be freed before the program
21. The syntax of free() function
a. void free(void* free)
b. int free(void* ptr)
c. float free(void* ptr)
d. void free(ptr)
22. Which of the memory function allocates a block of memory
a. malloc ( )
b. calloc( )
c. release( )
d. free( )
23. Return type of a calloc( ) function is
a. int
b. float
c. char
d. void
24. Return type of a realloc( ) function is
a. int
b. float
c. char
d. void
25. Which of the following memory management function used to release memory
a. malloc( )
b. calloc( )
c. release( )
d. free( )
26. Which of the following is considered auxiliary storage?
a. disk
b. random access memeory(RAM)
c. read only memory(ROM)
d. EEPROM
27. Which of the following is not a standard file stream?
a. stdin
b. stderr
c. stdfile
d. stdout
28. The C library that contains the prototype statements for the file operations is
a. file.h
b. proto.h
c. stdio.h
d. stdlib.h
29. In C, local variable are stored in
a. stack
b. heap
c. permanent storage
d. hard disk
30. The linked list field(s) are
a. data
b. pointer
c. pointer to next node
d. data and pointer to next node
31. The linked list structure is defined as
a. struct node
{
int item;
struct node *next;
};
b. node
{
int item;
struct node *next;
};
c. struct node
{
int item;
node *node;
};
d. node
{
Int item;
node next;
};
32. Dynamic memory area is
a. heap
b. stack
c. permanent storage
d. Hard disk
33. The contents of the storage space allocated dynamically, can be accessed through _ _ _ _ _ _ _
a. structure variables
b. pointers
c. unions
d. arrays
34. Each item in the list contains a �link� to structure containing the _ _ _ _ _ _ _ item
a. previous
b. next
c. present
d. last
35. In C, program instructions are stored in
a. stack
b. heap
c. permanent storage
d. Hard disk
36. In C, Global variables are stored in
a. permanent storage
b. stack
c. heap
d. Hard disk
37. In C, static variables are stored in
a. heap
b. permanent storage
c. Hard disk
d. Stack
38. A list refers to a set of items organized _ _ _ _ _
a. sequentially
b. exponentially
c. non-sequentially
d. factorially
39. Each structure of a linked list consists _ _ _ _ _ _ _ no. of fields
a. 2
b. 3
c. 4
d. 1
40. Linked lists are not suitable for data structures of which one of the following problem?
a. insertion sort
b. Binary search
c. radix sort
d. polynomial manipulation problem
41. An item that is read as input can be either pushed to a stack and latter popped and printed, or printed directly. Which of the following will be the output if the input is the sequence of items-1,2,3,4,5?
a. 3,4,5,1,2
b. 3,4,5,2,1
c. 1,5,2,3,4
d. 5,4,3,1,2
42. No.of pointers to be manipulated in a linked list to delete an item in the middle _ _ _ _ _ _ _
a. Zero
b. One
c. Two
d. Three
43. No.of pointers to be manipulated in a linked list to delete first item
a. Zero
b. One
c. Two
d. Three
44. Stack is useful for _ _ _ _ _ _ _
a. radix sort
b. breadth first search
c. recursion
d. quick sort
45. The end of the list is marked as
a. node.next=0
b. (node.last = 0)
c. node.next= &node;
d. node.previous=0;
46. No.of pointers to be manipulated in a linked list to insert an item in the middle _ _ _ _ _ _ _ _
a. Two
b. Three
c. One
d. Zero
47. No. of pointers to be manipulated in a linked list to delete last item
a. Zero
b. One
c. Two
d. Three
48. Single linked list uses _ _ _ _ _ _ no. of pointers
a. Zero
b. one
c. Two
d. Three
49. LIFO is
a. stack
b. queue
c. linked list
d. tree
50. A stack is has the entries a,b,c,(with a on top). Stack B is empty. An entry popped out of stack A can be printed immediately or pushed to stack B.An entry popped out of stack B can only be printed. In this arrangement, which of the following permutations a,b,c is not possible?
a. b a c
b. b c a
c. c a b
d. a b c
51. Which of the following programming languages features require a stack-base allocation
a. pointer
b. Block-structure
c. recursion
d. dynamic scoping
52. Push down stack or push down list is
a. stack
b. queue
c. linked list
d. dequeue
53. Stack is useful for
a. radix sort
b. breadth first search
c. recursion
d. Heap sort
54. Stacks can not be used to
a. evaluate an arithmetic expression in postfix form
b. implement recursion
c. convert a given arithmetic expression in infix form to is equivalent postfix form
d. allocates resources (like CPU) by the operating system
55. Stack is useful for implementing
a. radix sort
b. breadth first search
c. selection sort
d. depth first search
56. Which of the following is useful in implementing quick sort?
a. stack
b. set
c. list
d. queue
57. Which of the following is essential for converting an infix expression to postfix form efficiently?
a. An operator stack
b. An operand stack
c. An operator stack and an operand stack
d. A parse tree
58. A stack is most suitable to evaluate _ _ _ _ _ expression
a. postfix
b. prefix
c. infix
d. post & infix
59. Linear linked data structure is
a. tree
b. graph
c. stack
d. binary tree
60. A queue of characters currently contained a,b,c,d. What would be the contents of queue after the following operationDELETE, ADD W, ADD X, DELETE, ADD Y
a. A,B,C,W,Y
b. C,D,W,X,Y
c. W,Y,X,C,D
d. A,B,C,D,W
61. Which of the following data structure is suitable for priority queue?
a. Doubly linked list
b. Circular queues
c. Binary search
d. Heaps
62. For storing the sorted data on which often insert and deletion operations are performed, the following data structure is better
a. Array
b. queue
c. linked-list
d. doubly linked-list
63. A circular queue of size N will sign queue full when the number of elements in the queue is
a. N-1
b. N
c. N+1
d. N-2
64. The postfix equivalent of the prefix * + a b - c d is
a. ab + cd - *
b. ab cd + - *
c. ab + cd * -
d. ab + - cd *
65. The postfix expression for the infix expressionA + B* (C+D) / F + D*E is:
a. AB + CD + F / D + E*
b. ABCD + * F / + DE*
c. A*B + CD / F*DE ++
d. A+ BCD / F* DE ++
66. A telephone system which places cells to a particular number on hold can best represented by
a. queue
b. stack
c. linked-list
d. variable
67. The performance of an algorithm is specified by the following notation that represents the worst case
a. O-notation
b. Omega notation
c. Theta notation
d. alpha-notation
68. If front=rear ,then the queue is
a. full
b. empty
c. unknown value
d. 1/2 full
69. Reverse polish expression is
a. Infix
b. postfix
c. prefix
d. post & prefix
70. A list of integers is read in, one at a time, and a binary search tree is constructed. Next the tree is traversed and the integers are printed. Which traversed would result in a printout which duplicates the original order of the list of integers?
a. pre-order
b. post-order
c. in-order
d. in-fix order
71. The postfix expression for the infix expression A + B* (C+D) / F + D*E is
a. AB + CD + * F/D + E *
b. ABCD + *F / + DE* +
c. A*B + CD / F*DE ++
d. A + *BCD / F*DE ++
72. The equivalent of (a+b↑c↑d)*(e+f/d) in the post fix notation is
a. ab+c↑d↑e &fd/
b. abcd↑+↑efd/+*
c. abcdefd/+*↑↑+
d. abcd↑↑+efd/+*
73. The infix form of the postfix expression ABC-/D*E+ is
a. A/B-C*D+E
b. A-B/C*D+E
c. (A-B)/C*D+E
d. A/(B-C)*D+E
74. The postfix expression for the infix expression A/B*C+D*E is
a. AB/C*DE*+
b. ABC/*DE+*
c. ABCD/*E+*
d. ABC*/D*E+
75. The prefix expression for the infix expressionA/B*C+D*E is
a. AB/C*DE*+
b. +*/ABC*DE
c. +*AB/C*DE
d. /+ABCDE
76. Suffix expression is
a. Infix
b. postfix
c. prefix
d. post & prefix
77. polish expression is
a. infix
b. postfix
c. prefix
d. post & prefix
78. To convert an Infix expression into postfix we require
a. stack
b. queue
c. linked list
d. dequeue
79. A stack is most suitable to evaluate _ _ _ _ _ _ _ expression
a. postfix
b. prefix
c. infix
d. post & infix
80. The circular linked list have
a. no beginning
b. no ending
c. beginning but no ending
d. no beginning and no ending
81. To insert a node at the beginning of the doubly linked list _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
82. Doubly linked list uses _ _ _ _ _ _ _ _ no.of pointers
a. Zero
b. One
c. Two
d. Three
83. To insert a node at the beginning of the single linked list _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 0
84. To insert a node at middle of the single linked list _ _ _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
85. To insert a node at the end of the doubly linked list _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
86. To insert a node at the end of the single linked list _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
87. To delete the first node in single linked list _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
88. To delete the last node in single linked list _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 0
89. To delete the middle node in single linked list _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
90. To delete an item in the middle of a circular doubly linked list, _ _ _ _ _ _ _ _ no.of points to be manipulated
a. 2
b. 4
c. 6
d. 8
91. If storage class is missing in the array definition, by default it will be taken to be
a. automatic
b. external
c. static
d. either automatic or external depending on the place of occurrence
92. To delete the last node in doubly linked list _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
93. To delete the middle node in doubly linked list _ _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
94. To insert an item in a circular doubly linked list, _ _ _ _ _ _ _ no.of points to be manipulated
a. 1
b. 2
c. 3
d. 4
95. Which of the following features of C is meant to provide reliable access to special memory
a. static _ const
b. pragma
c. volatile
d. immutable
96. To insert a node at middle of the doubly linked list _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
97. To delete the first node in doubly linked list _ _ _ _ _ _ _ _ no. of pointers to be manipulated
a. 1
b. 2
c. 3
d. 4
98. To insert an item in a circular single linked list _ _ _ _ _ _ _ _ _ no.of points to be manipulated
a. 2
b. 3
c. 4
d. 1
99. To delete an item in a circular doubly linked list, _ _ _ _ _ _ _ _ no.of points to be manipulated
a. 1
b. 2
c. 3
d. 4
100. A sorting technique is called stable if:
a. it takes O ( n log n) time
b. It maintains the relative order of occurrence of non-distinct elements
c. It uses divide and conquer paradigm
d. The maximum number of nodes in a binary tree of height h is (2 -1)(The height of the root is reckoned as 0)
101. The maximum number of comparisons needed to sort 7 items using radix sort is (assume each item is a 4 digit decimal number)
a. 280
b. 40
c. 47
d. 38
102. If each node in a tree has a value greater than every value in its left sub tree and has value less than every value in its right sub tree, the binary tree is known as
a. Complete binary tree
b. Full binary tree
c. Binary search tree
d. Threaded binary tree
103. A binary tree in which if all its levels except possibly the last, have the maximum number of nodes and all the nodes at the last level appear as far as possible, is known as
a. full binary tree
b. 2-tree
c. threaded tree
d. Complete binary tree
104. You are asked 15 randomly generated numbers. You should prefer
a. bubble sort
b. quick sort
c. merge sort
d. heap sort
105. Which data structure is needed to convert infix notation to post fix notation
a. B-tee
b. Queue
c. Tree
d. Stack
106. The time required to search an element in a binary search tree having n elements is
a. O(1)
b. O(log2 n)
c. O(n)
d. O(n log2 n)
107. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is
a. log2 n
b. n-1
c. n
d. 2n
108. A tree, for which at every node the height of its left sub tree and right sub tree differ at most by one is a/an
a. Binary search tree
b. AVL tree
c. Complete binary tree
d. Threaded binary tree
109. Which of the following sorting algorithms does not have a worst case running time complexity of O(n2)?
a. Insertion sort
b. Merge sort
c. Quick sort
d. Bubble sort
110. Which of the following is not a correct statement
a. internal sorting is used if the number of items to be sorted is very large
b. External sorting is used if the number of items to be sorted is very large
c. External sorting needs auxiliary storage
d. Internal sorting needs auxiliary storage
111. There are 4 different algorithms A1,A2,A3,A4 to solve a given problem with the order log(n),log(log(n)),nlog(n),n/log(n) respectively. Which is the best algorithm?
a. A1
b. A2
c. A3
d. A4
112. Which of the following algorithms exhibits the unusual behavior that, minimum numbers of comparisons are needed if the list to be sorted is in the reverse order and maximum numbers of comparisons are needed if they are already in sorted order?
a. Heap tree
b. Radix sort
c. Binary insertion sort
d. Selection sort
113. You want to check whether a given set of items is sorted. Which of the following sorting methods will be the most efficient if it is already in sorted order?
a. bubble sort
b. selection sort
c. insertion sort
d. merge sort
114. The way a card game player arranges his cards as he picks them up one by one , is an example of
a. bubble sort
b. selection sort
c. insertion sort
d. merge sort
115. Which of the following sorting algorithm has the worst time complexity of nlog(n)?
a. Heap sort
b. Quick sort
c. Insertion sort
d. Selection sort
116. Which of the following sorting methods sorts a given set of items that is already in sorted order or in reverse sorted order with equal speed?
a. Heap sort
b. Quick sort
c. Insertion sort
d. Selection sort
117. Which of the following sorting methods will be the best if number of swapping done, is the only measure of efficiency?
a. bubble sort
b. insertion sort
c. selection sort
d. heap sort
118. As part of the maintenance work, you are entrusted with the work of rearranging the library books in a shelf in proper order, at the end of each day. The ideal choice will be
a. bubble sort
b. insertion sort
c. selection sort
d. heap sort
119. Sorting is not useful for
a. report generation
b. minimizing the storage needed
c. making searching easier and efficient
d. responding to queries easily
120. A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec. it can approximately sort _ _ _ _ _ _ _ _ _ names
a. 400
b. 800
c. 750
d. 1600
121. A machine needs a minimum of 100 sec. to sort 1000 names by quick sort. The minimum time needed to sort 100 names will be approximately
a. 50.2 sec
b. 6.7 sec
c. 72.7 sec.
d. 11.2 sec.
122. A sorting method with _ _ _ _ _ _ _ _ is the most efficient method
a. O(log n)
b. O(n)
c. O(1)
d. O(n2)
123. Which of the following statement is false?
a. Optimal binary search construction can be performed efficiently using dynamic programming
b. Breadth-first search cannot be used to find connected components of a graph
c. Given the prefix and postfix walks of a binary tree, the binary cannot be uniquely reconstructed
d. Depth-first search can be used to find the connected components of a graph
124. The average successful search time for sequential search on 'n' items is
a. n/2
b. (n-1)/2
c. (n+1)/2
d. log(n)+1
125. A hash function f defined as f(key)=key mod 7, with linear probing, is used to insert the keys 37,38,72,48,98,1,56, into a table indexed from 0 to 6. What will be the location of key 11?
a. 3
b. 4
c. 5
d. 6
126. The order of the binary search algorithm is
a. n
b. n2
c. nlog(n)
d. log(n)
127. Linked lists are not suitable for implementing
a. insertion sort
b. binary search
c. radix sort
d. polynomial manipulation
128. Stack is useful for
a. radix sort
b. breadth first search
c. heap sort
d. depth first search
129. Which of the following algorithm design technique is used in the quick sort algorithm?
a. Dynamic programming
b. Backtracking
c. Divide and conquer
d. Greedy method
130. The average successful search time taken by binary search on a sorted order array of 10 items is
a. 2.6
b. 2.7
c. 2.8
d. 2.9
131. A 3-ary tree in which every internal node has exactly 3 children. The number of leaf nodes in such a tree with 6 internal nodes will be
a. 10
b. 17
c. 23
d. 13
132. Which of the following traversal techniques lists the nodes of a binary search tree in ascending order?
a. post-order
b. In-order
c. Pre-order
d. No-order
133. A general linear list is a list in which operations, such as retrievals, insertions, changes, and deletions can be done _ _ _ _ _ _ _ _ _
a. any where in the list
b. only at the beginning
c. only at the end
d. only at the middle
134. A(n) _ _ _ _ _ _ _ is a collection of elements and relationship Among them.
a. abstract data type
b. array
c. data structure
d. standard type
135. Data that consists of a single, non decomposable entity are known as _ _ _ _ _ _
a. atomic data
b. array
c. data structure
d. standard type
136. A binary tree has n leaf nodes. The number of nodes of degree 2 in this tree is
a. logn
b. n-1
c. n
d. 2n
137. A full binary tree with n leaf nodes contains
a. n nodes
b. log2 n nodes
c. 2n-1 nodes
d. 2n nodes
138. The number of binary trees with 3 nodes which when traversed in post-order gives the sequence A,B,C is
a. 3
b. 9
c. 7
d. 5
139. Which of the following need not be a binary tree?
a. Search tree
b. Heap
c. AVL-tree
d. B-tree
140. A binary tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree.Such a tree with 10 leaves
a. cannot be more than 19 nodes
b. has exactly 19 nodes
c. has exactly 17 nodes
d. can not have more than 17 nodes
141. Find the odd man out
a. binary tree
b. Avl tree
c. graph
d. queue
142. The depth of a complete binary tree with n nodes(log is to the base two)
a. log(n+1)-1
b. log(n)
c. log(n+1)+1
d. log(n)+1
143. The following is an example of a non-linear data structure
a. stack
b. queue
c. tree
d. linear list
144. If a graph is represented as a linked list, _ _ _ _ _ _ _ _ _ no.of list nodes are required
a. 1
b. 2
c. 3
d. 4
145. The number of possible binary trees with 4 nodes is
a. 12
b. 14
c. 13
d. 15
146. The number of possible binary trees with 3 nodes is
a. 12
b. 13
c. 5
d. 15
147. The number of possible ordered trees with 3 nodes A,B,C is
a. 16
b. 12
c. 6
d. 10
148. A tree is a _ _ _ _ _ data structure
a. non-recursive
b. recursive
c. linear
d. non-linear
149. A node that does not have any sub-tree is called a _ _ _ _ _ _ _
a. terminal node
b. root node
c. left node
d. right node
150. The number of edges in a regular graph of degree d and n vertices is
a. maximum of n, d
b. n+d
c. nd
d. nd/2
151. Which of the following algorithms solves the all pair shortest path problem?
a. Diskstra's algorithm
b. Floyd algorithm
c. Prim's algorithm
d. Warshall's algorithm
152. The minimum number of colors required to color a graph having n (n>3) vertices and 2 edges is
a. 4
b. 3
c. 2
d. 1
153. The maximum degree of any vertex in a simple graph with n vertices is
a. n
b. n-1
c. n+1
d. 2n-1
154. A graph G with n nodes is bipartite if it contains
a. n edges
b. a cycle of odd length
c. no cycle of odd length
d. n2 edges
155. A graph can be represented as an _ _ _ _ _ _
a. Linked list
b. Structure
c. Union
d. Queue
156. A graph can be represented as an _ _ _ _ _ _
a. Array
b. Structure
c. Union
d. Queue
157. The minimum number of edges in a connected cyclic on n vertices is
a. n-1
b. n
c. n+1
d. n+2
158. Which of he following is useful in traversing a given graph by breadth first search?
a. Stack
b. Set
c. List
d. Queue
159. Sparse matrices have
a. many zero entries
b. many non-zero entries
c. higher dimensions
d. lower dimensions
160. The maximum no.of edges in an undirected graph with out loops with n vertices is
a. n
b. n*(n-1)
c. n*(n-1)/2
d. n-1
161. Which of the following abstract data types can be used to represent a many to many relationship
a. tree
b. graph
c. queue
d. stack
162. In a directed graph without self loops with n verices , the maximum no.of edges is
a. n
b. n*(n-1)
c. n*(n-1)/2
d. n-1
163. An n vertex undirected graph with exactly n*(n-1)/2 edges is said to be
a. Complete graph
b. Un complete graph
c. Directed graph
d. Un directed graph
164. To create a node dynamically in a singly linked list _ _ function in C is used
a. malloc()
b. calloc()
c. alloc()
d. dealloc()
165. In an undirected graph, the sum of degrees of all the nodes
a. must be even
b. is thrice the number of edges
c. must be odd
d. need not be even
166. In an undirected graph, the sum of degrees of all the nodes
a. is thrice the number of edges
b. is twice the number of edges
c. must be odd
d. need not be even
167. _ _ _ function is used to in C to dynamically allocate space for more than one object
a. malloc()
b. calloc()
c. alloc()
d. dealloc()
168. _ _ _ function is used to in C to dynamically allocate space for one object
a. malloc()
b. calloc()
c. alloc()
d. dealloc()
169. If n=2, then the value of O(n log n) is
a. 2
b. 4
c. 8
d. 16
170. Calloc(m,n); is equivalent to
a. malloc(m*n,0);
b. memset(0,m*n);
c. ptr=malloc(m*n);memset(p,0,m*n)
d. ptr=malloc(m*n);strcpy(p,0)
171. If the sequence of operations push(1),push(2) ,pop, push(1),push(2),pop, pop, pop, push(2),pop, are performed on a stack, the sequence of popped out values are
a. 2,2,1,1,2
b. 2,2,1,2,2
c. 2,1,2,2,1
d. 2,1,2,2,2
172. return type of a realloc( ) function is
a. int
b. float
c. char
d. void
173. To delete an element from a queue we use the _ _ _ _ _ operation
a. pop
b. push
c. enqueue
d. dequeue
174. To add an element to a queue we use the _ _ _ _ _ operation
a. pop
b. push
c. enqueue
d. dequeue
175. Which of the memory function allocates a contiguous memory
a. malloc( )
b. calloc( )
c. release( )
d. free( )
176. Return type of a malloc( ) function is
a. int
b. float
c. char
d. void
177. A queue is a _ _ _ _ _ _ structure
a. first in-last out
b. lasting-first-out
c. first in-first out
d. last in-last out
178. A queue is a list in which insertion can be done _ _ _ _
a. any where in the list
b. only at the beginning
c. only at the end
d. only at the middle
179. A _ _ _ _ _ _ is a first in - last out(FIFO) data structure in which insertions are restricted to one end, called the rear, and deletions are restricted to another end ,called the front
a. Stack
b. queue
c. tree
d. binary tree
180. The pointer(s) in a queue points to
a. start of the queue
b. end of the queue
c. middle of the queue
d. both start and end of the queue
181. The disadvantage of the queue is
a. when the item is deleted, the space for that item is not claimed
b. when the item is deleted, the space for that item is claimed
c. a non destructive
d. increases the memory space
182. A queue is a list in which deletion can be done _ _ _ _
a. any where in the list
b. only at the beginning
c. only at the end
d. only at the middle
183. Read() operation in queue is
a. non-destructive
b. additive
c. push()
d. destructive
184. In which of the data structure, space for the item is not claimed ,when an item is deleted
a. queue
b. circular queue
c. stack
d. linked list
185. As the items from a queue get deleted, the space for item is not reclaimed in queue. This problem is solved by
a. circular queue
b. stack
c. linked list
d. doubly linked list
186. Which of the following operation is used to add an item in a queue
a. write()
b. read()
c. pop()
d. push()
187. _ _ _ _ no.of pointers are required to implement read and write operations in a queue
a. two
b. three
c. four
d. five
188. FIFO is
a. stack
b. queue
c. linked list
d. tree
189. Which of the following operation is used to an item in a queue
a. write()
b. read()
c. pop()
d. push()
190. The number of swapping needed to sort the numbers 8,22,7,9,31,19,5,13 in an ascending order, using bubble sort is
a. 11
b. 12
c. 13
d. 14
191. Given two sorted list of size 'm' and 'n' respectively. The number of comparisons needed by the merge sort algorithm will be
a. m x n
b. maximum of m,n
c. minimum of m,n
d. m+n-1
192. For merging two sorted lists of sizes m and n into a sorted list of size m+n, requires _ _ _ _ _ _ _ _ no.of comparisons
a. O(m)
b. O(n)
c. O(m+n)
d. O(log(m)+log(n))
193. The principle of locality justifies the use of
a. interrupts
b. DMA
c. polling
d. cache memory
194. The concatenation of two lists is to be performed in O(1) time. Which of the following implementations of a list could be used?
a. Singly linked list
b. Doubly linked list
c. Circularly doubly linked list
d. Array implementation of list
195. The initial condition of a queue is
a. front=rear=-1
b. front=rear
c. front=rear=n
d. front=rear=1
196. A sorting technique that guarantees , that records with the same primary key occurs in the same order in the sorted list as in the original unsorted list is said to be
a. stable
b. consistent
c. external
d. linear
197. The average number of comparisons performed by the merge sort algorithm , in merging two sorted lists of length 2 is
a. 8/3
b. 8/5
c. 11/7
d. 1/16
198. Merge sort uses
a. divide and conquer strategy
b. backtracking approach
c. heuristic approach
d. greedy approach
199. Queue can be used to implement
a. radix sort
b. quick sort
c. recursion
d. depth first search

EXAMAPERS123.BLOGSPOT.COM

Charles Babbage 1791-1871

Charles Babbage  1791-1871

SUCCESS FOR CAREER

Charles Babbage 1791-1871

Introduction
The calculating engines of English mathematician Charles Babbage (1791-1871) are among the most celebrated icons in the prehistory of computing. Babbage’s Difference Engine No.1 was the first successful automatic calculator and remains one of the finest examples of precision engineering of the time. Babbage is sometimes referred to as "father of computing." The Charles Babbage Foundation took his name to honor his intellectual contributions and their relation to modern computers


1. Born December 26, 1791 in Teignmouth, Devonshire UK, Died 1871, London; known to some as the “Father of Computing” for his contributions to the basic design of the computer through his Analytical machine. His previous Difference Engine was a special purpose device intended for the production of tables.
2. Charles Babbage developed the Analytical Engine project after an earlier computing project the difference engine that Babbage started in 1822.
3. The Difference Engine could solve polynomial equations using a numerical method called the “Method of Differences”. However the analytical engine was the first general computational device, with the ability to solve different types of equations.
4. In 1823, He was started work on the Difference Engine through finding from the British Government. It was the significant event in his life.
5. The parts of the Difference Engine that had seemed possible of completion in 1830 gathered dust in the Museum of King’s College. He was an amazing intelligence.
6. The inventions of Charles Babbage were the cowcatcher, dynamometer, standard railroad gauge, uniform postal rates, occulting lights for lighthouses, Greenwich time signals, heliograph ophthalmoscope. He also had an interest in cyphers and lock-picking, but abhorred street musicians.
7. Babbage investigated biblical miracles. ”In the course of his analysis”, wrote B.V.Bowden in Faster than Thought , “he made the assumption that the chance of a man rising from the dead is one in 10^12”. Miracles are not, as he wrote in Passages From the Life of a philosopher, “the breach of established laws, but…. Indicate the existence of far higher laws”.

EXAMAPERS123.BLOGSPOT.COM

Basic structure of c- programmme

Basic structure of c- programmme

Documentation section(comment section)
Link section
Define section
Global declaration section
Main( ) ------- main function section
{

Declaration part
Executable part
}

Sub program section
Function 1
Function 2
Function 3 [ user defined functions]
--- ---- ----- ----
--- -------- -----
Function n

C program can be viewed as a group of building blocks called functions. A function is a sub routine that may include one or more statements designed to perform a specific task. To write a C program first creates function and then put them together .C program may contain one or more sections.

Documentation section :
Documentation section consists of a set of comment lines giving the name of the program, author, date and other details.

Line section :
Line section provides the instructions to the compiler to link functions from the system library.
Definition section:
Defines all symbolic constants.

Global declaration section:
There are some variables that are used in more than one function such variables are called global variables and are declared in global declaration i.e., outside of all the functions. The variables which is defined in function is called local variable(private variable).

Main function:
Declaration part
Executable part (input, arithmetic, output, control statements etc)

Sub program section :
This section contains all the user defined functions that are called in the main function. User defined functions are generally placed immediately after the main function although they may appear in any order.

Rules ;

1) each and every instruction in a C program is written in a separate statement, A complete C programme comprises a series of statement. The statements must appear in same order in which we wish them to be executed.
2) Usually all statements are entered in small case letters.
3) C has no specific rules for the position at which the statement is to be written that’s why it is often called free form language.
4) Every statement should always end with a semi colon.

Relational operators : 21/9/07
Symbol Associativity Description
> Left to right Is greater than
>= Left to right Is greater than or equal
< Left to right Is less than
<= Left to right Is less than or equal
== Is equal to
!= or <> Not equal

Note : the value of a relational expression is either non-zero
value (1) or zero value.
It is one if the specified relation is true and zero if specified relation is false.

Logical operators :

Symbol Associativity Description
&& Left to right Expressions must be satisfied
|| Left to right Any one of expression must be satisfied.
! (exclamatory) Right to left These operators reverse the value of an expression. It makes true expression as false and false expression as true.




Truth table :

Op-1 Op-2 Value of the
op1&&op2 Value of the
op1 || op2
Non-zero Non-zero Non-zero Non-zero
Non-zero zero zero Non-zero
Zero Non-zero zero Non-zero
Zero zero zero Zero


Note :
Like simple relational expressions, A logical expressions yields a value of one or zero.

6) Bit wise operators :
‘C’ as a distinction of supporting a special operator
known as operators. For manipulation of data at bit-level. These operators are used for testing the bits or shifting them from right to left.
Note: Bit wise operators maynot be applied to float or double.

Operator Meaning
&(amposand) Bitwise and
|(pipe) Bitwise or
^(carot) Bitwise exclusive or
<< Shift left
>> Shift right
Special operators :

Special operators are comma(,) operator,size of ( ) operator.
Syntax: sizeof (datatype);
Pointer operators are & and * and
Member selection operators -> and .
Example of comma operator :
X=(a-5,b=6,a+b);

Note : ANSI commity has introduce two pre processor operators string as “string zing” and “token pasting”
The operators are # and ## .

Control structures in C :-

Decision control structure or Bi directional conditional structures :-
There are three types of IF statements
1) simple if (simple conditional statements)
2) multiple if or if ladder (multiple conditional statements)
3) nested if (nested conditional statements)
C uses the keyword ‘IF’ to implement the decision control instruction the keyword if tells the compiler that what follows is the decision control instruction.
The condition following the keyword is always enclosed with a pair of parenthesis . if the condition is true the statement is executed and if the condition is false then the statement is not executed instead the program skips.

I syntax :-
If ()
{
Statements ;
}
Statements x;
Or
If ()
Statements ;
II syntax :
If ()
Statements ;
Else
Statements;
Statements x;
III syntax :
If()
{
Statements ;
}
Else
{
Statements ;
}
Statements x;


The if statement by itself will execute a single statement or a group of statements.
1) The group of statements of the if and not included else is called if block statement.
2) Similarly the statement after the else called else block statement.


Accept any two integer values and find whether the two integers are equal or not . ?

Program :

/* Equal of two numbers created on 22-09/07 */

#include
#include
main()
{
int x=0,y=0;
clrscr();
printf("enter x integer value :");
scanf("%d",&x);
printf("enter y integer value:");
scanf("%d",&y);
if(x==y)
printf("Both numbers are equal ");
else
printf("not equal");
getch();
return 0;
}


Accept any two integers and find the biggest value ? 22/9/07

Program :

/* Biggest of two numbers created on 22-09/07 */

#include
#include
main()
{
int x=0,y=0;
clrscr();
printf("enter x integer value :");
scanf("%d",&x);
printf("enter y integer value:");
scanf("%d",&y);
if(x>y)
printf("X is biggest ");
else
printf("Y is biggest");
getch();
return 0;
}

Case studies :
1) Accept any integer value and find whether the given integer is positive or negative.
program

/* To find the integer value is positive or negative */

#include
#include
main()
{
int a=0;
clrscr();
printf("enter integer value ");
scanf("%d",&a);
if(a>0)
printf("the integer value %d is positive ");
else
printf("the integer value %d is negative");
getch();
return 0;
}

2) Accept any integer value and find whether the given integer is even or odd?
Program :
/* To find the integer value is even or odd created on 23-09-07 */

#include
#include
main()
{
int x=0;
clrscr();
printf("enter integer value ");
scanf("%d",&x);
if(x%2==0)
printf("the integer value %d is an even number");
else
printf("the integer value %d is an odd number");
getch();
return 0;
}


3) Accept any alphabatical value and find whether the given alphabet is vowel or consonant ?
Program 24/09/07

/* To find the given character is vowel or consonant created on 24/9/07*/

#include
#include
main()
{
char x;
clrscr();
printf("enter a character\t");
scanf("%c",&x);
if(toupper(x)=='A'||toupper(x)=='E'||toupper(x)=='I'||toupper(x)=='O'||toupper(x)=='U')

[( or ) /* if(x=='a'||x=='A'||x=='e'||x=='E'||x=='i'||x=='I'||x=='u'||x=='U'||x=='o'||x=='O')]
*/ printf("it is a vowel");
else
printf("it is a consonant");
getch();
}
Program : 24/9/07
/* To find the character which is in upper case or lower case by using three methods */
/* created on 24/09/07 */

#include
#include
main()
{
char n;
clrscr();
printf("enter the character:\t");
scanf("%c",&n);
if(isupper(n))
printf("the given character is upper case letter");
else
printf("the given character is lower case letter");
/* SECOND METHOD

if(n>=65&&n<=90)
printf("the given character is uppercase letter");
else
printf("the given character is lowercase letter ");

THIRD METHOD

if(n>='A'&&n<='Z')
printf("the given character %c is uppercase letter");
else
printf("the given characte %c is lowercase letter");*/
getch();
return 0;
}



2) Multiple if(the if else ladder) :-
Syntax :
If()
{
Statements ;
}
Else if()
{
Statements;
}
Else if()
{
Statements;
}
- - - -- - - - - - - - - - -
- - - - - - - - - - - -
- - - - - - - - -- - - -
- ------ - - - - - - - -

Else
{
Statements;
}
Statements x;

There is another way putting if’s together when multiple path decisions are involved. A multiple path decision is a chain of if’s , if the statement associated with each else is as on if.
Program :
/* ABC sales data created on 24/09/07 */

#include
#include
main()
{
int ino=0;
unsigned int qty=0;
float r=0,dp=0.00,amt=0,damt=0,net=0;
/* dp=discount percent,damt=discount amount */
char iname[15];
clrscr();
printf("enter the item number :");
scanf("%d",&ino);
printf("enter the item name :");
scanf("%s",&iname);
printf("enter the quantity of particular item : ");
scanf("%u",&qty);
printf("enter the rate of the item :");
scanf("%f",&r);
amt=qty*r;
if(amt>=20000)
dp=0.1;
else if(amt>=10000&&amt<20000 br=""> dp=0.07;
else if(amt>=5000&&amt<10000 br=""> dp=0.05;
else
dp=0.02;
damt=amt*dp;

/* {
damt=(amt*0.1);
printf("the discount of the item is gives 10percent %f" ,damt);
}
else if(amt>=10000 && amt<20000 br=""> {
damt=(amt*0.07);
printf("the discount of the item gives 7percent is %f",damt);
}
else if(amt>=5000&&amt<10000 br=""> {
damt=(amt*0.05);
printf("the discount of the item gives is 5percent is %f",damt);
}
else
{
damt=(amt*0.02);
printf("the discount of the item is gives 2percent is %f",damt);
} */
net=amt-damt;
printf("\nthe total amount is %f\n the discount received is %f \ndiscount percent is%f \n total net is %f",amt,damt,dp,net);
getch();
return 0;
}


Gotoxy(C,R) : 25/9/7
This function will help us to keep the cursor at a desired location with in the limits of text mode x-columns, y-rows(80 columns,25rows
Program :
/* To calculate the electricity bill created on 25-9-07 */

#include
#include
main()
{
int cr=0,pr=0,nou=0;
float R=0,bill=0;
char mno[5],cname[20];
clrscr();
gotoxy(32,4);
printf("ELECTRICITY BILL ");
gotoxy(60,4);
printf("DATE :25/09/2007");
gotoxy(5,5);
printf("*******************************************************************");
gotoxy(5,7);
printf("Enter meter no :");
gotoxy(50,7);
printf("Enter Cname :");
gotoxy(5,8);
printf("********************************************************************");
gotoxy(32,9);
printf("Enter CR :");
gotoxy(32,11);
printf("Enter PR :");
gotoxy(5,13);
printf("********************************************************************");
gotoxy(5,15);
printf("No.of.Units :");
gotoxy(32,15);
printf("Rate :");
gotoxy(50,15);
printf("Bill :");
gotoxy(5,17);
printf("*********************************************************************");
gotoxy(32,19);
printf("THANK Q");
gotoxy(22,7);
scanf("%s",mno);
gotoxy(64,7);
scanf("%s",cname);
gotoxy(42,9);
scanf("%d",&cr);
gotoxy(42,11);
scanf("%d",&pr);
nou=cr-pr;
if(nou>=800)
{
R=5.50;
}
else if(nou>=600&&nou<800 br=""> {
R=3.50;
}
else if(nou>=300&&nou<600 br=""> {
R=2.50;
}
else if(nou>=100&&nou<300 br=""> {
R=1.50;
}
else
{
R=1.00;
}
bill=nou*R;
gotoxy(24,15);
printf("%d",nou);
gotoxy(44,15);
printf("%f",R);
gotoxy(60,15);
printf("%f",bill);
getch();
return 0;
}

EXAMAPERS123.BLOGSPOT.COM

'ARRAYS' in C LANGUAGE

'ARRAYS' in C LANGUAGE

HIGH-LEVEL LANGUAGES

So far, it has been necessary to know how many items are to be stored and to declare a variable for each item. Further more, if a large amount of data is to be stored, would be a long and tedious task to think of a separate variable name for each data, and then to type the declaration for each one of these variables.

Arrays are the solution to this problem. They are such an important part of the art of programming that they are included in every

What is an Array?
In C, as in other computer languages, it is possible to assign a single name to a whole group of similar data. For example, if we are interested in a large number of recorded Celsius temperature, we can assign a common name such as C_temp to all of the data. Then we can refer to each element in terms of its position within the list of items. This is done in mathematics, as well as in computer programming, using an entity called an array.

An array is a group of elements that share a common name and that are differentiated from one another by their positions within the array. For example, if we have five numbers, all of which are named x, they may be listed:

X
58
63
49
18
7

The position of each of these elements can be indicated by means of a subscript:

X1 = 58
X2 = 63
X3 = 49
X4 = 18
X5 = 7

In mathematics, a subscript is a number written to the right of the variable name, slightly below the line, and usually in small type. The subscript indicates the position of the particular element with respect to the rest of the elements.

For those movie buffs who are fans of the old Charlie Chan detective movies, you will remember that whenever it became necessary for Mr. Chan to introduce his sons to clients, he would always introduce them as: “This is my number one son…my number two son….” Etc. It is clear from this that even though computers were made, Mr. Chan actually resorted to the method of introducing his sons by their subscripts!

Since it is impossible to display subscripted numbers on the standard computer terminal, the usual recourse is to enclose the subscript in parentheses or brackets. In C (as in Pascal), square brackets are used. The following five statements are valid in C.
X[1] = 58;
X[2] = 63;
X[3] = 49;
X[4] = 18;
X[5] = 7;
HOW ARRAYS ARE USEFUL
To see the usefulness of arrays, consider the problem of reading the age of 5 persons, printing them out individually and computing the average. Here is a solution that does not use arrays.

#include
main()
{
int a1, a2, a3, a4, a5;
float sum=0;
printf (“Age:”);
scanf(“%d”, &a1);
sum += a1;
printf (“Age:”);
scanf(“%d”, &a2);
sum += a2;
printf (“Age:”);
scanf(“%d”, &a3);
sum += a3;
printf (“Age:”);
scanf(“%d”, &a4);
sum += a4;
printf (“Age:”);
scanf(“%d”, &a5);
sum += a5;
printf (“The ages that were input are:\n”);
printf(“%d\n”, a1);
printf(“%d\n”, a2);
printf(“%d\n”, a3);
printf(“%d\n”, a4);
printf(“%d\n”, a5);
printf (“Average =%f\n”, sum /5);
}
The program is very simple. It reads the ages of 5 persons, adds them up in a variable called sum, and at the end, divides sum by 5 to get the average age. Needless to say, this is a very clumsy way to write a program. If there are a large number of persons, the number of statements increases proportionately. To avoid this, use a loop. But the problem is that different variables are needed to store the ages of different persons and hence, the loop will have to store and print different variables each time. A more elegant way is to use an array of integers to store the ages, as shown in the example below. Notice the declaration of the array variable in the first line of main().

#include
void main()
{
int age[5]; /* Array of 5 ages, declaration for an array */
int i, n;
float sum = 0;
printf (“Number of persons:”);
scanf(“%d”, &n);
if (n<=0 || n>5)
printf (“Invalid number of persons entered.\n”);
else
{
for (i=0; i {
printf (“Age:”);
scanf(“%d”, &age[i]);
sum += age[i];
}
printf (“the ages input are :\n”);
for (i=0; i printf (“%d\n”, age[i]);
printf (“The average is : %f\n:, sum /n);
} /* end main */
Run
Number of persons: 5
Age: 10
Age: 20
Age: 30
Age: 40
Age: 50
The ages input are:
10
20
30
40
50
The average is : 30.000000

(i) Declaration
The previous program is examined now. Recall that all variables in C must be declared before use. Hence, we must first declare the array. It is done at the beginning of the function main() with the statement
int age[5];

This statement states that age is an array of 5 integers. Note the use of square braces after the array name (i.e., age) enclosing the integer 5 that gives the number of elements in the array. This statement reserves enough memory for age to hold 5 integers. Once the declaration is made, ag [0] refers to the first integer in the array, age [1] refers to the second integer and so on. Finally, age [4] refers to the last integer in the array. In C, array indices always begin with zero. Figure 7.1 shows the declaration of an array.

Fig. 7.1 Array definition

(ii) Accessing array elements
To access a particular element in an array, specify the array name, followed by square braces enclosing an integer, which is called array index. The array index indicates the particular element of the array which we want to access. The numbering of elements starts from zero (i.e. age[0] is the age of the first person). Figure 7.2 depicts the elements of an array in memory. It is assumed that each element of the array (i.e., each integer) occupies two bytes.

Next, observe the loop used to input the elements. It is reproduced here for convenience.

for (i=0; i {
printf (“Age:”);
scanf(“%d”, &age[i]);
sum += age[i];
}

The variable i was from 0 to n-1 (0 to 4 in the above sample run). The function scanf is called to input an integer value. The address of the ith element is passed to scanf. This makes scanf store the integer input into successive integer positions each time the loop is executed. Note that
&age[i];
in the scanf statement refers to the memory location of the integer at the ith position.

The statement
sum+= age[I];
adds the value of the ith integer to sum.

The rest of the program illustrates the use of the array variable in various situations. The first for loop is used to add to the variable sum, and in the second, to print out the values of age that are input.

An element such as age[i] can be used just like any other ordinary integer. Statements such as





Fig 7.2 Elements of the array age

age[i]++; (to increment the value of the ith integer in the array age) and age [i]=11; are perfectly valid.

(iii) Initialization of single dimensional array
Arrays can be initialized once they are declared. The declaration of an array can be done as follows:

int a[5] = { 13, 34, 2, 6, 234 };

Here, a is an array of 5 integers. The initial value of the five integers are specified in order, between the curly braces, separated by commas. The above declaration causes a [0] to be initialized to 13, a[1] to 34 and so on, till a [4], which is initialized to 234. A semicolon always follows the closing brace.

The array size may be omitted during declaration, as shown below.

int a[] = {13, 34, 2, 6, 234};

This declaration is equivalent to the first one. In this case, the subscript is assumed to be equal to the number of elements in the array (5 in this case). Figure 7.3 shows the initialization of an array.

Fig. 7.3 Array Initialization
(iv) Warning
C does not check the validity of the subscript when you use arrays. For example, take a look at the program below:

void main()
{
int a[40];
a[50] = 11;
a[50]++;
}

In essence, the program declares a as an array of 40 integers, and then modifies the 51st element! When you compile the above program, you do not get any error. The executable code is produced. When it is run, the results are unpredictable. Hence, we must be very careful while using array subscripts. A wrong subscript in a large program can cause it to behave erratically, demanding a lot of debugging time.

Similar to an array of integers, we can have an array of any data type. For example, the declaration for an array of 50 floating-point numbers is:
float f[50];
The individual floating-point numbers in this array are accessed as before, i.e., f[0] is the first floating-point number and f(49) the last.

(v) Name of the array
Take the case where f is an array of floating point numbers. It is declared as:

float f[50];

The name of the array is f. If it is used as it is, without any subscript, then it refers to the memory location of the first floating-point number in the array. Recall that placing an ampersand (&) before a variable name refers to its memory location. Thus, the array name f is equivalent to &f[0]. The statement

scanf(“%f”, &f[0]);
is equivalent to
scanf(“%f”, f);

Perhaps, this may not seem to be very useful now. But its potential will be made evident later, in the chapter on pointers.

SUCCESS FOR CAREER

Example 7.1
An example to find out the largest and smallest element in an array is illustrated below:

/* large1.c: largest and smallest element in the vector */
#include
main()
{
int i,n;
float a[50], large, small;
printf (“Size of vector ?”);
scanf (“%d, &n);
printf (“\n Vector elements?\n”);
for (i=0; i scanf (“%f”, &a[i]);

/* Initialization */
large = a[0];
small = a[0];
/* largest and smallest elements */
for (i=l; i {
if(a[i] > large)
large = a[i];
else if (a[i] < small)
small = a[i];
}
printf (“\n Largest element in vector is %8.2f\n”, large);
printf(“\n Smallest element in vector is %8.2f\n”, small);
}

Run:
Size of vector ? 7
Vector elements ?
3.400 -9.00 12.00 10.00 -6.00 0.00 36.00
Largest element in vector is 36.00
Smallest element in vector is -9.00

Example
/* sort.c: sorting the vector elements in ascending order */
#include
main ()
{
int i,j,k,n;
float a[50], temp;
printf (“Size of vector ?”);
scanf(“%d”, &n);
printf (“\n Vecntor elements ?\n”);
for (i=0; i scanf(“%f”, &a[i]);
/* sorting vector A using selection sort */
for (i=0; I for(j=i+l;j {
/* To sort in descending order change the ‘>’ */
/* operator to ‘<’ in the IF structure */
if (a[I] < a[j])
{
temp = a[i];
a [i] = a[j]
a[j] = temp;
}
}
printf (“\n Vector elements in ascending order: \n”);
for (i=0; i printf (“%8.2f’,a(i]);
}
Run:
Size of vector ? 8
Vector elements ?
91.00 20.00 1.00 7.00 34.00 11.00 -2.00 6.00
Vector elements in ascending order:
-2.00 1.00 6.00 7.00 11.00 20.00 34.00 91.00

Example

/* insert.c: inserting an element into an vector */
#include
main()
{
Int i,j,k,n,pos;
float a[50], item;
printf (“size of vector ?”);
scanf(“%d”,&n);
printf(\n vector elements ? \n”);
for (i=0; i scanf (%f”, &a[i];
printf (“\n element to be inserted ?”);
scanf (“%f”, &item);
printf (“\n position of insertion ? “);
scanf (“%d”, &pos);
/ * Pushing down elements */
n++;
for (k=n; k>=pos; k--_
a[k] = a[k-1];
a[--pos] = item; /* item inserted */
printf (“\n Vector after insertion : \n”);
for (i=0; i printf (“%6.2f”, a[i]);
printf (“\n”);
}

Run:
Size of vector? 6
Vector elements ?
1.00 2.00 3.00 4.00 5.00 6.00
Element to be inserted ? 10.00
Position of insertion ? 1
Vector after insertion :
10.00 1.00 2.00 3.00 4.00 5.00 6.00

Run 2:
Size of vector? 5
Vector elements ?
1.00 2.00 4.00 5.00 6.00
Element to be inserted ? 3.00
Position of insertion ? 3
Vector after insertion :
1.00 2.00 3.00 4.00 5.00 6.00

7.3 MULTIDIMENSIONAL ARRAYS
Often, there is a need to store and manipulate two-dimensional data structures such as matrices and tables. Here, the array has two subscripts. One subscript denotes the row, and the other, the column. As before, all subscripts (row and column) start with 0.

(i) Declaration
The declaration of a two-dimensional array is as follows:
float m[10][20];
Here, m is declared as a matrix having 10 rows (numbered 0 through 9) and 20 columns (numbered 0 through 19). The first element in the matrix (the element at the first row and first column) is:
m[0] [0]
and that at the last row and last column is:
m[9] [19]

(ii) Elements of multidimensional arrays
A two dimensional array marks [4] [3] is shown Figure 7.4. The first element is given by marks [0] [0] which contains 35.5, the second element is marks [0] [1] and contains 40.5 and so on. Figure 7.5 is a pictorial representation of the two dimensional array marks as stored in the memory.


Fig 7.4 Two dimensional matrix: marks [4] [3]




Fig 7.5 Two dimensional array to store marks

Note: The declaration of a two dimensional array, for example, m[10] [20] may be confusing to those who are familiar with other languages such as FORTRAN, where the array subscripts are separated by a comma. Consider the following program typed by a confused programmer.



# include
void main( )
{
int m[10] [20];
m[5] [16] = 13;
printf (“%d\n”, m[5,16]);
}

The first two lines in main() are fine, but the third line wrongly uses a comma inside the square braces, instead of enclosing the two subscripts separately. The danger lies in the fact that comma is an operator in C. Recall that the comma operator causes the expressions to be evaluated from left to right, and the value of the right most expression becomes the value of the entire expression containing the comma operators. In this case, the result of the expression with 5,16 inside the square braces, evaluates to 16 and hence, the printf statement shown above is equivalent to:
printf(“%d\n”, m[16]);

But since the array m is two dimensional, one would feel that m[16] would give a compile time error. But this is not so, since m[16] actually refers to the memory location of the first element in the 17th row. Even though there is no 17th row, C does not check this fact. So there will be no compile time errors on this account. At run time, instead of 13, some other number may get printed, or the program may crash. Needless to say, such errors made in a large program are difficult to detect.

(iii) Accessing two dimensional array elements
The elements of a two dimensional array can be accessed by the following expression:
marks [i][j]
where i refers to the row number and j, the column number.

(iv) Initializing two dimensional arrays
Initialization of a two-dimensional array during declaration is done by specifying the elements in row major order (i.e., with the elements of the first row in a sequence, followed by those of the second, and so on). An example is given below:

int two_dim_int[3] [4] =
{
{1, 2, 3, 4},
{2, 3, 4, 5},
{5, 6, 7, 8}
};

The variable two_dim_int is declared as a two dimensional integer array with certain initial values. The first subscript can be omitted. For example, the declaration below wherein the number of rows(3) is not explicitly specified, is equivalent to the previous one.
int two_dim_int[ ] [4] =
{
{1, 2, 3, 4},
{2, 3, 4, 5},
{5, 6, 7, 8}
};

Also, the inner braces can be omitted, giving the numbers in one continuous sequence. For example, has the same effect as the previous example, but is not as readable as before.

(v) Passing arrays to functions
Arrays can be passed as arguments to functions. Consider the following example:

/* arrfunc.c: passing arrays to functions */
#include
const int Rollno =4;
const int Subject = 3;

/* function declaration */
void display (float marks [Rollno] [Subjects]);

main()
{
float marks [Rollno] [Subjects] =

/* array initialization */
{
{35.5, 40.5, 45.5},
{50.5, 55.5, 60.5},
{65.0, 70.0, 75.5}
{80.0, 85.0, 90.0}
};
/* function call with array as an argument */
display (marks);
} /* end main */
/* function definition to display elements */
void display (float Studentmarks [Rollno] [Subjects])
{
int r,s;
for (r=0; r {
printf (“\n Rollno %d”);
for (s=0; s printf (“%10.24”, Studentmarks [r] [s]);
} /* end for */
} /* end display */

The function declaration in the above program,
void display (float marks [Rollno] [Subjects]);
can also be written as,

void display (float marks [ ] [Subjects]);

The function display visualizes marks as an array, where the number of columns is Subjects. While calling the function, the name of the array is sufficient as an argument. Hence, the function call in main is of the form:
display (marks); /* function call */

The name marks represents the memory address of the array and is similar to using a reference argument. Elements of an array are not copied but the function works with a different name, on the original array itself. Hence, any modifications done to the array in the function are reflected in the array of the caller too. Passing by reference is efficient, as arrays can be very large and copying the entire array into a function consumes time and memory.

The function definition.
void display (float StudentMarks [Rollno] [Subject])
uses the name of the array, datatype and their sizes. Inside the function the elements of the array are accessed by:
studentmarks [r][s]

Example

/* addmat.c: program to add tow matrices */
#include
main()
{
int a[10] [10], vb[10] [10], c[10] [10], i,j,m,n,p,q;
printf (“Input row and column of A matrix \n”);
scanf(“%d %d”, &n, &m);
printf (“Input row and column of B matrix \n”);
scanf(“%d %d”, &p, &q);
/* checks if matrices can be added */
if(n==p)&&(m==q))
{
printf(“matrices can be added\n”);
printf(“Input A-matrix\n”);
for(i=0; i for(j=0; j scanf(“%d”, &a[i][j]);
pritnf (“Input B-matrix \n”);
for(i=0; i for(j=0; j /* Addition of two matrices */
for(i=0; i for(j=0; j c[i][j] = a[i][j] + b[i][j];
printf (“sum of A and B matrices :\n”);
for (i=0, i {
for (j=-; j printf (“%5d”,c[i][j]);
printf(“\n”);
}
} /* endif */
else
printf (“matrices cannot be added \n”);
} /* main */

Run 1:
Input row and column of A matrix
3 3
Input row and column of B matrix
1 2
Matrices cannot be added

Run 2:
Input row and column of A matrix
3 3
Input row and column of B matrix
3 3
Matrices can be added

Input A-matrix
1 2 3
4 5 6
7 8 9

Input B-matrix
1 2 3
4 5 6
7 8 9

Input A and B-matrix
2 4 6
8 10 12
14 16 18

Example
/* trace.c: Trace of the matrix */
#include
main()
{
int a[10] [10], i,j, n, trace;
printf (“Enter the order of A matrix \n”);
scanf (“%d”, &n);
printf (“Input A-matrix\n”);
for (i=0; i for (j=0; j scanf (“%d”, &a[i[ [j]);
/* Trace = Sum of the diagonal elements of the matrix */
trace = 0;
for (i=0; i trace += a[i] [i];
printf (“trace = %d \n”, trace);
} /* main */

Run:
Enter the order of A matrix
3
Input A-matrix
1 2 3
4 5 6
7 8 9
Trace = 15

Example

/* mult.c: program to multiply tow matrixes */
#include
main()
{
int a [10] [10], b [10] [10], c[10] [10], i,j, m,n,ip,k,p,q;
printf (“Input row and column of A matrix :”);
scanf (“%d %d”, &m,&n);
printf (“Input row and column of B matrix:”);
scanf (“% %d, &k, &q);
if (n==k)
{
printf (“matrices can be multiplied \n”);
printf (“resultant matrix is %d X %d\n”,m,q);
printf (“input A-matx \n”);
read_mat (a,m,n);
printf(“Input B-matrix \n”);
/* function call to read the matrix */
read_mat(b,k,q);
/* Multiplication of two matrices */
for (i=0; i for )j=0; j {
c[i] [j] = 0;
for(ip=0; ip c[i] [j] = c[i] [j] + a[i] [ip] * b[ip] [j];
}
printf (“Resultant of A and B matrices :\n”);
write_mat (c,m,q);
} /* end if */
else
{
printf (“Col of matrix A must be equal to row of matrix B \n”);
printf (“matrices cannot be multiplied \n”);
} /* end else */
} /* End of main */
/* function re ad matrix */
read_mat(a,m,n)
int a[10] [10], m,n;
{
int i,j;
for (i=0; i for (j=0; j scanf (“%d”, &a[i] [j]);
}
/* function tow rite the matrix */
write_mat (a,m,n)
int a [10] [10], m,n;
{
int i,j;
for (i=0; i {
for (j=0; j printf (“%5d”, a[i] [j]);
printf (“\n”);
}
}

Run 1:
Input row and column of A matrix: 3 3
Input row and column of B matrix: 3 3
Matrices can be multiplied
Resultant matrix ix 3 X3
Input A-matrix
1 2 3
4 5 6
7 8 9

Input B-matrix
1 2 3
4 5 6
7 8 9
Resultant of A B matrices :
30 36 42
66 81 96
102 126 150
Run 2:
Input row and column of A matrix: 1 2
Input row and column of B matrix: 3 4
Col of matrix A must be equal to row of matrix B
Matrices cannot be multiplied
Example
/* trans.c: Transpose of a matrix */
#include
main()
{
int a [10] [10], b[10] [10], i,j,m,n;
printf (“Input row and column of A matrix:”);
scanf (“%d %d”, &n, &m);
printf (“\n Inpute A-matrix \n”);
for (i=0; i for (j=0; j scanf (“%d”, &a[i] [j]);
/* the rows and columns are interchanged: transpose */
for (i=0; i for (j=0; j b[i] [j] = a[j] [i];
printf (“\n Transpose of matrix A is :\n”);
for (i=0; i {
for (j=0; j printf (“%6d”, b[i] [j]);
printf (“\n”);
}
} /* main */

Run:
Input row and column of A matrix : 3 4
Input A-matrix
1 2 3 4
5 6 7 8
9 6 7 8

Transpose of matrix A is :
1 5 9
2 6 6
3 7 7
4 8 9

STRINGS
Strings are arrays of characters, i.e., they are characters arranged on e after another in memory. To mark the end of the string. C uses the null character. Strings in C are enclosed within double quotes. So, for example,
“My age is 2 (two)”
is a string. The string is stored in memory as ASCII codes of the characters that make up the string appended with 0 (ASCII value of null). ASCII values of all characters are given in Chapter 14, with the help of which we will examine the memory occupied by the string.

Normally, each character is stored in one byte, and successive characters of the string are stored in successive bytes.

Character: M Y a g e i s 2
ASCII Code: 77 121 32 97 103 101 32 105 115 32 50 32

( t w 0 ) \0
40 116 119 111 41 0

The last character, as you can see, is the null character, having the ASCII value zero.

(i) Initializing strings
Following the discussion on character arrays (i.e., a string), the initialization of a string must have the following form, (this is similar to initializing a one dimensional array):

Char month 1[] = (‘J’, ‘a’, ‘n’, ‘u’, ‘a’, ‘r’, ‘y’, 0);
Then the string month is initialized to January. This is perfectly valid, but C offers a special way to initialize strings. The above string can be initialized as:

Char month1 [] = “January”;

The characters of the string are enclosed within a pair of double quotes. The compiles takes care of storing the ASCII codes of the characters of the string in memory and also stores the null terminator in the end. A simple program to display a string is listed below.

/* string.c: string variable */
#include
main
{
char month [15];
printf (“Enter the string”);
gets (month);
printf (“the string entered is %s”, month);
}

In this example, a string is stored in the character string variable month. The string is displayed by the statement:
printf (“The string entered is %s”, = month)

It is a one dimensional array. Each character occupies a byte. A null character (‘\0’) that has the ASCII value 0 terminates the string. Figure 7.6 shows the storage of the string January in the memory. Recall that \0 specifies a single character whose ASCII value is zero.

Fig. 7.6 String stored in a string vairable month
Example:
/* string2.c: illustration using a string literal */
#include
main ()
{
char strc [] = “This is a string literal”;
printf (“%s”, strc);
}
Run:
This is a string literal

7.5 ARRAYS OF STRINGS
An array of strings is a two dimensional array. Consider an example that initializes 5 names in an array of strings and prints them.

/* starray.c: array of strings */
#include
const int NUM = 5;
const int LENGTH = 9;
main ()
{
int j;
char Name [NUM] [LENGTH] =
(“Tejaswi”, “Prasad”, “Prasanth”, “Prakash”, “Anand”};
for (j=0; j printf (“%s\n”, Name [j]);
}
run:
Tejaswi
Prasad
Prasanth
Prakash
Anand



Fig. 7.7 Array of strings

A string is an array; and Name is an array of strings. It can be represented by a two dimensional array of size [5] [9] as shown in Figure 7.7. The second dimension LENGTH specifies the length of the longest array string (9 characters for Prasanth including the terminal character ‘\0’) and each name is accessed by Names[j]. Here, we do not need the second index. Name [j] is sufficient to access string number j in array.

7.6 FUNCTIONS IN string.h

This section describes the functions that help in manipulating strings. To use these functions, the header file string.h must be included in the program with the statement:
#include
strcat
This function concatenates two strings, i.e., it appends one string at the end of another. The function accepts two strings as parameters and stores the contents of the second string at the end of the first. An example is given below.

/* stract.c: Example program for stract */
#include
#include
void main()
{

/* Declare two strings */
char oneString [10] = “Fish”;
char twoString [] = “face”;
/* Put twoString at the end of onestring. */
strcat (oneString, twoString);
printf (oneString);
}

The output of this program is:

Fish face

The central part of the program is the statement,
Strcat (oneString, twoString);
Which places the characters of twostring at the end ofoneString.

Observe that the declaration of oneString has the subscript 10 specifying the size of the string, while the declaration of twoString does not have any size specified. Recall that in the declaration of arrays, if the subscript is omitted, it is assumed to be size of the data with which the array is initialized. So, while the size of the string oneString is 10 (which means that oneString can hold a maximum of 10 characters), the size of twoString is equal to the size of the string face. This string has 4 characters plus a null character, which makes a total of 5. So, the size of the string twoString is 5.

If we declare oneString with the statement,
Char oneString [] = “Fish”;
then oneString will be able to hold a maximum of 6 characters only. When the statement,
strcat (oneString, twoString);
appends the characters of twoString at the end of oneString, the size of oneString would not suffice. This leads to unpredictable results at run time. Hence, in the above program, onestring is declared by the statement,

char oneString[10] = “fish”;
which is safe, since after concatenation, oneString becomes Fish face, which is 10 characters in length, including the null terminator. In general, whenever you use the stract function, check to see whether the first string is large enough to hold the resultant concatenated string. Note, there is no ‘+’ operator in C that can be applied to strings in order to concatenate them. The function strcat described here exists for that purpose.

Strcomp
The function strcmp compares two strings. This function is useful while writing programs for constructing and searching strings as arranged in a dictionary. The function accepts two strings as parameters and returns an integer, whose value is:
* Less than 0 if the first string is less than the second
* Equal to 0 if both are identical
* Greater than 0 if the first string is greater than the second

The function strcmp compares the two strings, character by character, to decide the greater one. Whenever two characters in the string differ, the string which has the character with a higher ASCII value is greater. For example, consider the strings hello and Hello!!. The first character itself differs. The ASCII code for h is 104, while that for H is 72. Since the ASCII code of h is greater, the string hello is greater than the string Hello!!. Once a differing character is found, there is no need to compare the other characters of the strings. The following code fragment compares two strings and output the result.

char str[30], str2[30];
int cmpResult;
scanf(“%s %s”, str1, str2);
cmpResult = strcmp (str1, str2);
if (cmpResult<0 br=""> printf (“str1 else if (cmpResult == 0)
printf (“str1 ==2”);
else
printf (“str1 > str2”);

A sample run is shown below:

azcd abzzi
str1 > str2

Again, note that the operators <, > and == cannot be used directly with strings. To compare strings, use strcmp.

Strcpy
The strcpy function copies one string to another. The function accepts two strings as parameters and copies the second string character by character into the first one, upto and including the null character of the second string. As in the function strcat, you need to be careful to make sure that the size of the string is greater or equal to the second.

For example the following code:
char str1[] = “Will be overwritten”;
char str2[] = “Will overwrite”;
printf (“Before strcpy str1 is \n”);
printf (“%s \n”, str1);
strcpy(“str1, str2);
printf (“After strcpy str1 is \n”);
printf (“%s\n”, str1);

will output:
before strcpy stril is
Will be overwritten
After strcpy strl is
Will overwrite

The operator = cannot be used to assign one string to another. Use strcpy for this purpose.
strlen
This function returns an integer which denotes the length of the string passed. The length of a string is the number of characters present in it, excluding the terminating null character. For example,

char str[] = “Hello”;
printf (“%d\n”, strlen (str));
will output 5, since there are 5 characters in the string Hello.
More on string library functions is given in the chapter on pointers.

7.7 PROGRAMMIN EXAMPLES

Example

/* dup.c: Deleting duplicates in a Vector */
#include
main()
{
int i,j,k,n,num,flag = 0;
float a[50];
printf (“Size of vector ? “);
scanf (“%d”, &n);
num = n;
printf (“\n Vector elements ? \n”)
for (i=0; i scanf (“%f”, &a[i]);
/* removing duplicates */
for (i=0; i for (j=I+1; j {
if (a[i] == a[j])
{
n=n – 1;
for (k=j; k a[k] = a[k+1];
flag = 1;
j=j-1;
}
}
/* use of IF and ELSE statement */
if (flag == 0)
printf (“\n No duplicates found in vector \n”);
else
{
printf (“\n Vector has %d duplicates”, num –n);
printf (“Vector after deleting duplicates : \n”);
for (i=0; i printf (“% 6.2f”, a[i]);
printf (“\n”);
}
}

Run:
Size of vector 7 6
Vector elements ?
1.00 2.00 1.00 3.00 2.00 4.00
Vector has 2 duplicates
Vector after deleting duplicates:
1.00 2.00 3.00 4.00

Example
/* grade.c: Calculating grades of ‘N’ students from 3 tests */
#include
main()
{
int i,j,k,n,m;
float a[50] [10], sum, avg;
char grade [50];
printf (“Number of students ?”);
scanf (“%d”, &n);
for (i=0; i {
sum = 0.0;
printf (“\n Enter 3 scores of student-%d \n”, i+1);
for (j=0; j<3 br="" i=""> {
scanf (“%f”, &a[i][j]);
sum += a[i] [j];
}
avg = sum / 3.0;
a [i] [3] = avg;
if (avg <30 .0="" br="" else="" if..="" of="" use=""> grade [i] = ‘E’;
else if (avg <45 .0="" br=""> grade [i] = ‘D’;
else if (avg <60 .0="" br=""> grade [i] = ‘C’;
else if (avg <75 .0="" br=""> grade [i] = ‘B’;
else
grade [i] = ‘A’;
}

printf (“\n Sl.no. Scores Average Grade \n”);
printf (“\n--------------------------------------\n\n”);
for (i=0; i {
printf (“%d.”, i+1);
for (j=0; j<4 br="" j=""> printf (“%82f”, a[i] [j]);
printf (“%6c”, grade [i]);
printf (“\n”);
printf (“\n--------------------------------------\n\n”);
}
}

Run:
Number of students ? 5
Enter 3 scores of student –1
67.00 86.00 58.00
Enter 3 scores of student –2
20.00 30.00 23.90
Enter 3 scores of student –3
80.00 97.00 73.00
Enter 3 scores of student –4
56.80 47.90 62.00
Enter 3 scores of student –5
45.00 35.00 40.00

Sl.No. SCORES AVERAGE GRADE
------------------------------------------------------------------------------------------------
1. 67.00 86.00 58.00 70.33 B
2. 20.00 30.00 23.00 24.63 E
3. 80.00 97.00 73.00 83.33 A
4. 56.80 47.90 62.00 55.57 C
5. 45.00 35.00 58.00 70.33 B
------------------------------------------------------------------------------------------------

Example

/* var.c: Calculating Mean, Variance and standard deviation */
#include
#include
main()
{
int i,n;
float x[50], mean, variance, sdn;
float sumsq = 0.0, sum = 0.0;
printf (“Calculating standard deviation of a\n”);
printf (“\n Enter size of the list:”);
scanf (“%d”, &n);
printf (“\n Enter the %d items \n”, n);
for (i=0; i {
scanf (“%f”, &x[i]);
sum += x[i]);
}
mean = sum/(float) n;
/* Computing variance */
for (i=0; i sumsq = sumsq + (mean – x[i])* (mean – x[i]);
variance = sumsq/(float)n;
sdn = sqrt (variance); /* Standard deviation */
printf (“\n\n Mean of %5d items : %10.6f\n”,n,mean);
printf (“\n variance : %10.6f\n”,varaince);
printf (“\n Standard Deviation : % 10.6f\n”,sdn);
}
Run:
Calculating standard deviation of a
Enter size of the list : 7
Enter the 7 items
32.00 11.00 90.00 34.00 52.00 24.00 7.00
Mean of 7 items : 35.714287
Variance : 685.918396
Standard Deviation : 26.190044

Example

/* norm.c: Program to compute the norm of the matrix */
#include
#include
main()
{
int i,j,m,n;
float norm, a[10] [10];
float nrm (float [] [], int, int);
printf (“Input row and column of A matrix:”);
scanf (“%d %d”, &n, &m);
printf (“%d %d n”, n,m);
printf (“Input A-matrix \n”);
for (i=0; i for (j=0; j scanf (“%f”, &a[i] [j]);
norm = nrm (a,n,m);
printf (“Norm = %6.2f \n”, norm);
} /* End of main */
/* norm of a matrix = sqsuareroot of the sum of the */
/* squares of the elements of the matrix */
float nrm
(float a[] [], int n, int m)
{
int i,j;
float sum = 0.0;
for (i=0; i for (j=0; j sum = sum + a[i] [j] * a[i] [j];
printf (“Sum = %6.24\n”, sum);
return (sqrt ((double)sum));
}
Run:
Input row and column of A matrix : 3 3
Input A-marix

1.00 2.00 3.00
4.00 5.00 6.00
7.00 8.00 9.00

Sum = 285.00
Norm – 16.88

Example

/* saddle.c: Program to find saddle point in a matrix */
#include
main()
{
int a[5] [5], i,j,min,max,n,m,flag=1,p,q;
printf (“Input the size of matrix:”);
scanf (“%d %d”, &n, &m);
printf (“Enter the elements of the matrix \n”);
for (i=0; i for (j=0; j scanf (“%d”, &a[i] [j]);
/* Find minimum element in row */
for (i=0; i {
min = a[i] [0];
p=i;
q = 0;
/* To check whether ‘min’ is the maximum in column */
for (j=0; j {
if (min>a[i] [j])
{
min=a[i] [j];
p = i;
q = j;
}
}
for (j=0; j{
if(j ! = q)
{
if (a[j] [q] > a[p] [q])
flag = 0;
}
}
if (flag)
printf (“Saddle point a [%d] [%d] = %d\n”, p+1, q+1, a[p] [q]);
else
printf (“No saddle point in row %d\n”, i+1);
flag = 1;
}
}

Run:
Input the size of matrix : 3 3
Enter the elements of the matrix

7 5 5
10 5 8
6 3 3
Saddle point a[1] [2] = 5
Saddle point a [2] [2] = 5
No saddle point in row 3

Example

/* sym.c: Program to find the symmetry of the matrix */
#include
main()
{
int a[10] [10], b[10] [10],i,j,n, flag;
printf (“Input order of the A matrix);
scanf (“%d”, &n);
printf (“Input A-matrix\n”);
for (i=0; i for (j=0; j scanf (“%d”, &a[i] [j]);
/* Transpose of the given Matrix */
for (i=0; i for (j=0; j b[i][j] = a[j] [i];
printf (“Transpose of A matrix : \n”);
for (i=0; i {
for (j=0; j printf (“%5d”, b[i] [j]);
printf (“\n”);
}
/* Find symmetry of a matrix */
for (i=0; i if (a[i] [j] != b[i] [j])
flag = 1;
}
if (flag)
printf (“Matrix is not symmetric \n”);
else
printf (“Matrix is symmetric \n”);
} /* main */

Run 1:
Input order of A matrix : 2 2
Input A-matirx
1 2
3 4
Transpose of A matrix:
1 2
3 4
Matrix is not symmetric

Run 2:
Input order of A matrix : 3 3
Input A – Matrix
1 2 5
2 3 4
5 4 9
Transpose of A – Matrix
1 2 5
2 3 4
5 4 9
Matrix is symmetric


{
min = a[i] [0];
p=i;
q = 0;
/* To check whether ‘min’ is the maximum in column */
for (j=0; j {
if (min>a[i] [j])
{
min=a[i] [j];
p = i;
q = j;
}
}
for (j=0; j{
if(j ! = q)
{
if (a[j] [q] > a[p] [q])
flag = 0;
}
}
if (flag)
printf (“Saddle point a [%d] [%d] = %d\n”, p+1, q+1, a[p] [q]);
else
printf (“No saddle point in row %d\n”, i+1);
flag = 1;
}
}

Run:
Input the size of matrix : 3 3
Enter the elements of the matrix

7 5 5
10 5 8
6 3 3
Saddle point a[1] [2] = 5
Saddle point a [2] [2] = 5
No saddle point in row 3


Tutorial
1. What is an array?
2. How is the integer array a, containing 100 elements, declared in C?
3. What is the subscript of the first element of an array in C?
4. What are the rules for naming arrays?
5. How would you declare an array x containing 50 integer elements followed immediately by 50 real elements?
6. What is the purpose of initializing an array?
7. Is it possible to declare and initialize an array in C simultaneously? If, so, how?
8. If array1 and array2 are dimensioned as follows:
Char array1 [10], array2[10];
and array1 has been initialized, what is the effect of the following?
array2 = array1;
9. What purpose is served by the break statement?
10. What criticism can be leveled against the break statement?
11. Explain the operation of the following expression (assume y has the value 5):
x = (y *=2) + (z=a=4);
12. How is a string stored in an array in C?
13. What declaration would be used for the array bingo, into which the string “I love C” is to be stored?
14. What conversion specification usually is used to read in a string?
15. When the conversion specification %s is used in a scanf statement to read in a string, what is unusual about the way the name of the array is specified?
16. How can one ensure that a scanf statement used to read in a string does not read in more characters than the corresponding character array can hold?
17. Is it obligatory to use all the elements of an array?
18. When a one-dimensional array is being declared, under what condition may the dimension be omitted, with the array name followed by an empty pair of square brackets?
19. What happens if an array is being initialized within its declaration, and too few initialization values are specified within the curly braces?
20. What happens if the number of initializing values is greater than the dimension specified for the array?
21. Must the elements of an array be read in or printed out in order or subscript?
22. When sorting the elements of an array, is it necessary to use another array to store the sorted elements?
23. Where is it legal to declare a new variable?
24. What is the name of the construct used in the following statement, ad how does it operator?
A = (b>c) ? b : c;
25. What is the maximum number of dimensions an array in C may have?
26. True or false: If all the elements of a two-dimensional array are initialized in the declaration of the array, both subscriptions may be omitted.

ANSWERS TO C TUTORIAL

1. An array is an ordered collection of elements that share the same name.
2. int a[100]
3. 0 (zero)
4. The same as for naming regular variables or functions. An array cannot have the same name as a variable or function within the same program.
5. It can’t be done. (All elements of a single array must be of the same type).
6. Before any element of an array can be used, it must have a value. Initializing an array gives a value to each of its elements.
7. Yes. The array declaration is followed immediately by an equal sign. This is followed by the list of values to be assigned (separated by commas) enclosed in braces.
8. A syntax error is fledged by the compiler. One array cannot be assigned to another using the assignment operator. Each element must be assigned individually.
9. It provides a means of immediately terminating the execution of a loop.
10. It violates the tenets of structured programming, in that it permits a jump to another part of the program.
11. The first set of parentheses is evaluated first, multiplying the value of y by 2; the new value of y, 10, is returned by the sub-expression. The second set of parentheses is then evaluated, assigning 4 to a and z and returning that value. The values returned by the two sub-expressions (10 and 4) then are added together to produce the result of 14, which is assigned to x.
12. It is terminated by the null character, which has the ASCII value 0 and is written in C as ‘\0’.
13. Char bingo [9]; /* One element is reserved for the null
Character, ‘\0’ */
14. %s
15. The ampersand (&) is not used, and the array is not subscripted.
16. A maximum field width specifier should be used with the 1%s conversion specification; for example, %10s.
17. No, but the program must keep track of how many elements are are being used, and which ones.
18. If the entire array is being initialized within the declaration.
19. This is perfectly acceptable, as long as the dimension is specified explicitly in the declaration. The initialization values that are specified are assigned to consecutive elements of the array, starting with element 0. The remaining elements are initialized to zero.
20. A syntax error occurs during compilation of the program, and the compilation is aborted.
21. No. the elements of an array (even a character array) may be accessed in any order at all.
22. Not always. In this chapter, the method employed did not use another array. The advantage to using another array is that the original array is retained. Its advantage is that it uses extra memory.
23. At the beginning of the body of a function, and at the beginning of a compound statement.
24. The statement makes use of the conditional expression. If b is greater than c, the conditional expression returns the value of b (the value following the ?); otherwise, it returns the value of c (the value following the :). The returned value is assigned to a. The overall effect is that the larger of the two variables b and c is assigned to a.
25. Theoretically, there is no limit. The only practical limits are memory size and the restrictions imposed by the compiler being used.
26. False. Only the first (row) subscript can be omitted, with the first pair of square brackets left empty. The second subscript must always be explicitly specified.

Keywords
break char do double else float
for if int long return short
unsigned

Exercises
1. What are the arrays? In C, can you have arrays of any data type?
2. In C, what is the index of the first element in an array?
3. What does the name of the array signify?
4. Can array indexes be negative?
5. Illustrate the initialization of a one dimensional array with an example.
6. Illustrate the initialization of a two dimensional array with an example.
7. Show the storage of a two dimensional array in memory with the help of a diagram.
8. Write a program to determine whether a matrix singular or not (solution 4).
9. Write a program to find the inverse of a square matrix (solution 5).
10. Write a program to test for the orthogonality of a square matrix (solution 6).
11. Write a program to maintain a circular queue in an array (solution 7).
12. Implement the following sorting techniques:
(i) bubble sort (solution 8)
(ii) selection sort (solution 9)
(iii) merge sort (solution 10)
(iv) quick sort (solution 11)
(v) heap sort (solution 12)
13. Write a program to find the minimum cost spanning tree by using:
(i) Prim’s algorithm (solution 13)
(ii) Krushkal’s algorithm (solution 14).
14. Solve the 8 queens problem using backtracking (solution 15).
15. Write a program to perform polynomial addition (solution 29).
16. What is the null character and what is it used for, in the context of strings?
17. Point out the difference between:
(i) strcat and strncat
(ii) strcmp and strncmp
18. Write the name of the function in string.h which:
(i) performs case insensitive string comparison
(ii) searches for a character inside a string
(iii) searches for a string inside another string.
19. What happens if the total size of the string after strcat becomes greater than the array size of the string used to hold the concatenated string? Does the compiler report an error?
20. Write a program to concatenate two strings (solution 1).
21. Write a program to count the number of vowels, consonants and spaces in a line (solution 2).

EXAMAPERS123.BLOGSPOT.COM