Lec 1 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005

Lecture - 1 Introduction to Data Structures and Algorithms

C++ PROGRAM TO ADD, SUBTRACT AND MULTIPLY TWO COMPLEX NUMBERS USING OPERATOR OVERLOADING

/*C++ program to add, subtract and multiply two complex numbers using operator overloading*/
#include
#include
class complex
{
float x,y;
public:
complex() {}
complex(float real,float img)
{
x=real; y=img;
}
complex operator+(complex);
complex operator-(complex);
complex operator*(complex);
void display()
{
cout< }
};
complex complex::operator+(complex c)
{
complex temp;
temp.x=x+c.x;
temp.y=y+c.y;
return(temp);
}
complex complex::operator-(complex d)
{
complex temp;
temp.x=x-d.x;
temp.y=y-d.y;
return(temp);
}
complex complex::operator*(complex e)
{
complex temp;
temp.x=x*e.x+y*e.y*(-1);
temp.y=x*e.y+y*e.x;
return(temp);
}
void main()
{
clrscr();
complex c1(5,3),c2(3,2),c3=c1+c2,c4=c1-c2,c5=c1*c2;
c1.display();
c2.display();
cout<<"Addition"< c3.display();
cout<<"Subtraction"< c4.display();
cout<<"Multiplication"< c5.display();
getch();
}

How To Change a Windows XP Limited User Account Into a Computer Administrator � Raymond.CC Blog

How To Change a Windows XP Limited User Account Into a Computer Administrator � Raymond.CC Blog

William Stallings Computer Organization and Architecture

Chapter 2
Computer Evolution and
Performance
Key Points


• The evolution of computers has been characterized by increasing processor speed, decreasing component size, increasing memory size and increasing I/O capacity and speed
• Processor speed is as a result of shrinking factor in the processor components; reducing the distance between the components hence, increasing speed. True cause is the organization of the processor e.g. pipelining and parallel execution techniques
• Critical issue here is the balancing of the performance of the various elements

A Brief History of Computers
• First generation – vacuum tubes
 ENIAC The
 Von Neumann Machine
 Commercial computers
• Second generation – Transistors
 The IBM 7094
 Third generation – Integrated Circuits
 Later generations

ENIAC - background
• Electronic Numerical Integrator And Computer
• By John Presper Eckert and Prof. John Mauchly at the
• University of Pennsylvania
• World’s first general-purpose electronic digital computer
• Started 1943
• Trajectory tables for weapons
• Finished 1946
 Too late for war effort
• Used until 1955

ENIAC - details
• Decimal (not binary)
• 20 accumulators, each capable of holding 10 digits each
• Programmed manually by switches
• 8,000 vacuum tubes
• 30 tons
• 15,000 square feet
• 140 kW of power consumption
• 5,000 additions per second

Von Neumann/Turing
• 1945-first publication of the idea; the EDVAC (Electronic Discrete Variable Computer)
• The manual programming was too tedious
• Stored Program concept by John Von Neumann; Alan Turing developed the idea at around the same time
• Main memory storing programs and data -a for suitable for storing in memory alongside data
• ALU operating on binary data
• Control unit interpreting instructions from memory and executing
• Input and output equipment operated by control unit
• Work on the computer begun at the Princeton Institute for Advanced Studies. The computer was named, IAS
• Computer and was completed in 1952
• This is the prototype of all subsequent general-purpose computer

Von Neumann/Turing Components
• A main memory that stores both data and instructions
• An ALU (Arithmetic and Logic Unit) capable of operating on binary data
• A control Unit which interprets the instructions in memory an causes them to be executed
• Input and output (I/O) equipment operated by the control unit

Structure of von Neumann


IAS - details
• 1000 storage locations (words) of 40 bits each; both data and instructions are stored here
• Everything must be in Binary number
• Each number is represented by a sign bit and a 39- bit value (see figure 2.2 on page 19 for the William’s book)
• 2 instructions per word of 20 bits each


