DOC-20240928-WA0014..pdf

Programming for problem solving Prepared by, Dr R. Sheeba, Assistant Professor/CSE, SRM Institute of Science and Technology, Tiruchirappalli.  UNIT 1 SRM institute of Science and Technology, 2...

Programming for problem solving Prepared by, Dr R. Sheeba, Assistant Professor/CSE, SRM Institute of Science and Technology, Tiruchirappalli.  UNIT 1 SRM institute of Science and Technology, 2 Tiruchirapalli  Evolution of programming languages Programming language is the fundamental unit of today’s tech world. The set of commands and instructions that we give to the machines to perform a particular task. There are 500 + programming languages available. First programmer is Ada Lovelace. In 1883, Ada programmed the analytical engine. In 1949, Assembly language is developed. It is a low level language. It consists of instructions that only machine can understand. Assembly languages are used in simulation flight navigation systems, medical equipment, to create virus. SRM institute of Science and Technology, Tiruchirapalli 3  Evolution contd.. In 1952, Autocode is developed by Alick glennie. The first complied computer programming language. In 1957, FORTRAN is developed by John Backus and IBM. It was designed for numeric computation and scientific computing. In 1958, ALGOL (ALGOrithmic Language) is developed. It was also the first language implementing the nested function and has a simple syntax than FORTRAN. In 1959, COBOL (COmmon Business-Oriented Language) is developed. In 1997, 80% of the world’s business ran on Cobol. SRM institute of Science and Technology, Tiruchirapalli 4  Evolution contd. In the 1960s, the term autocoders was used more generically as to refer to any high-level programming language using a compiler. The US internal revenue service scrambled its path to COBOL-based IMF (individual master file) in order to pay the tens of millions of payments mandated by the coronavirus aid, relief, and economic security. In 1964, BASIC (beginners All-purpose symbolic instruction code) is developed. In 1991, Microsoft visual basic is develop as updated BASIC. It is developed by Bill gates, paul allen and Monte Davidoff. SRM institute of Science and Technology, Tiruchirapalli 5  Evolution contd. In 1972, C language is developed. It is a general-purpose, procedural programming language and the most popular programming language till now. All the code that was previously written in assembly language gets replaced by the C language like operating system, kernel, and many other applications. C is the mother of almost all higher-level programming languages like C#, D, Go, Java, JavaScript, Limbo, LPC, Perl, PHP, Python, and Unix’s C shell. SRM institute of Science and Technology, Tiruchirapalli 6  Evolution contd. Year Programming languages Facts 1972 SQL Storing, manipulating and retrieving data in databases. 1978 MATLAB Multi-paradigm programming language and numeric computing environment 1983 Objective C, C++ To create high-performance applications 1990 Haskel Functional programming language 1991 Python Functional programming language, Data science 1995 JAVA, PHP, Javascript Building software, Web development. 2000 C# Building games 2009 GO open source programming language 2011 Kotlin Creating Android apps 2014 Swift General-purpose programming language. SRM institute of Science and Technology, 7 Tiruchirapalli  PROGRAMS AND PROGRAMMING Computer software: –System software – collection of programs that interface with the hardware. Eg., language translator, operating system. –Application software – solve specific data processing task. Pre-written software packages and user-written application programs. SRM institute of Science and Technology, 8 Tiruchirapalli  PROGRAMS AND PROGRAMMING Program – set of logically related instructions that is arranged in a sequence that directs the computer in solving a problem. Writing a program – programming. Two ways to acquire a program: –Packaged software – purchase an existing program. –Customized software – prepare a new program. SRM institute of Science and Technology, 9 Tiruchirapalli  Programming languages Programming language – set of instructions in a language understandable to the programmer and recognized by a computer. SRM institute of Science and Technology, 10 Tiruchirapalli  Problem solving in everyday life Solution in 6 steps: – Identify the problem – Understand the problem – Find alternative solutions – Select the best way – List instructions that enable to you to solve the problem – Evaluate the solution  Problems Usually a series of steps is followed – algorithmic solutions. Many might be available. The solution can be reached by completing the action in steps – algorithm. Solutions that cannot be reached through direct steps – heuristic solutions. Heuristic solutions are often built by humans. Computers are built to deal with algorithmic solutions.  Problem solving Problem solving is the systematic approach to define the problem and creating number of solutions. The problem solving process starts with the problem specifications and ends with a Correct program.  Problem solving techniques Problem solving can be expressed in the form of 1. Algorithms. 2. Flowcharts. Programs 3. Pseudo codes.  ALGORITHM Algorithm is an ordered sequence of finite, well defined, unambiguous instructions for completing a task. It is an English-like representation of the logic which is used to solve the problem. It is a step- by-step procedure for solving a task or a problem. It is also defined as “any problem whose solution can be expressed in a list of executable instruction”. It is defined as a sequence of instructions that describe a method for solving a problem. In other words it is a step by step procedure for solving a problem.  ALGORITHM Example- Algorithm to display your name ,dept 1. Start 2. Get/Read the name and department 3. Print the name and department 4. Stop  ALGORITHM Algorithm to find the area of the circle 1. Start 2. Read the value of radius r 3. Calculate - Area=3.14*r*r 4. Print the Area of the circle 5. Stop Programs  Characteristics of algorithm Should be written in simple English Each and every instruction should be precise and unambiguous. Instructions in an algorithm should not be repeated infinitely. Algorithm should conclude after a finite number of steps. Should have an end point Derived results should be obtained only after the algorithm terminates.  Qualities of a good algorithm The following are the primary factors that are often used to judge the quality of the algorithms. Time – To execute a program, the computer system takes some amount of time. The lesser is the time required, the better is the algorithm. Memory – To execute a program, computer system takes some amount of memory space. The lesser is the memory required, the better is the algorithm. Accuracy – Multiple algorithms may provide suitable or correct solutions to a given problem, some of these may provide more accurate results than others, and such algorithms may be suitable. Building blocks of an algorithm Statements – single action in a computer – Input data – Process data – Output data State – transition from one process to another. Control flow – executing individual statements in a given order – Sequence – Iteration – selection Functions  Selection Program control changes based on any condition.  Iteration Certain set of instructions are executed again and again based in conditional test.  Flow chart Flow chart is defined as graphical/diagrammatic representation of the logic for problem solving. Logic of the program is represented visually.  Rules for flowchart Clear, easy and easy to follow. Logical start and finish. Only one flow line should come out of a process. Only one decision symbol should enter the decision symbol and 2 or 3 may leave out.  Rules for flowchart Only one flow line is used in terminal symbol. Within standard symbols write briefly. Intersection of flow lines have to be avoided Advantages/benefits of flowchart Communication. Effective analysis. Proper documentation. Efficient coding. Proper debugging. Efficient program maintenance.  ALGORITHM & FLOWCHART Algorithm to find the area of the circle 1. Start 2. Read the value of radius r 3. Calculate - Area=3.14*r*r 4. Print the Area of the circle 5. Stop Programs FLOWCHART Fahrenheit to Celsius Print first 100 even numbers Pseudocode/Program Design Language (PDL) Pseudo – initiation/false. Code – set of statements/instructions written in a programming language. short, readable and formally styled in English. Variable declaration and subroutine. Easier to understand Sketch of the program before actual coding. Not machine readable. Cant be compiled and executed. No standard syntax.  Rules for pseudocode Write one statement per line. Capitalize initial word. Indent to hierarchy. End multiline hierarchy. Statements should be language independent. Keywords in pseudocode  Variables and constants Constants and variables are used to solve a problem by a computer. Constants – specific alphabetical/numeric value. – Its value does not change. Variables – changes during the execution of a program. – A programmer identifies the variable value with this name – Computer uses this, to identify the memory location that holds a value. – In most programming languages, it is known as identifiers. Rules for naming and using variables 1. Name a variable according to what it represents. 2. Do not use space between words. 3. Starts with a letter. 4. Do not use any symbols that are used in mathematical calculations in-between words. 5. A variable name used in one place has to be used as the same in all other places where it is represented. 6. Be consistent using the upper and lower case letters.  Data types Data - unorganized facts. They are given as input and processed and then got back as output/information. Common data types – numeric, logical and character.  Character/alphanumeric data set: all single digit numbers, letters and special characters (Ex: a, b, A,Z, 3, #, &,…..) Everything is placed within double quotes. ASCII (American Standard Code for Information Interchange) characters contains 256 characters. String data – when more than one character are put together they form as string. Some languages do not differentiate char and string.  Usually char and string are allotted with numbers by a computer. As computer operates on only numbers String/character are given numeric value. They are compared and stored accordingly. Letter ‘a’ is given value less than ‘b’, so b is stored before a, likewise c is stored before b Upper case letters are given lower values than lower case letters. Banana is larger than Apple. Joan is larger than James.  Why learn C? C is a core language. C is a small language – 32 keywords. C is quick. C is portable – no or little modifications might be required to run it on other systems. SRM institute of Science and Technology, 50 Tiruchirapalli  Introduction It started with Common Programming Language (CPL) which Martin Richards at the University of Cambridge turned into Basic Combined Programming Language (BCPL). At Bell labs, Ken Thompson developed a variant called B. Which was then modified to C in the early 1970s by Dennis Ritchie. It is admired for elegance, brevity and versatility of its operators and control structure. Mid – level language : provides capabilities like a high level language and allows interaction with computer like low level language. SRM institute of Science and Technology, 51 Tiruchirapalli  Developing programs in C Three steps: –Writing C program. –Compile the program. –Execute it. –Compilation – 3 stages 1. Preprocessing – modify the source. 2. Compilation – generates assembler source, checks for syntax. Errors identified are corrected and recompiled. 3. Assembly –Three types of errors: Compile errors – by compiler Linking errors – by linker Runtime errors SRM institute of Science and Technology, 52 Tiruchirapalli Steps for entering, compiling and executing C programs SRM institute of Science and Technology, 53 Tiruchirapalli Structure of a C program SRM institute of Science and Technology, 54 Tiruchirapalli  A simple C program Preprocessor directives – tells preprocessor to look for special code libraries. Declaration – name and type of data objects needed. Global declaration – visible to all parts of the program. main () – divided into two sections – Local definition – describes the data in the function. – Statement – instructions. SRM institute of Science and Technology, 55 Tiruchirapalli  A simple C program #include int main() { printf(“C is sea\n”); return 0; } SRM institute of Science and Technology, 56 Tiruchirapalli  A simple C program --> comment line Starts with Included anywhere in the program. Compiler – non executable statements. Use – describe a variable, purpose of a set of codes/instructions. // - comment also begins with and ends with line break. SRM institute of Science and Technology, 57 Tiruchirapalli  A simple C program #include # - directives for preprocessor. Directives are preprocessed before compiling the program. During compilation, includes the contents of the stdio.h into the program. stdio.h – header file that comes with C compiler. – Contains information on input and output functions. Eg., printf() Difference between a preprocessor and program statement, i. Begins in first column and no space between # and include. ii. They are not terminated by a semicolon. SRM institute of Science and Technology, 58 Tiruchirapalli  A simple C program main() – Starting point of a program. – Among one or more functions available , one must be main. – Functions are building blocks of C. – The action starts from main() from which other functions may be invoked or called. – Function – sub program that contains instructions or statements to perform a specific computation or processing. SRM institute of Science and Technology, 59 Tiruchirapalli  A simple C program Brace {} – Every open brace has a matching closing brace. – Contains a lump of program called block – printf(“C is sea\n”); printf is a library function. \n – blackslash n – new line character. \n does not appear in the output screen. SRM institute of Science and Technology, 60 Tiruchirapalli  A simple C program Backslash codes SRM institute of Science and Technology, 61 Tiruchirapalli  A simple C program return 0; – Indicates the value returned by the function. SRM institute of Science and Technology, 62 Tiruchirapalli COMPILATION AND LINKING PROCESS High level language has to be converted into low level language using Compiler. During this process, the syntax errors are checked – diagnostics. Interpreter – also translates high level language to low level language. SRM institute of Science and Technology, 63 Tiruchirapalli COMPILATION AND LINKING PROCESS SRM institute of Science and Technology, 64 Tiruchirapalli COMPILATION AND LINKING PROCESS 2 stages: 1. Analysis of the source program 2. Synthesis of the object program 3. Analysis – precise description of the source programming language( lexical rules, syntax rules and semantic rules). lexical rules – elements/words in the language. Syntax – notations Semantic rules – assign meanings to valid statements. SRM institute of Science and Technology, 65 Tiruchirapalli PROCESS OF COMPILATION SRM institute of Science and Technology, 66 Tiruchirapalli  PROCESS OF COMPILATION 1st block is the lexical analyzer – breaks the lines of program into individual lexical items. – Lexical items – identifier, operator, delimiter, etc. – Attaches type tag. – Constructs symbol table – find representation of each constant. – This symbol table is used later to allocate memory. SRM institute of Science and Technology, 67 Tiruchirapalli  PROCESS OF COMPILATION 2nd block – syntax analysis/parsing. – Expressions, declarations and other statements are identified. – Techniques based on the grammar of the programming language is used. 3rd block – semantic analysis – Syntactic units identified by the syntax analysis are processed. – Produces intermediate representation of the final machine language. SRM institute of Science and Technology, 68 Tiruchirapalli  PROCESS OF COMPILATION 4th – code generation Output machine language. 5th – linking/loading Any sub program / sub routine is used is linked/loaded. Linking – finds the correct main memory locations of the final executable program. Loader – places the program into the memory. SRM institute of Science and Technology, 69 Tiruchirapalli  Preprocessor directives Preprocessor directives are a block of statements that are handled before the actual compilation process starts. The preprocessor will process directives that are inserted into the C source code. These directives allow additional actions to be taken on the C source code before it is compiled into object code. It starts with # symbol. SRM institute of Science and Technology, 70 Tiruchirapalli SRM institute of Science and Technology, 71 Tiruchirapalli Preprocessor directives SRM institute of Science and Technology, 72 Tiruchirapalli SRM institute of Science and Technology, 73 Tiruchirapalli  Macro Small functions, it can have arguments also SRM institute of Science and Technology, 74 Tiruchirapalli SRM institute of Science and Technology, 75 Tiruchirapalli SRM institute of Science and Technology, 76 Tiruchirapalli SRM institute of Science and Technology, 77 Tiruchirapalli SRM institute of Science and Technology, 78 Tiruchirapalli  Conditional compilation Where we need a conditional logic #if, #elif, #else and #endif SRM institute of Science and Technology, 79 Tiruchirapalli  Ifndef # define T 8 void main() { clrscr(); #ifndef T printf(“\n Macro is not defined.”); #else printf(“\n Macro is defined.”); #endif getche(); } OUTPUT: Macro is defined. SRM institute of Science and Technology, 80 Tiruchirapalli  The value of FILE_SIZE is left in first line. The value of FILE_SIZE is defined as 42 SRM institute of Science and Technology, 81 Tiruchirapalli SRM institute of Science and Technology, 82 Tiruchirapalli  Error directive The #error is used to display the user-defined message during the compilation of the program. The syntax is as follows: #ifndef identifier # error #endif SRM institute of Science and Technology, 83 Tiruchirapalli SRM institute of Science and Technology, 84 Tiruchirapalli Output SRM institute of Science and Technology, 85 Tiruchirapalli  Pragma directive It sets /resets certain warning and errors during the compilation of C program. SRM institute of Science and Technology, 86 Tiruchirapalli SRM institute of Science and Technology, 87 Tiruchirapalli  Constants and variables Programs operate on data. Instructions/data have to be stored somewhere in the computer. So comes the Random Access Memory (RAM). Computer memory: – Made up of registers & cells. – Information is of 0 and 1 (bits). – Collection of bits – 8 bits, 16 bits, 32 bits or 64 bits. – Memory address - Data is stored in memory at physical memory locations. – Each byte is uniquely identified by its address. SRM institute of Science and Technology, 88 Tiruchirapalli Bits and bytes in memory SRM institute of Science and Technology, 89 Tiruchirapalli  Constants and variables Word length – amount of bits on which the computer can operate. Variable – identifier for a memory location. Holds data values. Reserves memory and gives name. This avoids remembering numbers like 46780. Variable -> unique memory address. SRM institute of Science and Technology, 90 Tiruchirapalli  Constants and variables Int salary = 65000; SRM institute of Science and Technology, 91 Tiruchirapalli  Constants and variables 3 attributes: – Data type – established when the variable is defined. Eg., integer, real, character. – Name. – Value. SRM institute of Science and Technology, 92 Tiruchirapalli  Constants and variables 3 attributes: – Data type – established when the variable is defined. Eg., integer, real, character. – Name – case sensitive. – Value. – Variable must be declared before using it. –Start of the block 2 purpose 1. Precise information on amount of memory 2. Provides compiler with a list of information on variables. SRM institute of Science and Technology, 93 Tiruchirapalli  Data types in C Determines a set of values and operations on values. SRM institute of Science and Technology, 94 Tiruchirapalli  Data types in C C provides basic data types, using which complex data types can be built. 5 basic data types: – Character – char – Integer – int – Floating point – float – Double precision floating point – float – Valueless – void. SRM institute of Science and Technology, 95 Tiruchirapalli Data types in C SRM institute of Science and Technology, 96 Tiruchirapalli Data types in C SRM institute of Science and Technology, 97 Tiruchirapalli  Subroutines in C Program = algorithms + data. Variables. Data types. Sub-routine – logical collection of instructions that is involved from within a larger program to perform a specific task. – Independent. – Invoked any number of times. – After completion, returns. SRM institute of Science and Technology, 98 Tiruchirapalli SRM institute of Science and Technology, 99 Tiruchirapalli  Expressions using operators in C Simple program – combination of statements. Statement block – group of statements. Procedure – specific block of statements, runs several times The arithmetic operators: