1 The Fundamentals of Computer Science

1.1 Solving Problems with the Computer

Analyzing the Problem

Designing a Solution

Implementing the Design

Testing the Code

Maintaining the Product

Summary

1.2 Breadth: The Discipline of Computer Science

Design Paradigm

Abstraction Paradigm

Theory Paradigm

1.3 Model of a Computer System

i.Input and Output Devices

Secondary Storage

Central Processing Unit

Main Memory

1.4 Breadth: Invention of the First Computers

Atanasoff

Eckert and Mauchly

von Neumann

Honeywell's lawsuit against Sperry Rand

1.5 Steps to Execution

Editor

Preprocessor

Compiler

Linker

1.6 Breadth: The History of C

Dennis Ritchie

ANSI C

1.7 Implementation of the Design

A Program to Display a Message

Comments

Inclusion of stdio.h

main

printf

Semicolon

Style

1.8 Top-Down Design and Functions

Using Library Functions

Connecting Functions to Top-Down Design

Function Definition

Calling a Function

Function Prototype

ANSI C Libraries

1.9 Breadth: Subject Areas of Computer Science

nine subject areas

Social, Ethical, and Professional Issues

Programming and Debugging Hints

Debugging

Walkthrough Technique

Modular Programming

Key Terms

Summary

Review Questions

Laboratory

examine various components of a program

observe the error messages from various errors

practice with functions

2 Integer Variables, Expressions, and Functions

2.1 Integer Data

concept of an integer

Variables

Variable Declaration

Naming of Variables

2.2 Assignment Statement

Lvalues and Rvalues

Labeled Output

Not an Algebraic Formula

Declaration-Initialization

2.3 Integer Arithmetic

Four Binary Operators

Modulus Operator

Printing %

Unary Minus

Operator Precedence

2.4 Breadth: Storage of Integers in the Computer

Binary Representation of Integers

Counting

Decrementing by 1

Range of Unsigned Integers in a Computer

Conversion of a Decimal Integer to Binary

2.5 Breadth: Integer Arithmetic in the Computer

Signed-Magnitude Notation

Two's Complement Notation

Addition

Subtraction

Multiplication and Division by Two

2.6 Interactive Programs

Interactive Versus Batch Programs

Interactive Programs in C

2.7 Problem Solving with Integer Functions

Preconditions and Postconditions

Analysis ;and Design of a Function

Implementation of an Integer Function

Procedures

Arguments and Parameters

Default Type Declaration;s for Functions

2.8 Problem Solving Revisited

Steps for Solving a Problem with a Computer;

Analysis

2.9 Scope of Variables

Local Variables and Scope

Pass by Value

Local Variables with the Same Name

Global Variables

Programming and Debugging Hints

Clarity of Comments

Clarity of Code

Clarity of User Interface

Key Terms

Summary

Review Questions

Laboratory

improve understanding of the declaration of integers, the assignment statement, arithmetic operations, the scanf function, and user-defined integer functions

examine scanf and printf and to make some observations about integers

study operator precedence and the truncation effect of integer division

study the scope of variables and functions

3 Making Decisions

3.1 Relational and Logical Operators

if statement

Relational Operators: ==, >, <, !=, >=, <=

Logical Operators: &&, ||, !

Boolean Constants, Expressions, and Variables

Operator Precedence

3.2 Selection

Flow of Control - sequential, modular, and selection control structures

The if Statement

The if-else Statement

3.3 Nesting

if and if-else statements within others

nested if statements equivalent to AND and OR operations

3.4 Multiple-Way Selection

The switch Statement

example of displaying a positive integer less than 100 in words

Branching to the Same Point

3.5 Breadth: Logic

George Boole and Edmund Berkeley

Basic Components of Logic

Truth Tables

Algebra of Propositions

DeMorgan's Laws

3.6 Testing Schemes

Top-Down Testing - stub

Bottom-Up Testing

Combined Top-Down and Bottom-Up Testing

Programming and Debugging Hints

Decision Control Structures

Testing

Key Terms

Summary

Review Questions

Laboratory

study the if-else statement, nested if statement, stubs, validation of input data and top-down design

study the switch and break statements

4 Additional Numeric Types

4.1 Floating Point Numbers

Distinctions between Integers and Floating Point Numbers

Floating Point Arithmetic

Exponential Notation

Printing Numbers

