Note For IT

Rolling a Six-Sided Die 6000 Times (Java Coding)

noreply@blogger.com (Han) — Sat, 29 Aug 2009 10:18:00 +0000

import java.util.Random;

public class RollDie {

public static void main(String[] args) {

Random randomNumbers = new Random();

int freq1 = 0;

int freq2 = 0;

int freq3 = 0;

int freq4 = 0;

int freq5 = 0;

int freq6 = 0;

int face;

for(int roll=1; roll<=6000; roll++)

{

face = 1 + randomNumbers.nextInt(6);

switch(face)

{

case 1:

++freq1;

break;

case 2:

++freq2;

break;

case 3:

++freq3;

break;

case 4:

++freq4;

break;

case 5:

++freq5;

break;

case 6:

++freq6;

break;

}

System.out.println("Face\tFrequency" );

System.out.printf("1\t%d\n2\t%d\n3\t%d\n4\t%d\n5\t%d\n6\t%d\n",

freq1, freq2, freq3, freq4, freq5, freq6);

}

Algorithms & Data Structures - Searching

noreply@blogger.com (Han) — Sat, 16 May 2009 13:45:00 +0000

Searching
√The process used to find the location of a target among the list of object.
√We begin with list searching and a discussion of two basic search algorithm

List Searches
√The two basic searches for arrays are the sequential search and the binary search.

Sequential Search
√The sequencial search is used whenever the list is not ordered.
√It is useful for small lists or lists that are not searched often.
√In sequential search, we start searching for the target at the beginning of the list and continue until we find the target or we are sure that it is not in the list.
√The efficiency of sequential search is O(n).

Binary Search
√The binary search starts by testing the data in the element at the middle of the array to determine if the target is in the first or the second half of the list.
√If it is in the first half, we do not need to check the second half.
√If it is in the second half, we do not need to check the first half.
√To find the middle of the list, we need 3 variables: one to identify the beginning of the list, one to identify the middle of the list and one to identify the end of the list.
√The formula to calculate the mid is:
Mid = [(begin + end ) / 2 ]
√The efficiency of the binary search is O(log n).

Binary Search Tree
√The array structure provides a very efficient search algorithm, but its insertion and deletion algorithms are very inefficient.
√The binary search tree and AVL tree (chapter 3)provides a very efficient search and at the same time efficient insertion and deletion algorithm.

Basic Concepts
A binary search tree is a binary tree with the following properties:
√All items in the left subtree are less than the root.
√All items in the right subtree are greater than or equal to the root.
√Each subtree is itself a binary search tree.

Algorithms & Data Structures - Sorting

noreply@blogger.com (Han) — Sat, 16 May 2009 12:34:00 +0000

Objective:
At the end of the class you should be in a position to answer:
√Understand the basic concepts of internal and external sorts
√Discuss the relative efficiency of different sorts
√Recognize and discuss selection, insertion and exchange sorts
√Discuss the design and operation of external sorts
√Design and implement sequential searches
√Discuss the relative merits of different sequential searches
√Design and implement binary searches

Sort Concepts
√Sorts arrange data according to their value.
√Sorting algorithm are classified as either internal or external.

Insertion Sorts
In each pass of an insertion sort, one or more pieces of data are inserted into their correct location in an ordered list. In this section we study two insertion sorts: the straight insertion sort and the shell sort.

Explanation
In a straight insertion sort, the list at any moment is divided into sorted and unsorted sublists. In each pass the first element of the unsorted sublist is inserted into the sorted sublist.
If we have a list of n elements, it will take at most n-1 passes to sort the data.
The straight selection sort efficiency is O(n²)

Shell Sort
The shell sort algorithm named after its creator, Donald L.Shell.
It is an improved version of the straight insertion sort in which diminishing partitions are used to sort the data.
The Worst case running time of shell sort using shell’s increment is O(N²).

Selection Sort
In each pass of the selection sort, the smallest element is selected from the unsorted sublist and exchanged with the element at the beginning of the unsorted list.
The straight selection sort efficiency is O(n²)

Bubble Sort
Bubble sort is an exchange sort. The basic operation is the exchange of an adjacent pair of elements. So in the single bubble sort algorithm, the program will pass through the data, switching consecutive items which are out of order. After each pass through the list, the program checks to see if any switches were made. If there were, it passes through the list again, switching consecutive items which are still out of order. If no switches are made during an entire pass through the list, the data is sorted.

In the best case the efficiency of bubble sort is O(N).
In the worst case the efficiency of bubble sort is O(NM²)

Example of Bubble sort
Here is an example : we want to sort 390, 205, 182, 45, 235
Bubble sort for the first pass (exchange of an adjacent pairs)
390 205 182 45 235 (Switch 1)
205 390 182 45 235 (Switch 2)
205 182 390 45 235 (Switch 3)
205 182 45 390 235 (Switch 4)
205 182 45 235 390 ( First pass-sorted list)

the first pass moves the largest element (390) to the n^th position ,forming a sorted list of length one
the second pass only has to consider (n-1) elements and moves the second largest element to the (n-1) position.

Quick Sort
Quick sort is an exchange sort in which a pivot key is placed in its correct position in the array while rearranging other elements widely dispersed across the list.
The efficiemcy of the Quick sort is :
Worst Case = O(N²) - the pivot is the smallest element
Average Case = O(N log n)
Best case = O(N log N) - the pivot is in the middle

Radix Sort
The bin sorting approach can be generalized in a technique that is known as radix sorting.
Assume that we have n integers in the range (0,n²) to be sorted. (For a bin sort, m = n², and we would have an O(n+m) = O(n²) algorithm.) Sort them in two phases:
1. Using n bins, place a_i into bin a_i mod n,
2. Repeat the process using n bins, placing a_i into bin floor(a_i/n), being careful to append to the end of each bin.
This results in a sorted list.

Example
Consider the list of integers
36 9 0 25 1 49 64 16 81 4
Step1: Arrange the element according to the least significant decimal digits

Step2:Arrange the elements according to the most significant digits

Step3: Sorted list is :
0 1 4 9 16 25 36 49 64 81

Merge Sort
The basic merging algorithm takes two input arrays A and B, an output array C, and three counters, Aptr, Bptr, and Cptr, which are initially set to the beginning of their respective arrays. The smaller of A[Aptr] and B[Bptr] is copied to the next entry in C, and the appropriate counters are advanced. When either input list is exhausted, the remainder of the order list is copied to C.

Example
If the array A (Aptr) contains 1, 13 and B (Bptr) contains 2, 15, 27, 38, then the algorithm proceeds as follows.

First, a comparison is done between 1 and 2.
1 is added to C, and then 13 and 2 are compared.

2 is added in C, and 13 and 15 are compared.

The remainder of the array B is then copied to C.

Algorithms & Data Structures - Queue

noreply@blogger.com (Han) — Fri, 27 Feb 2009 23:47:00 +0000

Definition

Queue is an ordered collection of items.
These items may be deleted at one end (called the HEAD of the queue) and inserted at other end (called the TAIL of the queue).
Example, to withdraw money at ATM
Also known as FIFO – first in first out

Array and linked list implementation

Operations of Queue

Dequeue
Enqueue
QueueEmpty
QueueFull

Enqueue

Enqueue is the shortened version of "entering a queue".
It refers to a situation where a new item is inserted to the queue.
After a new insertion is made, the new item becomes the tail of the queue.

Dequeue

Dequeue is a shortened version of "deleting from a queue".
This is a situation where the data element at the head of the queue will be deleted.

Array implementation

Using array to implement the queue
Will create a problem when the queue is full – memory space are fixed.

Problem solution

Create a circular queue. (using linked list)
Circular queue wraps around to the beginning whenever the Head or the Tail reaches the end of the queue.

Linked list implementation
* Enqueue

Enqueue- Implementation
void Enqueue(QUEUENODEPTR *tailPtr, QUEUENODEPTR *headPtr, char Value)
{
QUEUENODEPTR newPtr;
newPtr = malloc(sizeof(LISTNODE)); //Create a new node
if (newPtr != NULL)
{
newPtr->data = Value;
newPtr->nextPtr = NULL;
(*tailPtr)->nextPtr = newPtr;
(*tailPtr) = (*tailPtr)->nextPtr;
if (*headPtr == NULL)
*headPtr = *tailPtr;
}

Dequeue - Implementation
char Dequeue(QUEUENODEPTR *headPtr)
{
char value;
QUEUENODEPTR tempPtr;
if (*headPtr != NULL)
{
tempPtr = *headPtr;
(*headPtr) = (*headPtr)->nextPtr;
value = tempPtr->data;
free(tempPtr);
return value;
{
else
printf(“Queue is empty”);
}

Application of queue

Scheduling system
- Advantages
Support print spooling
Information packet

Linked List Based Implementation of Stack and Queue

noreply@blogger.com (Han) — Sun, 21 Dec 2008 07:46:00 +0000

Why different implementations

The way the data structure is implemented is a measure of its efficiency (time and space)
It is important to see different alternatives
So far we have discussed array based implementation (vector). What if we use second class arrays?

Objectives:
Discuss linked list based implementation of stack and queue.
Compare and contrast two implementations

Linked List based Stack

Stack is LIFO data structure
Linked list is a collection of nodes where each node has a data element and a pointer to the next element in the list.

Linked List based Stack- basic concepts

Stack we push into and pop from the top of the stack.
Therefore a special pointer “toOftheStack” which is pointing to the top of the stack is created.
Intially toOftheStack is null.
Try following operations

push (a), push(b), push(c)
pop()

Linked List based Stack- C++ Details
A Node: (figure 16.19)

struct ListNode
{
Object element;
ListNode *next;
ListNode ( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { }

};

Linked List based Stack- C++ Details
Template
template <class Object> class Stack {
public:
Stack( );
Stack( const Stack & rhs );
~Stack( ); bool isEmpty( ) const;
const Object & top( ) const;
void makeEmpty( );
void pop( );
void push( const Object & x );
Object topAndPop( );
const Stack & operator=( const Stack & rhs );

private:
struct ListNode { Object element; ListNode *next; ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n ) { } };

ListNode *topOfStack; };

Linked List based Stack- C++ Details
Implementation
Stacklist.cpp
push, pop, top, makeEmpty and = operator

Linked List based Queue

Queue if FIFO data structure
Implementation is very similar to stack. Here, both from and back of the data structure need pointers.

Linked List based Queue- basic concepts

Queue, enqueue into the front of the stack. Dequeue from the back of the stack
Therefore two special pointers “front,” and “back,” are created.
Initially both both front and back are null.
Try following operations

enqueue (a), enqueue(b), enqueue(c)
dequeue()

Linked List based Queue - C++ Details
A Node:

struct ListNode {
Object element;
ListNode *next;
ListNode( const Object & theElement, ListNode * n = NULL ) : element( theElement ), next( n )
{ }
};

Linked List based Queue - C++ Details
Template
Queuelist.h
Notice that there are two pointers, front and back

Linked List based Queue - C++ Details
Implementation
Queuelist.cpp
Enqueue, dequeue, copy constructure and = operator

Array base vs. Linked list based Implementation

For large size stacks and queue specially the size is not known linked list is better.
For memory scare devices such as small handheld devices, linked list may perform better.

Algorithms & Data Structures - Linked List

noreply@blogger.com (Han) — Sun, 21 Dec 2008 06:50:00 +0000

Objectives
At the end of the class you should be able to answer:

Explain the design, use, and operation of a linear list

Implement a linear list using a linked list structure

Understand the operation of the linear list ADT

Write application programs using the linear list ADT

Design and implement different link-list structures

Basic Operations
The four basic list operations are :

Insertion
Deletion
Retrieval
Traversal

Insertion

Insertion is used to add a new element to the list.
List insertion can be ordered or random.
Ordered list are maintained in sequence according to the data or, when available, a key that identifies the data.
In random lists there is no sequential relationship between two elements.Random lists are sometimes called chronological lists.

Figure 5-1 Shows the insertion of data into a list

Deletion

Deletion is used to remove an element from the list.
Deletion from a list requires that the list be searched to locate the data being deleted
Once located, the data are removed from the list.

Figure 5-2 Shows the Deletion operation

Retrieval

Retrieval is used to get the information related to an element without changing the structure of the list.
List retrieval requires that data be located in a list and presented to the calling module without changing the contents of the list.

Figure 5-3 Shows retrieving data from a list

Traversal

List traversal processes each element in a list in sequence
It requires a looping algorithm rather than a search.

Implementation

Several data structures can be used to implement a list; we use a linked list.
Linked list is a good structure for a list because data are easily inserted and deleted at the beginning, in the middle, or at the end of the list.

Data Structure
To implement a list, we need two different structures, a head node and data node.

Figure 5-5 Shows a head node and data node

Algorithm
Create List:
Create list allocate the head structure and initializes the metadata for the list.
Figure 5-6 shows the header before and after it is initialized by create list.

Figure 5-6 Create list

Algorithm for creating a list

Insert Node
Insert node adds data to a list. Given the predecessor, there are three steps to the insertion:
1. Allocate memory for the new node and move data to the node.
2. Point the new node to its successor.
3. Point the new node’s predecessor to the new node.

Figure 5-7 Add node to empty list

Insert at Beginning

To insert a node at the beginning of the list, we simply point the new node to the first node of the list and then ser the head pointer to point to the new first node.
Figure 5-8 shows inserting a node at the beginning

Figure 5-8 Shows Add node at Beginning

Insert in Middle

To insert a node between two nodes, we point the new node to its successor and then point its predecessor to the new node.
Figure 5-9 shows inserting a node in the middle.

Figure 5-9 Add node in Middle

Insert at End

To add at the end of the list, we only need to point the predessor to the new node.
The Figure5-10 insert the node at the end

Figure 5-10 Add node at End

Algorithm for Insertion is shown in figure 5-2

Delete Node

The delete node algorithm logically removes a node from the list by changing various link pointers and then physically delete the node from dynamic memory.
Figure 5-11 shows Deleting the first node

Delete First Node

Algorithm for Deleting a node

Retrieve Node
Figure 5-5 Shows retrieve list node algorithm

Advance Linked List

Circular Linked List
Circular linked list is a type of linked list where the last node will point back to the first node

Graphical view of a circular linked list

Algorithms & Data Structures - Heap

noreply@blogger.com (Han) — Mon, 01 Dec 2008 08:53:00 +0000

A priority queue is a special type of queue where items with special characteristic are removed from the list first.

Heap is a priority queue data structure.

heap is a structure that fulfils two properties:

1.Shape (no hole)
A heap must be a complete tree.

2.Order of its element
The value stored in each node of the heap must be greater than, less than, or equal to the value of its children, depending on what type of heap it is.

Nodes in a heap are filled from left to right, and we cannot proceed to the next lower level of the tree until all nodes in that particular level are filled.

There are two types of heaps:

Ascending heap

This is a heap in which the values of the parent's nodes are smaller than or equal to the value of the children's nodes.

Descending heap

This is a heap in which the value of the parent's nodes are greater than or equal to the value of the children's nodes

Example:
Given these data: 17, 8, 12, 4, 26, 5, 14.
Build a descending and ascending Heap

BINARY HEAP

The binary heap is the classic method used to implement priority queues.

A binary heap is a binary tree that, except for the bottommost level, is completely filled from left to right.

HEAP SORT

A heapSort is a method of sorting an array of items of no particular order into an array of certain order.

Applicable to its name, this method uses a heap to facilitate sort operations.

Operations with HEAPSORT

Insertion
Deletion

delete Min
delete Max

Insertion

REHEAP UP CONCEPT

Delete Min

Coding : check previous courseware

Delete Max
Involved descending heap

Exercise 1:
Given the following numbers, build an ascending and descending heap.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Perform deletemin for the ascending heap and deletemax for the descending heap

Exercise 2:
Use heapsort to sort the numbers into ascending list.

8, 54, 43, 3, 77, 89, 21, 23, 5, 40

Algorithms & Data Structures - Hashing

noreply@blogger.com (Han) — Tue, 25 Nov 2008 09:29:00 +0000

Objective

At the end of the class learner will be able to answer the following:

Design and implement hash-list searches
Discuss the merits of different collision resolution algorithms

Hashed List Searches

The goal of a hashed search is to find the target data in only one test. After discussing some basic hashed list concepts, we discuss eight hashing methods.

Definition:
Hashing is a key-to-address mapping process.

Terms must be familiarized.
Synonyms: The set of keys that hash to the same location
Collision: A collision occurs when a hashing algorithm produces an address for an insertion key and that address is already occupied.
Home address: The address produced by the hashing algorithm is known as the home address.
Prime area: The memory that contains all of the home addresses is known as the prime area.
Probe: Each calculation of an address and test for success is known as a probe.

Hash Concept

Figure 13-7 shows collision Resolution concept

Hashing Methods
There are eight hashing methods they are:

Direct method
Substraction method
Modulo-division
Midsquare
Digit extraction
Rotation
Folding
Pseudorandom generation

Figure 13-8 shows Basic Hashing Techniques

Direct Method
In direct hashing the key is the address without any algorithmic manipulation.
Direct hashing is limited, but it can be very powerful because it guarantees that there are no synonyms and therefore no collision.

Example:

Modulo-division Method

This is also known as division remainder method.
This algorithm works with any list size, but a list size that is a prime number produces fewer collisions than other list sizes.
The formula to calculate the address is:
Address = key MODULO listsize + 1
Where listsize is the number of elements in the arrary.

Example:
Given data :
Keys are : 137456 214562 140145
137456 % 19 +1 = 11
214562 % 19 + 1 = 15
140145 % 19 + 1 = 2

Digit-extraction Method

Using digit extraction selected digits are extracted from the key and used as the address.

Example:

Using six-digit employee number to hash to a three digit address (000-999), we could select the first, third, and fourth digits( from the left) and use them as the address.

The keys are:
379452 -> 394
121267 -> 112
378845 -> 388

Folding Method
Two folding methods are used they are:

Fold shift
Fold boundary

Fold Shift
In fold shift the key value is divided into parts whose size matches the size of the required address. Then the left and right parts are shifted and added with the middle part.

Fold boundary
In fold boundary the left and right numbers are folded on a fixed boundary between them and the center number. The two outside values are thus reversed.

Example:

Midsquare Method

In midsquare hashing the key is squared and the address is selected from the middle of the square number.
Limitation is the size of the key.

Example:
9452² = 89340304: address is 3403

Rotation Method

Rotation method is generally not used by itself but rather is incorporated in combination with other hashing methods.
It is most useful when keys are assigned serially.

Example:

Pseudorandom Hasing
A common random-number generator is shown below.
y= ax + c
To use the pseudorandom-number generator as a hashing method, we set x to the key, multiply it by the coefficient a, and then add the constant c. The result is then divided by the list size, with the remainder being the hashed address.

Example:
Y= ((17 * 121267) + 7) modulo 307
Y= (2061539 + 7) modulo 307
Y= 2061546
Y=41

Hashing Algorithm

Collision Resolution
There are several methods for handling collisions, each of them independent of the hashing algorithm.

Collision resolution methods

In this section I will discuss the Linear probe and Quadratic probe

Linear Probe
In a linear probe when data cannot be stored in the home address we resolve the collision by adding 1 to the current address.

Example for Linear Probe collision Resolution

Quadratic Collision Resolution
In the quadratic probe, the increment is the collision probe number squared. Thus for the first probe we add 1², for the second collision probe we add 2² etc.

Algorithms & Data Structures - Algorithm analysis

noreply@blogger.com (Han) — Wed, 19 Nov 2008 08:30:00 +0000

OBJECTIVES

Understands what is algorithms analysis

Identify the reasons for conducting algorithm analysis

Obtain the basic mathematics background

Able to estimate the running time

Understand the efficiency of algorithm

Able to select the best algorithm for a program

What is algorithm analysis?

The process of estimating the running time of an algorithm.
Used to find the best algorithm to solve the problem.
The role of algorithm analysis is to estimate the algorithm resource consumption.
Algorithm analysis estimates the exact time and memory space required by an algorithm to solve a certain problem.

Algorithm Analysis --> Algorithm Efficiency

less code
economic
less workload
easy to maintain
Faster to execute and get the result (speed)

How to conduct?

Algorithm Analysis

Empirical Analysis

based on experimental Analysis

Theoretical Analysis

based on mathematical Analysis

Theoretical Analysis

Use mathematical calculation

Big–O notation
Omega (Ω) notation

Big-O notation

Expressed as O(n) - On the Order of n

Instruction speed in loop

Program Structure	Big-O	Iterations	Estimate Time
Logarithmic	O(log n)	14	Microseconds
Linear	O(n)	10000	0.1 second
Linear Logarithmic	O(n(log n))	140000	2 seconds
Quadratic	O(n²)	10000²	15 – 20 min

ALGORITHM EFFICIENCY

Comparing two different algorithms that solve the same problem
Algorithmics : “the systematic study of the fundamental techniques used to design and analyze efficient algorithms”
Linear loops
Logarithmic loops
Linear logarithmic
Dependent Quadratic
Quadratic
Best Case
Worst Case
Average case

CALCULATION Big O

State the equation
Remove the coefficients
Keep the largest factor
State in Big O notation

Exercises
Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 15; i++)
p = p + i;
q = 0;
for (j = 0; j < 60; j++)
q = q + j;

Calculate the running time for this segment program
int i, j, p, q;
p = 5;
for (i = 0; i < 30; i++)
for (j = 0; j < 60; j++)
p = p + i + j;
for (i = 0; i < 60; i++)
q = q * i + p;

Order the following function by growth rate:
n log2(n), n + n2, 24, n, √n, log2 n, 2n
Indicate which function grow at the same rate.

Calculate the running time for this segment program
Fun(int x)
{
if (x < 1)
return 1;
else
return (Fun(x - 2));

Calculate the running time

log(n) * n + 2n + log (n)

3n4 + 8n3/5 + 4

6 log(n) + 9n

3 n5/2 + n log(n)

6 log(n) + 7 log(n)

Algorithms & Data Structures - Data Structures And Operations

noreply@blogger.com (Han) — Tue, 18 Nov 2008 15:31:00 +0000

Objectives
At the end of the class learner will be able to answer the :

Insert, delete, and process nodes in an AVL tree

Understand the operation of the AVL tree ADT

Write application programs using an AVL tree

AVL Tree

Introduction
In 1962, two Russian mathematicians, G.M Adelson-velskii and E.M Landis, created the balanced binary tree structure that is named after them-the AVL tree.

Definition
An AVL tree is a height-balanced binary search tree.

AVL Balance Factor:
The formula to calculate the height-balance is :
│ H_L – H_R │ <=1 Where H_L is the height of the left subtree and H_R is the height of the right subtree

The balance factor for any node in an AVL tree must be +1, or -1,we will use the descriptive identifiers

LH for left hight(+1) to indicate that the left subtree is higher than the right subtree.
EH for even high(0) to indicate that the subtrees are the same height, and
RH for right high(-1) to indicate that the left subtree is shorter than the right subtree.

Example of an AVL tree

Balancing Trees
Whenever we insert or delete a node the tree is unbalance. To make it balance we have to perform the rotations either to the left or to the right.

There are four cases required to rebalance the tree they are:

Left of Left
Right of Right
Right of left
Left of right

Left of Left - Single Rotation right:

Right of Right - Single Rotation Left:

Right of Left - Double Rotation Right:

Left of Right - Double Rotation Right:

AVL tree Implementation

AVL Tree Insert:

AVL Tree Left Balance:

Rotate AVL Tree Right and Left:

AVL Tree delete:

Algorithms & Data Structures - AVL TREE

noreply@blogger.com (Han) — Thu, 13 Nov 2008 05:18:00 +0000

A balance binary search tree.
The best search time, that is O(log N) search times

An AVL tree is defined to be a well-balanced binary search tree in which each of its nodes has the AVL property.
The AVL property is that the heights of the left and right sub-trees of a node are either equal or if they differ only by 1

Keeping the Tree Balance

the height of the right subtree and height of the left subtree for any node cannot differ by more than one.
This process is usually done through rotation.

A single counter clockwise rotate will balance it.
s_ right_rotate() - because it involves the right subtree.

A single counter clockwise rotate will balance it.
s_ left_rotate() - because it involves the left subtree.

A double clockwise rotate will balance it.

1st - single clockwise rotation with the parent of the inserted node (this produces the tree in diagram 1)
2nd - single counter clockwise rotation on the root

d_ right_rotate() - because it involves the right subtree.

A double clockwise rotate will balance it.

1st - single counter clockwise rotation with the parent of the inserted node (this produces the tree in diagram 2)
2nd - single clockwise rotation with the root.

d_ left_rotate() - because it involves the left subtree.

Example:
Given these data: build an AVL tree.
12 , 10 , 3 , 23 , 11, 14 , 2 , 4 , 1
Click the picture below to see the answer! ^_^

Algorithms & Data Structures - Sorting 1 and Analysis

noreply@blogger.com (Han) — Sun, 02 Nov 2008 13:14:00 +0000

Sort problem is obvious to all
Several distinct algorithms to solve it
Algorithms use different data structures
Algorithm performance varies widely
See Chapters 1, 2, and 7

For now, skip ShellSort and QuickSort

Bubble Sort
Insertion Sort
Merge Sort
And analysis as we go…

BubbleSort
procedure BubbleSort( var A : InputArray; N : int);
var
j, P : integer;
begin
for P := N to 2 by -1 do begin
for j := 1 to P - 1 do begin
if A[ j ] > A[ j + 1 ] then
Swap( A[ j ], A[ j + 1 ] );
end; {for}
end; {for}
end;

Template BubbleSort class
template<class T> class CBubbleSort {
public:
void Sort(T *A, int N)
{
for(int P = N-1; P >= 1; P--)
{
for(int j = 0; j<＝P-1; j++) { if(A[j + 1] < t =" A[j">Utilizing it…

// Data …
vector<double> data;

// fill in the data…

// Instantiate the sort object…
CBubbleSort<double> sort;

sort.Sort(&data[0], data.size());

Running time for BubbleSort
How many times does c,d get executed?
for P := N to 2 by -1 do begin
for j := 1 to P - 1 do begin
if A[ j ] > A[ j + 1 ] then
Swap( A[ j ], A[ j + 1 ] );
end; {for}
end; {for}

Running time for BubbleSort
How many times does c,d get executed?

So, we could say:

Big-Oh notation
Definition: T(N)=O( f(N) ) if there are positive constants c and n0 such that T(N) <= cf(N) when N >= n0
Another notation:

Intuitively what does this mean?

Asymptotic Upper Bound

Example of Asymptotic Upper Bound

Is BubbleSort O(N2)?

Can we find a c and n0?:

Some rules to simplify things…

Loops:

Running time is body time times # iterations

Nested loops:

Analysis from the inside out…

Statements:

Assume time of 1 each

Unless the statement is an algorithm

So, we could say:

Usage

Exercise in Big O-notation

What’s the minimum time?

Omega notation

Asymptotic Lower Bound

What these tell us

O(f(N)) - Upper bound on running timg

Ω(g(N)) - Lower bound on running time

What about the “constants”?

Algorithm 1: O(N), actual time is:

T(N)=1,000,000N

Algorithm 2: O(N2), actual time is:

T(N)=10N2
When is algorithm 2 faster?

Why do we care?

After all, computers just keep getting faster, don’t they?

Is today’s slow algorithm acceptable tomorrow?

Algorithm 1: O(N2)
Algorithm 2: O(N)

If your computer is suddenly 10 times faster, can you handle 10 times as much data in the same time?

Faster Computer or Algorithm?
√ What happens when we buy a computer 10 times faster?

Constant running time

Theta Notation

Big O, Omega, Theta

In general:
O is used to denote the upper bound of the complexity
Ω is used to denote the lower bound of the complexity
Ø is used to denote the tight bound of the complexity

Example, the general sorting problem has the time complexity Ω(nlogn). Any sorting based on compare-interchange takes c.nlogn time for some constant c.

Sorting problem has a time complexity O(nlogn)
(since there is an algorithm which sorts in O(nlogn) time)

Aside: Can we make this faster in some cases?
procedure BubbleSort( var A : InputArray; N : int);
var
j, P : integer;
begin
for P := N to 2 by -1 do begin
for j := 1 to P - 1 do begin
if A[ j ] > A[ j + 1 ] then
Swap( A[ j ], A[ j + 1 ] );
end; {for}
end; {for}
end;

Insertion Sort
procedure InsertionSort( var A : InputArray; N : integer);
var j, P : integer; Tmp : InputType;
begin
for P := 2 to N do begin
j := P;
Tmp := A[ P ];

while j > 1 and Tmp < A[ j - 1 ] do begin
A[ j ] := A[ j - 1 ];
j := j - 1;
end; {while}
A[ j ] := Tmp;
end; {for}
end;

Worst case analysis

N outer loops
Each item moved maximum distance

For item i, that would be i-1, right?

Best case analysis

N outer loops
Each is not moved at all

For item i, 0 moves, which is constant time.

Worst-Case and Average-Case Analysis

Worst-case analysis

Big O, the upper bound, of the running time of any input of size N.

Average-case analysis

Some algorithms are fast in practice.
The analysis is usually much harder.
Need to assume that all input are equally likely.
Sometimes, it is not obvious what is the average.

InsertionSort Average Case

On average, how much would you have to move a item to sort the list?

For item i, the minimum is 0 and the maximum is i-1. So, the average is i/2

Insertion Sort Average Case More formal solution

For sorting, we assume randomly ordered data.
Inversions:

An inversion in an array of numbers is any ordered pair (i, j) having the property that
i < j and A[i] > A[j]

How many inversions in this list:

12, 17, 5, 7, 21, 1, 8
How many are possible altogether?

Inversions
√ The maximum inversions for a list of size N is N(N-1)/2
√ Theorem: The average number of inversions in an array of N distinct numbers is N(N-1)/4

Average case for exchanging adjacent elements
√ When we exchange adjacent elements we remove exactly one inversion

12, 17, 5, 7, 21, 1, 8

√ We have to remove on average N(N-1)/4 inversions=Ω(N2)

Mergesort
procedure MergeSort( var A : InputArray; N : int);
Begin
MSort(A, 1, N)
end;

Procedure MSort(var A : InputArray; F, L : int);
var q: int;
Begin
if F < L then begin
q := (F + L) / 2
MSort(A, F, Q);
MSort(A, Q+1, L);

Merge(A, F, Q, L);
end;
End;

How long does merge take?

One of the earliest sorting sorting algorithms, invented by John von Neumann in 1945.
Mergesort is Divide-and-conquer Algorithm

Given an instance of the problem to be solved, split this into several, smaller, sub-instances (of the same problem) independently solve each of the sub-instances and then combine the sub-instance solutions so as to yield a solution for the original instance.
The problem is divided into smaller problems and solved recursively.
Quicksort and heapsort are also such algorithms

Running Time

T(1)=O(1)

T(N)=T(N/2)+T(N/2)+O(N)

Mergesort

O(n log n) worst-case running time
Same ops done regardless of input order
Mergesort is Divide-and-conquer Algorithm
Copying to and from temporary array

Extra memory requirement
Extra work

Into the wild: AdSense for feeds

noreply@blogger.com (Han) — Sun, 02 Nov 2008 10:54:00 +0000

We've been hinting at this for awhile, but it's finally time to spill the beans: Starting next week, we'll be rolling out AdSense for feeds to a small group of publishers, in anticipation of a full launch to all FeedBurner and AdSense publishers "coming soon". If you start seeing "Ads by Google" on an ad in a feed somewhere, that'd be us.

So what will this mean for you? Well, publishers already in the FeedBurner Ad Network will continue to see premium CPM ads directly sold onto their content, but with the added bonus of contextually targeted ads that will fill up the remainder of their inventory. That means you get the best of both worlds: a dedicated Google sales force that knows how and why to sell onto your content, with the added revenue that full back-fill coverage provides. And with AdSense, you'll know that your back-filled ads are using the strongest contextual ad engine, ensuring the most relevant and profitable ads are delivered to your subscribers. And yes, ads are also sold via Google's AdWords program.

For publishers who are not yet placing ads in their feeds, any publisher who meets the requirements to join the AdSense program will also be able to use AdSense for feeds. You will be able to manage your feed ad units directly from AdSense Setup tab, and track performance right on the AdSense Report tab. You can slice, dice, mix, or mash your tracking across feed units and content units, or keep them totally separate. You're in control. You can still control the frequency and rules around when ads appear in your feeds, without having to mess with templates on your content management system.

You might be wondering what you'll need to do to use AdSense for feeds. You'll learn more about the details when we fully launch, but here are the basics: you will need to sign up for AdSense if you haven't already, and you will want to set up your AdSense channels for "placement targeting" in order to make sure that advertisers can target your syndicated content specifically. As a publisher, you will remain be in control of the campaigns that are targeted at your feed by harnessing the power of Ad Review Center.

And, this is just the beginning of the chocolaty goodness that will come from ongoing integration effort with Google - there are many more "things" and "stuff" yet to come, as we mentioned a few weeks back.

We'll give you the full details on AdSense for feeds, including supported formats, how to sign up, etc., etc. when we're ready for the full launch to all publishers. In the meantime, FeedBurner feeds will continue to be fed as usual, and we'll be reaching out to select publishers individually to try out AdSense for feeds.

http://blogs.feedburner.com/feedburner/archives/2008/05/into_the_wild_adsense_for_feed_1.php

Multimedia Storage Devices

noreply@blogger.com (Han) — Wed, 15 Oct 2008 17:02:00 +0000

Multimedia storage and retrieval
Magnetic media technology

hard disk

Redundant Array of Inexpensive Disks (RAID)

Optical media technology

large capacity but slower access near-line mass-storage (jukeboxes)

CD-ROM

CD-WORM

CD-WR (erasable CD)

CD-ROM
CD-ROM - Compact Disc Read Only memory.
CD-ROM has several advantages and few disadvantages.

Advantages:
a) CD-ROM can hold about 650 megabytes of data, the equivalent of thousands of floppy disc.
b) CD-ROM are not damaged by magnetic fields or the x-rays.
c) The data on a CD-ROM can be accessed much faster than on a tape.

Disadvantage :
CD-ROM are 10 to 20 times slower than hard discs.

CD-ROM Capacity
The capacity of a CD-ROM depends on the drive.
Almost all CD-ROM drives will handle up to 620 megabytes without any problems.
Many newer drives can read discs with over 700 megabytes.
The fundamental unit of data on a CD-ROM is the sector.
Every CD-ROM is composed of a given amount of a sector.

Example of Storage in Multimedia

CD-RW Rewritable Compact Discs

Rewritable-- Data can be Overwritten Directly and Repeatedly
650MB Storage Capacity/74 Minutes Digital Audio Recording Time
Playable on All CD-ROM Drives With MultiRead Functionality

CD-R Recordable Compact Discs;

Offer high-density storage and superior audio recording.
650MB/ 74 Min. Capacity

RAID Technology
RAID = Redundant Array of Inexpensive Disks.

RAID is a new technology that provides a potential alternative to mass storage combined with high throughput and reliability.

It is a set of disk drives viewed by the user as one or more logical drives.

Data is distributed across the set of drives in a pre-defined manner.

There are 8 discrete levels of RAID functionality
1) Level 0 : Disk Striping
2) Level 1 : Disk Mirroring
3) Level 2 : Bit Interleaving and Header Error Correction (HEC) Parity
4) Level 3 : Bit Interleaving and XOR Parity
5) Level 4 : Block Interleaving with XOR Parity
6) Level 5 : Block Interleaving with Parity Distribution
7) Level 6 : Fault tolerant system
8) Level 7 : Heterogeneous system

1) RAID Level 0 - Disk Striping

Disk Striping for RAID Level 0
RAID Level 0 is based on distribution of data across multiple drives connected to a single disk controller

Characteristics/Advantages
1) RAID 0 implements a striped disk array, the data is broken down into blocks and each block is written to a
separate disk drive.
2) I/O performance is greatly improved by spreading the I/O load across many channels and drives
3) Best performance is achieved when data is striped across
multiple controllers with only one drive per controller

2) RAID Level 1 - Disk Mirroring

Disk Layout in RAID Level 1
RAID Level 1 focuses on fault tolerance in addition to striping. Disk Layout in RAID Level 1

3) RAID Level 2 - Bit Interleaving and HEC Parity

RAID 2 disk subsystem contain multiple drives connected to a disk controller, with either single or multiple channels.

4) RAID Level 3 - Bit Interleaving with XOR Parity

RAID 3 introduces parity to the model by interleaving the data at a bit level across several drives similar to data striping.

5) RAID Level 4 - Block Interleaving with XOR Parity

Very similar to RAID 3 except that striping is done at block level across several drives.

6) RAID Level 5 - Block Interleaving with Parity Distribution

Parity is distributed across various drives.
Removing a potential bottleneck.

7) RAID level 6 - Fault-Tolerant System

Improvement over RAID 5 model through the addition error recovery information.

8) RAID Level 7 - Heterogeneous System

Allows each individual drive to access data as fast as possible by incorporating a few crucial features.

Multimedia Enabling Technologies

noreply@blogger.com (Han) — Sun, 30 Dec 2007 23:26:00 +0000

1. Computation technology

Higher Processing Power Per Chip

Continual progress in microelectronics, especially VLSI, has resulted in higher processing power per chip.
Single microprocessor with 107 transistors is available

Higher Capacity Memory Chips

Growth in VLSI and more recently ULSI has resulted in 512 Mbytes DRAM chips being routinely available.

2. Storage technology

Progress In Storage Capacity

Storage is the key to the performance and functionality of any computer system.
This is even more true for multimedia applications because digitized audio, image and video require large storage capacity (even after compression)
Magnetic media has been the primary storage base for at least four decades.
Rapid technological advances in optical storage media are now a serious challenge to magnetic media

3. Compression technology

Progress In Compression Technologies

Compression is necessary for two reasons:

To reduce storage volumes of sounds, images, and motion video
To reduce the bit rate to transmit them over networks

Assuming no compression is used, a 8 minutes of CD-quality stereophonic sound or a 3.5 seconds of TV broadcast quality motion video need 80 MB of disk space for storage.
Assuming no compression is used, digital motion video of PAL quality requires 160 Mbps