IAS - details
• Set of registers (storage in CPU)
• Memory Buffer Register (MBR) contains a word to be stored in memory or is used to receive word from memory
• Memory Address Register(MAR) – specifies the address in memory of the word to be written from or read into the MBR
• Instruction Register(IR) – contains the 8-bit opcode instruction being executed
• Instruction Buffer Register (IBR) – employed to hold temporarily the right-hand instruction from a word memory
• Program Counter (PC)- contains the address of the next instruction-pair to be fetched from memory
• Accumulator (AC) and Multiplier Quotient (MQ) – employed to hold temporarily operands and results of ALU operations; e.g. a*b=c(80bits) so the most significant 40 bits are stored in the
• AC and the least significant stored in MQ

Structure of IAS - detail

Commercial Computers
• 1947 -Eckert-Mauchly Computer Corporation
• UNIVAC I (Universal Automatic Computer)
• US Bureau of Census 1950 calculations
• Became part of Sperry-Rand Corporation
• Late 1950s -UNIVAC II
• Faster
• More memory

• IBM
• Punched-card processing equipment
• 1953 - the 701
 IBM’s first stored program computer
 What does IBM stand for?
 Scientific calculations
• 1955 - the 702
 Business applications
• Lead to 700/7000 series

Transistors
• Replaced vacuum tubes
• Smaller
• Cheaper
• Less heat dissipation
• Solid State device
• Made from Silicon (Sand)
• Invented 1947 at Bell Labs
• William Shockley et al.

Transistor Based Computers
• Second generation machines
• NCR (?) & RCA (?) produced small transistor machines
• IBM 7000
• DEC -1957
 Produced PDP-1

Microelectronics
• Literally - “small electronics”
• A computer is made up of gates, memory cells and interconnections
• These can be manufactured on a semiconductor

Generations of Computer
• Vacuum tube -1946-1957
• Transistor -1958-1964
• Small scale integration -1965 on
 Up to 100 devices on a chip
• Medium scale integration -to 1971
 100-3,000 devices on a chip
• Large scale integration -1971-1977
 3,000 -100,000 devices on a chip
• Very large scale integration -1978 to date
 100,000 -100,000,000 devices on a chip
• Ultra large scale integration
 Over 100,000,000 devices on a chip

Moore’s Law
• Increased density of components on chip
• Gordon Moore - cofounder of Intel
• Number of transistors on a chip, will double every year
 Since 1970’s development has slowed a little
• Number of transistors doubles every 18 months
• Cost of a chip has remained almost unchanged
• Higher packing density means shorter electrical paths, giving higher performance
• Smaller size gives increased flexibility
• Reduced power and cooling requirements
• Fewer interconnections increases reliability

Growth in CPU Transistor Count



IBM 360 series
• 1964
• Replaced (& not compatible with) 7000 series
• First planned “family” of computers
 Similar or identical instruction sets
 Similar or identical O/S
 Increasing speed
 Increasing number of I/O ports (i.e. more terminals)
 Increased memory size
 Increased cost
• Multiplexed switch structure

DEC PDP-8
• 1964
• First minicomputer (after miniskirt!)
• Did not need air conditioned room
• Small enough to sit on a lab bench
• $16,000
 $100k+ for IBM 360
• Embedded applications & OEM
• BUS STRUCTURE
•

DEC -PDP-8 Bus Structure

Intel
• 1971 - 4004
 First microprocessor
 All CPU components on a single chip
 4 bit
• Followed in 1972 by 8008
 8 bit
 Both designed for specific applications
• z1974 - 8080
 Intel’s first general purpose microprocessor

Designing for Performance
• The cost of computers continue to drop while the performance and capacity continue to rise
• However, the basic building blocks for today’s computers are virtually the same as those of the IAS computer from over 50 years ago!
• The key idea is therefore the techniques for squeezing performance out of the material.

