Programming for Problem Solving Unit 1 PDF

Programming for Problem Solving UNIT-1 1 Objectives - UNIT-1 Introduction to the components of a computer system: ⚫ Computer Systems: Computer Hardware, Computer Software, ⚫ Computer Environments:...

Programming for Problem Solving UNIT-1 1 Objectives - UNIT-1 Introduction to the components of a computer system: ⚫ Computer Systems: Computer Hardware, Computer Software, ⚫ Computer Environments: ⚫ Personal Computing, Time-sharing, Client/Server, Distributed Computing, Cloud computing and Cluster Computing environments. ⚫ Computer Languages: ⚫ Machine Languages, Symbolic Languages, High-Level Languages, ⚫ Creating and Running Programs: ⚫ Writing, editing, compiling, linking, and executing programs, 2  Objectives - UNIT-1 Idea and representation of Algorithm: ⚫ Algorithms, pseudo code, flowcharts ⚫ History of C Language, Features of C, Structure of C, character set, identifiers, constants, variables and keywords. ⚫ Simple data types: void, integral, floating-point , memory allocation for these types, type qualifier const. ⚫ Operators: Categories,Errors 3 What is a Computer? A computer is an electronic device that : 1) accepts data, 2) processes it 3) to give the required output. 4) and can store the data for later use. 4  Computer Systems  A computer system consists of hardware and software. 5 Computer Hardware  Hardware refers to any physical, electrical components of the computer.  The physical equipment required to create, use, manipulate and store the electronic data.  Hardware consist of five parts: 1. Input Devices 2. CPU (Central Processing Unit), 3. Output Devices 4. Memory 5. Storage Devices ( Hard disk, Flash , SD Ram) 6  Computer Hardware 7 COMPUTER ARCHITECTURE (BLOCK DIAGRAM) 8 1. Input Devices:  The input device is used to enter data into a computer.  The devices like keyboard, mouse and scanner are commonly used as input devices. 2. Central Processing Unit:  It is the main part of the computer.  It’s main function is to execute programs stored in the main memory.  It consists of three functional units: ALU, CU and MU. Arithmetic and Logic Unit (ALU):  It performs arithmetic and logical operations on the data. Control Unit:  It controls the overall activities of the components of the computer. Memory Unit:  It is used to hold the waiting data to be processed. 9 3. Output Devices:  Are used to display or print the results.  Monitor, printer and plotter are commonly used output devices.  If output is shown on the screen it is called soft copy.  If it is printed on the paper is called hard copy. 10 Memory: There are two types of memories. Volatile Memory Non-volatile Memory Volatile Memory: It means that the information present in these types of memory devices is lost as soon as the power is switched off. Non-volatile Memory: Information present in these types of memory devices is not lost as soon as the power is switched off. Types of Storage Devices: Primary Storage or Main Memory. Auxiliary Storage or Secondary Storage Cache memory Registers 11 Types of Storage Devices: 12  Primary Storage/Main Memory: This is the place where the data is stored temporarily during processing. Primary memory (main memory) is available in two forms: RAM and ROM. RAM (Random Access Memory): It is a temporary storage medium in a computer. The data which is to be processed by the computer is transferred from a storage device(usually hard disk) to RAM during data processing.  RAM is a volatile memory. ROM (Read Only Memory) : It is a permanent storage medium which stores start up programs of the computer. These programs are loaded when computer is switched on. It is non-volatile memory. 13 Auxiliary Storage/Secondary Memory:  Are the devices where data is stored permanently. Ex: Hard disks, magnetic tapes, flash drives etc. Cache Memory:  It is a very high speed memory present in CPU.  It is much faster than compared to the primary memory.  Parts of the program or data that need to be accessed repeatedly are stored in cache memory.  It is a volatile memory. Registers:  Registers are superfast small memory units internally available within the processor.  They are volatile 14 15 Computer Software  Software: refers to a program or set of programs that are written to achieve a specified task.  Programming Language: An artificial set of rules, vocabulary and syntax used to instruct the computer to execute certain tasks. Software is mainly categorized into two groups.  System Software  Application Software 16  Computer Software (contd) 17 System Software  System Software: consists of programs that manage the software and hardware resources of a computer and perform required information processing tasks.  It is divided in to three categories: 1. Operating System:  It consists of programs that manages the software and computer hardware.  It keeps the system operating in an efficient manner while allowing the users access to the same system. 2. System Support Software: provides all the utilities and other operations that enable the computer to function well. Example: Disk formatting programs. 3. System Development Software: includes language translators that convert high level languages into machine language for execution, Ensures that the programs are error-free. Ex- Compilers. 18  Application Software  Application Software are used to solve general or specific problems.  It is divided in to two categories: 1. General Purpose Software:  It can be used for several purposes. That is the same software can be used in more than one application.  Ex- MS Word, Google Docs, Powerpoint, Excel. 2. Application Specific Software:  It can be used only for its intended purpose.  Ex- College information system, Matlab, Auto CAD , STAD pro etc. 19 Relationship between System and Application Software 20  Computing Environments  Several different environments exist today: 1. Personal Computing Environment 2. Time-Sharing Environment 3. Client-Server Environment 4. Distributed Environment 5. Cloud computing environment 6. Cluster computing environment 21 Computing Environments 22  1. Personal Computing Environment  In this environment, a single personal computer is maintained and to which all the computer hardware components are tied together. You can work on PC independently that is you can perform which ever operations you want. 23 2. Time Sharing Environment Time-sharing Environment 24  Time Sharing Environment (Contd..)  In this environment many users are connected to one or more computers.  That is concurrent use of a computer by more than one user, all users share the computer’s cpu time.  The output devices like printers and auxiliary storage devices are shared by all the users.  All the shared resources are connected to central computer so that it must control the shared resources in an efficient manner.  In which all the computing must done by the central computer.  Example: In the lab, the server computer is shared by all the students. 25 3. Client/Server Environment 26  Client/Server Environment (Contd..)  In this environment, all the computing functions are shared between the central computer and user computers.  The users are given personal computer or workstation which are known as clients.  The central computer is called as the server.  This environment is much faster than the time-sharing environment as the work is shared between the user computers and the server. 27 4. Distributed Computing  It is the integration of different clients and different servers.  The connectivity between different users and different servers is provided using internet throughout the world. 28  5. Cloud Computing  29 5. Cloud Computing  30  5. Cloud Computing  31 5. Cloud Computing The computing is moved away from individual computer systems to a cloud of computers in cloud computing environment. Resources like processing and storage are availed. Here computing is not done in individual technology or computer rather it is computed in cloud of computers where all required resources are provided by the cloud vendor. This environment is primarily comprised of three services: i) Software-as-a-service (SaaS) ii) Infrastructure-as-a-service (IaaS), iii) and Platform-as-a-service (PaaS). 32  6. Cluster Computing Independent computers combined into a unified system through software and networking. At the most fundamental level, when two or more computers are used together to solve a problem, it is considered a cluster. Clusters are typically used for High Availability (HA) for greater reliability or High Performance Computing (HPC) to provide greater computational power than a single computer can provide. Some examples of game console clusters are Sony PlayStation clusters and Microsoft Xbox clusters. 33 Computer Languages  A program’s instructions need to be written in a programming language that the computer can understand.  The first programming language is machine language.  Computer languages were evolved from machine language to natural language ( like English language).  Computer Languages are basically divided into three categories:  Machine language  Symbolic language  High level languages 34  Computer Language Evolution 35 Machine Language  Machine language was the first programming language in the early days of computers.  The language which is understand by the computer hardware is called machine language.  It consists of 0’s and 1’s.  Internally the computer consists of circuits which are made up of switches, transistors and other electronic devices that can be in one of the two states: off or on, where off is represented by 0 and on is represented by 1. 36  Example for Number Systems 37 Number Systems – A comparision 38  Data Representation Definitions: 1) Bit (Binary digit): is the smallest unit of data that can be stored in a computer. - It is either 0 or 1. 2) Bit Pattern: is a sequence of bits (or a string of bits). 3) Byte:– A bit pattern of length 8 is called a byte. 8 bits = 1 Byte Example : 10011001 is one byte instruction This term(byte) is used to measure the size of the memory 1111 0000 1111 0000 is 16 bits instruction=2 bytes 1111 0001 1111 0010 1111 0100 1111 1000(32 bit instruction) = 4 bytes 39 39 40 41 The Number Systems 1. Decimal Number System ( Base 10) Uses :10 digits i.e., 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 Each place corresponds to a power of 10 Example: 1943=1000+900+40+3 =1x1000+9x100+4x10+3 = 1 * 103 + 9 * 102 + 4 * 101 + 3 * 100 2. Binary Number System(Base 2) Uses: 2 digits: 0 and 1 Each place corresponds to a power of 2 1101 = 1 * 23 + 1 * 22 + 0 * 21 + 1 * 20 = 13 42 42  The Number Systems(continued) 3. Octal Number System (Base 8) Uses : 0,1,2,3,4,5,6,7 numbers 4. Hexadecimal Number System (Base 16) Uses: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F where A=10, B=11, C=12, D=13, E=14 and F=15 43 43 Example for Machine Language 44  Symbolic Language or Assembly language  Writing program in machine language was difficult.  Assembly language : uses symbols or mnemonics  This language is not understandable by the computer.  Hence, it must be translated to the machine language using the assembler.  Assembler: is a translator program used to translate assembly language into machine language. 45 Sample Assembly Program START 1000 MOV A, 10 MOV B, 20 ADD A, B STO 2000 STOP END 46  High Level Language  It is like natural language which can be understood by the programmer.  The High Level Language instructions are not understandable by the machine.  Compiler: is used to convert High Level Language instructions into the Machine Language instructions.  First High Level Language is FORTRAN.  Examples for High Level Languages are : C, C++,JAVA, COBOL etc., 47 The Multiplication Program in C 48  Creating and Running Programs Creating and running programs takes place in 4 steps. 1. Writing and editing the program. 2. Compiling. 3. Linking the program with the required library functions. 4. Executing the program. 49 Building a C Program 50  1. Writing and Editing the program  Software used to write programs is known as a text editor, where you can type, edit and store the data.  You can write a C program in text editor and save that file on to the disk with “.c” extension.  This file is called source file. 51 2. Compiling Program  Compiler is used to convert High Level Language instructions into the Machine Language instructions.  It could complete its task in two steps. i) Preprocessor ii) Translator Preprocessor:  It reads the source file and checks for special commands known as preprocessor commands ( instructions which starts with # symbols ).  The result of preprocessor is called as translation unit.  Preprocessor processes the source file before compilation only. 52  3. Linking a program with required library functions  C program is made up of different functions in which:  a) some functions can be written by the programmer,  b) other functions like input/output functions  c) and mathematical library functions  that exist elsewhere and must be attached to our program.  The linker assembles all of these functions and produces the executable file which is ready to run on the computer. 53 4. Executing the program.  Once a program has been linked, it is ready for execution.  Now, you can execute the program by using the run command.  Loader : is a program which is used to load the program from the disk to main memory. 54  Writing and Running Programs 1. Write a program (source code) using text editor and save it with.c extension. 2. Run the compiler to convert a program into to “binary” code. 3. Compiler gives errors and warnings if any, then edit the source file, fix it, and re-compile. 4. Run it and see the output. 55 Program Development It is a multistep process that requires to: 1. Understand the problem 2. Develop the solution using: 1. Structure Chart 2. Algorithm / Pseudo code 3. Flowchart 3. Write the program 4. Test the program 56  1. Understand the Problem  The first step in solving any problem is to understand it.  To solve any problem first you must understand the problem by reading the requirements of the problem.  Once you understand it, review with user(customer) and system analyst. 57 2. Develop the Solution To develop a solution to a problem the following tools are needed. 1. Structure Chart: also known as a hierarchy chart, shows the functional flow through your program.  It shows how the problem is broken into logical steps, each step will be a separate module.  It also shows the interaction between all the parts of your program.  It is like the architect’s blueprint. The below two are used to design the individual parts of the program. 1. Algorithm / Pseudo Code 2. Flowchart 58  Example for Structure Chart Buy a Computer Get Calculate Print Report Configuration Desktop Laptop DELL HP DELL HP 59 Algorithm Algorithm: is an ordered sequence of unambiguous and well-defined instructions that performs some task and halts in a finite time. Let's examine the four parts of this definition more closely. 1. Ordered Sequence: You can number the steps. 2. Unambiguous and well defined instructions: Each instruction should be clear and understandable without any difficulty. 3. Performs some task : Example: addition of two numbers. 4. Halts in finite time: Algorithm must terminate. 60  Properties of an Algorithm:-  Finiteness: An algorithm must terminate in a finite number of steps.  Definiteness: Each step of an algorithm must be precisely and unambiguously(clearly) stated.  Effectiveness: Each step must be effective, and can be performed exactly in a finite amount of time.  Generality: The algorithm must be complete in itself.  Input/Output: Each algorithm must take zero, one or more inputs and produce one or more outputs or results. 61 Pseudo Code Definition: English-like statements that follow a loosely defined syntax and are used to convey the design of an algorithm. Pseudocode is a tool for designing algorithms. Pseudocode uses: structured code simple English (well understood) mathematical notations  Pseudocode can be easily translated into an algorithm or to a programming language 62  Pseudo Code Example Example1: To determine whether a student is passed or not Pseudo Code: 1. If student's grade is greater than or equal to 60 1. Print "passed" 2. else Algorithm: 1. Print "failed" Begin 1. If grade >= 60 1. Print "passed" 2. else 1. Print "failed” End 63 Example 2: Write an algorithm to determine a student’s final grade and indicate whether he is passing or failing. The final grade is calculated as the average of four marks. Pseudo Code: 1. Input set of 4 marks 2. Calculate their average by summing and dividing by 4 3. if average is below 50 Algorithm: 4. Print “FAIL” Begin 5. else Step 1: Input M1,M2,M3,M4 6. Print “PASS” Step 2: GRADE  (M1+M2+M3+M4)/4 Step 3: if (GRADE < 50) then Step 4: Print “FAIL” Step 5: else Step 6: Print “PASS” Step 7: endif End 64  Flowchart Flowchart: is a graphical representation of the sequence of operations in a program. It uses graphical symbols to depict the nature and flow of the steps in a process. 65 SYMBOLS USED WITH FLOWCHARTS 66  Flowchart to find the addition of two numbers start accept a, b c=a+b display c End 67 Algorithm to find sum of two numbers. Algorithm: Step 1: BEGIN Step 2: read a and b Step 3: c = a + b Step 4: print c Step 5: END 68 Flowchart to find whether it’s leap year or not Start Accept year false if(year%4 = = 0) true Display non leap year Display leap year end 69 Algorithm to find whether a given year is a leap year or not. Algorithm: Step 1: BEGIN Step 2: read year Step 3: if (year % 4 == 0) then Display “Year is a leap year” Step 4: else Display “Year is not a leap year” Step 5: end if Step 6: END 70  Types of algorithmic operations Question: How many types of algorithmic operations are there? Answer: 1. Sequential ( step by step ) 2. Conditional ( “if” ) 3. Iterative ( loop ) 6 71 Representing Algorithms (continued) Type 1 – Sequential Operation Question: What does the sequential operations performs? Answer: Sequential operations: perform a single task having: 1) Input: accept data values ( from keyboard ) 2) Computation: numeric calculation ( of the formula) 3) Output: print data ( send the result to the screen ) 72 72  Example 1 Write an algorithm and draw a flowchart to convert the length in feet to centimeter. Flowchart START Algorithm Input Lft Step 1: Input Lft Step 2: Lcm = Lft x 30 Lcm  Lft x 30 Step 3: Print Lcm Print Lcm STOP 73 73 Example 2 Write an algorithm and draw a flowchart that will read the two sides Flowchart of a rectangle and calculate its area. START Algorithm Input W, L Step 1: read W,L Step 2: A=L * W A L*W Step 3: Print A Print A STOP 74 74  Representing Algorithms (continued) Type 2 – Conditional Operation Definition: Control operation: changes the normal flow of control. Question: What does the conditional statement will do? Answer: Conditional statement will : 1. Test the condition (either true or false) 2. If true, then execute statement1 (and skip the statement2) 3. If false, then execute statement2 (and skip the statement1) 75 75 Representing Algorithms (continued) Type 2 – Conditional Operation Example: Check a>b in finding the bigger number among two numbers. Example: Example: int a=5,b=3; int a=3,b=5; If ( a > b) If ( a > b) statement1; statement1; else else statement2; statement2; 76 76  Example 3 Write an algorithm to find largest among two numbers Flowchart START Read a & b Algorithm Step 1: Start Step 2: Read a and b Step 3: if (a>b) then N Print “a is largest” IS Y else a>b Print “b is largest” endif Print Print Step 4: Stop “b is largest” “a is largest” STOP 77 77 Representing Algorithms (continued) Type 3 – Iterative Operation Definition: Iteration: an operation that causes looping (repeating a block of instructions) While statement repeats until the condition becomes false. It has a: 1. continuation condition : ( a test ) whether the loop should continue or not. 2. loop body: (containing) instructions to perform repeatedly 78 78  Representing Algorithms (continued) Type 3 – Iterative Example: Print ten numbers from 1 to 10 on the screen. Condition i=1; while ( i