4. Carrier and Transmission technology
Growth in carrier/transmission technologies such as optical fiber lead to transmission of multimedia information with high speed, high capacity and high reliability.
Network Switching Services Technology
New networking switching services such as B-ISDN can easily support multimedia. Asynchronous transfer mode (ATM) is the technology used to support B-ISDN.

5. Input/Output Device Technology

Technological Developments have covered a wide range of input and output devices for all aspects of multimedia. These devices include pen input, display systems, scanners, laser printers, digital voice and video input and output systems, video animation input.
Electronic pen input is a new technology which is expected to become more popular in the future
CRT based display systems have achieved higher and higher resolution.
Flat panel display systems using LCDs have also become popular and are used for portable computers as well as personal computers.
Printing technology has also matured sufficiently. Laser printers for normal office work having resolution of 300 to 600 DPI are routinely available. Higher resolution ranging from 600 to 1200 DPI are useful for specialized multimedia applications. Dot matrix printers also able to print out photo quality images.
Digital Camera does not contain film roll; Instead, it stores the captured images in digital form. Images are stored on a magnetic or optical disk in the camera or on a memory cartridge. In some cases, the image is downloaded directly to a computer. A digital camera uses charged-coupled devices (CCD) and CMOS as photo-sensors.
Digital images created by digital cameras offer a number of advantages