Microprocessor Speed-
Speeding it up
• Pipelining
• On board cache
• On board L1 & L2 cache
• Branch prediction
• Data flow analysis
• Speculative execution

Performance Mismatch
• Processor speed increased
• Memory capacity increased
• Memory speed lags behind processor speed

Solutions
• Increase number of bits retrieved at one time
 Make DRAM “wider” rather than “deeper”
• Change DRAM interface
 Cache
• Reduce frequency of memory access
 More complex cache and cache on chip
• Increase interconnection bandwidth
 High speed buses
 Hierarchy of buses

Internet Resources
• http://www.intel.com/
 Search for the Intel Museum
• http://www.ibm.com
• http://www.dec.com
• Charles Babbage Institute
• PowerPC
• Intel Developer Home

ICS 113: Programming


Structures in C


Introduction to structures
n Arrays are data structures whose elements are of the
same type.
n Structure is “a data structure ” in which the individual
elements can di ffer in type.
n A structure is a data type that consists of a collection of
several variables stored together. A structure can also be
referred to as a record.
n The individual structure elements are known as
elements.

Defining a structure

•
A structure must be def ined in terms of its indi vidual
members. In general terms, a structure may be def ined
as:
struct tag{
member 1;
member 2;
member 3;
........
member m;
};


Structure members



•
The individual members can be ordinary var iables,
pointers, arrays or other structures.
•
The member names wi thin a particular structure must be
distinct from one another, though a member name can be
the same as the name of a variable that is defined
outside the structure.
•
Individual members cannot be initiali zed within a
structure type declarati on.
•
A storage class cannot be assigned to an individualmember.

Declaring a structure
n Once the composition of the structure has been defined, individual
structure type variables can be declared as follows:
storage_class struct tag variable1, variable2, variable n;
– Storage_class is an optional storage class specifier
e.g. static, external e.t.c.
– struct is a required keyword,
– tag is the name that appeared in the structure
declaration and
– variable1 to variable n are structure variables of type
tag.

Example 1

struct account{
int acct_no;
char acct_type;
char name[80];
float balance;

};

•
We can now declare the structure variables customer1
and customer2 as follows:
struct account customer1, customer2;

•
Thus, customer1 and customer2 are variables of type
account. In other word s, customer1 and customer2 are
structure-type variables whose composition i s identified
by the tag account.

Combining structure and variable declarations

storage_class struct tag{

member 1;

member 2;

member 3;

.........


member m;
}variable1, variable2, ..., variable n;

•
The tag is optional in this situation.

Example 2



struct account{ struct {
int acct_no; int acct_no;
char acct_type; char acct_type;
char name[80]; char name[80];
float balance; float balance;

} customer1, customer2; } customer1, customer2;


Case 1 and 2 serve the same purpose


Embedded structures



•
A structure variable can also be a def ined as a member
of another structure.
•
In such situations, the declaration of the embedded
structure must appear bef ore the declaration of the outer
structure.

Example 3

struct date{

int month;

int day;

int year;
};

struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
} customer1, customer2;


Structure initialization
n The members of a structure can be assigned initial
values in much the same manner as the elements of an
array.
n The initial values must appear in the order in wh ich they
will be assigned to thei r corresponding structure
members, enclosed in braces and separated by
commas. The general form is:
storage_class struct tag variable ={value1,
value2, value3, …., valuem};
n N.B. A structure variable, like an array, can be initialized
only if its storage class is either external or static.

Example 4
struct date{
int month;
int day;
int year;
};
struct {
int acct_no;
char acct_type;
char name[80];
float balance;
struct date lastpayment;
};
static struct account customer = {987654, ‘S’, “Will Obongo”, 102,589.30, 8, 12,
2005}

Array of structures


•
It is also possible to define anarray of structures, i.e. an
array in which each element is
a structure.
struct date{

int month;

int day;

int year;
};
struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
}customer[100];

