Transcript CPS120 Introduction to Computer Science

CPS120 Introduction to
Computer Science
Final Exam Review
Common Flowchart Symbols
Common Flowchart Symbols
Terminator. Shows the starting and ending points of the program. A terminator has
flow lines in only one direction, either in (a stop node) or out (a start node).
Data Input or Output. Allows the user to input data and results to be displayed.
Processing. Indicates an operation performed by the computer, such as a variable
assignment or mathematical operation. With a heading – an internal subroutine
Decision. The diamond indicates a decision structure. A diamond always has two
flow lines out. One flow lineout is labeled the “yes” branch and the other is labeled the
“no” branch.
Predefined Process. One statement denotes a group of previously defined statements.
Such as a function or a subroutine created externally
Connector. Connectors avoid crossing flow lines, making the flowchart easier to read.
Connectors indicate where flow lines are connected. Connectors come in pairs, one with
a flow line in and the other with a flow line out.
Off-page connector. Even fairly small programs can have flowcharts that extend several
pages. The off-page connector indicates the continuation of the flowchart on another
page. Just like connectors, off-page connectors come in pairs.
Flow line. Flow lines connect the flowchart symbols and show the sequence of operations
during the program execution.
Syntax & Logic Errors
• A syntax error is simply the violation of the rules
of a language; misuse of structure and form in
programming or a violation of the compiler’s
rules. These errors are detected by the compiler
– Also know as 'fatal compilation errors'
• A logic error is a mistake that complies with the
rules of the compiler that causes the program to
generate incorrect output
Compiling and Debugging
• Executable code will not be created until
you correct all of the syntax errors in your
source code
Introduction to C++
Variable Names
• Choose your own variable names but you
must be careful to use valid ones:
– do not use keywords that are defined in the
programming language (Reserved Words)
– do not include spaces or other disallowed
characters
– do not use more than 255 characters
– do begin the identifier with a letter
Declaring & Initializing Variables
• In C++ all variables must be declared before they
can be used.
– Declare a variable by indicating its type and name
• int myVariable;
• C++ does not automatically initialize all variables
to the value 0
• If you do not initialize a variable, the variable will
have an indeterminate value.
• Initialize your variables at the same time that you
declare them.
– int myVariable = 0;
Constants
• Sometimes you need to use the same value
many times throughout a program. In this
case, it is proper to use a constant rather
than a variable
• Constants allow you to give a name to a
value used several times in a program
• The value never changes
The Assignment Operator
• The assignment operator is the equal symbol (=)
• The assignment operator changes the value of the
variable to its left after evaluating the expression
on its right
• For example:
– sum = 3 + 1000;
• The variable sum ends up with the value 1003
–
–
–
–
salary = 40000;
poundsPressure = 15 + 12;
sum = original + 300;
salary = salary + raise;
Common Arithmetic Operators
+
*
/
%
for addition
for subtraction
for multiplication
for division
for modulus (like finding the remainder
of a division problem)
Increments and Decrement
• The incrementing (++) and decrementing (--)
operators are useful at times if used carefully
• counter++;
• is equivalent to counter = counter + 1;
1;
and
counter +=
and
counter -= 1;
• counter--;
• is equivalent to counter = counter - 1;
• Use the incrementing and decrementing operators
with variables in statements such as these, that is
with no other operators or code except the variable
name that is being incremented or decremented.
Using Relational Operators
• Relational operators provide the tools with
which programs make decisions
==
equal to
NOTE: this is two equals symbols next to each
other, not to be confused with the assignment operator, =
>
greater than
<
less than
>=
greater than or equal to
<=
less than or equal to
!=
not equal to
Order of Logical Operations
•
Logical operators may be mixed within
evaluation statements but the following
order of preference must be respected:
1. NOT operator (!)
2. AND operator (&&)
3. OR operator (||)
Complete order of operations
• The complete order of operations including all of
the arithmetic, relational, and logical operators
including all of the basic arithmetic, relational, &
logical operators is:
*, /, %
+, <, >, <=, >=, ==, !=
!
&&
||
String Literals
• A string literal is a sequence of characters that is
used in a C++ program between double quotes
such as in the statement
cout << "Hello world!";
where "Hello world!" is the string literal
• Similar to a constant
• Ends with an invisible null terminator (ASCII 0)
– Represented as \0
Character Arrays
• Used to store strings that change as the
program runs
– Unlike string literal
• An array is a group of variables of the same
data type that appear together in memory
– In this case each variable holds a character and
the last variable in the string holds the null
terminator (/0)
Using Strings In Programs
• In order to use string variables within any
C++program, you must use the compiler
directive:
#include <string.h>
using namespace std;
Input Operations
• The operator >> is known as the input
operator. It is also known as the extraction
operator
• You use the input operator in statements
like,
cin >> numItems;
which would allow the user to input a
value to be stored in the variable
numItems.
Decision Making in C++
1.
2.
3.
4.
if statement
switch statement
? conditional operator statement
goto statement
IF-THEN
Entry
Test
condition p
Exit
false
true
True
statement a
IF…ELSE
Entry
Test
condition p
false
“false”
statement a
true
Exit
“true”
statement a
General Form
if (test expression)
{
True-block statements;
}
else
{
False-block statements;
}
next statement;
Switch Structure
• The switch structure is a multiple-selection
structure that allows even more complicated
decision statements than a two-way if/else
structure allows.
• Only variables with the INT or CHAR data types
may be used in the control expressions (i.e.
parentheses) of switch statements.
– Single quotes must be used around CHAR variables
– Single quotes are NOT used around the integer values
Iteration
• A program loop is a
form of iteration. A
computer can be
instructed to repeat
instructions under
certain conditions.
No
Syntax of a for Loop
for (initializing expression; control expression;
step expression)
{
// one or more statements
}
• The initializing expression sets the counter
variable for the loop to its initial value.
• The control expression ends the loop at the
specified moment.
• The step expression changes the counter variable
• Semi-colons, not commas, divide the expressions
WHILE Loop
Entry
Exit
No
Test
condition p
Yes
Loop
statement a
While Loop Syntax
while (control expression)
{
// one or more statements
}
• The control expression must evaluate to
TRUE in order for the while loop to iterate
even once
DO WHILE Loop
Entry
Loop
statement a
Test
condition p
Exit
No
Yes
Do While Syntax
do
{
// body statements would be placed here
}while (control expression);
• Don't forget to include the required semicolon
after the control expression
In Summary
• Loops
– for
– while
– do … while
-- fixed number of loops
-- may never be run
-- always run once
• continue causes while, do… while, and for
loops to start over
• break causes while, do … while, for and
switch statements to end
An Example of A Function
#include <iostream.h>
void printMyMessage(int numOfTimes);
// PROTOTYPE and NAME
int main( )
{
int userInput = 0;
cout << "Enter a number between 1 and 10 (0 to Exit): " ;
cin >> userInput;
if (userInput != 0)
{
printMyMessage (userInput);
// CALL STATEMENT WITH ACTUAL PARAMETER
}
else
cout << "Thanks, Bye!";
return 0;
} // end of main
void printMyMessage(int numOfTimes)
{
int i=0;
// FUNCTION HEADER W/ RETURN TYPE & ACTUAL PARAMETER
for (i=0; i<= numOfTimes; i++)
{cout << "Let's Go State!!" << endl;}
} //end of printMyMessage
// BODY
// OF THE
// FUNCTION
/ LOCAL VARIABLE WITHIN THE FUNCTION
Scope of Variables
• The scope of a variable is the area in which
it can be legally referenced
– Variables are either global or local in nature
• Global variables can be used in any function
throughout the program.
• Local variables are ones that are declared inside of a
function, including main. They cannot be used or
referred to in other functions
– It is not wise to use global variables any more
than you have to
Required Compiler Directives
• Any program that uses file pointers must
include the fstream.h header file with the
compiler directive,
#include <fstream.h>
at the top of the program
Opening Output Files
• Opening a sequential-access file
ofstream outfile;
– ofstream is a C++ keyword indicating the type of
pointer that you created
– outfile is simply the programmer's chosen name
for the file pointer (and can be any valid name)
• Open the file "mydata.txt" that is stored on
your PC's hard drive
outfile.open("mydata.txt", ios::out);
Opening Input Files
• Declare a file pointer as an ifstream object
with:
ifstream infile;
– ifstream is a keyword and infile is the name for
the file pointer.
– infile is simply the programmer's chosen
name for the file pointer (and can be any
valid name)
• Open the actual file for reading with:
infile.open("mydata.txt", ios::in);
Writing Output
• To write data to a sequential-access data file
you would use a statement like:
outfile << "John Doe" << endl;
to print that name to the next line in the data
file pointed to by the file pointer, outfile.
Appending Data
• Adding data to the end of a sequentialaccess data file is called appending
• Open the file using the ios::app stream
operation mode as in:
outfile.open("myfile.txt", ios::app);
• where the app is short for append.
Detecting the End of a File.
• Use the eof function to determine whether the end
of a sequential-access file has been reached.
• This function returns a 1 (true) if an attempt has
been made to read past the end of the file.
do
{
infile >> x;
if ( !infile.eof( ) )
{
cout << x << endl;
}
} while ( !infile.eof( ) );
Arrays: A Definition
• A list of variables accessed using a single
identifier
– May be of any data type
• Can be single or multi-dimensioned
• Vector classifications are object-oriented
representations of arrays
Declaring an Array
• To declare an array before it is used in the body of
your program, you must use a statement like:
int scores[10];
• In this case, scores can store up to 10 different
integer values.
– The positions of the array are identified by their index
positions which run from 0 to 9 (not 1 to 10.)
• Each one of the 10 variables in scores is called an
element
Initializing an Array
• If you wish to initialize each element of an array
to a specific value, you can use the statement,
int scores[] = {65, 76, 45, 83, 99};
• You don't even have to specify a size of the array
in this case since the initialization statement
would cause the compiler to declare an array of
size 5 since there are five values in the set of curly
braces
Declaring a Multi-dimensional
Array
• To declare an array of integers called
studentGrades to be a 2-dimensional array with 3
rows and 4 columns, you would use the statement:
int studentGrades[3] [4];
where the first integer value is used to specify the
number of rows in the array and the second value
specifies the number of columns
• Think of remote control
Initializing a Multi-dimensional
Array
• You can initialize the 2-dimensional array when
you declare it by using commas and braces
appropriately
int studentGrades[3] [4] = {
{ 1, 2, 3, 4},
{ 5, 6, 7, 8},
{ 9, 10, 11, 12}
};
Key Computing Concepts
What Is a Network
• A network is a group of connected
computers that allow people to share
information and equipment
Small Networks
• Peer-to-Peer:
– Used for a small number of computes (e.g. 10)
– Files stored on own computers; access given to
them to others on the network
The Networking Revolution
• Computer networks have permanently
altered the world of computing with the
client/server model
Client/Server interaction
Types of Networks
Various network topologies
• A bus technology called Ethernet has become the industry
standard for local-area networks
Ethernet
• A bus technology called Ethernet has become the
industry standard for local-area networks
– Most popular and least expensive solution
– Each computer waits for a pause before sending
information
– Collisions between information often occur
• Computers wait a moment, then resend
Packet Switching
• To improve the efficiency of transferring information over
a shared communication line, messages are divided into
fixed-sized, numbered packets
• Network devices called routers are used to direct packets
between networks
Messages
sent by
packet
switching
TCP/IP
• TCP stands for Transmission Control Protocol
– TCP software breaks messages into packets, hands
them off to the IP software for delivery, and then orders
and reassembles the packets at their destination
• IP stands for Internet Protocol
– IP software deals with the routing of packets through
the maze of interconnected networks to their final
destination
Firewalls
• A firewall is a machine and its software that serve
as a special gateway to a network, protecting it
from inappropriate access
– Filters the network traffic that comes in, checking the
validity of the messages as much as possible and
perhaps denying some messages altogether
– Enforces an organization’s access control policy
Network Addresses
• An IP address can be split into
– network address, which specifies a specific network
– host number, which specifies a particular machine in
that network
An IP address is
stored in four
bytes
Domain Name System
• A hostname consists of the computer name
followed by the domain name
• orchard.wccnet.org is the domain name
– A domain name is separated into two or more sections
that specify the organization, and possibly a subset of
an organization, of which the computer is a part
– Two organizations can have a computer named the
same thing because the domain name makes it clear
which one is being referred to
Other Programming Concepts
Approaches to Sorting
• There are two basic approaches to sorting data
– The incremental approach
– The divide and conquer approach.
• Using the incremental approach, one sorts the
whole list at once
• The divide and conquer approach splits the list up
into parts and sorts each part separately.
Selection Sort
Example of a selection sort (sorted elements are shaded)
The Insertion Sort
• The insertion sort is incremental in nature.
• This is similar to the way a person usually
organizes a hand of playing cards.
• The insertion sort is relatively quick for
small lists that are close to being sorted
Insertion Sorting
Mary
Mary
Gerri
Terry
Gerri
Kari
Gerri
Kari
Harry
Kari
Harry
Barry
Harry
Barry
Mary
Barry
Terry
Terry
Bubble Sort
• Starting with the last list element, we
compare successive pairs of elements,
swapping whenever the bottom element of
the pair is smaller than the one above it
Bubble Sort
Example of a
bubble sort
Understanding the Quick Sort
• The quicksort is a divide and conquer
algorithm and is more efficient than
incremental sorts. It can be difficult to code
though since it uses recursion or stacks.
• The original list is partitioned into two lists.
– One of the lists contains elements that are
greater than the first original element.
– The second list contains elements that are less
than or equal to the first original element.
Quicksort
Sequential Searching
• Although there are more efficient ways to search
for data, sequential searching is a good choice of
methods when amount of data to be searched is
small.
• You simply check each element of an array
position by position until you find the one that you
are looking for.
• In any search, the item upon which the search is
based is called the key and the field being
searched is called the key field.
Binary Search
• A binary search looks for an item in a list using a divideand-conquer strategy
– Binary search algorithm assumes that the items in the list being
searched are sorted
– The algorithm begins at the middle of the list in a binary search
– If the item for which we are searching is less than the item in
the middle, we know that the item won’t be in the second half
of the list
– Once again we examine the “middle” element (which is really
the item 25% of the way into the list)
– The process continues with each comparison cutting in half the
portion of the list where the item might be
Binary Search
•
•
•
•
•
•
•
•
•
•
•
[0] Ant
[1] Cat
[2] Chicken
[3] Cow
[4] Deer
[5] Dog
[6] Fish
[7] Goat
[8] Horse
[9] Monkey
[10] Snake
Trace of the binary search
Object-Oriented Programming
Object-Oriented Paradigm
• Data should be placed inside the
objects and that these objects should
communicate with each other in the
form of messages
Thinking Object-Oriented
• Think in an object-oriented way
– E.g. an answering machine encapsulates the
functions of an answering machine with the
data (messages).
• The buttons are the equivalent of sending messages
to the machine
Encapsulation
• Encapsulation is a language feature that
enforces information hiding
– Both data and methods are contained within an
object
Inheritance
• Inheritance fosters reuse by allowing an
application to take an already-tested class
and derive a class from it that inherits the
properties the application needs
Polymorphism
• Polymorphism: the ability of a
language to have duplicate method
names in an inheritance hierarchy and to
apply the method that is appropriate for
the object to which the method is applied
Designing A Class
• A class is a language construct that is a
pattern for an object and provides a
mechanism for encapsulating the properties
and actions of the object class
– We instantiate the class
– Private and public are called access modifiers
OOP Advantages: Reusability
• Reusability is a major benefit of objectoriented programming
Public vs. Private
• Private: Cannot be accessed outside the object
• Public: Can have access to all the variables and
functions
public:
// constructors
circle();
// default constructor
circle(const circle &); // copy constructor
// member functions
void SetRadius(float);
double Area();
private:
// data
float radius;