Digital images can be printed immediately and any number of times for duplication
Digital images can be integrated with word processor
Digital images can be embedded in mail messages.

Video frame grabber is used to capture, manipulate, and enhance still video images. Once a digital still image is available, it can easily be enhance, restored, distorted, or analyzed.
Powerful image animation techniques are now available using computers where illusion of movement is created by sequentially playing still image frames at a rate of 15-20 frames per second.
Full-Motion video is the most complex component of multimedia systems. Its most important component is the video capture board. A video capture board for full motion video is a circuit card which contains video input, ADC/DAC, audio and video compression and decompression circuits, video frame memory etc.

6. Protocol Technology
These technologies relate to providing generic services to the applications such as address location, address resolution, connection setup, multicasting, end-to-end control. New protocol suites are being developed at the application level to support multimedia applications.

7. Application Technology
These technologies act as a interface between the protocol technology and the applications themselves. Often these technologies are specific to a class of applications and require to be developed as communication subsystem independent and protocol independent, for deployment to a variety of systems.

8. Database Technology
These technologies address the issue of storing and retrieving multimedia information of the order of several gigabits. For example large databases, integrated databases, federated databases, active and proactive databases.

9. Software Technology
These technologies become vital in the modern computing environment as the development of multimedia applications require an appropriate development environment. For example the object-oriented software development environment, distributed environment and parallel environment.

10. System Integration Technology
This is by far the most important requirement in the context of multimedia . Integration involves hardware, software, communication, sensor, coding and compression technologies to coexist in the modern multimedia system and the whole system should have a simple and easy-to-use interface.

Software Quality Assurance

noreply@blogger.com (Han) — Mon, 24 Dec 2007 00:02:00 +0000

Concepts and Definitions

Software Quality Assurance (SQA) is defined as a planned and systematic approach to the evaluation of the quality of and adherence to software product standards, processes, and procedures.

SQA includes the process of assuring that standards and procedures are established and are followed throughout the software acquisition life cycle.

Compliance with agreed-upon standards and procedures is evaluation through process monitoring, product evaluation, and audits.

Software development and control processes should include quality assurance approval points, where an SQA evaluation of the product may be done in relation to the applicable standards.

Components of SQA

Pre-project components

Software project life cycle components

Infrastructure components for error prevention and improvements

Management SQA components

SQA standards, system certification and assessment components

Organizing for SQA

Pre-project Components

Pre-project

Contract reviews
Development and quality plans

Common Contract Situations

Participation in a tender

Proposal submission according to customer's request for proposal

Receipt of an order from a company's customer

Internet request from another department in the organization

Contract Review Stages

The contract review consist of

Proposal draft review

Reviews the proposal prior to submission to the potential customer
This includes customer's requirement documents, cost and resource estimates, existing contracts or contract drafts.

Contract draft review

Reviews the contract draft prior to signing
Review on the basis of the proposal and the understanding (including changes) reached during the contract negotiation sessions.

Implementing Contract Reviews

Who perfoms the review?

The leader or another member of the proposal team
The members of the proposal team
An outside professional or company staff member who is not member of the proposal team
A team of outside experts

Development and Quality Plan

Planning is meant to prepare adequate foundations for successful and timely completion of the project.

The planning process includes:

Development Plan: Elements
1. Project products, specifying "deliverables"
2. Project interfaces
3. Project's methodology and development tools
4. Software development standards and procedures
5. Map of the development process
6. Project milestones
7. Project staff organization and coordination with external participants
8. Required development facilities
9. Development risks and risk management actions
10. Control methods
11. Project cost estimates

Quality Assurance Plan: Elements
[Sommerville2004]

A quality assurance plan sets out the desired product qualities and how these are assessed and defines the most significant quality attributes.

The quality assurance plan should define the quality assessment process.

It should set out which organizational standards should be applied and, where necessary, define new standards to be used

[Galin2004]
Elements:
1. List of quality goals
2. Review activities
3. Software tests
4. Acceptance tests for software externally developed
5. Configuration management plans: tools, procedures, and dates for version release

Project Life Cycle Components
Development
-Reviews
-Expert Opinions
-Software Testing
-Assurance of the quality of external participants’ work
Maintenance
-Software maintenance components

The Objectives of SQA activities in Software Development

Assuring an acceptable level of confidence that the software will conform to functional technical requirements.

Assuring an acceptable level of confidence that the software will conform to managerial scheduling and budgetary requirements.

Initiation and management of activities for the improvement and greater efficiency of software development and SQA activities.

Several Quality Assurance Activities
Requirement specification review
-Approval of the requirement specification to proceed with the next phase
Design inspection
-Detecting errors and derivations from standards
Design review
-Approval of the design to proceed with the next phase
Code inspection
-Detecting errors and derivations from standards
Unit test
-Approval of the unit quality to proceed with the next phase
Integration tests
-Approval of the integrated units to proceed with the system test
Documentation review
-Approval of the documentation for operation
System test
-Approval of the system for operation
Operation phase detection
-Defects will be found during operation by the customer.

Infrastructure Components
- Procedures and work instruction
- Templates and checklists
- Staff training, retraining and certification
- Preventive and corrective actions
- Configuration management
- Documentation control

Management SQA Components

Project progress control

Software quality metrics

Software quality costs

Standards, Certification, Assessment

Project process standards

Quality management standards

Organizing for SQA

Management’s role in SQA

The SQA Unit

SQA trusties

SQA committees

SQA forums

Introduction to Software Quality

noreply@blogger.com (Han) — Sun, 02 Dec 2007 22:38:00 +0000

Software - IEEE definition
Software is:
Computer programs, procedures, and possibly associated documentation and data pertaining to the operation of a computer system.

Software quality - IEEE definition
Software quality is:
(1)The degree to which a system, component, or process meets specified requirements.
(2)The degree to which a system, component, or process meets customer or user needs or expectations.

Software quality - Pressman's definition
Software quality is :
Conformance to explicitly stated functional and performance requirements, explicitly documented development standards, and implicit characteristics that are expected of all professionally developed software.

SQA - IEEE definition
Software quality assurance is:
1.A planned and systematic pattern of all actions necessary to provide adequate confidence that an item or product conforms to established technical requirements.
2.A set of activities designed to evaluate the process by which the products are developed or manufactured. Contrast with: quality control.

SQA - expanded definition
Software quality assurance is:
A systematic, planned set of actions necessary to provide adequate confidence that the software development process or the maintenance process of a software system product conforms to established functional technical requirements as well as with the managerial requirements of keeping the schedule and operating within the budgetary confines.

The objectives of SQA activities in software development
(1)Assuring an acceptable level of confidence that the software will conform to functional technical requirements.
(2)Assuring an acceptable level of confidence that the software will conform to managerial scheduling and budgetary requirements.
(3)Initiation and management of activities for the improvement and greater efficiency of software development and SQA activities.

The objectives of SQA activities in software maintenance
(1)Assuring an acceptable level of confidence that the software maintenance activities will conform to the functional technical requirements.
(2)Assuring an acceptable level of confidence that the software maintenance activities will conform to managerial scheduling and budgetary requirements.
(3)Initiate and manage activities to improve and increase the efficiency of software maintenance and SQA activities.

Introduction to Computer

noreply@blogger.com (Han) — Wed, 21 Nov 2007 10:50:00 +0000

What are computers?

Problem solving tools that:
1.Accept data
2.Process data
3.Store data
4.Present results

Why is a computer so powerful?
1.Speed
2.Accuracy (GIGO)
3.Reliability
4.Storage
5.Communications

What is Computing Literacy?

Learning how to use computer to benefit your life or work.

Required by most occupations.

Functions of a Computer
1.Arithmetic - add, subtract, multiply, divide
2.Comparisons - greater than, less than, equal
3.Storage and retrieval

What Computers Can Do?
1.Data processing
2.Control
3.Design and Development
4.Data Communication

What Computers Cannot Do?
1.Cannot identify a problem to be solved.
2.Cannot identify and collect data.
3.Cannot design software.
4.Cannot identify the output needed to solve a problem.
5.Cannot interpret and use information to solve a problem.

Elements of an Information System
1.Hardware
2.Software
3.Data
4.People
5.Procedures

Hardware

Equipment associated with computer
1.System unit
2.Communication device
3.Storage
4.Input devices
5.Output devices

Example
Keyboard, monitor, speaker

Software

Set of instructions that a computer understand (program)
Types of software

Application softwar
System software

Application software
Programs designed to perform specific tasks for users.
1.Packaged software
2.Custom software
3.Shareware (distributed free for a trial period)
4.Freeware (copyright)
5.Public domain software

System Software
Interface = Programs that control the operations of the computer and its devices.

Operating system

Instructions that coordinate activities of hardware devices
Instruction to run application software