Type double

4.2 Breadth: Storage of Floating Point Numbers

Conversion from Base 2 to Base 10

Conversion from Base 10 to Base 2

Multiplication and Division by 2

Storage of Floating Point Numbers

Truncation Error

4.3 Coercion

Implicit Coercion

Explicit Coercion

Strong and Weak Typing

4.4 Additional Integer Types

Different Sizes of Integers

Unsigned Integers

Mixed-Mode Arithmetic

4.5 ANSI C Header Files and #define

Numerical Constants

Defining Preprocessor Constants

Absolute Value Function

Square Root Function

Additional Math Library Functions

Programming and Debugging Hints

Interfaces between Functions

Global Variables

Preprocessor Constants

Reader's Understanding of the Interface

Key Terms

Summary

Review Questions

Laboratory

the importance of matching conversion specifications and types

study implementation-dependent information about types short, int, long, float, and double

use floating point variables and design and test solutions with different preconditions

5 Looping

5.1 Updating Assignment Operators

+=, -+, *=, /=, %=

Increment and Decrement Operators

operator precedence

Pre- and Post-Increment and Decrement

5.2 Looping with a Pre-Test

The while Loop

Infinite Loop

Nature of the Pre-Test

Manipulation of Loop Variable

5.3 Looping with a Post-Test

The do-while Loop

Applications - validating input, accumulating a sum, separating digits

5.4 Looping and Interactive Programming

The Sentinel Technique

Random Numbers in Interactive Programs

Seeding the Random Number Generator

Ranges of Random Numbers - playing a guessing game

5.5 Structured Programming

control structure - modular, sequential, selection, looping

"Go To Statement Considered Harmful" by Edsgar Dijkstra

5.6 Breadth: Computer Time

metric system

computer speed

cycle time, flops

5.7 Breadth: Truncation Error in Loops

absolute and relative errors

example with accumulation

Programming and Debugging Hints

Updating Assignment Operators

Assignment and Relational Equals Operators

Key Terms

Summary

Review Questions

Laboratory

guessing game - sequential and binary searches

use the increment operator, ++, to revise PlayGame to count number of guesses

use constants and random_range to specify a different range

use loops to allow the user to play the game more than once

observations about seeding the random number generator

6 Counter-Controlled Loops

6.1 The for Loop

general form

Loop Choice

Counting Down

Tables

6.2 Nesting of Loops

example of generating multiplication table

example of an interactive program to compute the average for each student in a class; validation of input

6.3 Breadth: A Technique of Numerical Computing

simulation

example of finding the area under a curve using a simulated dart board

6.4 Breadth: Intellectual Property

Copyright Law - intellectual property, user interface, look and feel, license, public domain software, shareware

Patents

The Company Perspective - trade secret, trademark

Programming and Debugging Hints

Debugging Techniques:

printing intermediate results

debugger - trace, watch, breakpoint

Key Terms

Summary

Review Questions

Laboratory

practice using the debugger

casting with float.

examine the division-by-zero error

consider the for loop and error correction

improve the information to the use

7 Characters

7.1 Character Input and Output

putchar

getchar

Buffers

Y/N Responses

7.2 The ASCII Encoding Scheme

Numeric Code

Integer Equivalent of Character Digit

Escape Sequences

7.3 Character Functions

Changing Case

Boolean Character Functions

7.4 Breadth: Octal and Hexadecimal Number Systems

Conversion to Decimal; Numbers

Conversion between Binary and Hexadecimal; Number Systems

Constants and Conversion Specifications in C

Applications

Conversion of Decimal Numbers to Hexadecimal

7.5 A Brief Introduction to Files

Opening a File

Closing a File

File I/O

Character I/O with Files

Programming and Debugging Hints

Defensive Programming: Detection and Recovery

Defensive Programming: Read Data as Strings

Defensive Programming: "Bullet-Proof" All Levels

Key Terms

Summary

Review Questions

Laboratory

make a program that helps children practice arithmetic problems more user-friendly by having character responses

examine the application of some control characters

consider prototypes and counting

8 Arrays

8.1 What is an Array?

Declaration

Assigning Values

Array Index

Declaration-Initialization

8.2 Functions with Array Parameters

Read, Average, and Print

Minimum and Maximum

Frequency

8.3 Sequential and Binary Searches

Sequential Search

Number of Elements to Search

Binary Search

