ES1101-Computational Engineering

ES1101

Computational Engineering

Created by Panchatcharam Mariappan

Down arrow

Disclaimer

This Presentation has been prepared based on the C: How to Program book. However, it may contain some typo and mistakes. Contact the author for any mistakes

Marks

Components Marks
Quiz 1 10
Quiz 2 10
Assignments+Coding Marathon 10+15
Lab Exams 15
End Sem 40
Total 100

References

  • H. M. Deitel and P. J. Deitel, C: How to program, Prentice Hall India, (2014).
  • S. C. Chapra and R. P. Canale, Numerical Methods for Engineers, Mc-Graw Hill, (2010).

Online Resources

Moodle

Join IIT Tirupati Moodle

For any updates about the course

Moodle

Send Assignments and Queries related to this course to

panch.m@iittp.ac.in

Working Online

Onling GDB

repl.it

Jdoodle

RexTester

Tips

  • Program like a child
  • Learn by doing
  • Remember the syntax
  • Do hand calculations or Code by hand
  • Generate Unit Test
  • Debug code
  • Don't memorize a code, try to understand the logic
  • Do little by little
  • Practice! More Practice! More and More Practice!
  • Don't panic while making mistakes, learn from it

Computer Systems

Computer Systems

Developed by Academia and Industry

Daily usage: General Purpose Machines

Specific applications: Special Purpose Machines

Defined through their interfaces at a number of layered abstraction levels

Computer Systems

Application Programs

High-Level Languages: Set of Machine Instructions

Language Architecture: Interface between Application Program and High-Level Language

Instruction set Architecture: Interface between machine instructions set and runtime, I/O Control

Four Basic View Points

Structure: Interconnection of various hardware components

Organization Dynamic Interplay and Management of various components

Implementation: Design of hardware components

Performance: Behaviour of the computer system

History

History

Z1 (1938): First Program controlled (Mechanical Computer)

Z2 (1939): First Operational Program controlled computer with fixed point arithmetic

1940: Iowa State University, small-scale, special-purpose electronic computer, not operational

Z3 (1941): Fully functional programmable special-purpose machine (Germany)

History

ENIAC(1944)

Electronic Numerical Integration And Calculator

First operational general-purpose machine, 18000 vaccum tubes

For World War II, Weight: 30 tons, 1500 Sq.ft, 140kW power

Programmable through manaul switching, Very slow by today's standard, very less storage

Von-Neumann Machine

Von-Neumann

EDVAC

Successor of ENIAC, 1946-1952, Electronic Discrete Variable Automatic Computer

Institute for Advanced Study, Princeton

Executes stored program

Memory buffer register, Memory address register, instruction register, instruction buffer register, program counter, accumulator, multiplier quotient.

Von-Neumann

  • EDSAC(1949): Electronic Delay Storage Automatic Calculator
  • MARK I, II, III, IV
  • BINAC(1949): Binary Automatic Computer
  • UNIVAC(1951): Universal Automatic Computer
  • IBM701(1952): International Business Machines

Von-Neumann

  • Second Generations: Transistor
  • Third Generations: Integrated Circuits
    • Microelectronics
    • Semiconductor
    • Microprocessors: 4004, 8080, 8086, ...
    • Pentium I, II, III, IV, Core, Core 2

Personal Computer

  • 1977: Apple
  • Atlair, Processor Techonolgy
  • North Star
  • Tandy
  • Commodore
  • ...

Personal Computer

  • Compaq
  • IBM
  • Dell
  • HP
  • Lenovo
  • ...

Hardware and Software

Hardware and Software

Hardware: Any Physical device used in or with machines

Software: Collection of Code Installed on computers' hard drive

Hardware and Software

  • Billions of Calculations in one second
  • SuperComputers: Quadrillions of instructions per second
  • Computer Programs: Computer processes data under the control of sequences of instructions
    • Guides the computers through ordered actions
    • Guided by people: Programmers

Moore's Law

  • Hardware cost decreases rapidly
  • Capacities of computers doubles every year
  • Number of transistors in dense integrated circuit doubles every year

SSI,LSI,VLSI,VVLSI,UVLSI,WSI,SOC,3D-IC

Performance

  • Short Response Time
  • High Throughput
  • Availability
  • Processing Speed
  • Latency
  • Bandwidth
  • Power consumption
  • Scalability

Computer Organization

Computer Organization

Input Unit

  • Keyboard
  • Touch screens
  • Mouse
  • Voice Commands
  • Scanning Images
  • Barcode...

Computer Organization

Output Unit

  • Screens
  • Printed On Paper
  • Audio
  • Video
  • ...

Computer Organization

Memory Unit

  • CPU Registers
  • Main Memory or RAM
  • Secondary Storage
  • HDD,SSD,USB,DVD
  • ...

Computer Organization

ALU

  • Calculations: Add, Subtract, Divide, Multiply
  • Decision Making

Computer Organization

CPU

  • Administrative Section
  • Tells the ALU when information should be read from MU
  • Tells the ALU when information should be used from MU
  • Tells the ALU when information should be send from MU to Output
  • Multi-Core Processors

Data Hierarchy

  • Bits: Smallest Data item, 0 or 1, binary digit
  • Characters: Decimal digits, letters, symbols, Unicode, ASCII
  • Fields: Composed of Bits, Bytes or Characters
  • Records: Composed of field
  • Files: Group of records
  • Database: A collection of data
  • Big Data

Byte Measurements

Unit Bytes Bytes(10x)
1 KB 1024 Bytes 103
1 MB 1024 KB 106
1 GB 1024 MB 109
1 TB 1024 GB 1012
1 PB (Peta) 1024 TB 1015
1 EB (exa) 1024 PB 1018
1 ZB (Zetta) 1024 EB 1021

Machine/Assembly/High-Level Languages

Machine Language

It is the lowest-level programming language which only the specific computer can understand, consists of strings of numbers and almost impossible for humans to understand.

Machine Language

  • Computer can directly understand only its own ML
  • Defined by its hardware design
  • Strings of Numbers (0s and 1s)
  • Machine Dependent
  • Difficult for human to understand
  • Slow and tedious for a programmer

Assembly Language

It is a low level programming language that allows a user to write a program using alphanumeric mnemonic codes instead of numeric codes for a set of instructions. It can be translated using an assembler into machine language.

Assembly Language

  • Strings of numbers computer can understand
  • English-like abbreviations
  • Abbreviations are basis of AL
  • Assembler: Translator programs, AL to ML
  • Code is quite easier than ML to understand by human
  • Need more instructions for simplest task

High-Level Language

It is a programming language that is understood by humans/programmers. It can be translated using a translator, for example, compiler or interpreters, into a simple machine language that computer can understand and execute. It does not depend on specific computer.

High-Level Language

  • Single Statment to accomplish substantial tasks
  • Compilers: Translator program HLL to ML
  • Easy to understand
  • Variables, Arrays,Objects,Loop
  • Boolean,Functions,threads,abstract


Compiler Vs Interpreter

What is a compiler?

A compiler is a program that reads a program written in the high-level language and converts it into the machine or low-level language and reports the errors present in the program.

It converts the entire source code in one go or could take multiple passes to do so, but at last, the user gets the compiled code which is ready to execute.

Examples: C, C++, C#, Scala

6 Phases of Compiler

  • Lexical Analyzer: Scans the code as a stream of characters into lexemes. Output: Sequence of tokens with refernce to the programming language
  • Syntax Analyzer: Tokens generated in Lexical analyzer phase are against grammar of programming language. Checks whether the expressions are syntactically correct or not. It makes parse trees

6 Phases of Compiler

  • Semantic Analyzer: Checks whether the expressions and statements generated by previous phase follow the rule of programming language or not. Creates annotated parse trees
  • Intermediate Code:Equivalent intermediate code of the source code.
  • Code Optimizer:Improves space and time requirement of the program. Eliminates the redundant code

6 Phases of Compiler

  • Code Generator:Final phase. Target code for a particular machine is generated. Performs memory, register managments and machine specific optimization

What is an Interpreter?