•
In this declaration,
customer is a 100
element array ofstructures.Hence, each
element of customer is a
separate structure of typeaccount i.e. each element
of customer represents anindividual customer
record.

Initializing an array of structures


struct date{
char name[80];
int month;
int day;
int year;

};

static struct date bday[]={
{"Amy", 12, 30, 73},
{"Gail", 5, 13, 66},
{"Marc", 7, 15, 72},
{"Maria", 5 29, 67}
};

struct date{
char name[80];
int month;
int day;
int year;

};

static struct date bday[]={
"Amy", 12, 30, 73,
"Gail", 5, 13, 66,
"Marc", 7, 15, 72,
"Maria", 5 29, 67
};


Naming members



•
Remember that each structure is a sel f contained entity
with respect to member def initions.
•
Thus, the same member name can be used i n different
structures to represent di fferent data, i.e. the scope of a
member name is conf ined to the particular structure
within which it is def ined.

Processing a structure


•
The members of a structure are usually processed
individually, as separate entities. Theref ore, we can
access the individual members by writin g:
variable.member

•
Where variable refers to the name of a structure -type
variable, and member refers to the name of a member
within the structure.
•
Notice the period (.) that separates the variable name
from the member name. T his period is an operator; it is a
member of the highest precedence group, and its
associativity is left to right.

Example 5



struct date{ •
customer.acct_no;
int month; •
date.month;

•
customer.balance;
int day;

int year;
};
struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
}customer;


(.) operator



•
Since this operator is a member of the highest
precedence group, this operator wil l take precedence
over the unary operators as well as the various
arithmetic, relational, l ogical and assignment operators.
•
Thus ++variable.member = ++(variable.member) and
&variable.member = &(variable.member)

(.) expressions



•
More complex expressions invol ving the repeated use of
the period operator may also be written.
•
For example, if a structure member is itself a structure,
then a member of the embedded structure can be
accessed by writing
variable.member.submember

•
Where member refers to the name of the member within
the outer structure, and submember refers to the name of
the member withinn the embedded structure.

Example 6

struct date{
int month;
int day;
int year;

}; •
customer.lastpayment.month

struct { •
++customer.lastpayment.month
int acct_no; •
customer.name[2]
char acct_type; •
&customer.name[2]
char name[80];
float balance;
struct date lastpayment;

}customer;


(.) with arrays of structures



•
The use of the period operator can be extended to arrays of
structures, by writing:
array[expression].member

where array refers to the array name, and array[expression] refers
to an individual array element (a structure variable). Therefore
array[expression].member will refer to a specific member within a
particular structure.


Example 7

struct date{
int month;
int day;
int year;

}; •
Customer[13].acct_no

•
Customer[13].balance
struct {

•
Customer[13].name
int acct_no;

•
Customer[13].name[6]
char acct_type;

•
Customer[13].lastpayment.month
char name[80];

•
++Customer[13].lastpayment.day

float balance;
struct date lastpayment;
}customer[100];


Processing structure members


•
Structure members can be processed in the same
manner as ordinary va riables of the same data type.
•
Single-valued structure members can appear in
expressions, they can be passed to functions, and they
can be returned f rom functions as though they were
ordinary single-valued variables.
•
Complex structure members are processed i n the same
way as ordinary data items of that same type. E.g. a
structure member that is an array can be processed in
the same manner as an ordinary array, and with the
same restrictions.

User defined data types (typedef)


•
The typedef feature allows users to define new data-
types that are equivale nt to existing data types.
•
Once a user-defined data type has been established,
then new variables, arr ays, structures etc can be
declared in terms of thi s new data type.

typedef


•
In general terms, a new data type is def ined as:
typedef type new-type
where type refers to an existing data type (either a
standard data type, or previous user -defined data type),
and new-type refers to the new user -defined data type.

•
It should be understood however, that the new data
type will be new in name only. In reality, this new data
type will not be fundamentally different f rom one of the
standard data types.

