Algorithms and Problem Solving
(Programming Concept)
Objectives
• Identify the basic components of a C++
• Identify and use the standard C++ data types.
• Define and use variables.
• Read data from the keyboard and output data.
• Add comments to a program as a form of inline documentation.
• Create “intelligent” names to make programs easier to read and
understand.
2
Write a program calculating the sum of two numbers
Input Processing Output
5, 10 15
1) Declare variables 3) Process
2) Assign values
input_1 sum = input_1 + input_2
input_1 = 5
input_2
input_2 = 10
sum
Names for our cells The computer (and so C)
provides basic arithmetic 3
operations. If the operation
you want to use is not provided,
you have
3 to compose it.
Write a program calculating the sum of two numbers
There are many models supporting the development
of the code. We will see now the same algorithm
expressed as
• Pseudocode, A precise algorithmic description of program logic
• Structure Diagram
• Flowcharts
and finally in C++.
4
Write a program calculating the sum of two numbers
Version 1: Pseudocode
PROGRAM Add Two Numbers
READ two numbers
ADD the numbers
WRITE the sum Version 2:
END PROGRAM PROGRAM Add Two Numbers
READ First
READ Second
Sum = First + Second
Pseudocode are WRITE Sum
English-like statements that END PROGRAM
follow a loosely defined syntax
and are used to convey the design
of an algorithm.
5
Write a program calculating the sum of two numbers
Version 1: PROGRAM
Add Two Numbers Structure Diagram
READ ADD WRITE
Two Numbers Two Numbers The Sum
Version 2: PROGRAM
Add Two Numbers
READ ADD WRITE
Two Numbers Two Numbers The Sum
READ READ Sum =
Input_1 Input_2 Input_1 + Input_2
6
Write a program calculating the sum of two numbers
Flowcharts
START
READ First
READ Second
Sum = First + Second
WRITE Sum
STOP
7
Write a program calculating the sum of two numbers
Pseudocode are more closely to the programming
language and for the advanced programmer.
Structure Diagrams are helpful to break the algorithm
into more manageable pieces.
Flowcharts show the workflow of the algorithm and
stress on structured programming.
Every model has its advantages and disadvantages. But all try to
help you to structure your code in a top-down style and this is the
way you should implement your algorithm.
8
8
Write a program calculating the sum of two numbers
C++
#include <iostream>
using namespace std;
int main()
{
int first, second, sum;
cin >> first;
cin >> second;
sum = first + second;
cout << “the sum is ”;
cout << sum << endl;
return(0);
}
9
Top-Down Design
If we look at a problem as a whole, it may seem impossible to
solve because it is so complex. Examples:
Writing a tax computation program
Writing a library system
Writing a bank system
Complex problems can be solved using top-down design, also
known as stepwise refinement, where
We break the problem into parts
Then break the parts into smaller parts
Soon, each of the parts will be easy to solve
10
Advantages of Top-Down Design
• Breaking the problem into parts helps us to clarify
what needs to be done.
• At each step of refinement, the new parts become
less complicated and, therefore, easier to figure out.
• Parts of the solution may turn out to be reusable.
• Breaking the problem into parts allows more than
one person to work on the solution.
11
A Top-down analysis of a simple cooking task
Cook
breakfast
Bring out Take out Cook Serve
cook ware Uncooked food food food
Get Get Get Get
coffee pot frying pan fork serving dishes
12
Rules for Structure Charts
• A module which resides above others is
referred to as a Calling module
• A module which resides below another is
referred to as a Called module
• A module can be both a calling and called
module
• A called module can only be called by one
calling module
13
An example on Structured design
Mr ABC is a school teacher. He wants to develop a
computer program to help him analyze his student‟s
results. The program should allow him to input data, do
analysis and print out some reports. The analysis
involves statistical tools such as calculating the average,
finding the minimum and maximum marks, calculating
the CGPA of the students, assigning the grade to each
student, and counts how many students passed his
subject. The system also should print out reports
summarizing the class results, printing a report of an
individual, and showing a histogram of the grades
assigned in the class.
14
The structured chart
Mark Analyzer
Statistical Generate
Input Data
Analysis Reports
Pass/Fail CGPA Grade
Min Max Avg Pass/Fail CGPA Grade
15
Flowcharts
What is a flowchart?
• A flowchart illustrates the steps or process to solve a problem.
• By visualizing the process, a flowchart can quickly help
identify bottlenecks or inefficiencies where the process can be
streamlined or improved.
• The final visualization can then be easily translated in to a
program.
16
17
Flowcharting symbols
• Input/Output (used for all I/O operations)
• Processing (used for all arithmetic and data transfer operations).
• Decision (used to test for a condition).
Terminal (used to indicate the beginning and end of a
program or module).
Connector (used to indicate the point at which a
transfer of control operation occurs).
Predefined (used to indicate the name process of a
module to be executed).
Connecting all the symbols and showing the flow
18
FLOWCHARTING CONVENTIONS
1. Each symbol denotes a type of operation.
2. A note is written inside each symbol to indicate the specific
function to be performed.
3. The symbols are connected by flow-lines.
4. Flowcharts are drawn and read from top to bottom unless a
specific condition is met that alters the path.
5. A sequence of operations is performed until a terminal symbol
designates the sequence's end or the end of the program.
6. Sometimes several steps or statements are combined in a single
processing symbol for ease of reading.
19
Structured Programming
• Structured Programming is a technique using logical control constructs
that make programs easier to read, debug, and modify if changes are
required.
true false
true
Sequence Selection
Repetition
20
start
A flowchart to accept two numbers as
input and prints out the maximum
Input A
Input B
False IF
True
A> B
print B print A
end
21
Different selection structures
If a > 10 then do S1 If a > 10 then do nothing else do S2
false true
true false
A>10
A>10
S1 S1
If a > 10 then do S1 else do S2 If a <= 10 then do S2
True False
true false
A>10 A<=10
S1 S2 S1
22
Loop structures
False
S1 A<=10
true
S2
S1
true
A<=10
S2
False
Repeat While A is less than or
S1 equal to 10 repeat
S2 S1
As long as A is Less than or S2
equal to 10 otherwise exit End loop
the loop
What is the difference
23
?
Loop example (do..While)
Draw a flowchart to allow the input of 5 Start
numbers and displays out the sum of these
numbers
1 C=1
Assume the numbers given to
A are 3,2,4,5,6 in order
2 Sum=0
C=1 C=1 C=2
C=1
Sum = 0 Sum = 3 Sum = 3
Sum = 0
A=3 A=3 A=3 3 Input A
1,2 3 4 5
4 Sum = Sum + A
C=2 C=2 C=2 C=3
Sum = 3
5 C=C+1
Sum = 3 Sum = 5 Sum = 5
A=3 A=2 A=2 A=2
C <=5 true true
3 4 6 c<=5
6 5
False
C=3 C=3 C=3 C=4 Output
7 Sum
Sum = 3 Sum = 5 Sum = 8 Sum = 8
A=3 A=4 A=4 A=4
C <=5 true End
24
6 3 4 5
Loop example (while…)
Draw a flowchart to allow the input of Start
5 numbers and displays out the sum
of these numbers
1 C=1
1 C=1 Assume the numbers given to
2 Sum=0
A are 3,2,4,5,6 in order
2 C=1 False
Sum = 0 3 c<=5
4 5 6
true
3
C=1 C=1 C=1 C=2 4
Sum = 0 Sum = 3 Sum = 3 Sum = 3 Input A
C <=5 true A=3 A=3 A=3
5 Sum = Sum + A
C=2 C=2 C=2 C=3 6 C=C+1
Sum = 3 Sum = 3 Sum = 5 Sum = 5
C <=5 true A=2 A=2 A=3
Output
3 4 5 6 7 Sum
25 End
Prime number example flowchart
Start 1
Pseudo code algorithm to
solve this problem: Input M 2
I=2 3
1. Start
C=0 4
2. Input a number M
3. Set an Index (I) to start from 2
4. Set C to 0 R=M%I 5
5. Divide the number M by the False
R=0
True
Index (I) value and store the ?
remainder in R C=C+1 6
6. If R is equal to zero then add 1
to C
I=I+1 7
7. Increment Index (I) by 1
True I<M 8
8. If the Index (I) value is less ?
than the number M go to step 5 False
False
9. If C is equal to 0 then output C=0
True 9
?
Prime otherwise output not prime. Output Output
Not Prime Prime
10. end
26
End 10
Structured Flowcharts Start 1
Start 1 Input M 2
Input M 2 I=2 3
I=2 3 4
C=0
C=0 4
R=M%I 5
R=M%I 5
Replace If
False
R=0
True statement 6
? in step 6
C=C+1 6
I=I+1 7
I=I+1 7 True I<M 8
?
True I<M 8
?
False
False Replace If
False
C=0
True 9 statement 9
? in step 9
Output Output
Not Prime Prime
End 10
27
End 10
Structured flowcharts
Start 1 Start 1 Start 1 Start
Input M 2
Steps 2,3,4 Steps 2,3,4
I=2 3 since they are 2 since they are 2
executed once executed once
C=0 4
R=M%I 5
Replaces the Steps 2,3 and
Sequence
Steps 3 and 4
blocks 5,6, 4 form a
Replace If form a loop
statement in 6 and 7 since 3 which is one
sequence
they are which is one
of the
step 6 repeated
structure
3 of the
equal number structure
types (loop)
of times types
I=I+1 7
True I<M 8 True I<M 4
? ?
False False
Replace If Replace If Replace If
statement in 9 statement in 5 statement in 4
step 9 step 9 step 9
28
End 10 End 6 End 5 End
Another example of structured flowchart
29
Unstructured Flowchart
Now try to simplify this flowchart to any of the three
structured types……Try it if you can !!!!!
30
Introduction to C++
• Where did C++ come from?
– Derived from the C language
– C was derived from the B language
– B was derived from the BCPL language
• Why the „++‟?
++ is an operator in C++ and results in a cute pun
31
Introduction to C++
32
C++ History
• C developed by Dennis Ritchie at AT&T
Bell Labs in the 1970s.
– Used to maintain UNIX systems
– Many commercial applications written in c
• C++ developed by Bjarne Stroustrup at AT&T
Bell Labs in the 1980s.
– Overcame several shortcomings of C
– Incorporated object oriented programming
– C remains a subset of C++
33
A Sample C++ Program
• A simple C++ program begins this way
#include <iostream>
using namespace std;
int main()
{
• And ends this way
return 0;
}
34
35
Comments
Comments are pieces of source code discarded from the code by the
compiler. They do nothing. Their purpose is only to allow the
programmer to insert notes or descriptions embedded within the
source code.
C++ supports two ways to insert comments:
// line comment
/* block comment */
/* my second program in C++
with more comments */
#include <iostream.h>
int main ()
{
cout << "Hello World! "; // says Hello World!
return 0;
} 36
My first program in C++ Hello World!
a comment line
a pound sign (#) is a directive for
the preprocessor. It is not
// my first program in C++ executable code but indications for
the compiler.
#include <iostream.h>
int main () tells the compiler's preprocessor to
include the iostream standard header
{ file.
cout << "Hello World!"; Corresponds to the beginning of the
main function declaration. The main
return 0; function is the point where all C++
programs begin their execution.
}
to terminate a program cout is the standard output stream in C++
37
Standard data types
38
Data Types
Type Sign Byte Bits Minimum Maximum Precision
short int Signed 2 16 -32768 32767 -
Unsigned 0 65535
int Signed 2 16 -32768 32767 -
16 bits Unsigned 0 65535
int Signed 4 32 -2147483648 2147483647 -
32 bits Unsigned 0 4294967295
long int Signed 4, 32 -2147483648 2147483647 -
unsigned 6, 48 0
8 64 4294967295
float 4 32 App. 10-38 App 1038 7 digits
double 8 64 App. 10-308 App 10308 15 digits
Long 10 80 App. 10-4932 App 104932 19 digits
double
39
Note:
• Use single quotes for character constants.
• Use double quotes for string constants
• The only bool types constants are true,
printed as 1, and false, printed as 0
40
Program Layout
• Variables are declared before they are used
– Typically variables are declared at the beginning of
the program
– Statements (not always lines) end with a semi-colon
• Include Directives
#include <iostream>
– Tells compiler where to find information about items
used in the program
– iostream is a library containing definitions of cin and
cout
41
Program Layout
using namespace std;
• Tells the compiler to use names in iostream in
a “standard” way
• To begin the main function of the program
int main()
{
• To end the main function
return 0;
}
– Main function ends with a return statement
42
Running a C++ Program
• C++ source code is written with a text
editor
• The compiler on your system converts
source code to object code.
• The linker combines all the object code
into an executable program.
43
Concepts
Compiler: is a program that translates a high-level
language program, such as a C++ program, into a
machine-language program that the computer can
directly understand and execute.
Linking: The object code for your C++ program must
be combined with the object code for routines (such as
input and output routines) that your program uses. This
process of combining object code is called linking and
is done by a program called a linker. For simple
programs, linking may be done for you automatically.
44
Run a Program
• Obtain code
• Compile the code
• Fix any errors the compiler indicates and
re-compile the code
• Run the program
• Now you know how to run a program on
your system
45
1.4
Testing and Debugging
• Bug
– A mistake in a program
• Debugging
– Eliminating mistakes in programs
– Term used when a moth caused a failed relay
on the Harvard Mark 1 computer. Grace Hopper
and other programmers taped the moth in logbook
stating:
“First actual case of a bug being found.”
46
Errors
• Syntax errors
– Violation of the grammar rules of the language
– Discovered by the compiler
• Error messages may not always show correct location of
errors
• Run-time errors
– Error conditions detected by the computer at run-time
• Logic errors (warning)
– Errors in the program’s algorithm
– Most difficult to diagnose
– Computer does not recognize an error
47
Building a C++ program
48
END
49