An altnerative for implementing a programming language and does the same work as compiler

  • It Performs lexing, parsing and type checking similar to compiler.
  • Processes syntax tree directly to access expressions and executes statements rather than generating code from the syntax tree
  • Require processing same syntax tree more than once. Slower than compiler
  • Examples: JAVA, Python, Ruby, PHP

Interpreters

  • Large HLL to ML takes more time to compile
  • Interpreters: Developed to execute HLL directly
  • No compilation delay
  • Slower than compiled programs
  • JIT in Java, Python,Matab

Compiler Vs Interpreter

Process Compiler Interpreter
Input Takes an entire program at a time Takes a single line of code at a time
Output Generates intermediate object code Won't produce any intermediate object code
When? Before execution Simultaneous Compilation and execution

Compiler Vs Interpreter

Process Compiler Interpreter
Speed Faster Slower
Memory Requirment More for object code Less, no object code
Errors All errors at a time after compilation, difficult Error, line by line, easier


C Programming

History

  • BCPL (1967): Basic Combined Programming Language
  • B (1969): Bell Labs - Ken Thompson and Dennis Ritchie
  • C (1972): Bell Labs - Dennis Ritchie
  • To Develop the UNIX operating System

Usage

  • Operating System: C or C++
  • Mostly Hardware independent
  • Portable to Many Computers
  • Embedded systems
  • Real-time systems
  • Communications systems

Operating System

  • A System software to manage hardware and software
  • Provides common services for computer programs
  • Linux,MS Windows,Google Andriod, Apple OS and so on
  • Objective-C: Derived from C

Embedded System

  • Programmed, Controlled OS
  • Embedded as part of a complete device
  • Majority of microprocessors manufactured to target embedded navigation system, smart home appliances, smart phone, tablets, robots and so on
  • C is the most popular programming for embedded

Real-time System

  • Real time-OS (RTOS): To serve real-time applications
  • Processes data as it comes in, no buffer delay
  • Misson critical applications, requires instantaneous response time
  • Air-traffic control system, networked multimedia system

Communication System

  • System needs to route massive amounts of data to their destinations
  • To deliver audio and video smoothly without delay
  • Optical, Radio, Power line
  • Telephone,Mobile


C Standard

Book

  • 1978: First Book on C
  • The C Programming Language: Kernighan and Dennis Ritchie

Variations

  • Rapid Growth
  • Different Variations for various type of hardware platforms
  • Incompatible
  • Requirement of Standard C: 1983
  • American National Standards Committee on Computers and Information Processing

ANSI

  • American National Standards Institute
  • 1989: ANSI X3.159-1989
  • or ANSI C or Standard C
  • Approved by ISO 1999: ISO C
  • 1999: C99

C11 and C18

  • C11: 2011
  • Expands C's capabilities: Atomic operations, multi-thread
  • C18: 2017/2018
  • Clarifications of defects of C11
  • Technical Corrections
  • No new language features


C Standard Library

Functions

  • C Program: Pieces of blocks, functions
  • Rich collection of existing functions
  • C Standard Library

How to Program

  • Learning the C language itself
  • Learning how to use the functions in the C Standard Library

When Programming in C

  • C Standard Library Functions
  • Functions you create yourself
    • Advantage: You know exactly what it does
    • Disadvantage: Time consuming to design, develop, debug, tuning to perform
  • Functions created by other people (open source, closed source)


Other Languages

C++

  • Bjarne Stroustrup: Bell Labs
  • Imperative
  • Object Oriented: Reusable software components
  • ISO/IEC14882-1998,2003,2011,2014,2017
  • C++98,C++03,C++11,C++0X,C++14,C++1y,C++17,C++1z,C++20

Objective C

  • Object Oriented C
  • Developed: 1980. Acquired NeXT and then Apple
  • Key programming language for OS X and iOS devices

Java

  • Sun Microsystems, 1991
  • Runs on a broad variety of
    • Computer systems
    • Computer-controlled devices
  • Write once, run anywhere
  • Smart phone, Android App Development

C#

  • Microsoft's Prorgramming language
  • VB,VC++,VC#
  • VC#-C++ and Java
  • integrating internet and web

PHP

  • Scripting language
  • Millions of websites
  • Platform independent
  • Supports database

Python

  • 1991: National Research Institute for Mathematics and Computer Science
  • Extended through classes
  • Programming interfaces

Javascript

  • Scripting language
  • Used to add dynamic behaviour of web pages
  • Animations, interaction with user
  • Major Web browsers

Swift

  • Apple's programming language for iOS: 2014
  • Modern language for app-development
  • Easy for beginners
  • Performance and security


C Program Development

Processes

  • Editor
  • Preprocessor
  • Compiler
  • Linker
  • Loading
  • Execution
  • Debugging

Phase 1: Editor

  • Editing or creating a C file
  • gedit, vim, emacs
  • Eclipse, MSVC, geany, DevC
  • Store the program on secondary hard disk
  • Save the file name with an extension .c

Phase 2: Preprocessing

  • While the compiler translates the C program to ML or object code
  • Including other files for compilation
  • Preprocessor program obeys preprocessor directives

Phase 3: Compilation

  • Compiler translates the C program to ML or object code
  • Compile error due to syntax error, violating the rules of the language
  • Issues an error message to fix the error
  • Error message may differ from system to system

Phase 4: Linking

  • References of functions defined elsewhere
  • Object code provided by many programmers are linked
  • Object code produced by the compiler has holes due to missing parts
  • Links the object code for the missing functions
  • Produces an executable image

Phas 2,3 and 4

  • Usually, Phase 2,3 and 4 can be done by a single command for smaller program
  • gcc FileName.C
  • It compiles, links and creates an executable a.out

Phase 5: Loading

  • Before Execution
  • Must be placed in memory first
  • Loader loads executable image from disk to memory
  • Additional components from shared libraries required for the program

Phase 6: Execution

  • Under the control of CPU
  • Executes one instruction at a time
  • To load and execute, ./a.out
  • Provides necessary input from stdin(a keyboard)
  • Produces output to stdout(a computer screen)
  • stderr: to display the error to the screen

Debugging

  • Not necessary to produce error free code in first attempt
  • Syntax error, runtime error, segmentation fault
  • Make necessary corrections depending on the code and repeat all steps

Simple C Program

FirstProgram.C

#include<stdio.h> //header file //Function main begins program execution int main(void)

