Algorithm and Programming (Semester 1)



Algorithm & Programming and Introduction to C Programming
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
Pseudo code an artificial and informal language that helps you develop algorithms
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)
Flow chart                                                                           Good Algorithm
•       Having the right logical flow to solve the problem
•       Producing the correct output in a time efficient manner
•       Written using unambiguous structured language
•       Easy implementation into real programming language
•       All steps and operations are clearly defined and ended



Structure Theorem
Structure theorem which makes the computer programming possible using only three control structure, which are:
      1. Sequence: Sequence is series of consecutive commands/statements.
      2. Selection: Selection control structure is structure that allow us to choose from several options of statement/command.
      3. Repetition: A number of statements/commands can be repeated several times using Repetition structure control.
C Standard Library Functions                                                                                     Escape Sequences
Text Box:                 Example:
                -  <math.h>                        : Mathematical Functions
                -  <stdio.h>                         : Input and Output
                -  <stdlib.h>                        : Utility Functions
                -  <string.h>                        : String Functions
                -  <time.h>                          : Time and Date Functions
Data Type









Formatted Input / Output
Output Formatting
%[flags][width][.precision] type
Text Box: Text Box: type : d –or- i : signed decimal o : unsigned octal u : unsigned decimal x : unsigned hexadecimal f : floating point e : floating point (exponent) c : single character s : string % : % character p : pointer

                             

Text Box: Syntax for Output: printf, putchar, putch, puts Syntax for Input: scanf, getchar, getch, getche, gets


Operator, Operand, and Arithmetic
1.      Operator and Operand Introduction
Text Box: • 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: – Unary operator (needs one operand) – Binary operator (needs two operands) – Ternary operator (needs three operands)  
2.      Assignment Operators

3.      Arithmetic Operators
4.      Relational Operators
5.      Conditional Expressions
Text Box: Ex: if(a > b) z = a; else z = b; or exp1 ? exp2 : exp3;

6.      Logical Operators
Symbol
Functionality
&&
AND
||
OR
!
NOT

7.      Bitwise Operators
8.      Pointer Operators
9.      Precedence and Associative

Program Control: Selection
An instruction or block of instructions may be executed (or not) with certain predetermined condition
1.      If
2.      If-Else
3.      Nested If
4.      Program Examples Using If
5.      Switch-Case
6.      ?: Operator
7.      Error Type

Program Control: Repetition
1.      For
2.      While
3.      Do-While
4.      Repetition Operation
5.      Break vs Continue



Pointers and Arrays
String Manipulation
•       In Standard Library Function (header file string.h) provides functions to manipulate string:
–      strlen()
                        Return a value of string length; excluded null char
–      strcpy(s1,s2)
                        Copy s2 to s1
–      strncpy(s1,s2,n)
                        Copy first n characters of s2 to s1
–      strcat(s1,s2)
                        Adding string s2 to the end of string s1
–      strncat(s1,s2,n)
                        Adding n characters of string s2 to the end of string s1
–      strcmp(s1,s2)
                        Comparing the value of string s1 and s2, if similar returning 0
–      etc.

Function and Recursion
1.      Modular Programming
2.      Function
3.      Identifier Scoping
4.      Passing Parameter
5.      Recursion Definition
6.      Recursive Function
7.      Iterative vs. Recursive

Structures and Unions & Memory Allocation
1.      Structures
·         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
2.      Union
3.      Memory Allocation





File Processing
1.      Open File
·         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.
Sorting & Searching
•       Simple:
–                      Bubble sortText Box: void Bubble(int *DataArr, int n) { int i, j; for(i=1; i<n; i++) for(j=n-1; j>=i; j--) if(DataArr[j-1] > DataArr[j]) Swap(&DataArr[j-1],&DataArr[j]); }
–                      Selection sort
Text Box: 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
Text Box: for(i=1; i<n; i++) { x = A[i], insert x to its suitable place between A[0] and A[i-1]. }
•       Intermediate:
–                      Quick Sort
Text Box: 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
Text Box: 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
Several types of searching algorithm:
–     Linear Search
Text Box: • 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
Text Box: • 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
Text Box: Algorithm: 1. Looking for a mid value by entering into the interpolation formula 2. If data[mid] > sought data, high = mid – 1 3. If data[mid] < sought data, low = mid + 1 4. It will be looped until the requirements point ** are not met then return (-1), data not found

Comments

Post a Comment