Number of Elements to Search

8.4 Selection Sort

algorithm

Index of Minimum Element

Swapping Values

8.5 Multidimensional Arrays

Indices

Declaration

interactive program to print price of a particular make and year car

8.6 Breadth: Color in Computer Graphics

Display Devices

Color Lookup Table

Programming and Debugging Hints

Selecting Test Data: Edge Data

Data to Test Branches - exponential growth

Testing by Novices or with Random Data

Key Terms

Summary

Review Questions

Laboratory

print particular array elements, print the array, add array elements, insert an element into an array, delete an element from an array, and read values from a file into an array

9 Pointers

9.1 The Concept of Pointers

Declarations

Address Operator

Indirection Operator

NULL

Summary

Point before Dereferencing

9.2 Breadth: Memory

Types of Memory - main memory, secondary storage, cache memory

Memory Sizes

RAM and ROM

9.3 Passing Pointers as Parameters

passing by value and reference

swap

9.4 Arrays and Pointers

Array Name as a Constant Pointer

Parameters

Pointer Arithmetic

9.5 Dynamic Memory Allocation

Allocate Memory

Deallocate Memory

Allocate Initialized Memory

Reallocate Memory

9.6 Pointers to Functions

Declarations and Assignments

Calling Functions Indirectly

Function Pointers as Parameters

Programming and Debugging Hints

Pointer Post-Increment

Pointer Assignment

Allocation of Space

Key Terms

Summary

Review Questions

Laboratory

examine pointers and indirection by creating our own memory dump

practice working with pointers as parameters, pointers and arrays, pointer arithmetic, and pass by reference

10 Strings and String Functions

10.1 Character Strings

Literals

Displaying Strings

Reading Strings

Interactive Responses

10.2 String I/O Functions

Writing to Standard Output

Reading from Standard Input

Writing to a File

Reading from a File

Summary

10.3 Constant and Variable Strings

manipulation of char pointer to a literal constant or a char array

manipulation of char array holding a variable string

String Arguments

Constant Parameters

Two-Dimensional Array of Characters

One-Dimensional Array of Strings

10.4 Validation of Data

read as string, verify proper format and size, convert

10.5 Several String Functions

Storage Size

String Length

Copying Strings

Concatenation

10.6 String Comparisons

Search for a String

Search for a Character

String Comparison

10.7 Breadth: Software Life Cycle for Large Systems

software life cycle

Analysis

Design

Implementation and Testing

Maintenance

Programming and Debugging Hints

Verification with sscanf

Semicolon and Closing Brace

Comment Delimiters

Key Terms

Summary

Review Questions

Laboratory

develop a command-driven, line-oriented text editor with a team using string storage and functions

11 Structures and User-Defined Types

11.1 The Concept of a Structure

Declaration

Reference to Members

Declaration-Initialization

Element by Element

Naming Structures

Size of a Structure

Structure Members

11.2 User-Defined Types

typedef

Type Definitions in Header Files

Arrays of Structures

11.3 Breadth: Databases

Traditional File Processing

Database Management System

Relational Database

11.4 Pointers and Structures

Passing a Structure Reference

Dereferencing;

Linked Lists

11.5 Enumeration Types

Implementation

Boolean

Coercion

11.6 Union Types

union overlay

structure with a flag and a union

11.7 Breadth: A Computer Graphics Package

Device Driver

Device Coordinates

World and Device Coordinate Systems

Polylines

Programming and Debugging Hints

Internal Limitations

Structures with Array Elements

Key Terms

Summary

Review Questions

Laboratory

develop a program to maintain a stock portfolio with a team

12 Levels of Programming Abstraction

12.1 Macros

Continuation of Definitions

Parameters

Parentheses

Speed of Execution

Conditional Expression Operator

Incrementing and Decrementing

When to Use

12.2 Separate Compilation

Header Files - random number generator example

External Variable;s

static and auto Storage Classes

Command-Line Parameters

12.3 Conditional Compilation

#ifdef and #endif

Command Line Definitions

#ifndef

#else

#if

12.4 Breadth: Some Operating System Features

operating system (OS) features: time-sharing, memory allocation, automatic error recovery, managing I/O

UNIX - history, directory structure, some basic commands, grep, make

MS-DOS - directory structure, some basic commands, Turbo C's GREP.COM and make