{//Body of the main begins here printf("Hello World\n"); return 0; }//end of function main

Comments

  • The two slashes
  • Insert comments to document programs
  • Improve program readability
  • Compiler wont perform any action (ignoers)
  • Multi line comments /*..*/

Preprocessor Directive

#include<stdio.h> //header file
  • stdio.h is a directive preprocessor
  • Processed before compilation
  • Includes the contents of the standard input output header in the program
  • For printf function

Alignments

  • Give spaces and alignments
  • Easy to read
  • White or blank spaces or tab

main

int main(void) //header file
  • Part of every C program
  • main is a building block, function
  • C program contains one or more functions, one must be main
  • Function can return information
  • The keyword int returns an integer value
  • Function can receive an information, here void, means no information received
  • The body of every function starts at the left brace { and ends before the right brace }

printf

int printf(const char *format, ...);
printf("Hello World\n");
  • Instructs the computer to perform an action
  • Print on the screen the string characters marked by quotation marks
  • f stands for formated
  • Every statement must end with a semicolon, ; statment terminator
  • Exact characters as they appear between quotes

Escape Sequence

  • The backslash (\) is an escape character
  • The escape sequence (\n) means newline
  • The escape sequence (\t) means horizontal tab
  • The escape sequence (\\) means insert a backslash in string
  • The escape sequence (\") means insert a double-quoter character in string


Compile, Link and Execute

Phase 1: Editor

  • Editor: gedit
  • Type the following in the editor
#include<stdio.h> //header file
//Function main begins program execution
int main(void)
{//Body of the main begins here
    printf("Hello World\n");
    return 0;
}//end of function main
  • Save the file as FirstProgram.C in Documents directory

Open the Terminal

  • Open the terminal in Ubuntu
  • Navigate to the directory where you have saved the FirstProgram.C file

Phase 2-5:Simplest

  • gcc FirstProgram.C
  • It compiles, links and creates an executable a.out
  • Type ./a.out

Output

Hello World

Phase 2-5:Recommended

  • gcc FirstProgram.C -o FirstProgram
  • It compiles, links and creates an executable FirstProgram
  • Type ./FirstProgram


Second C Program

SecondProgram.C


#include<stdio.h> //header file
//Function main begins program execution
int main(void)
{//Body of the main begins here
    printf("This is my First ES1101 Exercise\n");
    printf("My Name is Panchatcharam\n");
    printf("My Roll Number is AA8245\n");
    return 0;
}//end of function main

Output


This is my First ES1101 Exercise
My Name is Panchatcharam
My Roll Number is AA8245


Basic Variables

Basic Variable Data Type

  • char
  • int
  • float
  • double
  • void

Basic Variable Data Type

Variable Type Description Min Max
signed char 7 bit ASCII -127 127
unsigned char 8 bit ASCII 0 255
The minimum range is guaranteed in all compilers. See ISO C. However, it varies. See gcc range.

Basic Variable Data Type

Variable Type Description Min Max
signed int or int signed integer 16 bit -(215)-1 215-1
unsigned short int or unsigned int unsigned integer 16 bit 0 216-1
The minimum range is guaranteed in all compilers. See ISO C. However, it varies. See gcc range.

Basic Variable Data Type

Variable Type Description Min Max
long int signed integer 32 bit -(231)-1 231-1
unsigned long int unsigned integer 32 bit 0 232-1
long long int signed integer 64 bit -(263)-1 263-1
unsigned long long int unsigned integer 64 bit 0 264-1

Basic Variable Data Type

Type Description Min Max
float single precision real 32 bit -1.175*10-38 3.402*1038
double double precision real 64 bit -2.25*10-308 1.797*10308
long double extended precision real 80 bit -3.362*10-4932 1.189*104932

Basic Variable Data Type

Type Description Min Max
long double extended precision real 80 bit -3.362*10-4932 1.189*104932


Variable Declaration syntax

Variable Declaration Syntax


VariableType VariableName1[=Value1] [,VariableName2[=Value2],...VariableNameN[=ValueN]];

Constant Variable Declaration Syntax


const VariableType VariableName1[=Value1];

Example

/* Sum of Two Integers */
#include<stdio.h>
int main(void)
{
    int a, b, c;
    printf("Enter an Integer: ");
    scanf("%d", &a);
    printf("Enter another Integer: ");
    scanf("%d", &b);
    c = a + b;
    printf("%d + %d = %d\n", a, b, c);
    return 0;
}

scanf

int scanf(const char *format, ...);
scanf("%d", &a);
  • Instructs the computer to perform an action
  • Receives an integer from the screen
  • f stands for formatedd
  • Every statement must end with a semicolon, ; statment terminator

Example

Enter an Integer: 3
Enter another Integer: 2
3 + 2 = 5

Details

int a, b, c;//Definitions
a=10;//Declaration
b=14;//Declaration
  • All Variables must be defined with a name and a data type before they can be used in C program
  • Multiple variables of the same type in a single statement
  • Case Sensitive


Four Frequent Specifiers

Examples: integer

int StudStrength;
printf("Enter the number of students in your course: ");
scanf("%d",&StudStrength);
printf("Number of Students in my course is %d\n",StudStrength);

Examples: Float

float cost;
printf("Enter the cost of C Programming book: ");
scanf("%f",&cost);
printf("The cost of the C Programming book = %f\n",cost);

Examples: Double

double cost;
printf("Enter the cost of C Programming book: ");
scanf("%lf",&cost);
printf("The cost of the C Programming book = %lf\n",cost);

Examples: Characters/Strings

char CourseName[50];
char Enrolled;
printf("Have you Enrolled this course: ");
scanf("%c",&Enrolled);
printf("Enter the Course Name: ");
scanf("%s",CourseName);
printf("Enter the number of students in %s course: ",CourseName);

Format Specifiers

Specifier Description For printf For scanf
%d Integer StudStrength &StudStrength
%f Float cost &cost
%lf double cost &cost
%c character Enrolled &Enrolled
%s string CourseName CourseName

Other Specifiers

Specifier Description
%i Integer
%u unsigned decimal integer
%e or %E Scientific
%o octal
%x or %X unsigned hexadecimal

printf format type

%[flags][width][.precision][length]specifier

scanf format type

%[width][length]specifier

Other Specifiers

Variable Type Format Specifier
%c char,signed char, unsigned char
%hi or %hd short int, signed short int
%hu unsigned short int
%d or %i int, signed int
%u unsigned int
%ld or %li long int,signed long int

Other Specifiers

Variable Type Format Specifier
%lu unsigned long int
%lli or %lld long long int, signed long long int
%llu unsigned long long int

Other Specifiers

Variable Type Format Specifier
%f, %F, %g, %G, %e, %E, %a, %A float
%lf, %lF, %lg, %lG, %le, %lE, %la, %lA double
%Lf, %LF, %Lg, %LG, %Le, %LE, %La, %LA long double

Operator Precedence

Operators Operations Precedence
() Parentheses First
* Multiplication
/ Divison Second
% Remainder
+ Addition Third
- Subtraction
= Assignment Last

Single Precision (Float)

Decimal To Floating Point

  • 2.625
  • 210=102
  • 0.62510=1012
  • 2.62510=10.1012
  • 2.62510=1.01012x21
  • Mantissa : 0101 0000 0000 0000 0000 000
  • Exponent : 1 + 127 = 128 = 1000 0000
  • Sign bit: 0
  • 0 1000 0000 0101 0000 0000 0000 0000 000

Decimal To Floating Point

  • -12.375
  • 1210=11002
  • 0.37510=0112
  • 12.37510=1100.0112
  • 12.37510=1.1000112x23
  • Mantissa : 1000 1100 0000 0000 0000 000
  • Exponent : 3 + 127 = 130 = 1000 0010
  • Sign bit: 1
  • 1 1000 0010 1000 1100 0000 0000 0000 000

Double Precision (Double)

Quadrupe Precision



Decision Making

if Statement

if (Expression)
{
    //Code Block
}
    
  • If the expression is true, inside the body of if is executed
  • If the expression is false, inside the body of if is skipped from execution

Examples: If

int n=5;
if(n%2==0)
{
    printf("%d is even",n);
}

if Statement

if (Expression)
{
    //Code Block-1
}
else
{
    //Code Block-2
}
  • If the expression is true, inside the body of if is executed
  • If the expression is false, inside the body of if is skipped from execution
  • If the expression is false, else body of if is executed

Examples: If...else

int n=5;
if(n%2==0)
{
    printf("%d is even\n",n);
}
else
{
    printf("%d is odd\n",n)
}

if...else ladder Statement

if (Expression-1)
{
    //Code Block-1
}
else if (Expression-2)
{
    //Code Block-2
}
else if (Expression-3)
{
    //Code Block-3
}
    ....
else if (Expression-N)
{
    //Code Block-N
}
else
{
    //Code Block - (N+1)
}

if...else ladder Statement

  • If the expression-1 is true, Code Block-1 is executed
  • If the expression-2 is true, Code Block-2 is executed
  • ...
  • If the expression-N is true, Code Block-N is executed
  • If all N-expressions are false, else block is executed

Examples: if...else ladder

int x=2;
int y=3
if(x==y)
{
    printf("%d Equal to %d\n",x,y);
}
else if(x > y)
{
    printf("%d Greater than to %d\n",x,y);
}
else
{
    printf("%d Less than to %d\n",x,y);
}

Examples: if...else ladder

float a=4;
float b=5;
float c;
char op;
scanf("%c",&op);
if (op=='+')
{
    c = a + b;
}
else if(op=='-')
{
    c = a - b;
}
else if(op == '*')
{
    c = a * b;
}
else if(op == '/')
{
    c = a / b;
}
else
{
    printf("Invalid Operator");
}

Nested if Statement

if (Expression-1)
{
    //Code Block-1
    if (Expression-11)
    {
        //Code Block-11
    }
    else if (Expression-12)
    {
        //Code Block-12
    }
    ...
    else if (Expression-1N)
    {
        //Code Block-1N
    }
    else
    {
        //Code Block-1(N+1)
    }
}
else if (Expression-2)
{
    //Code Block-2
    if (Expression-21)
    {
        //Code Block-21
    }
    else if (Expression-22)
    {
        //Code Block-22
    }
    ...
    else if (Expression-2N)
    {
        //Code Block-2N
    }
    else
    {
        //Code Block-2(N+1)
    }
}
    ....
else if (Expression-M)
{
    //Code Block-M
    if (Expression-M1)
    {
        //Code Block-M1
    }
    else if (Expression-M2)
    {
        //Code Block-M2
    }
    ...
    else if (Expression-MN)
    {
        //Code Block-MN
    }
    else
    {
        //Code Block-M(N+1)
    }
}
else
{
    //Code Block-M+1
    if (Expression-(M+1)1)
    {
        //Code Block-(M+1)1
    }
    else if (Expression-(M+1)2)
    {
        //Code Block-(M+1)2
    }
    ...
    else if (Expression-(M+1)N)
    {
        //Code Block-(M+1)N
    }
    else
    {
        //Code Block-(M+1)(N+1)
    }
}

Nested if Statement

  • If the expression-1 is true, Code Block-1 is executed
  • If the expression-1 is true and the expression-11 is true, Code Block-11 is executed
  • If the expression-1 is true and the expression-12 is true, Code Block-12 is executed
  • ...

Nested if Statement

  • If the expression-N is true, Code Block-N is executed
  • If the expression-M is true and the expression-M1 is true, Code Block-M1 is executed
  • If the expression-M is true and the expression-M2 is true, Code Block-M2 is executed
  • If all M-expressions are false, else block is executed

Examples: if...else ladder

int x=2;
int y=3
if(x>=y)
{
    if(x==y)
    {
        printf("%d Equal to %d\n",x,y);
    }
    else
    {
        printf("%d Greater than  %d\n",x,y);
    }
}
else
{
    printf("%d Less than %d\n",x,y);
}

Relational Operators

int x=2; int y=3;
Operator Description Example Result
> Greater than x>y False(0)
< Less than x < y True(1)
>= Greater than or equal to x>=y False(0)
<= Less than or equal to x<=y True(1)

Relational Operators

int x=2; int y=3;
Operator Description Example Result
== Equal to x==y False(0)
!= Not Equal to x!=y True(1)

Logical AND Operators (&&)

int x=2; int y=3; int z=4;
Example Result
x > y && x > z False(0)
x > y && x < z False(0)
x < y && x > z False(0)
x < y && x < z True(1)

Logical OR Operators (||)

int x=2; int y=3; int z=4;
Example Result
x < y || x < z True(1)
x < y || x > z True(1)
x > y || x < z True(1)
x > y || x > z False(0)

Logical NOT Operators (!)

int x=2; int y=3;
Example Result
!(x==y) True(1)
!(x < y) False(0)

switch Statement

switch (n)
{
    case constant1:
        //Code Block-1
        break;
    case constant2:
        //Code Block-2
        break;
    ....
    case constantN:
        //Code Block-N
        break;
    default:
        //Code Block - (N+1)
}

Examples: switch Statement

float a=4;
float b=5;
float c;
char op;
scanf("%c",&op);
switch (op)
{
    case '+':
        c = a + b;
        break;
    case '-':
        c = a - b;
        break;
    case '*':
        c = a * b;
        break;
    case '/':
        c = a / b;
        break;
    default:
        printf("Invalid Operator");
}

Selection Statements

  • if - single-selection statement
  • if...else - double-selection statement
  • switch - multiple-selection statement

Conditional Operator

  • Ternary Operator
  • Three operands
  • Conditional expression
Syntax:
Expression ? TrueStatment: FalseStatement;
grade>=40 ? printf("Pass"): printf("Fail");
x>=y ? max=x: max=y;
x>=y && x>=z? max=x: (y>=x && y>=z ? max=y : max=z);

Comma Operator

  • binary Operator
  • evaluates its first operand and discards the result
  • evaluates the second operand and returns the result
int i = (5,7);//7 is assigned to i
int i = (5,7,4);//4 is assigned to i

Comma Separator

  • Variable Declarations
  • Function Calls
  • Enum declarations
int a=4,b=5,c=6;
int a=3,b=3,c=2;int i = (a,b,c);//2 is assigned to i
printf("%d %f %c", a,b,c);
scantf("%d %f %c", &a,&b,&c);


Key words

Key Words

auto break case char signed
const continue default do short
double else enum extern sizeof
float for goto if static
int long register return struct
switch typedef union unsigned void
volatile while inline restrict _Bool

Operators Associativity

Operators Associativity
() left to right
* / % left to right
+ - left to right
< <= > >= left to right
== != left to right
= right to left

Express Evaluation

  • z=pr mod q + w/x-y
  • z = p * r % q + w / x - y
  • z = a * (b + c) + c * (d + e)
  • y = a * x * x + b * x + c
  • average = a + b + c + d + e / 5

Decimal To Floating Point

  • -12.375
  • 1210=11002
  • 0.37510=0112
  • 12.37510=1100.0112
  • 12.37510=1.1000112x23
  • Mantissa : 1000 1100 0000 0000 0000 000
  • Exponent : 3 + 127 = 130 = 1000 0010
  • Sign bit: 1
  • 1 1000 0010 1000 1100 0000 0000 0000 000


Structured Program

Algorithm

  • The solution to any computing problem involves executing a series of actions in a specific order
  • A procedure for solving a problem in terms of
    1. The actions to be executed
    2. The order in which these actions are to be executed
  • Specifying the order in which statements are to be executed in a computer program is called program control

Pseudocode

  • An artificial and informal language that helps you to develop algorithms
  • Useful for developing algorithms that will be converted to structure programming
  • Similar to Everyday English
  • Not an actual computer programming language
  • Can't be executed on computers
  • Replace pseudo code statements with C equivalents

Pseudocode

  • Contains only action and decision statements
  • Executed only when converted to C and run in C

Control Structure

  • Sequential Execution:Statments are executed one after another in the order in which they're written
  • Transfer of control: got statement
  • Sequence Structure
  • Selection Structure
  • Iteration Structure

Flow Chart

  • A graphical representation of an algorithm or a portion of an algorithm
  • Rounded Rectangles (Start/End)
  • Parallelogram (Input/Output)
  • Rectangles (Process/action)
  • Diamonds (Decision/Condition)
  • Small Circles (Connector)
  • Arrows or flow lines (to connect)

Flow Chart

  • Useful to develop and represent algorithms
  • Shows how control strucutures operate
  • Rectangles (Process)
  • Diamonds (Selection/Condition)
  • Small Circles (Connector)
  • Arrows or flow lines (to connect)

Errors

  • Syntax Error: Compiler identifies
  • Logic Error: Has its effect at execution time
  • Fatal Logic Error: Causes a program to fail and terminate prematurely
  • Nonfatal Logic Error: Allows a program to continue executing but to produce incorrect results

Errors

  • Fatal error: An attempt to divide by zero
  • Infinite Loop: Never ending loop


Iteration Structure

Increment Operators

++ Increases the integer value by 1 x++
-- Decreases the integer value by 1 x--

Bitwise Operators

a = 10; b = 15; a = 0000 1010, b = 0000 1111

& Binary AND a & b 0000 1010
| Binary OR a | b 0000 1111
^ Binary XOR a ^ b 0000 0101
~ Binary OR ~a 1111 0101
<< Binary Left Shift a << 2 0010 1000
>> Binary Right Shift a >> 2 0000 0010
x << y is x * 2y and x >> y is x /(2y)

Assignment (Arithmetic) Operators

a = 10;

= Simple Assignment a=10
+= Add and Assigns a+=5 a = a + 5 15
-= Subtract and Assigns a-=5 a = a - 5 5
*= Multiply and Assigns a*=5 a = a * 5 50
/= Divide and Assigns a/=5 a = a / 5 2
%= Modulus and Assigns a%=5 a = a % 5 0

Assignment (Bitwise Logic) Operators

a = 4; a = 0000 0100

&= Binary AND and Assigns a&=2 a=a & 2; 0
|= Binary OR and Assigns a|=2 a = a | 2 6
^= Binary XOR and Assigns a^=2 a = a ^ 2 6

Assignment (Shift) Operators

a = 4; a = 0000 0100

<<= Binary Left Shift and Assigns a<<=2 a = a << 2 16
>>= Binary Right shift and Assigns a>>=2 a = a >> 2 1

for loop

for(initialization; condition; Update)
{
    statement(s);
}            
  • Initialization: declare and initialize any loop variables. Executed once
  • Condition: Evaluated at each step. True: body of the loop is executed. False: jumps out of the loop
  • UpdateStatement: Evaluated at each step. Once the body of the loop is executed, loop variable is incremented or decremented or updated

while loop

while(condition)
{
    statement(s);
}            
  • Condition: Evaluated at each step. If condition is true, body of the loop is executed. Otherwise, it jumps out of the loop
  • Entry controlled loop

do...while loop

do
{
    statement(s);
}while(condition);            
  • Body of the loop is executed at least once
  • Condition: Evaluated at each step. If condition is true, body of the loop is executed. Otherwise, it jumps out of the loop
  • Exit controlled loop

Example

#include< stdio.h >
int main(void)
{
    int n,sum;
    printf("Enter the integer to get the sum of 1 to n: ");
    scanf("%d",&n);
    if (n<=0)
    {
        printf("Invalid Input\n");
        return 0;
    }
    sum=0;
    for(int i=1;i<=n;i++)
    {
        sum+=i;
    }
    printf("The sum first %d natural numbers  = %d\n",n,sum);
    return 0;
}

Example

#include< stdio.h >
int main()
{
    int n;
    int Prime;

    printf("Enter an integer to find prime numbers between 1 to n: ");
    scanf("%d", &n);

    printf("Prime numbers between 1 to %d are:\n", n);

    for(int i=2; i<=n; i++)
    {
        Prime = 1;
        for(int j=2; j<=i/2; j++)
        {
            if(i%j==0)
            {
                Prime = 0;
                break;
            }
        }

        if(Prime==1)
        {
            printf("%d \t", i);
        }
    }
    printf("\n");

    return 0;
}

Example

#include< stdio.h >
int main()
{
    int n;
    bool Prime;
    int vote;
    int cup=0,candle=0,pen=0,pencil=0,chalk=0;
    printf("Enter the number of voters ");
    scanf("%d", &n);

    int i=0;
    while(i< n) 
    {
        printf("Voter %d: Enter one of the following number to Vote: \n",i+1);
        printf("1. Cup\n");
        printf("2. Candle\n");
        printf("3. Chalk\n");
        printf("4. Pen\n");
        printf("5. Pencil\n");
        scanf("%d",&vote);
        switch(vote)
        {
            case 1:
                cup++;
                i++;
                break;
            case 2:
                candle++;
                i++;
                break;
            case 3:
                chalk++;
                i++;
                break;
            case 4:
                pen++;
                i++;
                break;
            case 5:
                pencil++;
                i++;
                break;
            default:
                printf("Invalid Input, ReEnter\n");
        }
    }
    printf("Number of Votes for Cup: %d\n",cup);
    printf("Number of Votes for Candle: %d\n",candle);
    printf("Number of Votes for Chalk: %d\n",chalk);
    printf("Number of Votes for Pen: %d\n",pen);
    printf("Number of Votes for Pencil: %d\n",pencil);
    return 0;
}

Example

#include< stdio.h >
#include< stdlib.h >
int main()
{
    int n,s=0;
    float num,sum=0,sum2=0;
    printf("Enter the matrix dimension: ");
    scanf("%d",&n);
    if(n<=0)
    {
        printf("Invalid Input\n");
        exit(0);
    }
    for(int i=0;i< n;++i) 
    {
        for(int j=0;j< n;++j)
	    {
		    printf("Enter the a[%d][%d] :",i,j);
		    scanf("%f",&num);
		    s++;
		    sum2=sum2+num;
		    if(num< 0.0)
			    goto jump;
		    if(i==j)
			    continue;
		    if(i+j==n-1)
			    continue;
		    sum=sum+num;
	    }
    }
    printf("Required Sum = %f\n",sum);
jump:
	float average=sum2/s;
	printf("Average of the given input is %.4f\n",average);
	return 0;
}

Operators Associativity

Operators Associativity Type
++, -- left to right postfix
+,-,++, -- right to left prefix,unary
*, /, % left to right multiplicative
+, - left to right additive

Operators Associativity

Operators Associativity Type
< , <=, >, >= left to right relational
== , != left to right equality
?: right to left conditional
=,+=,-=,*=,/=,%= right to left assignment

Iterations

  • Counter Controlled Iteration of definite iteration
  • Sentinel-Controlled iteration or indefinite iteration

while, do...while

Comparison while do...while
Controlling Condition appears at the start of the loop appears at the end of the loop
Iterations won't occur if the condition at the first iteration is false occurs at least once irrespective of the condition is true or false

for and while

Comparison for while
Initalization, Conditions, iteration at the top of the loop before/top the loop, top of the loop, unnecessary
Number of Iterations known unknown
If no Condition infinite loop compilation error

for and while

Comparison for while
Initalization Only once, never repeated can be done inside the loop
Iterations at the top or inside, preferably top inside the loop, can be with condition


Functions

Function

  • A collection of statements grouped together to perform a specific task
  • Allow you modularize the program
  • All variables in function are local variables
  • Divide code into separate functions logically

Function

  • Declaration: tells the compiler about its name, parameter (input) and return type
  • Definition: Provides actual body
  • Method, sub-routine, procedure
  • Recursion: A function that calls itself is known as a recursive function

Syntax

returnType functionName( input parameters )
{
    statement(s);
}
  • returnType is the data type of the value that function returns, can be void
  • input parameters: can be empty, if non-empty, same number of arguments should be specified while calling.

Examples

#include< stdio.h >
int smallest(int x, int y)
{
    if(x< y) 
    {
        return x;
    }
    else
    {
        return y;
    }
}
int main(void)
{
    int a,b;
    printf("Enter two integers, let me tell your their relations\n");
    printf("Enter the first integer: ");
    scanf(" %d",&a);
    printf("Enter the second integer: ");
    scanf(" %d",&b);
    int c=smallest(a,b);
    printf("%d is the smallest between %d and %d\n",c,a,b);
    return 0;
}

Examples

#include < stdio.h>
void PrimeNumber(int x)
{
    int Prime = 1;
    for(int j=2; j<=x/2; j++)
    {
        if(x%j==0)
        {
            Prime = 0;
            break;
        }
    }

    if(Prime==1)
    {
        printf("%d \t", x);
    }
}
int main()
{
    int n;
    int Prime;

    printf("Enter an integer to find prime numbers between 1 to n: ");
    scanf("%d", &n);

    printf("Prime numbers between 1 to %d are:\n", n);

    for(int i=2; i<=n; i++)
    {
        PrimeNumber(i);
    }
    printf("\n");
    return 0;
}

math.h

Function Description Example
sqrt(x) Square root of x sqrt(900.0)
cbrt(x) Cube root of x cbrt(8.0)
exp(x) exponential ex exp(3.0)
log(x) natural logarithm function log(3.0)

math.h

Function Description Example
pow(x,y) x raised to power y xy pow(2,5)
fmod(x,y) remainder of x/y as a floating point fmod(13.657,2.333)
sin(x),cos(x),tan(x) trignometric functions in radians sin(0),cos(0),tan(0)

math.h

Function Description Example
log10(x) logarithm of x log10(900.0)
fabs(x) absolute value of float fabs(-8.0)
ceil(x) smallest integer not less than x ceil(9.2)
floor(x) smallest integer not greater than x floor(8.5)

Recursive Function

  • Recursion: A function that calls itself is known as a recursive function

Examples

#include < stdio.h>
int factorial(int x)
{
    if(x>1)
    {
        x=x*factorial(x-1);
    }
    else
        return 1;
}

int main()
{
    int n;
    printf("Enter an integer to find the factorial: ");
    scanf("%d", &n);
    int f;
    if(n < 0) 
    {
        printf("Factorial of Negative number is not possible\n");
        return 0;
    }
    else if(n= =0)
    {
        f=1;
    }
    else
        f=factorial(n);
    printf("(%d)!=%d\n", n,f);
    return 0;
}

Pass by Value

  • Copies the actual value of an argument into the formal parameter of the function
  • Parameter modified inside the function, but has no effect on the argument

Examples

#include< stdio.h >
void swap(int x, int y)
{
    int temp=x;
    x=y;
    y=temp;
}
int main(void)
{
    int a,b;
    printf("Enter two integers\n");
    scanf(" %d %d",&a,&b);
    printf("a = %d b= %d\n",a,b);
    swap(a,b);
    printf("a = %d b= %d\n",a,b);
    return 0;
}

Pass by Reference

  • Copies the address of an argument into the formal parameter of the function
  • Parameter modified inside the function, affects value of the argument

Examples

#include< stdio.h >
void swap(int *x, int *y)
{
    int temp=x;
    x=y;
    y=temp;
}
int main(void)
{
    int a,b;
    printf("Enter two integers\n");
    scanf(" %d %d",&a,&b);
    printf("a = %d b= %d\n",a,b);
    swap(&a,&b);
    printf("a = %d b= %d\n",a,b);
    return 0;
}


Numerical Methods

Eigen Values/Vectors

Eigen Values/Vectors

  • Eigen vector is a non-zero vector. If T is a linear transformation from V to V and v is a non-zero vector of V, then v is said to be an eigen vector if T(v) is a scalar multiple of v
  • The scalar multiple is called eigen value

SVD

Image Compression

  • Hundreds of ways to Compress images, BTC, SVD,...
  • 9MP gray scale image: 3000 x 3000 pixel
  • For each pixel, we have same level of black and white
  • 1 Pixel requires 1 byte storage
  • For 9MP gray scale image ~ 8.6MB
  • For 9MP RGB image ~ 25.8MB
  • For 9MP CMYK image ~ 34.4MB

Image/Video Compression

  • For a HD TV, we need 1080 x 1920 pixels
  • Most probably 24 frames per second
  • Per Frame for RGB image, we need 5.94MB
  • For 24 frames, we need 142.32MB

SVD

  • Any real or complex matrix matrix A can be factorized as
  • U is an Unitary Matrix
  • V is an Unitary Matrix
  • Matrix with non-negative real numbers
  • entries are known as singular values

SVD

  • SVD: There are orthonormal bases (v's and u's for the row and colum spaces) such that entries are known as singular values
  • Use the unit eigenvectors of u (left singular vectors) of
  • Use the unit eigenvectors of v (right singular vectors) of
  • are singular value, square roots of the eigenvalues of

SVD

  • Both are spectral decompositions
  • gives positive square roots of the eigenvalues of We can re-arrange the decomposition such that
  • Spectral Theorem: If A is a symmetric matrix, then ,where U is an orthonormal matrix of eigen vectors and is a diagonal matirx of eigenvalues

Image/Video Compression

  • Send the vector U, ,V
  • Send only few vectors that contribute most to the sum. It can reduce image quality, but reduces storage space.
  • Let us send first k vectors and see the result

SVD Compression

SVD Compression

SVD Compression

SVD Compression

Image/Video Compression

  • For k=100, accurate production with 7.53% error
  • For k=100, 40% of the original image size
  • For 3000 x 3000 pixel, RGB image, it is enough to transmit 10.32MB
  • For HD TV, RGB image, it is enough to transmit 56.92MB


Graphical Method

Graphical Method

  • Simple Method
  • An estimate to find the root of the equation
  • Make a plot of the function
  • Find when does it cross the x axis

Roots

Different Roots



Bracketing Methods

Bisection Method

Intermediate Value Theorem

  • If is continuous on a closed interval and is any number between and then there is at least one number in the closed interval such that

Intermediate Value Theorem

  • If is continuous on a closed interval and then there is at least one number in the closed interval such that

Bisection Method

Bisection Method

Bisection Algorithm

  • Input: and
  • Output: root
  1. Guess and for the root such that the
  2. Estimate the root:
  3. If , the root lies in the lower subinterval. Set and return to Step 2
  4. Else If , the root lies in the lower subinterval. Set and return to Step 2
  5. Else , then is the root of the function

Bisection Method

Parachutist

  • Assume

Bisection Algorithm Output

Quadratic Equation

  • Assume

Different Roots



Bracketing Methods

False position Method

False-Position Method

  • Alternative to bisection method
  • Drawback of bisection method: When dividing the interval and into equal halves, we don't worry about and
  • To overcome, this we join and by a straight line.

False Position Method

False Position Algorithm

  • Input: and
  • Output: root
  1. Guess and for the root such that the
  2. Estimate the root:
  3. If , the root lies in the lower subinterval. Set and return to Step 2
  4. Else If , the root lies in the lower subinterval. Set and return to Step 2
  5. Else , then is the root of the function

False Position

Bisection/False Position Comparison

Modified False Position

  • The draw back of false position method is its onsideness
  • To overcome this drawback modified false position method implement the following strategy
    • It counts the number of times the bounds stays in oneside
    • If it stays at least two times, then the function value at this stagnant bound is halved


Numerical Errors

Accuracy and Precision

  • Accuarcy: It refers to how closely a computed or measured values agrees with the true value
  • Precision: It refers to how closely computed or measured values agree with each other
  • Inaccuracy or bias: Systmatic deviation from truth
  • Imprecision or uncertainty: Refers to the magnitude of the scatter

Accuracy and Precision

Errors

  • True Error:
  • True Relative Error
  • True Percent Relative Error
  • Normalized approximat percent relative error

Round off Error

  • Round off error: The difference between an approximation of a number used in computation and its exact value.
  • or The difference between the result produced by a given algorithm using exact arithmetic and the result produced by the same algorithm using finite-precision

Round off Error

  • Computers can represent to a finite precision
  • Most important for real numbers
  • Machine dependent
  • Result from using an approximate number to represent exact number
  • Examples:
  • Due to limited bits for storage

Floating Point Representation

  • m: mantissa, b: base, e: exponent
  • Chopping
  • If e is too large, overflow error: nan or -nan
  • If e is too small, underflow error: simply set to 0

Truncation Error

  • Method dependent
  • Errors obtained from using an approximation rather than exact procedure
  • Examples: Taylor Series

Big O, little o

Let be two different sequences, we write if there are constants C and r such that , when .

remains bounded by C as That is

Big O, little o

Examples:

Big O, little o

Examples:

Order of Convergence

Let be a sequence which converges to TV. If there exists a number s.t.
  • is called the order of convergence
  • C is error constant
  • Linear Convergence, if That is

Order of Convergence

  • Super Linear, if , That is,
  • Quadratic, if

Order of Convergence for Bisection



Open Methods

Fixed Point Iteration

Disadvantages of Brakceting methods

  • Root is located within an interval
  • Although, this method converges always, it is not always possible to locate the lower and upper interval
  • Slow convergence
  • Not suitable to find multiple roots or function whose tangent is x-axis or function with significant curvature

Open Methods

  • Require one initial guess or two starting values
  • It is not necessary that initial guesses should bracket the root
  • It can diverge or move away from the true root
  • Converge much more quickly than the bracketing methods

Fixed Point

A fixed point of a function is an element of the function's domain that is mapped to itself by the function

x is a fixed point of the function f, if f(x)=x

Fixed Point and continuous

Let be a continuous function. Define a sequence in by and then

Therefore, is called a fixed point of the function

Brouwer's fixed point theorem

Every continuous function from a closed disk to itself has at least one fixed point

Contractive Mapping

A function is said to be contractive if there exists a number such that for all points

Contractive Mapping Theorem

Let be a contractive mapping. Then has a unique fixed point. Moreover, this fixed point is the limit of every sequences obtained from with any starting point

Fixed Point Iteration

  • Suppose is a given function and you would like to find the roots of the function
  • Then write
  • Re-arrange the function in such a way that
  • Simply you can add and subtract on both sides, that is
  • Now, finding the root of is same as finding the fixed point

Fixed Point Iteration

  • Define
  • Then for given initial guess , we obtain the fixed point of the function and hence the root of the function

Fixed Point Iteration

Fixed Point Iteration

Fixed Point Iteration Algorithm

  • Input: and
  • Output: root
  1. Convert to
  2. If ,
  3. If , then goto step 3

Order of Convergence for Fixed Point Iterations

and

By MVT for some which is a point between and TV

for some

Order of Convergence for Fixed Point Iterations

If ,then the error decreases.

Also

Therefore, p=1, C < 1 and linear convergent


Open Methods

Newton Raphson Method

Newton-Raphson Method

Most widely used method to find roots

x is a fixed point of the function f, if f(x)=x

Newton-Raphson Method

Taylor Series

Let be a continuous function and exists and continuous, then

Suppose the root of is then

Let then

Newton-Raphson Algorithm

  • Input: and
  • Output: root
  1. For i=1,2,...,M
    1. If , Stop
    2. If
    3. If ,
    4. If , then stop

Order of Convergence for Newton-Rapshon

By Taylor's Theorem for some which is a point between and TV

Order of Convergence for Newton-Rapshon

Order of Convergence for Newton-Rapshon

p=2, therefore quadratic convergence

Newton-Raphson Method-Fails

Newton-Raphson Method-Fails



Open Methods

Secant Method

Newton-Raphson Method

Difficult to find the derivatives for a few function

It can perform poorly

It can diverge from the root

Secant Method

Secant Method

In the Newton-Raphson method replace the derivative using backward finite difference method

Secant Method

It requires two initial estimates

Secant Algorithm

  • Input: and
  • Output: root
  1. For i=1,2,...,M
    1. If , Stop
    2. If
    3. If ,
    4. If , then stop

Secant vs False-Position

Secant,Bisection,False-position,Newton

Modified Secant Method

It requires only one initial estimate



Muller's Method for Roots of Polynomials

Muller's Method

Secant method obtains a root estimate by projecting a straight line to the x-axis through function values

Muller's method takes a similar approach but projects a parabola through three points

Muller's Method

Muller's Method

Let us find a parabola equation joining three points

Consider the following parabola

At given three points

Muller's Method

Muller's Method

Let

Then on simplification, we get

Muller's Method

Muller's Algorithm

  • Input: and
  • Output: root
  1. For i=1,2,...,M
    1. ,
    2. If , then Else
    3. ,
    4. If , Stop.
    5. Else


CPU Cache

CPU Cache

  • A CPU cache is a smaller faster memory used by the CPU of a computer to reduce the average time to access memory
  • L1 Cache - Level 1 Cache - 2KB - 64 KB
  • L2 Cache - Level 2 Cache - 256KB - 512 KB
  • L3 Cache - Level 3 Cache - 1MB - 8 MB

L1 Cache

  • Instructions are first searched in this cache
  • Very small in size. Faster than the rest

L2 Cache

  • If the instructions are not present in the L1 cache then it looks in the L2 Cache
  • It is bigger in size than L1, slower than L1, but faster than L3

L3 Cache

  • If the instructions are not present in the L1 and L2 cache then it looks in the L3 Cache
  • It is bigger in size than L1 and L2, slower than L1 and L2, but faster than RAM

CPU Cache



Arrays

Arrays

  • An array is a group of contiguous memory locations that all have same data type.
  • To refer a particular location or element in the array specity the array's name and the position number of the particular element in the array
  • Firs Element in every arrays is the zeroth element

Arrays

  • Any one of the elements may be referred to by giving the array's name followed by the position number of the particular element in square brackets []
  • The position number in the square bracket is called the element's index or subscript

Types

  • One Dimensional Arrays
  • Multidimensional Arrays

1D Arrays

VariableType ArrayName[N1];
  • A structured collection of components or often called array elements
  • Must be declared before usage
  • Example: Vectors
  • Number of Elements = N1

1D Arrays

  • Initializing Arrays
  • Accessing Array elements

2D Arrays

VariableType ArrayName[N1][N2];
  • Array of arrays
  • Require two indices
  • Example: Matrices
  • Number of Elements = N1*N2

2D Arrays

  • Initializing Arrays
  • Accessing Array elements

Multidimensional Arrays

VariableType ArrayName[N1][N2]...[Nm];
  • Require multi indices
  • Number of Elements N1*N2*..*Nm

1DArray.C

#include<stdio.h> //header file
int main(void)
{
    int n[5]={2,3,4,5,8};
    for(int i=0;i< 5;i++)
    {
        printf("n[%d]=%d\n",i,n[i]);
    }
    return 0;
}

1DArrayEx.C

#include<stdio.h> //header file
#define SIZE 100
int main(void)
{
    int n[10]={0};
    int s[]={1,3,4,56,78,34};
    int t[SIZE];
    for(int i=0;i < SIZE;i++)
    {
        t[i]=2*i;
    }
//Codes here
    return 0;
}

Preprocessor directive

  • #define SIZE 100
  • It defines symbolic constant SIZE whose value is 100
  • A symbolic constant is an identifier that is replaced with replacement text by the C preprocessor before the program is compiled

Arrays and Function

  • To pass an array argument to a function, specify the arrays name without brackets
#include<stdio.h> //header file
#define VECSIZE 100
double dotproduct(const double vectorA[],const double vectorB[])
{
    double sum=0;
    for(int i=0;i < VECSIZE;i++)
    {
        sum+=vectorA[i]*vectorB[i];
    }
    return sum;
}
int main(void)
{
    double vec_A[VECSIZE];
    double vec_B[VECSIZE];
    for(int i=0;i < VECSIZE;i++)
    {
        vec_A[i]=100-i*i;
        vec_B[i]=300-i*i;
    }
    printf("A.B=%lf\n",dotproduct(vec_A,vec_B));
    return 0;
}


Pointers

Pointers

  • A Variable whose value is the address of another variable
  • Direct access of memory location
  • Must declare before you can use it to store any variable address
  • Allows us to indirectly access variables, that is, talk about its address rather than its value

Pointers

  • Understanding of pointers and your ability to use separate you from novice programmer to experienced one
  • The basic concept is simple: variable that stores the address of a memory location
  • However, complicated when we start applying pointer operators and discern their cryptic notations

Pointers-Syntax

VariableType *PtrVariable;
  • * indicates variable is a pointer
  • Pointers can be defined to point to objects of any type

Pointers-Declaration

int y=5;
int *yPtr;
yPtr=&y; 
  • Caution: Each pointer must be declared with * prefixed to the name

Pointers-Initialization

  • Should be initialized when they are defined or they can be assigned a value
  • A pointer may be initialized to NULL, 0 or an address
  • NULL - A symbolic constant
  • Initializing to 0 is equivalent to initializing NULL

Pointers And Memory

Types Scope Lifetime
Global The entire file The lifetime of the application
Static The function where it is declared within The lifetime of the application
Automatic/local The function where it is declared within While the function is executing
Dynamic Determined by the pointers that reference this memory Until the memory is freed

Why Pointers

  • Creating fast and efficient code
  • Providing a convenient means for addressing many types of problems
  • Supporting dynamic memory allocation
  • Making expressions compact and succinct
  • Providing the ability to pass data structures by pointer without incurring a large overhead
  • Protecting data passed as a parameter to a function

Problems with Pointers

Although Pointer is a powerful tool, the following problems can occur
  • Accessing arrays and other data structures beyond their bounds
  • Reference local variables after they have gone out of existence
  • Referencing heap allocated memory after it has been released
  • Dereferencing a pointer before memory has been allocated to it

Address (&) Operator

  • Unary Operator
  • Returns address of its operand
int y=5;
int *yPtr;
yPtr=&y;
  • The last statement assigns the address of the variable y to pointer variable yPtr.
  • yPtr is said to be point to y

Address (&) Operator

  • The operand of the address operator must be a variable
  • The address operator can't be applied to constants or expression

Indirection (*) Operator

  • Unary operator
  • Indirection or Dereferencing operator
  • Returns the value of the object to which its operand points
printf("%d", *yPtr);
prints the value of the variable y(5).

Caution: Fatal Execution Error: Dereferencing a pointer that has not been properly initialized or that has not been assigned to point to a specific location in memory is an error.

Operators Associativity

Operators Associativity Type
[], (), ++(postfix), --(postfix) left to right postfix
+,-,++, --, !, *, & right to left prefix,unary
*, /, % left to right multiplicative
+, - left to right additive

Operators Associativity

Operators Associativity Type
< , <=, >, >= left to right relational
== , != left to right equality
&& left to right logical AND
|| left to right logical OR

Operators Associativity

Operators Associativity Type
?: right to left conditional
=,+=,-=,*=,/=,%= right to left assignment
, left to right comma

Passing Arguments and Pointers

  • Pass by value
  • Pass by reference

Pass by Value

#include<stdio.h> //header file
int Square(int n)
{
    return n*n;
}
  
int main(void)
{
    int num=5;
    printf("Square of %d is %d\n",num,Square(num));
    return 0;
}

Pass by Reference

#include<stdio.h> //header file
void Square(int *numPtr)
{
    *numPtr = *numPtr * *numPtr;
}
int main(void)
{
    int num=5;
    Square(&num);
    printf("Square of %d is %d\n",num,Square(num));
    return 0;
}

Pass by Reference

  • Address of the number is passed to function Square
  • Function takes as a parameter pointer to an integer, numPtr
  • The function dereferences the pointer and squares the value to which the numPtr points
  • Assigns the result to *numPtr
  • The *numPtr is same as num in main
  • Changes the value of num in main

Pass by Reference

Caution: Use pass-by-value to pass arguments to a function, unless the caller explicity requires the called function to modify the value of the argument variable in the caller's environment. This prevents accidental modification of the caller's arguments and is another example of the principle of least privilege.



Numerical Linear Algebra

Linear System

  • Linear System has a plenty of applications
  • Artificial Intelligence, Machine Learning
  • Spring System, Electrical Circuits
  • All Engineering Disciplines and so on

Diagonal System

  • When the linear system is diagonal( ), it is easy to solve
and

The solution is

Upper Triangular System

  • When the linear system is an Upper Triangular system( ), we can move from the backward direction to find the solution.
and

The solution is

Backward Substitution Algorithm

  • Input: and
  • Output:

Lower Triangular System

  • When the linear system is a lower Triangular system( ), we can move from the forward direction to find the solution.
and

The solution is

Forward Substitution Algorithm

  • Input: and
  • and



Gauss Elimination

  • It is a method to solve a linear system
  • Using elementary row operations, we reduce the system to upper triangular form
  • Using Forward Substitution, we can solve the system

Gauss Elimination

=

,

,

Gauss Elimination

,

,

,

Gauss Elimination

,

On Repeating the procedure ,

Using Backward substitution we can solve this problem to find the solution.

Gauss Elimination Algorithm

  • Input:
  • Output:

  1. Initialization


LU Decomposition

LU Decomposition

  • We know that it is easy to solve diagonal system
  • We know that it is easy to solve upper triangular system using backward substitution
  • We know that it is easy to solve lower triangular system using forward substitution
  • If we can decompose the system as follows , then we can solve it in the following manner
  • Therefore, first we can solve using forward substitution and then using backward substitution

LU Decomposition

It is not necessary that we get an unique LU decomposition. We can select or or or or we can select any non-zero values, that is or

LU Decomposition Algorithm

  • Input:
  • Output:

  1. Initialization

Doolittle Decomposition Algorithm

Here we assume that, unit upper triangular system, that is,

  • Input:
  • Output:

  1. Initialization

Crout Decomposition Algorithm

Here we assume that, unit lower triangular system, that is,

  • Input:
  • Output:

  1. Initialization

Cholesky Decomposition Algorithm

Here we assume that is symmetric, therefore, we get

  • Input:
  • Output:

  1. Initialization, Check Symmetri Matrix


Operation Counting

Operation Counting

  • When an algorithm is developed, we should discuss the complexity and the number of floating point operations involved in the process
  • Let us revisit Gauss Elimination method with a matrix and generalize it for

Gauss Elimination

=

,

  • We have done, 4 divisions on the matrix
  • Therefore, in case of d matrix, we have division (floating point operations).
  • Similarly for computing the RHS, we have one division
  • Therefore we have operations

Gauss Elimination

,

  • For each row, we have to multiply by and subtract.
  • Therefore, we require 4 operations for each row to multiply and four operations to subtract. Hence, operations per row is required.
  • For each row of the RHS, we require 2 operations.
  • We should perform above operations for each of the 3 rows. So, finally, we require operations for matrix.
  • In terms of matrix, we require operations per row for RHS and operations for LHS
  • Therefore, we require, operations.

Gauss Elimination

,

  • To reduce the system to the above form, we require operations.
  • Therefore, we require, operations for system.
  • If we concentrate only the red color matrices, then it is an system.
  • If we repeat the same operations to get system, we require operations.
  • Hence, if we would like to reduce from system to system, we require operations.
  • To reach from system to system, we require operations.

Gauss Elimination

  • For a matrix, we have operations.

Backward/Forward Substitution

  • Now let us see, how many operations required for forward/backward substitution.
  • Operation Count is 1 for
  • Number of Operation Count for step is multiplications and additions, then 1 subtraction and 1 division.
  • Therefore, we require operations/
  • Total number of operations is
  • For a unit upper/lower triangular system, we require only

Gaussian Elimination to solve a system

  • Therefore to solve a system using Gauss Elimination method, we require operations.
  • When the system is too large, we require more computations. For example for we require operations.

Doolittle/Crout/LU/Cholesky Decomposition Operation Count

  • For Doolittle, Crout, Cholesky and LU Decomposition also we require operations. (Exercise!)


Theorems

Sufficient Condition for LU Decomposition

  • If all leading principla minors of the matrix are non-singular then has an LU-Decomposition.

Condition for Cholesky Decomposition

  • If is a real, symmetric and positive definite matrix, then it has a unique ffactorization in which is lower triangular with a positive diagonal


Tridiagonal System

Tridiagonal System

  • A square matrix is said to be tridiagonal if

Using Gaussian elimination, you can develope a simple algorithm to solve this problem (Exercise: Develop an algorithm to solve this kind of matrices)



Matrix Norm

Vector Norms

  • On a vector space a norm is a function from to the set of nonnegative reals that obeys the following three postulats
  • Euclidean norm
  • - norm
  • - norm,
  • - norm

Matrix Norms

  • If a vector norm has been specified, the matrix norm subordinate to it is defined by
  • Euclidean norm
  • row sum norm
  • Column sum norm

Condition Number and Ill-Conditioned System

  • Matrix Condition number is defined by
  • Well-conditioned system: A system is said to be well-conditioned if small changes on one or more of the coefficients results in a similar smaller change in the solution
  • Ill-conditioned system: A system is said to be ill-conditioned if small changes on one or more of the coefficients results in a large changes in the solution
  • A matrix with large condition number is said to be ill-conditioned.
  • A matrix with moderate condition number is said to be well-conditioned.

An example for ill-conditioned system: A small change (perturbation) produces a big change to the solution



Iterative Methods

Solution by Iteration

  • For the given system , we introduce a splitting matrix that splits then
  • For the given initial guess
  • , we get
  • If the sequence converges to , then
  • By repeating we obtain
  • Theorem: If , we get a convergent solution for the system

Iterative Methods

  • Richardson Method
  • Jacobi Method where denotes the diagonal elements of the matrix
  • Gauss-Seidel Method denote the diagonal elements of the matrix of , the negative of strictly lower triangular part of and the negative of strictly upper triangular part of respectively

Richardson Iteration

  • Input:
  • Output:

  1. Initialization
  2. stop

Jacobi Iteration

  • Input:
  • Output:

  1. Initialization
  2. stop

Gauss-Seidel Iteration

  • Input:
  • Output:

  1. Initialization
  2. stop