CS 131- Data Structure and Algorithm (copy)

-A powerful general-purpose programming language.

-an extension to the C language that can be used to develop operating systems, browsers, games, and so on.

-can support different ways of programming like procedural, object-oriented, functional, and so on,

C++

He developed C++

Bjarne Stroustrup

Why learn C++

-it is used to develop games, desktop apps,

operating systems, browsers, and so on because

of its performance.

-it is a good foundation for learning other

programming languages like Java, Python, etc.

-it will help you to understand the internal

architecture of a computer, how computer stores and retrieves information.

-it is a "library" in C++.

-a toolbox developed by the programmers of the C++ language which contains functions that we could use in our own program.

iostream

-the entrypoint of your program. If we were to imagine that our whole program is a room, the main is basically the "door" of our program.

-So when our code is executed by the computer, it'll find the ____ and will start executing all the code inside it (the ones

inside the curly braces).

main

-This line of code is the exit status of our application.

-If we ______ as the exit status, that means that our program worked fine until the end, without errors.

return 0;

special characters characterized by a backslash (\) and a letter or symbol beside it.

Escape sequences

std::cout << "I’m\tpretty";

I’m pretty

std::cout << "I’m\npretty";

I’m

pretty

std::cout << "\\";

\

std::cout << "\"";

"

to be able to use std::setprecision, we need to include the <_________> library

#include<iomanip>

this is needed to change the default formatting of the numbers that are printed to "fixed-point notation".

std::cout << std::fixed;

this is the line that sets the number of decimal places to be printed.

std::setprecision(3)

is used to place the text in the new line, but sometimes, itcan be confusing. Another way to add a new line is by using the std::endl statement.

\n

-objects that are used to store values.

-As an object, they act as containers or buckets

where the data will be put into and stored.

Variables

Variable declaration in C++ requires three parts:

● the data type of the variable;

● the variable name of your choice; and,

● a semicolon at the end

A letter, symbol, or white space). This should be enclosed in single quotes.

example: ‘A’;

Character (char)

Whole numbers ranging between ±32767.

example:

___ mynum = 6;

___ ynum = 16;

___ xnum = 1997;

Integer (int)

-Real numbers that can handle up to 7 decimals. To indicate that it is float, you should add an f at the end of the value.

example:

float myfloat = 1.2f;

float xfloat = 3.12f;

Floating Point Values (float)

Real numbers that can handle up to 15 decimals

Double is just the same as a Float but can hold larger numbers.

example:

double mynum = 100.23;

double xnum = 22.11;:

Double Floating Point Values (double)

Truth values (true/false).

bool myboolean = true;

bool xboolean = false;

Boolean (bool)

special type of variables

whose values can't be changed.

Constant variables

1. #include<iostream>

2. using namespace std;

3. int main(void) {

4. int letter_value = 'J';

5. cout << letter_value;

6. return 0;

7. }

What will the output be?

74

-As you can see in the example, we tried to assign the character 'J' to the variable letter_value which is an int. The output became 74 and not J, why is that?

-The character J was converted to its integer

equivalent, or the American Standard Code for

Information Interchange acronymed as ASCII value, which is 74.

- All the characters have their equivalent ASCII values. The uppercase A is 65, the uppercase B is 66. The lowercase a is 97, the lowercase b is 98.

ASCII

American Standard Code for Information Interchange

1. #include<iostream>

2. using namespace std;

3. int main(void) {

4.

5. // We create an int variable to represent sides and assign 3 to it.

6. int sides = 3;

7.

8. cout <<"A triangle has " <<sides <<" sides." <<endl;

9. cout <<"Isosceles triangle has " <<sides <<" too." <<endl;

10. return 0;

11. }

What will the output be?

A triangle has 3 sides.

Isosceles triangle has 3 sides too.

in your code this will not be executed because

they serve as guide to the programmers, which makes it very useful especially when making a project with lots of lines of codes.

Comments

There are two types of comments
//I am the 1st line of a C++ code. (What type of comment is this?)

and

1. /* I am the 1st line of a C++ code.

2. I am the 2nd line of this code

3. And I am the 3rd.*/

-Single line comments are preceded by double slash.

-Multiple line comments are enclosed in /* and */.

There are restrictions and guidelines to follow in

naming variables in C++.

-Variable names will only compose of letters, numbers, and/or a single symbol, underscore (_). That being said, all names must always start with a letter or an underscore (A-Z, a-z, _). But, Ma’am Fatima recommends that you should use names that are specific to what you are representing that variable for.

-Avoid using lengthy names for a variable. As much as possible, just make sure that the first three letters of its name makes sense when you read it so that it will be easy to remember and easy to type as well.

-Avoid using very short names for a variable that it won't make sense the first time you read them.

a number is basically increasing it by 1.

Increment

varname = varname + 1;

or
varname ++;

on the other hand is decreasing it by 1.

Decrement

varname = varname - 1;

or

varname --;

-allow the user to type in or inputa specific data that is asked by the program.
-gets a value from the user and stores it to thevariable

CIN »

-gets the value of the variable and prints/outputs it to the screen.

COUT «

-is a set of well-defined instructions to solve a particular problem

Algorithm

A good-quality algorithm:

-Precisely defined input and output

-clear and unambiguous steps

-most effective in solving problems

-not written in computer codes

-usable in any programming language

-is a storage that is used to store and organize data

-It is a way of arranging data on a computer so that it can be accessed and updated efficiently

Data structure

elements are arranged in sequence one after the other, which makes it easy to implement.

Linear data structures

elements are not in any sequence. They are arranged in a hierarchical manner where one element will be connected to one or more elements.

Nonlinear data structures

Why Learn DSA?