MacOS - graphical user interface, file structure, Think C's Find with Grep option and project construction

12.5 Breadth: The Object-Oriented Paradigm

Abstract Data Type

An Abstract View of the Integer Type

Levels of Implementation

An Abstract View of Arrays

Object-Oriented Programming - encapsulation, inheritance, polymorphism

12.6 Breadth: C++: Object-Oriented Programming

Information Hiding

Input/Output

Constructors

Polymorphism and Inheritance

12.7 Breadth: Machine and Assembler Languages

Machine Architecture

Machine Instructions

Fetch/Execute Cycle

Branching

CPU Simulator Program cpusim

Programming and Debugging Hints

Debugging with Conditional Compilation

Levels of Debugging

Key Terms

Summary

Review Questions

Laboratory - CPU Simulator

become acquainted with the machine and assembler languages of Section 12.7 and the CPU simulator, cpusim.

illustrate looping in machine language

Alternative Laboratory - Stock Portfolio Program

practice in separate compilation, macros, and conditional compilation

13 Recursion

13.1 Recursive Functions

factorial function - stack of activation records

minimum of elements 0 through n in an array of integers

power function - comparison of efficiency of two algorithms

erase an object in an image

Towers of Hanoi

13.2 Recursion vs. Iteration

pros and cons of using recursion

Solving a Recursive Routine

Tail Recursion

13.3 Breadth: Formal Grammars

BNF

Parsing - grammar, boolean function to recognize strings in a language, parse tree

Programming and Debugging Hints

The lint Program

Some Errors C Compilers Do Not Flag: Number of Arguments

Types of Arguments

Key Terms

Summary

Review Questions

Laboratory

develop a nonrecursive function, sum, to find the sum of elements 0 through n of an array of integers

develop a recursive counterpart to sum

develop another recursive solution to the summation problem using the divide-and-conquer technique

perform an experiment to compare the efficiency of the three summation algorithms, encounter a stack-overflow situation, and consider the approach best suited to parallel processing

14 Input/Output and Files

14.1 Basic File Manipulation

Standard Files

Summary

14.2 Breadth: External Storage

Tape Storage

Disk Storage

CD-ROM

14.3 File Handling Modes

Append Mode

Combining Modes

14.4 Binary Files

Reading from a Binary File

Writing to a Binary File

14.5 Random Access Files

Seeking a File Position

Obtaining the Current Position

Programming and Debugging Hints

Run-Time Errors and Buffering

Key Terms

Summary

Review Questions

Laboratory

experience maintaining a program and working in teams

CPU Simulator Version: extend the CPU simulator from Chapter 12's Laboratory

Stock Portfolio Program Version: extend the stock portfolio program from Chapter 11's Laboratory

15 Binary Operations

15.1 Bitwise Operators

Bitwise AND and OR

Masks

Bitwise NOT Operator

EXCLUSIVE OR Operator

Shifting

Bit Fields

15.2 Breadth: Logic Gates

Boolean Algebra

Gates

Combinational Circuits

15.3 Breadth: Logic Circuits

Canonical Sum-of-Products - half-adder, circuit for odd parity

Programming and Debugging Hints

Mistaken Operator Symbols

Program Correctness

Key Terms

Summary

Review Questions

Laboratory

cover the documentation needed with system maintenance, as well as provide further team-work experience

16 Data Structures

16.1 Linked Lists

Initialize List

Make a Node

Insert at the First of a List

Insert Later in a List

Advance the Current Pointer

Delete the First Node

Delete a Later Node

16.2 Stack Abstraction

LIFO

stack ADT

RetrieveStack

AddTop

AddStack

PrintStackUp

16.3 Linked List Implementation of Stacks

Stack Creation

Initialize Stack

Never Fills

Push

Pop

Summary

16.4 Breadth: Run-Time Stack during Program Execution

operating system

stack of activation records

contents of activation record

Programming and Debugging Hints

Freeing Pointers

Destroying Linked Structures

Key Terms

Summary

Review Questions

Laboratory

develop and use a tool to practice with stacks

Appendices

A The ASCII Table

B Keywords in C

C Operator Precedence

D Conversion Specifications

E File I/O

Input Text File Manipulation

Output Text File Manipulation

Binary File Manipulation

Mode Strings

F Random Number Generators

G Contents of Text Disk

H Debuggers

I Glossary

J Answers to Selected Exercises