Introduction to Computer Science

2000 Spring
Exam 1: 4/20/00
Final:     6/19/00

Project 1: 3/30/00 (Savitch, p.287 #9)
Project 2: 4/27/00 (Savitch, p.355 #9)
 
 

1999 Fall
Exam 1: 10/20/99 (15%)   Answers
Exam 2: 11/17/99 (15%)   Answers
Exam 3: 12/15/99 (15%)   Answers
Final    :  1/14/99 (25%)

Project 1: 10/29/99 (10%)
Project 2: 11/26/99 (10%)   Program Output
Project 3: 12/24/99 (10%)

Text Books:

W. Savitch, Problem Solving with C++, 2nd ed., Addison-Wesley, 1999. (2 Hours/Week)
H. L. Capron, Computers: Tools for an Information Age, 5th ed., Addison-Wesley, 1998. (1 Hour/Week)

Chapter 1   Introduction to Computer and C++ Programming

Computer Systems

Hareware

• I/O Devices, CPU, Main Memory, Secondary Memory
• 1 Bit = 0 or 1 (on or off)
• 1 Byte = 8 Bits
• Why 8?
• 2^8=2^7*2=128*2
• The ASCII Charater Set (p 772): ASCII (American Standard Code for Information Interchange) E.g. A=01000001.
• Bytes and Addresses (p 5)
• Display 1.2: Memory Locations and Bytes (p 5)

Software

• A program (code) is a set of instructions for a computer to follows.
• Propramming=Coding
• An operating system is a program that acts as an intermediary between human beings and computer.
• Windows 98, Linux for PCs
• Unix for Workstations
• Computer Languages
• High-Level Languages: They are designed to be easy for human begins to write programs and to read them.
• C++, C, FORTRAN, BASIC, COBOL
• Low-Level Languages: They are designed to be executed very fast by a computer. They contain simple instructions, such as, ADD X Y Z (Add the number in the memory location called X to the number in the location Y, and place the result in the location Z) in the assembly language.
• Machine Languages:  They are programs written in the form of 0s and 1s that the computer actually reads and follows.
• A program that translates a high-level language like C++ to a machine language is called a compiler.
• Visual C++ for Win98.
• Linker (p 11)
• Display 1.5: Compiling, Linking, and Executing a C++ Program (p 10)
• Include source (input) code, object code, CPU, output code.
• An algorithm is a sequence of precise step-by-step instructions that leads to a solution.
• Al-Khowarizmi (9 A.D. Arabic mathematician) wrote the book Kitab al-jabr w'almuqabala (Rules for reuniting and reducing). Al-jabr => Algebra ~ Algorithm.
• Display 1.7: Program Design Process (p 17)
• Software Life Cycle
• Analysis and Specification (Problem Definition)
• Design (Algorithm Design)
• Implementation (Coding)
• Testing and Debugging
• Maintenance and Revision
• Obsolescence

Introduction to C++

Origins

• The B Language was developed by Ken Thompson who is the originator of  the UNIX operating system.
• The C Language was developed by Dennis Ritchie of AT&T Bell Lab in 1970s for writing and maintaing UNIX. C is a high-level language with many of the features of a low-level language.
• The C++ language developed by Bjarne Stroustrup of AT&T Bell Lab in 1980s is derived from C and is based on the object-oriented programming (OOP) principles.

A Sample C++ Program

• Display 2.15: A Sample C++ Program and Program Layout (p 93)
• Documentation
• Beginning of program
• Libraries with directives
• Main function
• Variable declaration
• Main body (statements) of program with comments
• Return-statement
• End of program
• A statement is an instruction that ends with a semicolon.
• A library is a program that is pre-written and pre-compiled by the user, other programmers, or the developers of the compiler.
• #include <lib1.h> // lib1 is provided by the compiler.

#include "lib2.hpp" // lib2 is provided by the user. The header (h, hpp) can be different.

Chapter 2   C++ Basics

Documentation

• Comment Symbols

// A comment on a single line.

/* A comment spans on multiple lines.
*/

Variables

• A C++ variable is the name of a number or data (value) of certain types.

Its value can vary from place to place within the program.
• D2.15: main, NORMAL, temperature.

Identifiers

• An identifier is the name of a variable (NORMAL, temperature) or other item (main, include, double, cout, cin, if, etc.) that must start with either a letter or the underscore symbol followed by letters, digits, or underscore.
• C++ is case-sensitive, e.g., rate, RATE, and Rate are three distinct variables.
• D2.15: include, iostream, int, main, const, double, NORMAL, cin, etc.

C++ Keywords

• Keywords (reserved words) are predefined identifiers in C++ compiler, that you cannot use as names for variables or anything else.
• D2.15: int, main, include, etc.
• Appendix 1 (p 861)

Data Types

• D2.2 Some Number Types (p 60)
• Type char, bool (value= true or false)
• Every variable must be delared to a type.
• Variable Declaration Syntax (p 43)
• The syntax for a programming language is the set of grammar rules for that language.

Values

• The number or other type of data held in a variable is called its value.
• Values of int: 2, -5, 1, 0 etc.

Values of char: a, abc, A2, etc.
Values of bool: true, false
• D2.15 98.6 is the value of NORMAL.

Functions

Syntax 1

Type_Name   Function_Name(Type1 Argument1, Type2 Argument2, ...)
{
     Statement1
     Statement2
     Statement3
     .
     .
     .
    return value; // Return a value of the type Type_Name.
}
The argument list Type1 Argument1, Type2 Argument2, ... is optional (with or without it is okay).

Syntax 2

Type_Returned Function_Name(Type1 Argument1, Type2 Argument2, ...)
Single_Statement;

D2.15: main

Operators

• An operator is a special type of function that takes one or more arguments and creates a new value.
• D2.15:    =, <<, >>, >.
• Appendix 2 Precedence of Operators (p 863)
• E.g. 2*3+4 == 10 not 14 since the precedence of the operator * is higher than that of +.

• The assignment operator =  assigns the value on the right hand side (RHS) to the variable on the left hand side (LHS).

D2.15: NORMAL = 98.6
• The insertion operator << inserts the value "...." or the value of the variable on RHS to the variable on LHS.

D2.15: cout << "Enter your temperature: "
cout is a predefined ouput function. You can think of it as a name for the screen. So you will see Enter your temperature: on your screen when this statement is executed.
• The extraction operator >> extracts the value  "...." or the value of the variable on LHS to the variable on RHS.

D2.15: cin >> temperature
cin is a predefined input function. This statement means that >> obtains the value (100 e.g.) from the input device keyboard and assigns it to the variable temperature.

Comparison (Boolean) Operators

• D2.8 (p 74)
• The comparison operator < compares the values of LHS and of RHS and returns a boolean value true or false.
• D2.15: temperature > NORMAL (100 > 98.6)

Hence > returns the true value.

Introduction to the Use of Microsoft Visual C++

Expressions

• An expression is a combination of variables and/or values using operators.
• D2.15: temperature > NORMAL is a Boolean expression.
• D2.7 Syntax for an if-else-Statement (p 73)
• D2.15: if (....

Arithmetic Operators and Expressions

• D2.4 (p 66) D2.5 (p 67)

Input and Output (I/O)

• Stream: A current of water.
• An input stream is simply the stream of input that is being fed into the computer for the program to use.
• An ouput stream is the stream of output generated by the program.
• D2.15: iostream is the name of a library that contains the definitions of the functions (such as cin and cout) that handle input from input devices (keyboard etc.) and output to output devices (screen etc.).

iostream.h is an header file that contains some basic information about this library.
The \n at the end of quoted string tells the computer to start a new line after writing out the text.

Review D2.15

Chapter 3  Functions, Abstraction, Overloading

Answer: Using a Taylor polynomial
exp(x)=1+1/x+..... (see Calculus)
sin(x)=....
ln(1+x)=....
Polynomial, Power, Factorial

Programming Example 1 (PE1): Develope a C++ project for solving MP1.

Program 1 (PE1-1): Factorial Function (p. 149)

How to use PE1-1? Write a main program to call the factorial function. (See Exam 2)

Function Prototype Syntax (p. 119, 126)

Function Definition (p. 117, 126)

Function Call Syntax (p. 108)

Formal Parameters, Arguments (p. 185)

Call-by-Value (p. 185)

Procedural Abstraction (p. 129, 130)

Local Variables (p. 142)

Review Project 2.

PE1-2: Power Function

Predefined Functions (p. 111)

Programmer-Defined Functions

Automatic Type Conversion (p. 154)

Top-Down Design (Divide and Conquer): Break the project into many subprograms. (p. 106)

12/17/99 計算機與網路中心 電腦教室 4

Project 3:
Given f(x)=sum_{n=0}^{n=infinity} ((-1)^(n+k(n)) x^n)/(n!*(n-0.5)) where k(n)=0 if n%4=1 or 2 and k(n)=1 if n%4=0 or 3, compute f(1), f(10), f(20), f(30) up to 12 significant digits.

12/17/99

12/24/99 計算機與網路中心 電腦教室 2
1/7/2000 計算機與網路中心 電腦教室 4
 
 
 

------ Scratch below -----

Polymorphism (p. 153)
Overloading a function name (p. 151)
double power(double x, int n);
double power(double x, double y, int n); Use pow()

Chapter 4  Void, Call-by-Reference, Abstraction

• Variables (p. 38, p. 43, p.47)
• Global Variables (p. 143), Global Constants
• void-Function Syntax (p. 170)
• Precondition, Postcondition (p. 193): Abstraction