typedef int age;

thus

age male, female;

Is equivalent to

int male, female;

Example 8

The following declarations:

•
typedef float height[100];
•
Height men, women;
define height as a 100-element floating
point array type, hence men and
women are 100 element floating point
arrays. Another way to express this is

•
typedef float height;
•
height men[100], women[100];

typedef and structures



•
The typedef feature is particularly convenient when defining
structures, since it eliminates the need to repeatedly write struct tag
whenever a structure is referenced.
•
In addition, the name given to a user-defined structure type often
suggests the purpose of the structure within the program.
•
In general terms, a user defined structure type can be written as:
typedef struct{
member1;
member2;
.......
membern;


}new_type;


Example 9


typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}record;

record oldcustomer,
newcustomer;


typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}record;

record customer[100];


Example 10



typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}record[100];

record customer;

typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}customer [100];


Structures and pointers


•
The beginning address of a structure can be accessed in the
same manner as any other address, through the use of the
address (&) operator.
•
Thus if variable represents a structure-type variable, then
&variable represents the starting address of that variable.
•
Moreover, we can declare a pointer vari able for a structure by
writing
type *ptvar;
where type is a data type that identifies the composition of the
structure and ptvar represents the name of the pointer variable.

•
We can then assign the beginning address of a structure variable
to this pointer by writing
ptvar = &variable;


Example 11


typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}account;

account customer, *pc;
pc = &customer;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}customer, *pc;

pc = &customer;



Accessing individual members using
pointers


•
An individual structure member can be accessed in
terms of its corresponding pointer variable by writin g
ptvar->member

•
ptvar refers to a structure -type pointer variable and the
operator -> is comparable to the period (.) operator. Thus
the expression ptvar->member is equivalent to writing
variable.member where variable is a structure -type
variable.
•
The operator falls into the highest precedence group, like
the period operator and its associativity is also left to
right.

(.) and ->
n The –> operator and the period operator can be
combined to access a submember within a structure.
Hence the submember can be accessed by writing
ptvar->member.submember
n Similarly, the -> operator can be used to access an
element of an array that is a member of a structure..
ptvar->member[expression]

Example 12


•
customer.acct_no
•
pc->acct_no
•
(*pc).acct_no
typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}customer, *pc=&customer;


The parentheses are
required in the last
expression because
the period operator
has a higher
precedence than the
*.


Pointers as structure members



•
A structure can also include one or more pointers
as members.
•
If ptmember is a pointer and a member of
variable, then *variable.ptmember will access the
value to which ptmember points.

Passing structures to functions


•
Individual structure members can be passed to a
function as arguments in the function call, and a
single structure member can be returned via the
return statement.

Example 13


float adjust(char name[], int acct_no,
float balance)
main(){
typedef struct{
int month;
int day;
int year;
}date;
typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;
}customer;

customer.balance =
adjust(customer.name,
customer.acct_no,
customer.balance);

}

float adjust(char name[],
int acct_no, float
balance)

{
float newbalance;
newbalance=.....;
return(newbalance);

}


Passing structures to functions


•
A complete structure can be transferred to a function by
passing a structure -type pointer as an argument.
•
However, we must use explicit pointer notation to
represent a structure that is passed as an argument.
•
A structure passed in this manner is passed by reference
rather than by value.

Example 12

#include
typedef struct {

void adjust(record *pt)

char *name;

{

char acct_type;
int acct_no; pt->name="John
float balance; W.";


}record;

pt->acct_type='S';

void adjust(record *pt);

pt>
acct_no=34569;

main()
{ pt->balance=0.0;
static record cust =

}

{"smith",'C',333,34765};
printf("%s %c %d %.2f\n", cust.name,


cust.acct_type, cust.acct_no,
cust.balance);
adjust(&cust);
printf("%s %c %d %.2f\n", cust.name,


cust.acct_type, cust.acct_no,
cust.balance)
}