-DSA gives you an insight into how efficient it is to use each solutions.

-It also teaches you the science of evaluating the efficiency of an algorithm.

-This enables you to choose the best of various choices.

• It is an ordered collection of values of the same type.

• Elements can be accessed via its index.

• All arrays consist of contiguous memory locations.

ARRAY

It is made up of one row or one column of array members with the same name but different index values

ONE-DIMENSIONAL

ARRAY USE

-maintaining a large chunk of data using variable names.

-to easily sort elements

-for matrix operations

-CPU scheduling

-for implementing other data structures such as: stacks, queue, heaps,etc.

• Used for visiting, accessing, and printing each element of an array exactly once

• It is necessary to create a variable that will track the position of the element that is currently being accessed

ARRAY TRAVERSAL

• Most straightforward sorting method

• Repeatedly switches nearby components if they are in the wrong order.

• The name “bubble sort” comes from each item in the list “bubbles” up to where it should go, similar to water bubbles.

BUBBLE

• Works similarly to how one sorts playing cards in one’s hands.

• The array is virtually split into a sorted and an unsorted part.

• It uses in-place comparisons.

• A sub-list is kept here, which is always sorted.

• An element to be inserted in this sorted sub-list must first find its appropriate place and then insert it.

INSERTION

• In each iteration, the smallest element from an unsorted list is chosen and placed at the top of

the unsorted list.

• Based on in-place comparison and divides the list into two parts, one sorted and one unsorted.

SELECTION

• A container for a few lines of code that accomplish a specific task

• Contains the set of programming statements enclosed by { and }

• Can be called numerous times in a program for reusability and modularity

• It has its own parentheses and an opening (and closing) bracket , where variables, declarations, and parameters can be called

FUNCTION

Built into the language to perform operations. It is stored in Standard Function Library.

Pre-defined Functions.

Defined by the user to perform specific tasks.

User-defined Functions.

IMPORTANCE OF FUNCTION

-helps avoid repetition of the same logic

-can be called any number of times

-large programs can be easily tracked

-reusability is the key accomplishment

WHAT ARE THE ASPECTS OF A FUNCTION?

FUNCTION DECLARATION

FUNCTION DEFENITION

FUNCTION CALL

• A function must be declared globally to inform the compiler of the function name, parameters, and return type.

• This tells the compiler about a function name and how to call the function.

FUNCTION DECLARATION

THIS ASPECT OF FUNCTION CONTAINS THE TASKS OF THE FUNCTION WHEN CALLED. THEY ARE ENCLOSED { AND

• Contains the actual statements which are to be executed.

• The control comes to the most crucial feature when invoked.

• The function can only return one value.

FUNCTION DEFINITION

• When called, the function performs a defined task.

• To call a function, pass the following: required parameters and the function name.

• If the function returns a value, one can store the returned value.

• The parameter list must not differ in function calling and function declaration.

FUNCTION CALL

• Values which are passed in the function call.

• Can be constant, variables, expressions

ACTUAL PARAMETERS (ARGUMENTS)

• Variables local to that function and cannot be used in other parts of the program.

• All of the method’s required values are included in the list, along with their variable names and data types.

FORMAL PARAMETERS (REPLICA OF ACTUAL PARAMETER)

• Only statements that are inside that function or block of code can use them.

• They are not known to functions outside their own.

LOCAL VARIABLES (DEFINED WITHIN A FUNCTION OR BLOCK)

• Their values are maintained throughout the life of your program.

• It may be accessed from any of the program’s functions.

GLOBAL VARIABLES (DEFINED AT START OF THE PROGRAM)

THIS TYPE OF FUNCTION REFERS TO WHERE THEY CALL THEMSELVES REPEATEDLY, WHILE INPUT VALUE CHANGES EVERY TURN.
Functions that call themselves repeatedly.

RECURSIVE FUNCTIONS

• The function calls itself as the final statement of the function.

• When it is called, it must process or carry out some action.

• It does nothing after that call.

TAIL RECURSION

• The initial statement of a recursive function is also the first time it calls itself.

• At the time of calling, is not required to process anything.

• Everything is completed when the method returns.

HEAD RECURSION

In an array, the index starts at this value

0

this is used to access the elements of an array

index

this keyword is used if the function does not require to return a value

void

In order to use the different mathematical functions for complex operations, we have to include the library where those functions are contained into the code.

#include<cmath>.

Returns the value of the left operand (base) raised to the power of the right operand (exponent).

pow()
syntax = pow(base, exponent)

Returns the square root of a number.

sqrt()

syntax = sqrt(num)

The opposite of floor. Rounds up the number to the smallest integer greater than or equal to the number

ceil()

syntax = ceil(num)

Returns the absolute, positive value of num.

fabs()

syntax = fabs(num)

Rounds down a number to the largest

integer less than or equal to the number.

floor()

syntax = floor(num)

• collection of different data types under a single name

• used to express data about anything that is more complex than what can be represented by a single integer, character, or Boolean.

STRUCTURE

• compile multiple pieces of information on a single topic in one location

• collect data of the same data kinds and parameters

• incredibly simple to maintain

• aggregating together related data in one entity through the struct keyword allows programs to construct user-defined types.

IMPROTANCE OF STRUCTURES

Structures are declared by starting with the _____ keyword then the structure name (identifier).

struct

pk.pkname = "Pikachu";
• Use the ____ operator to access the inner variables of the structure

• One accesses the pkname field of the struct Pokemon pk and by using the _____ operator, assigning Pikachu as a string value to pkname.

. [ . ]

• A keyword used to specify alternative names for primitive types.

• With the application of typedef struct, variable declaration no longer needs the keyword struct.

TYPEDEF