Session 1
•
Algorithm is a procedure for solving a
problem in terms of the actions to be executed, and the order in
which these actions are to be executed
•
In the programming domain, algorithm
define as method that consist of structured steps in problem solving using
computer.
Simple Algorithm Example
How to fishing Algorithm
1. Prepare
your bait and rod
2. Place
your bait into the hook
3. Throw
your hook into the water
4. Wait
until the fish took your bait
5. You
catch the fish
6. You
already done the fishing
How to develop an algorithm?
We can use:
1. Writing
: Structure English and Pseudo-code.
2. Drawing
: Flow Chart
Pseudo-code
•
An artificial and informal language that
helps you develop algorithms
•
Pseudo-code is similar to everyday
English, convenient, and user friendly
•
Keywords are
used to describe control structure. Example: if, else, print, set, add, while,
etc.
Basic Computer Operation:
1. Input
2. Output
3. Compute
4. Storing
value to an identifier (Store)
5. Compare
(Selection)
6. Repetition
(Loop)
Structure theorem which makes the computer programming
possible using only three control structure, which are:
1. Sequence
- Selection
- Repetition
1. Sequence
•
Sequence is series of consecutive
commands/statements
•
Commonly programming language has sequence
of statements flowing from top of the program to its end
2. Selection
•
Selection control structure is structure
that allow us to choose from several options of statement/command
•
The first statement will be executed if
the condition is satisfied, if not then the else statement
will be executed (if the other exist)
3. Repetition
•
A number of statements/commands can be
repeated several times using Repetition structure control
•
Statements/commands will be repeated while
the looping condition is satisfied
(may
use DOWHILE – ENDDO)
C Structure
•
C language is a structural programming
language
•
It consists of functions
•
There is no separation between function
and procedure (if you are from Pascal language background)
•
Each C program has one main function
called main
•
Program will be started from the first
line of the main function
•
C language is case sensitive
Every statement should be ended with a semi-colon (;)
Variable
•
Identifier for storing data/information
•
Each variable has its name, address
(L-value), type, size and data (R-value)
•
Data or variable value can be modified at
run time
•
Declaration format:
<data
type> <variable name>;
<data
type> <variable name> = <initial value>;
•
Example:
int a, b, c, total;
float salary, bonus;
int num_students = 20;
Session 2
•
Standard library function,
are predefined functions that C compiler provides. Using them by point out the
header files of where to find those functions (include directive)
•
Programmer-defined function,
or user defined function are
functions that are created by the programmer/developer to be used inside a
program
Output Operation
•
To show data on the display
screen/monitor. Some of standard library function in C :
1. printf();
2. putchar();
3. putch();
4. puts();
5. etc.
Input Operation:
scanf() function
•
Header
file: stdio.h
•
Format:
int scanf( const char
*format [,argument]... );
•
All
the argument type are pointers (address of a variable)
•
To
get the address of a variable use “&” sign
•
Example
:
int aValue;
scanf(”%d”,&aValue);
•
Input
format: ”%type”
Session 3
•
Operator is
a symbol to process values in result for a new value
•
Operand
is part which specifies what data is to be manipulated or operated on
•
Example
:
C = A + B
(= and + sign are operators,
A, B and C are operands)
•
Based on its operand number, operator can
be divided into three:
1. Unary
operator (needs
one operand)
2.
Binary operator (needs
two operands)
3. Ternary
operator (needs
three operands)
•
Based on its operation type, operator
can be grouped as:
1. Assignment
Operator
2. Logical
Operator
3. Arithmetic
Operator
4. Relational
Operator
5. Bitwise
Operator
6. Pointer
Operator
Session 6
Program
Control: Selection
Selection Definition
- In
an algorithm implementation, an instruction or block of instructions may
be executed (or not) with certain predetermined condition
- Syntax:
1. if
2. if-else
3. switch-case
IF Selection :
Syntax :
if (boolean
expression) statement;
or
if (boolean
expression) {
statement1;
statement2; Block of statements
……
}
If boolean expression
resulting in True, then a statement or some statements will be executed.
IF-Else Selection :
Syntax :
if (boolean
expression) statement1;
else statement2;
or
if (boolean expression){
statement1;
statement2; Block statement1
……
}
else {
statement3;
statement4; Block statement2
…
}
Nested IF Selection :
•
Nested
selection occurs when the word IF appears more than once within IF statement.
Syntax :
if (boolean
expression) statement1;
if (boolean expression) statement2;
if (boolean expression) statement3;
or
if (boolean
expression) statement1;
else
if (boolean expression) statement2;
else
if (boolean expression)
statement3;
Swich Case selection :
•
Switch-Case Operation
This
statement is used in exchange of IF-ELSE, when if-else nested number of level
is enormous and difficult to read
•
Syntax:
switch (expression) {
case
constant1 : statements1; break;
.
.
case
constant2 : statements2; break;
default
: statements;
}
•
Switch statement evaluate an
expression by looking up for each case constant value. If an expression value
matches with a case constant value then related statement/s is executed. If
nothing match then default statement is executed.
•
Note:
Expression
and constant type should be integer (including char)
?: Operator
•
The
operator ? : is similar to the IF statement, but it returns a value
•
Syntax:
condition ? then-expression : else-expression
•
Using
this operator, you can rewrite
if(a > b)
max_value = a;
else
max_value = b;
as
max_value = (a > b) ? a : b;
Session 9
Repetition Definition :
- One
or more instruction repeated for certain amount of time
- Number
of repetition can be predefined (hard-coded in program) or defined later
at run time
- Repetition/looping
operation:
– for
– while
– do-while
Repetition: FOR
•
Syntax:
for(exp1; exp2; exp3) statement;
or:
for(exp1; exp2; exp3){
statement1;
statement2;
…….
}
exp1
: initialization
exp2
: conditional
exp3
: increment or decrement
exp1, exp2 and exp3 are optional
•
exp1
and exp3 can consist of several expression separated with comma
•
Example:
void reverse(char
ss[])
{
int c,i,j;
for(i=0, j=strlen(ss)-1; i<j; i++, j--){
c=ss[i];
ss[i]=ss[j];
ss[j]=c;
}
}
•
Infinite Loop
Loop with no stop condition can use
“for-loop” by removing all parameters (exp1, exp2, exp3). To end the loop use break.
•
Nested Loop
Loop in a loop. The repetition operation
will start from the inner side loop.
Repetition: WHILE
•
Syntax :
while (exp) statements;
or:
while(exp){
statement1;
statement2;
…..
}
while (exp) statements;
•
exp is
Boolean expression. It will result in true (not zero) or false (equal to zero).
•
Statement will be executed while the exp
is not equal to zero.
•
exp
evaluation is done before the statements executed.
Repetition: DO-WHILE
•
Syntax :
do{
< statements >;
} while(exp);
•
Keep executing while exp is true
•
exp evaluation done after executing
the statement(s)
Repetition Operation
•
In while operation, statement block
of statements may never be executed at all if exp value is false
•
In do-while on the other hand
statement block of statements will be executed min once
•
To end the repetition, can be done
through several ways:
– Sentinel
– Question,
should the repetition continue?
Break vs Continue
•
break:
– ending
loop (for, while and do-while)
– end
the switch operation
•
continue:
skip
all the rest of statements (subsequent to the skip statement) inside a
repetition, and continue normally to the next loop
Session 12
Pointer Definition
•
Pointer is a variable that store the
address of another variable
•
Syntax :
<type>
*ptr_name;
•
Two
operators mostly used in pointer : * (content of) and & (address of)
•
Example:
Initialize an integer
pointer into a data variable:
int i, *ptr;
ptr = &i;
To assign a new value
to the variable pointed by the pointer:
*ptr = 5; /* means i=5 */
Pointer to Pointer
•
Pointer to pointer is a variable that
saves another address of a pointer
•
Syntax:
<type>
**ptr_ptr ;
•
Example:
int i, *ptr, **ptr_ptr;
ptr = &i;
ptr_ptr = &ptr;
To assign new value to i:
*ptr = 5; // means i=5 ;
**ptr_ptr = 9; // means i=9; or *ptr=9;
Array Definition
•
Data saved in a certain structure to
be accessed as a group or individually. Some variables saved using the same
name distinguish by their index.
•
Array characteristics:
–
Homogenous
All
elements have similar data type
–
Random Access
Each
element can be reached individually, does not have to be sequential
Array Definition
•
Syntax:
type array_value [value_dim];
•
Example
:
int A[10];
•
The definition consists of 4
components:
–
Type specified
–
Identifier (name of the array)
–
Operator index ([ ])
–
Dimensional value inside operator [ ]
Accessing Arrays
•
Two analogous ways of accessing an
element i=2;
*(A+2)
or A[2]
•
A
is equivalent with &A[0] or a constant pointer to the first element
of particular array
•
To show A[2] on the monitor screen:
printf(“%d”,A[2]) or
printf(“%d\n”,*(A+2));
Pointer Constant & Pointer Variable
•
Pointer variable is a pointer that
can be assigned with new value at run-time.
•
Pointer constant is a pointer that
can not be assigned with new value at run-time
•
Array is Pointer Constant to its
first element of the array. Array can be filled with pointer variable.
•
Example:
–
int
x=10, y=20;
–
int
*ptr; //ptr is pointer variable
–
ptr
= &x;
–
ptr
= &y;
Accessing Arrays
•
Accessing array using a pointer
int arr[10];
int *ptr_arr;
ptr_arr = arr; //or
ptr_arr = &arr[0];
•
To access certain element can be done
using:
ptr_arr[i];
arr[i];
*(ptr_arr + i);
*(arr + i);
ptr_arr = ptr_arr + i;
*ptr_arr;
String
•
String is an array of character
that ended with null character ( ‘\0’ or in ASCII = 0)
•
String constant or string literal is
some characters written between double quote
–
Example: ”Welcome to Binus”
–
String constant type is pointer
constant, thus can be assigned to an array of character :
–
Example :
char
name[40] = ”Amir”; //ok
name
= ”Amir”; // error name is a constant
pointer
Name[40]=
“Amir”; //error
Session 20
Function and
Recursion
•
Program is divided into modules
•
Module in C programming language is
implemented using function
•
Function is formed through grouping
some statements to do a particular job
•
Module is needed when a certain block
of statement frequently used by other distinct code in a program
•
Also called Sub-Program
•
Advantages of using Modules:
1. Top-down
design with sub goal, huge program divided into smaller modules
2. Can
be done by more than one developer/ programmer
3. Easier
to debug, as logical flow is easy to follow and easier to pin point errors
4. Modification
can be done without affecting overall codes
Easier to document
•
Best practice in module programming:
1. High
Fan-In, frequently used
2. Low
Fan-Out, more specific functionality/ small number of job
3. Self-Contained,
self resource sufficient
Function
Definition
Function Construction
return-value-type function-name( parameter-list )
{
statements;
statements;
}
return-value-type: data type of the value returned
•
If not filled, then default data type
will be used (default integer)
•
If return-value-type is void then the
function will not return value
Parameter-list: list of value sent from
the function initiator (user)
Recursive Definition
•
Recursive is a function call inside a
certain function calling itself
•
Recursive Function, suitable for
recursive problem
•
Example :
Factorial (n) or n! defined as
follows :
n! = 1, for n = 0;
n! = n * (n-1)!, for n > 0
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! =
1* 0!
0! =
1
Trace back : 4! = 1*2*3*4 = 24
Recursive Function
Recursive Function has two components:
–
Base case:
return
value(constant) without calling next recursive call.
–
Reduction step:
sequence
of input value converging to the base case.
Example: (Factorial function)
– Base
case : n = 0
– Reduction
step: f(n) = n * f(n-1)
Session 21
Structures
and Unions & Memory Allocation
Structure Definition
•
Structure is
a data type to store group of data with various of data type
•
Structure component called member/field/element.
•
Heterogeneous (various element data type)
Structure in other programming language also called record
Memory Allocation
•
Memory allocation:
acquiring
some memory space (RAM) managed by the OS to be used by a program.
•
Memory de-allocation:
releasing
memory space (RAM) back to the OS.
Memory Allocation as a data store:
1. static
Ä can
be assigned with name à variable
Ä allocated
at compile time
Ä stored at local
stack memory
Ä
remain unchanged during the program run
Ä de-allocated
when the program end
2. dynamic
Ä can
be assigned with name
Ä allocated
at run-time
Ä
stored at heap memory
Ä can be
de-allocated at any time
Array Memory Allocation
# include
<stdio.h>
# include
<stdlib.h>
int main() {
int *arr, n, i;
do {
fflush(stdin);
printf(“total
element ? ");
scanf("%d", &n);
if (n == 0) break;
arr = (int *) malloc (n * sizeof(int));
printf(“Input %d numbers: ", n);
for (i = 0; i < n; i++) scanf(“%d",
&arr[i]);
printf(“reversed: ");
for (i = n - 1; i >= 0; i--)
printf("%d ", arr[i]);
printf("\n\n");
free(arr);
}while (1);
return 1;
}
Pointer to Functions
•
Pointer
to function is the address of a function in the memory
•
Syntax:
return_type
(* pointer_name)(parameter);
•
Example:
int
(*compare)(int a, int b);
note: compare is pointer to function
name, pointing to a function that return integer value which has 2 integer
parameters
•
Note
the difference:
int
compare (int a, int b);
Means: compare is a function name
with integer return value that has 2 integer parameters
Session 26
File
Processing
Files and Streams
Streams Definition
•
To keep key in data from keyboard need to be
saved at secondary storage device as a data file.
•
Stream
is a sequence of character. All input and output data is a stream. C sees file as a stream.
•
When
a C program run, there are three (3) standard streams activated:
1. Standard
Input Stream
Controlling input stream from keyboard
2. Standard
Output Stream
Controlling output stream to the monitor
3. Standard
Error Stream
Controlling the error messaging
•
Each stream associated with a file.
File
Definition
•
File is a collection of record
•
Record is a collection of field
•
Field is a block of byte
•
Byte is collection of bit
File Definition
•
TEXT FILE saved in a text format or ASCII File
–
Storage
size depends on its data: 10000 needs 5 byte
–
Can
be open using standard text editor application
–
or
c:>TYPE file_name
•
BINARY
FILE storing numerical
data in affixed format in line with micro-processor format definition (example:
format sign-magnitude 2’s complement).
Buffer Area
•
Buffer area is part of the memory used as
a temporary space before data moved to a file.
•
Syntax:
FILE *fp;
Where
fp
is a file pointer pointing to the start of the buffer area.
•
Also known as stream pointer.
Open File
•
Opening
a File using fopen():
FILE *fopen (const char
*filename, const char *mode );
•
fopen()
defined at <stdio.h>
•
fopen()
return a pointer to the start of
a buffer area. Null will be returned if file unable to open.
•
Possible mode value :
Mode Description
“r” opening
a file to be read.
“w” creating
a file to be written.
“a” opening
a File for data append.
“r+” opening
a File for read/write.
“w+” creating
file for read/write.
“a+” opening
a File for read/append
“rb” opening a File (binary) to be read.
“wb” creating
a file (binary) for write operation.
Close File
•
Closing a File using fclose():
int fclose (FILE *stream);
•
fclose()
defined at <stdio.h>
•
fclose()
will return 0 if successful, and
EOF if error
•
EOF
(End Of File) equals to -1
•
fclose()
will release the buffer area and
immediately send the remaining data to file.
•
Closing a File using fcloseall():
int fcloseall (void);
ü Close all active stream except: stdin, stdout, stdprn,
stderr, and stdaux.
ü Will return the number of stream closed if successful,
and return EOF instead.
ü Header file <stdio.h>
Input & Output File
•
fgetc
(INPUT)
–
Read
one character from a file
–
fgetc(stdin) equivalent with getchar()
–
Syntax : int fgetc( FILE *stream );
–
Return
the character when successful, and EOF while error
•
fputc
(OUTPUT)
–
Writing
one character to a file
–
fputc('a', stdout) similar with putchar( 'a' )
–
Syntax: int fputc( int c, FILE *stream );
–
Return
a character when successful, and EOF if error
•
fgets
(INPUT)
–
Syntax:
char *fgets( char *string, int n, FILE *stream );
–
Read
one line from a file that ended with new line, or at maximum of n-1 number of
character.
–
Return
a string if successful and NULL while error
•
fputs
(OUTPUT)
–
Writing
a line to a file
–
Syntax:
int fputs( const char *string, FILE *stream );
–
Return
non-negative value while successful and EOF if error.
•
fscanf (INPUT)
–
Syntax:
int fscanf( FILE *stream,
const char *format [, argument ]... );
–
Read
data from file inline with the scanf formatting.
–
Return
the number of field read while successful, and EOF if error
•
fprintf
(OUTPUT)
–
Syntax:
int fprintf( FILE *stream,
const char *format [, argument ]...);
–
Writing
data to a file using the printf format.
–
Return
number of byte written if successful and negative value if error.
–
fwrite
–
syntax:
size_t fwrite( const void *buffer, size_t size, size_t count,
FILE *stream );
–
Writing
a block of data in the buffer area to the file
–
Return
number of byte data written, and error otherwise.
–
fread
–
Syntax:
size_t fread( void *buffer, size_t size, size_t count,
FILE *stream );
–
Read
a block size of data from a file
–
feof
–
Syntax
: int feof( FILE *stream );
–
Finding
out if the pointer has reached end-of-file
–
Return
0 if not end-of-file
•
Example
using fwrite():
fwrite( &mhs, sizeof( mhs ), 1, fp );
–
&mhs
= data origin location
–
sizeof(mhs)
= return the size of mhs
–
1
=> one time write sizeof(mhs)
–
fp
= file pointer
Session 29
Sorting & Searching
Sorting
•
Sorting
needs to speed up searching operation in a list.
•
Sorting type:
–
Ascending
–
Descending
Sorting algorithm:
1. Internal sorting
All data to be sorted are loaded to RAM
2. External sorting
Sorting process using secondary storage
•
Simple:
–
Bubble sort
–
Selection
sort
–
Insertion
sort
•
Intermediate:
–
Quick Sort
–
Merge
Sort
Bubble Sort
•
Compare two neighboring values.
•
Compare and swap (if necessary)
•
Also known as exchange sort
Selection Sort
Algorithm:
for(i=0; i<N-1; i++){ /* N=number of data */
Set
idx_smallest equal to i
for(j=i+1; j<N; j++){
If
array[ j ] < array [ idx_smallest ] then idx_smallest = j
}
Swap array[ i ] with array[ idx_smallest ]
}
Insertion Sort
Algorithm:
for(i=1; i<n; i++) {
x = A[i], insert x to its suitable place
between A[0] and A[i-1].
}
Quick Sort
Algorithm:
void QuickSort(int left, int right)
{
if(left < right){
//arrange elements R[left],...,R[right] that
//producing new sequence:
R[left],...,R[J-1] <
R[J] and R[J+1],...,R[right] > R[J].
QuickSort(left, J-1);
QuickSort(J+1, right);
}
}
Merge Sort
•
Merge Sort is
a sorting algorithm based on the divide-and-conquer algorithm
•
Divide-and-conquer is
a general algorithm design paradigm
–
Divide:
divide the input data in two disjoint subsets
–
Recur:
solve the sub problems associated with subsets
–
Conquer:
combine the solutions for each subset into a solution
Searching
•
We’ll often work with large amounts of
data stored in arrays
•
It may be necessary to determine whether an
array contains a value that matches a certain key value
•
The process of finding a particular
element of an array is called searching
•
Searching
is
an action to retrieve information based on particular key from some saved
information
•
Key is
used to do record searching which is desired from a set of data list
•
Key must
be unique, means there must not be any same key in the data
•
Example:
Student data consists of name, nim, gender, address, place and date of birth
nim
is used as key from the data, as it is unique.
•
Several types of searching algorithm:
–
Linear Search
–
Binary Search
–
Interpolation Search
Linear Search
•
Linear search compares each element of the
array with the search key.
•
Since the array is not in any particular
order, it’s just as likely that the value will be found in the first element as
in the last
•
On average, therefore, the program will
have to compare the search key with half the elements of the array
•
Algorithm:
1. n : total record of array x.
2. For each x[i], 0 £ i £ n-1, check
whether x[i] = key.
3. If x[i] = key, then the searched data is found in index=i.
Finished.
4. If x[i] ¹ key,
then continue searching until the last data which is i = n-1.
5. If i= n-1 and x[i] ¹ key, it
means the data is not exist in the list, and set index = -1. Finished.
Binary Search
•
The linear searching method works
well for small or unsorted arrays. However, for large arrays linear searching
is inefficient
•
If the array sorted, the high-speed
binary search technique can be used
•
Algorithm:
1. n : total record of
array x.
2. left=0, right= n-1.
3. mid =(int) (left + right)/2.
4. If x[mid]=key then index
= mid. Finished.
5. If x[mid]<key then left
= mid+1.
6. If x[mid]>key then right = mid-1.
7. If left £
right and x[mid] ¹ key, then repeat point 3.
8. If x[mid] ¹ key
then index = -1. Finished.
Interpolation Search
•
Interpolation search technique is
performed on the sorted data
•
This searching process is almost
similar with binary search technique
•
Searching technique is done with the
approximate location of the data
•
Example:
– If
we want to find a name in the phone book, for example the one beginning with
the letter T, then we would not look for from the beginning of the book, but we
opened it at 2/3 or ¾ of the book.
•
Algorithm:
1.
In the interpolation search, we'll
split the data according to the following formula:
2.
If data[mid] = sought data, data has been found, searching is stopped and return mid.
3.
If data[mid]!= sought data, repeat point **
4.
**Searching
is continued while sought data > data[min] and sought data < data[max].
5.
Looking for a mid value by entering
into the interpolation formula
6.
If data[mid] > sought data, high
= mid
– 1
7.
If data[mid] < sought data, low =
mid
+ 1
8.
It will be looped until the
requirements point ** are not met then return (-1), data not found
Tidak ada komentar:
Posting Komentar