Utility programs

Perform a specific task.
Uninstaller, anti virus.

User Interface

Controls how data and instructions are entered and how information is presented in the screen.

GUI allows interaction between users and software using visual images such as icons or button.

Software Development
1.Computer programmers
2.System analyst
3.Programming language

Users
5 categories of computer users:
1.Home Users
2.Mobile Users
3.Large Business Users
4.Small Office/Home Office Users
5.Power Users

Common Computer Hardware Components - Monitor

Output device

Also called VDU (visual display unit).

Common Computer Hardware Components - Keyboard and Mouse

Common Computer Hardware Components - System Unit

Common Computer Hardware Components - Printer

Output device

Common Computer Hardware Components - Speaker and modem

SPEAKER

MODEM

Categories of Computer

Personal Computer ( Microcomputer)

Handheld Computer

Internet Appliance

Mid Range Server

Mainframe

Supercomputers

Personal Computer (Microcomputer)
Types:
1.Desktop

2 most popular series : IBM compatible and Apple Macintosh
2.laptop/notebook

Portable, small enough to fit on your lap

Generally more expensive than a desktop computer

Handheld Computer

Small computer that fits in your hand
Also called a palmtop or pocket computer
How do you input data with a handheld computer?

Stylus
Speech recognition
Handwriting recognitionld computer?

What is a personal digital assistant (PDA)?

Provides personal organizer functions

1.Calendar
2.Appointment book
3.Address book
4.Calculator
5.Notepad

Internet Appliance

What is an Internet appliance?

Computer whose main purpose is to connect to Internet from home.

Web TV is one example.

Mid Range Server

Use in medium-sized organizations
Cheaper than mainframe
Process faster than microcomputer
When it is uneconomical to use mainframes.
Organizations that use minicomputer:

Airlines
Domestic Banks

Examples:

IBM AS/400
NEC Astra

Mainframe

Huge computer

Can process large volume of data per second

Faster than minicomputer

More expensive than minicomputer

Can do intensive computational task

Supercomputer

Most powerful computer (very fast)

Most expensive

Used for running applications requiring complex and sophisticated mathematical calculations and applications.

Process several billions of instructions per seconds (bips)

Sensitive to temperature, humidity and dust.

Systems Analysis & Design - Determining System Requirements

noreply@blogger.com (Han) — Sun, 18 Nov 2007 02:40:00 +0000

Determining System Requirements

Learning Objectives

Describe options for designing and conducting interviews and develop a plan for conducting an interview to determine system requirements.

Design, distribute, and analyze questionnaires to determine system requirements.

Explain advantages and pitfalls of observing workers and analyzing business documents to determine requirements.

Explain how computing can provide support for requirements determination.

Learn about Joint Application Design (JAD)

Use prototyping during requirements determination.

Select the appropriate methods to elicit system requirements.

Apply requirements determination to Internet applications.

Performing Requirements Determination

Gather information on what system should do from many sources.

Users
Reports
Forms
Procedures

Characteristics for gathering requirements

-Impertinence
-Question everything
-Impartiality
-Find the best organizational solution
-Relaxation of constraints
-Attention to detail
-Reframing - View the organization in new ways

Deliverables and Outcomes

Types of deliverables:

Information collected from users
Existing documents and files
Computer-based information
Understanding of organizational components

Business objective
Information needs
Rules of data processing
Key events

Traditional Methods for Determining Requirements

Interviewing and Listening

Gather facts, opinions and speculations
Observe body language and emotions
Guidelines

Plan

Checklist
Appointment

Be neutral
Listen
Seek a diverse view

Interviewing (Continued)

Interview Questions

Open-Ended

No pre-specified answers

Close-Ended

Respondent is asked to choose from a set of specified responses

Additional Guidelines

Do not phrase questions in ways that imply a wrong or right answer
Listen very carefully to what is being said
Type up notes within 48 hours
Do not set expectations about the new system

Administering Questionnaires

More cost-effective than interviews
Choosing respondents

Should be representative of all users
Types of samples

Convenient
Random sample
Purposeful sample
Stratified sample

Questionnaires

Design

Mostly closed-ended questions
Can be administered over the phone or in person

Vs. Interviews

Interviews cost more but yield more information
Questionnaires are more cost-effective
See table 7-4 for a complete comparison

Interviewing Groups

Advantages

More effective use of time
Enables people to hear opinions of others and to agree or disagree

Disadvantages

Difficulty in scheduling

Nominal Group Technique

Facilitated process to support idea generation by groups
Individuals work alone to generate ideas which are pooled under guidance of a trained facilitator

Directly Observing Users

Serves as a good method to supplement interviews
Often difficult to obtain unbiased data

People often work differently when being observed

Analyzing Procedures and Other Documents

Types of information to be discovered:

Problems with existing system
Opportunity to meet new need
Organizational direction
Names of key individuals
Values of organization
Special information processing circumstances
Reasons for current system design
Rules for processing data

Four types of useful documents

Written work procedures

Describes how a job is performed
Includes data and information used and created in the process of performing the job or task
Business form

Explicitly indicate data flow in or out of a system.

Report

Enables the analyst to work backwards from the report to the data that generated it

Description of current information system

Modern Methods for Determining Requirements
Joint Application Design (JAD)

Brings together key users, managers and systems analysts

Purpose: collect system requirements simultaneously from key people

Conducted off-site

Prototyping

Repetitive process

Rudimentary version of system is built
Replaces or augments SDLC

Goal: to develop concrete specifications for ultimate system

Joint Application Design (JAD)
Participants
-Session Leader
-Users
-Managers
-Sponsor
-Systems Analysts
-Scribe
-IS Staff
End Result
-Documentation detailing existing system
-Features of proposed system
CASE Tools During JAD
-Upper CASE tools are used
-Enables analysts to enter system models directly into CASE during the JAD session
-Screen designs and prototyping can be done during JAD and shown to users
Supporting JAD with GSS
-Group support systems (GSS) can be used to enable more participation by group members in JAD
-Members type their answers into the computer
-All members of the group see what other members have been typing

Prototyping

Quickly converts requirements to working version of system

Once the user sees requirements converted to system, will ask for modifications or will generate additional requests

Most useful when:

-User requests are not clear
-Few users are involved in the system
-Designs are complex and require concrete form
-History of communication problems between analysts and users
-Tools are readily available to build prototype

Drawbacks

-Tendency to avoid formal documentation
-Difficult to adapt to more general user audience
-Sharing data with other systems is often not considered
-Systems Development Life Cycle (SDLC) checks are often bypassed

Business Process Reengineering (BPR)

Search for and implementation of radical change in business processes to achieve breakthrough improvements in products and services
Goals

Reorganize complete flow of data in major sections of an organization
Eliminate unnecessary steps
Combine steps
Become more responsive to future change

Identification of processes to reengineer

Key business processes

Set of activities designed to produce specific output for a particular customer or market
Focused on customers and outcome
Same techniques are used as were used for requirements determination

Identify specific activities that can be improved through BPR
Disruptive technologies

Technologies that enable the breaking of long-held business rules that inhibit organizations from making radical business changes

Systems Analysis & Design - Initiating & Planning Systems Development Projects

noreply@blogger.com (Han) — Sun, 18 Nov 2007 02:18:00 +0000

Activities
Project Initiation

Focuses on activities designed to assist in organizing team to conduct project planning.

Includes forming the project initiation team, establishing customer relationships, developing a plan to get the project started, setting project management procedures and creating overall environment.
Project Planning

Define activities and the work needed to complete each activity within a single project.

Outcomes :

1. BPP (Baseline Project Plan)
2. SOW (Statement of Work)

ssumptions about resources availability and potential problems will be made.

Assessing Project Feasibility
Economic
-a process of identifying the financial benefits and costs associated with a development project.
Technical
-a process of assessing the development organization’s ability to construct a proposed system.
-Include hardware, software, and operating system to be used in development.
Operational
-a process of assessing the degree to which a proposed system solves business problems or takes advantage of business opportunities.
Schedule
-a process of assessing the degree to which the potential time frame and completion dates for all major activities within a project meet the deadline and constraints for affecting change.
Legal and contractual
-a process of assessing potential legal and contractual ramifications due to the construction of a system.
Political
-a process of evaluating how stakeholders within the organization view the proposed system.

Economic Feasibility
Identify financial benefits and costs associated with a development project
Benefits :
Tangible - can be measured in dollars and with certainty
Categories :
1. Cost of reduction and avoidance
2. Error reduction
3. Increased feasibility
4. Increased speed of activity
5. Improvement of mgmt planning & control
6. New markets & increase sales opportunity
Intangible - cannot be measured in dollars/with certainty

May have direct organizational benefits or societal impact

Economic Feasibility - Costs
Tangible - Examples: items like hardware, software, operational
Intangible - Examples: loss of customer goodwill
One-time - associated with project initiation & development and the startup of the system.
- Example: new hardware, software purchase
Recurring - cost resulting from the ongoing evolution and use of the system
- Example: application software maintenance incremental data storage expense

Technical Feasibility
Assess the development organization’s ability to construct a proposed system.
Assessment Factors:
1. Project size.
2. Project structure.
3. The development group’s experience with the application and technology area.
4. The user group’s experience with development projects and application area.

Building the BPP
Baseline Project Plan (BPP)
contains all information collected during project initiation and planning.
Four Sections in BPP:
1. Introduction - project review & recommendation.
2. System Description - alternatives & system description.
3. Feasibility Assessment - economic, political & schedule, timeline and resource analysis.
4. Management Issues - team configuration and management, communication plan, project standards and procedures, others.

Systems Analysis & Design - Identifying & Selecting Systems Development Projects

noreply@blogger.com (Han) — Sat, 17 Nov 2007 12:56:00 +0000

Identifying and Selecting Systems Development Projects

Project Identification & Selection
The process

Identifying potential development projects

top management, steering committee, user department, development group

Classifying and ranking projects

value chain analysis, strategic alignment, potential benefits, resource availability, project size, technical difficulty/risks

Selecting projects for development

decisions factors ->decisions outcomes

Deliverables

A schedule of specific IS development projects.

An assurance that careful consideration was given to project selection.

IS Development Projects

Corporate Strategic Planning
an ongoing process that defines the mission, objectives and strategies of an organization.

Gain an understanding of the current enterprise

Top management must determine where it wants the enterprise to be in the future

A strategic plan can be developed to guide this transition.

IS Planning (ISP)
an orderly means of assessing the information needs of an organization and defining the systems, databases and technologies that will best satisfy those needs.

Assess current IS related assets - human resources,data, processes and technology.

The blueprints of those resources are developed to reach the organization’s objectives.

A series of scheduled projects is defined.

Describing the Current Situation
Top-down planning

A generic information systems planning methodology that attempts to gain a broad understanding of the information system needs of the entire organization.

Begins by conducting an analysis of the organization’s mission, objectives, strategy and determining the information requirements needed to achieve each objective.

Involved top-level management

Bottom-up planning

A generic information systems planning methodology that identifies and defines IS development projects based on problem solving or taking advantage of some business opportunities.

ns by the identification of business problems and opportunities.

an be faster and less costly to develop IS project.

t often fail to view the informational needs of the entire organization.

Systems Analysis & Design - Managing IS Project

noreply@blogger.com (Han) — Fri, 16 Nov 2007 12:19:00 +0000

Managing IS Project

Managing the IS Project

Managing the Information Systems Project

Representing and Scheduling Project Plans

Managing the Information Systems Project
Project?
* a planned undertaking of related activities to reach an objective that have a beginning and an end

Project management process
1. Initiating the project
2. Planning the project
3. Executing the project
4. Closing down the project

Initiating the project
1. Establishing the project initiation team
2. Establishing a relationship with the customer
3. Establishing the project initiation plan
4. Establishing management procedures
5. Establishing the project management and project workbook

Project Planning
1. Describing project scope, alternatives, and feasibility
2. Dividing the project into manageable tasks
3. Estimating resources and creating a resource plan
4. Developing a preliminary schedule
5. Developing a communication plan
6. Determining project standards and procedures
7. Identifying and assessing risk
8. Creating a preliminary budget
9. Developing a statement of work
10. Setting a baseline project plan

Representing and Scheduling Project Plans

Representing Project Plans

PERT and Gantt Chart

Using project management software

Microsoft Project
Primavera, KickStart etc

PERT vs. Gantt

PERT chart

All us to show dependencies explicitly
Allow us to calculate critical path
Can tell us how one task filling behind affects other tasks

Gantt charts

Allow us to record progress of project
Allow us to see what tasks are falling behind
Allow us to represent overlapping tasks

Project Management Tools
An example is MS Project

Allow us to specify tasks, dependencies, etc

Allow us to specify progress on tasks, etc

Can generate either PERT or Gantt charts (whichever we want) from data entered

PERT CHART

PERT CHART - the making
Steps:
1. Identify each activity to be completed in the project
2. Determine:

o + 4r + p

3. Determine the sequence of the activities and precedence relationships among all activities
Example :

4. Determine the critical path(CP)
* CP - delay in completion of an activity will result in delaying the entire project
* slack time - the amount of time that an activity can be delayed without delaying the project
* calculate T_E (sum of the ET for each activity from LR)
* calculate T_L (time an activity can be completed without delaying the project - RL)

** CP = activities slack time equals to zero

Systems Analysis & Design - Systems Development

noreply@blogger.com (Han) — Fri, 16 Nov 2007 11:23:00 +0000

Systems Development

Foundations for Systems Development

The concept of systems development

A modern approach to system analysis and design

System Analyst in System Development

Types of Information System and System development

System development life cycle

Skills required of a system analyst

Systems Analysis and Design
A complex, challenging, and stimulating organizational process that a team of business and systems professionals uses to develop and maintain computer-based information systems.

The concept of systems development

information system and design

application software

software engineering processes

methodologies

techniques

tools

A Modern Approach to System Analysis and Design

Separating data and processes that handle data

3 components of IS :
i. Data
ii. Data flow
iii. Processing logic
* Process-oriented approach v.s.
data-oriented approach

Separating databases and applications database?

Application independence

Team:
1. IS manager
2. system analyst(SA)
3. programmers
4. end-users
5. supporting end-user
6. business managers
7. other IS Managers/Technicians

SA in System Development
Systems Analyst
"the key individuals in the systems development process"
Skills required :
1. Analytical skills
2. Technical skills
3. Management skills
4. Interpersonal skills

Skills Required for SA
Technical Skills
understands the potential and the limitations of IT
Management Skills

resource management

project management

risk management

change management

Interpersonal Skills

communication skills

interviewing, listening and questionnaires

written and oral presentations

working alone and with a team

facilitating groups

managing expectations

Analytical Skills
Sets of Analytical Skills:

System Thinking

Organizational Knowledge

Problem Identifications

Problem Analyzing and Solutions

Organizational Knowledge

How work officially gets done in a particular organization

Understand the organization’s internal politics

Understand the organization’s competitive and regulatory environment

Understand the organization’s strategies and tactics

Types of IS and System development
1. Transaction processing systems
2. Management Information system
3. Decision support system (DSS)
4. Expert systems

System development life cycle

Systems Thinking
1. Identify something as a SYSTEM
2. Translate a specific physical situation into abstract terms
3. Think about the essential characteristics of a specific situation
What is "SYSTEM"?
DEFINITION : "An inter-related set of components with an identifiable boundary working together for some purpose"
Characteristic of a SYSTEM

Components/subsystems

Inter-related components

A boundary

A purpose

An environment

Interfaces

Input

Output

Constraints

Important System Concepts
To guide the design of Information System
Decomposition - Breaking down a system into its components
Modularity - Dividing a system up into chunks or modules of a relatively uniform size
Coupling - The extent to which subsystems depend on each other
Cohesion - The extent to which a system/subsystems performs a single function

Problem Identification
What is "PROBLEM"?
To identify:

compare current situation to the desired situation

Use models which are relied on by the IS users but it depends on organizational areas

see problems from a broader perspective

Problem Analyzing & Solving
Analysis :

find out more about the problem

Formulate alternative solutions to the problems

Phases :

1. Intelligence
2. Design
3. Choice
4. Implementation

Human Computer Interaction

noreply@blogger.com (Han) — Wed, 14 Nov 2007 10:28:00 +0000

Introduction

What is Human Computer Interaction?
Is the study of the relationships which exist between human users and the computer systems they use in the performance of their various tasks.

HCI seeks to provide an understanding of how users function, the tasks they need to perform and the way in which a computer systems needs to be structured to facilitate the easy carrying out of those tasks.

The importance of HCI

HCI is important in the design process since the computer interface is the first point of contact the user has with the system and the user will judge the system on the basis of the interface.
Systems should consider some aspects of the cost:

The cost of software is high and the competitive edge is more difficult to achieve. The interface to a system might give it this edge.
The cost to train users is high, therefore, a system which is easy and natural to use will save money in the long run, since the training time will be kept to a minimum.
The cost of human error can be high. Systems that are transparent ought to reduce the likelihood of error or to aid error recovery.

Taxonomy of HCI

• Use and context
o social organization and work
§ Points of view (e.g. Industrial engineering, operations resesarch)
§ Models of human activity
§ Models of small groups and organisations
§ Models of work, workflow, offices.
o application areas
§ Characterization of application areas (eg. Individual, group)
§ Document-oriented interfaces (eg. Text-editing, document formatting, spreadsheets, hypertext)
o human-machine fit & adaptation
§ Arrange a fit between the designed object and its use.
§ Changes to fit can be made
· At a design time/ at time of use
· Either changing the system or the user
• Human characteristics (how people work and how they are expected to interact with machines)
o human information processing
§ Phenomena and theory of memory, perception, motor skills, problem solving, motivation.
o language, communication, and interaction
§ Syntax, semantics
§ Graphical interaction, query, command
o ergonomics
§ physical factors
§ mental factors
• Computer system & interface architecture
o input & output devices
o dialogue techniques
o dialogue genre
o computer graphics
o dialog architecture
• Development process
o design approaches
o implementation techniques & tool
o evaluation techniques

Components of HCI
1. Human -user
2. Computer - mediator
3. Interface - used

Relationship of HCI to other disciplines
HCI

Engineering

Artificial Intelligence

psychology

Computer Science

physiology

Anthropology

Ergonomics

Linguistics

Philosophy

Art

Sociology

Disciplines contributing to HCI
• Computer Science
o To provide knowledge about the capability of technology and ideas about how this potential can be harnessed.
o Concerned about developing various kinds of techniques to support software design, development and maintenance.
• Cognitive Psychology
o Concerned with understanding human behavior and the mental processes that underlie it.
o To account for human behavior, cognitive psychology has adopted the notion of information processing such as what we see, what we touch, what we taste.
• Social and organizational psychology
o Concerned with studying the nature and causes of human behaviour in a social context.
o The role of social and organizational psychology is to inform designers about social and organizational structures and about how the introduction of computers will influence working practices.
• Ergonomics
o Developed from the interests of a number of different disciplines.
o Its purpose is to define and design tools and various artifacts for different work, leisure and domestic environments to suit the capabilities and capacities of users.
• Linguistics
o Is the scientific study of language
o Understanding of the syntax (structure) and semantic (meaning) is important
• Artificial Intelligence
o Concerned with the design of intelligent computer programs which simulate different aspects of intelligent human behaviour.
o The relationship of AI and HCI is mainly concerned with users’ needs when interacting with an intelligent interface.
• Philosophy, sociology and anthropology
o Traditionally, they have not been directly involved with the actual design of computer systems, but rather with the consequences of developments in information technology and technology transfer.
• Engineering and design
o Engineering is the applies science which relies heavily on model building and empirical testing. its takes the findings of science and utilizes them in the production of artifacts.
o Design contributes creative skills and knowledge to this process.

Factors in HCI

Human Factors (Ergonomics)

Is the study of the physical characteristics of the interaction:

How the controls are designed
The physical environment in which the interaction takes place
The layout and physical qualities of the screen.

Issues Addressed by Ergonomics

Arrangement of controls and displays

Sets of controls and parts of the display should be grouped logically to allow rapid access by the user.
Should be organized in terms of:

Functionality – controls and displays are organized so that those that are functionally related are placed together
Sequential - controls and displays are organized in a particular task sequence.
Frequency - controls and displays are organized based on the frequency of used

The physical environment of the interaction

Where will the system be used
By whom will it be used
Will users be sitting, standing or moving about
Considerations

Size The smallest user should be able to reach all the controls (this may include a user in a wheelchair), and the largest user should not be cramped in the environment. In particular, all users should be comfortably able to see critical displays.
Seat For long period of use, the user should be seated for comfort and stability, and seating should provide back support.
Stand If required to stand, the user should have room to move around in order to reach all the controls.

Health Issues

These are the factors in the physical environment that directly affect the quality of the interaction and the user's performance :

Physical Position
Temperature
Lighting
Noise
Time

The use of colour

Importance of Arrangement of Control and Displays

Give strong emotional reaction
Add accents to an uninteresting display
Facilitate subtle discrimination in complex displays
Emphasize the logical organization of information
Draw attention to alert the users

The C Language

noreply@blogger.com (Han) — Wed, 14 Nov 2007 10:18:00 +0000

The Language
Where did it come from?
-Seed language was the Basic Combined Programming Language(BCPL) in 1967
-BCPL refined into a language called B
-Dennis Ritchie enhanced B to form C in 1972
-The American National Standards Institute(ANSI) completed C standards in 1988

Why C?
-C is a powerful and flexible language.
-C is a popular language preferred by professional programmers.
-C is a portable language.
-C is a language of few words, containing only a handful of terms keywords.
-C is modular.
-Structured language.

Forming a C Program
Whitespace
-spaces, tabs, line endings, and blank lines.
-irrelevant to the compiler.
-should be used in specific places to make your program more readable.

Outline Form
-Your program should resemble an outline with main topics to the left and subordinate topics to the right.
-Statements end with semicolon ";"
-Where the line ends is usually not important.
-However, line breaks are not allowed inside of quotations.

Comments
-Comments in C are shown by /* and */
-Everything between /* and */ is ignored by the compiler.
-Comments are very important to the understandability of a program.
-Make sure you end all of your comments.

Directives
-Directives tell the preprocessor to do things
-Directives always begin with #
-Directives end at the end of the source line
-The #include in the example program tells the preprocessor to insert the code found in the stdio.h file at that location.

Statements
-A statement is a HLL instruction that performs a specific operation.
e.g. quiz = 20;
-All single statements end with a semicolon and may extend over multiple lines.
e.g. printf("A perfect quiz is %d points.\n", quiz);
Assignment statement
-A statement is a complete direction instructing the computer to carry out some task.
e.g. x = 2 + 3;
Compound statement
-A block, group two or more C statement enclosed in braces
e.g. { printf("Hello");
printf("Class"); }

Functions
-A function is a set of instructions that performs an operation
-A function will always have a name that can be used to reference (or call) the function.
-The function name will be followed by the argument list in parentheses (sometimes there will be no arguments and so the parentheses will be empty).

Values in C
Numeric values
-Real numbers
-Integral number (or whole numbers)
Character values
-ASCII code is an integer value for characters
-The character 'A' is the same as 65 in ASCII
-You can add characters
'A' + ' ' = 'a' 65 + 32 = 97

Special ASCII Characters
-Special characters have a backslash \ followed by a printable character
\0 = Null \t = Horizontal tab
\a = Audible alarm \v = Vertical tab
\b = Backspace \' = Apostrophe
\f = Form feed \" = Quote
\n = New line \? = Question mark
\r = Carriage Return \\ = Backslash

Integral Data Types
- Basic types
§ Character type char
§ Integer type int
§ Floating type float
§ Valueless type void
- Both can be signed (default) or unsigned
- Type int can be short, long, or neither
- Type float can be double, long double
- Signed allows the value to be negative
- Unsigned allows only positive (and zero)

The char Data Type
- Eight bits long
- Used to store characters, but really numbers
- Range for signed char values is -128 to 127
- Range for unsigned char values is 0 to 255
- Some valid char declarations
char letter;
unsigned char index;
char TopGrade = ‘A’, BottonGrade = ‘F’;
char TopGrade = 65, BottonGrade = 70;

The int Data Type
- Variable length
- Type long int at least as big as short int
- The word int can be implicit
- Some valid int declarations
int currentPage, lastPage;
short age;
unsigned volts = 110;
unsigned volts = ‘n’;
unsigned long nationalDebt;
signed short variance;

Floating Point Data Types
-Stored in scientific notation
o Mantissa of significant digits
o Exponent power of 10
-Expressed in standard or scientific notation
o Can use 7146.0 or 7.146e3
-Three flavors (float, double, long double)
o Type double greater than or equal to float
o Type long double greater than or equal to double

Floating Point Forms
-A value with a decimal stored as double
-Explicitly assign type
o Use F or f for a float (3.806e-3F or 0.003806F)
o Use L or l for a long double
-Some valid floating point declarations
float wageRate = 12.75;
double area, volume;
long double humongous;

String Data
- A string is a set of characters
- String values indicated by quotes
o For example, “This is a string”
- The quotes are not part of the string
printf(“This is a string”);
results in
This is a string

More String Data
- Adjacent strings are concatenated
o So, “This is just” “one string.” would be stored as This is just one string.
- Remember, no line endings inside a string
- Quote marks within the string are special characters and are indicated by \”
printf(“Her name\nis \”Henrietta.\””);
Her name
is “Henrietta.”

Variables
- Represent a location or locations in memory
- Values are placed there to be used in a program
- Values can change, thus are “variable”
- Variable names are used to reference

Variable Names
- Length depends on compiler (at least 31)
- Only alpha-numeric (A to Z, a to z, and 0 to 9) characters and the underscore ( _ )
- Must begin with alpha or underscore
- No blank space between variable names
- C is case-sensitive
o So Total is different from total and toTal
- No reserved words (also called keywords)

Variable Declarations
- All variables must be declared before used
datatype variable [= initialization]
int frequency;
int StartValue = 14;
- A declaration does a number of things
o Tells the compiler how to store the value
o Defines it, memory is allocated for it
o May initialize it, giving it an initial value

Simple Output
- Most common output function is printf()
- Uses codes to represent data placement
o Character values represented by %c
o Integer values represented by %d
o Float values represented by %f
o ASCII values for characters can be printed by using the integer code %d

Conversion Characters
%s string of character
%c character
%d decimal integer
%f floating-point numbers
%e exponential notation
%o octal integer
%x hexadecimal integer
%% percent sign (%)

Example of Output
Program :
#include
void main(void)
{
printf(“Here is the character %c,\n”, ‘X’);
printf(“and the numbers %d and %f.\n”, 46, 12.345);
printf(“Now we will print %d as a number.\n”, ‘X’);
printf(“Things will really be messed up if we confuse\n”
“data types, such as %f and %d.\n”, 46, 12.345);
}
Output:
Here is the character X,
and the numbers 46 and 12.345.
Now we will print 88 as a number.
Things will really be messed up if we confuse
data types, such as -2.19317e-73 and 16424.

Expression
- Anything that evaluates to a numeric value
- consist of a single item, simple variable, literal constant or symbolic constant
e.g.
2 + 3;
or
rate * 5;

Operators
- An operator is a symbol that performs a specific mathematical or logical operation
- Types of operators
· arithmetic
· assignment
· equality
· relational
· logical
· Increment and Decrement operators

Arithmetic Expressions
- Anything reducible to a single value
- Consists of values and/or variables connected by arithmetic operators
- Precedence determines what operator gets done first
- Associativity dictates the order if two operators have the same precedence

RULES OF OPERATOR PRECEDENCE
1. Parentheses ( )
2. Multiplication *
Division /
Modulus %
3. Addition +
Subtraction -

Integer Arithmetic
- Result is integer
- Be careful result is not too big
o For example, 32000 * 10 can result in -7680
- Division truncates any fractions
o The result of 3 / 2 is 1, not 1.5
- Remainder (or modulo or modulus)
o Only good with positive integers
o The result of 14 % 10 is 4, 3 % 10 is 3

Mixed Arithmetic
- Result is the highest data type used
- Highest data type takes most memory
o Floats are higher than Integers

Example

Assignment Operator	Sample Expression
+=	c+=7
-=	d-=4
*=	e*=5
/=	f/=3
%=	g%=9

Equality
To determine whether two items are equal to one another.

C equality	standard algebraic
== (x == 100)	=
!= (5 != x)	≠

Relational
C provides a set of relational that allows you to compare numbers.
Operator Example
> x>100
>= x>=20

Logical
C provides a set of logical that are used to combine expressions into logical expression
Operator
&& logical AND
II logical OR

Increment & Decrement
++ ++a = increment a by 1 then use the new value of a in the expression in which a resides
++ a++ = use the current value of a in the expression in which a resides, then increment a by 1
-- --a = decrement a by 1 then use the new value of a in the expression in which a resides
-- a-- = use the current value of a in the expression in which a resides, then decrement a by 1