StudyHalo

Quiz
About

Contact Us

Thank you for contacting us
We'll get back to you as soon as possible

Name: Email: Message:

×

Add Concept

Search or create concept:

×

Add Post

Title:

Type:

URL:

Explanation:

File:

Supported file types: PDF, Images, Word documents, etc. Maximum size: 10 MB

Concept:

COS1512
Introduction to Programming II

Running Times and Big-O Notation

← Generic Algorithms Container Access Running Times →

Table of Contents

1. Introduction to Computers and C++ Programming

1.1. Computer Systems
1.1.1. Hardware
1.1.2. Software
1.1.3. High-Level Languages
1.1.4. Compilers
1.1.5. History Note
1.2. Programming and Problem-Solving
1.2.1. Algorithms
1.2.2. Program Design
1.2.3. Object-Oriented Programming
1.2.4. The Software Life Cycle
1.3. Introduction to C++
1.3.1. Origins of the C++ Language
1.3.2. A Sample C++ Program
1.3.3. Layout of a Simple C++ Program
1.3.4. Compiling and Running a C++ Program
1.4. Testing and Debugging
1.4.1. Kinds of Program Errors

2.1. Variables and Assignments
2.1.1. Variables
2.1.2. Names: Identifiers
2.1.3. Variable Declarations
2.1.4. Assignment Statements
2.2. Input and Output
2.2.1. Output Using cout
2.2.2. Include Directives and Namespaces
2.2.3. Escape Sequences
2.2.4. Input Using cin
2.2.5. Designing Input and Output
2.3. Data Types and Expressions
2.3.1. The Types int and double
2.3.2. Other Number Types
2.3.3. C++11 Types
2.3.4. The Type char
2.3.5. The Type bool
2.3.6. Introduction to the Class string
2.3.7. Type Compatibilities
2.3.8. Arithmetic Operators and Expressions
2.4. Simple Flow of Control
2.4.1. A Simple Branching Mechanism
2.4.2. Compound Statements
2.4.3. Simple Loop Mechanisms
2.4.4. Increment and Decrement Operators
2.5. Program Style
2.5.1. Indenting
2.5.2. Comments
2.5.3. Naming Constants

3. More Flow of Control

3.1. Using Boolean Expressions
3.1.1. Evaluating Boolean Expressions
3.1.2. Enumeration Types
3.2. Multiway Branches
3.2.1. Nested Statements
3.2.2. Multiway if-else Statements
3.2.3. The switch Statement
3.2.4. Using switch Statements for Menus
3.2.5. Blocks
3.3. More About C++ Loop Statements
3.3.1. The while Statements Reviewed
3.3.2. Increment and Decrement Operators Revisited
3.3.3. The for Statement
3.3.4. The break Statement
3.4. Designing Loops
3.4.1. Loops for Sums and Products
3.4.2. Ending a Loop
3.4.3. Nested Loops
3.4.4. Debugging Loops

4. Procedural Abstraction and Functions That Return a Value

4.1. Top-Down Design
4.2. Predefined Functions
4.2.1. Using Predefined Functions
4.2.2. Random Number Generation
4.2.3. Type Casting
4.3. Programmer-Defined Functions
4.3.1. Function Definitions
4.3.2. Functions That Return a Boolean Value
4.3.3. Function Definition–Syntax Summary
4.4. Procedural Abstraction
4.4.1. The Black-Box Analogy
4.5. Scope and Local Variables
4.5.1. The Small Program Analogy
4.5.2. Global Constants and Global Variables
4.5.3. Block Scope
4.5.4. Namespaces Revisited
4.6. Overloading Function Names
4.6.1. Introduction to Overloading
4.6.2. Automatic Type Conversion

5. Functions for All Subtasks

5.1. Void Functions
5.1.1. Definitions of void Functions
5.1.2. return Statements in void Functions
5.2. Call-by-Reference Parameters
5.2.1. A First View of Call-by-Reference
5.2.2. Call-by-Reference in Detail
5.2.3. Mixed Parameter Lists
5.3. Using Procedural Abstraction
5.3.1. Functions Calling Functions
5.3.2. Preconditions and Postconditions
5.4. Testing and Debugging Functions
5.4.1. Stubs and Drivers
5.5. General Debugging Techniques
5.5.1. Keep an Open Mind
5.5.2. Check Common Errors
5.5.3. Localize the Error
5.5.4. The assert Macro

6. I/O Streams as an Introduction to Objects and Classes

6.1. Streams and Basic File I/O
6.1.1. Why Use Files for I/O?
6.1.2. File I/O
6.1.3. Introduction to Classes and Objects
6.1.4. Techniques for File I/O
6.1.5. Appending to a File
6.1.6. File Names as Input
6.2. Tools for Stream I/O
6.2.1. Formatting Output with Stream Functions
6.2.2. Manipulators
6.2.3. Streams as Arguments to Functions
6.3. Character I/O
6.3.1. The Member Functions get and put
6.3.2. The putback Member Function
6.3.3. The eof Member Function
6.3.4. Predefined Character Functions

7.1. Introduction to Arrays
7.1.1. Declaring and Referencing Arrays
7.1.2. Arrays in Memory
7.1.3. Initializing Arrays
7.2. Arrays in Functions
7.2.1. Indexed Variables as Function Arguments
7.2.2. Entire Arrays as Function Arguments
7.2.3. The const Parameter Modifier
7.2.4. Functions That Return an Array
7.3. Programming with Arrays
7.3.1. Partially Filled Arrays
7.3.2. Programming Example: Searching an Array
7.3.3. Programming Example: Sorting an Array
7.4. Multidimensional Arrays
7.4.1. Multidimensional Array Basics
7.4.2. Multidimensional Array Parameters

8. Strings and Vectors

8.1. An Array Type for Strings
8.1.1. C-String Values and C-String Variables
8.1.2. Other Functions in <cstring>
8.1.3. C-String Input and Output
8.1.4. C-String-to-Number Conversions and Robust Input
8.2. The Standard String Class
8.2.1. Introduction to the Standard Class string
8.2.2. I/O with the Class string
8.2.3. String Processing with the Class string
8.2.4. Converting between string Objects and C Strings
8.2.5. Converting Between Strings and Numbers
8.3. Vectors
8.3.1. Vector Basics
8.3.2. Efficiency Issues

9. Pointers and Dynamic Arrays

9.1. Pointers
9.1.1. Pointer Variables
9.1.2. Basic Memory Management
9.1.3. Static Variables and Automatic Variables
9.2. Dynamic Arrays
9.2.1. Array Variables and Pointer Variables
9.2.2. Creating and Using Dynamic Arrays
9.2.3. Pointer Arithmetic
9.2.4. Multidimensional Dynamic Arrays

10. Defining Classes

10.1. Structures
10.1.1. Structures for Diverse Data
10.1.2. Structures as Function Arguments
10.1.3. Initializing Structures
10.2. Classes
10.2.1. Defining Classes and Member Functions
10.2.2. Public and Private Members
10.2.3. Constructors for Initialization
10.2.4. Member Initializers and Constructor Delegation in C++11
10.3. Abstract Data Types
10.3.1. Classes to Produce Abstract Data Types
10.4. Introduction to Inheritance
10.4.1. Derived Classes
10.4.2. Defining Derived Classes

11. Friends, Overloaded Operators, and Arrays in Classes

11.1. Friend Functions
11.1.1. Programming Example: An Equality Function
11.1.2. Friend Functions
11.1.3. The const Parameter Modifier
11.2. Overloading Operators
11.2.1. Overloading Operators
11.2.2. Constructors for Automatic Type Conversion
11.2.3. Overloading Unary Operators
11.2.4. Overloading >> and <<
11.3. Arrays and Classes
11.3.1. Arrays of Classes
11.3.2. Arrays as Class Members
11.4. Classes and Dynamic Arrays
11.4.1. Programming Example: A String Variable Class
11.4.2. Destructors
11.4.3. Copy Constructors
11.4.4. Overloading the Assignment Operator

12. Separate Compilation and Namespaces

12.1. Separate Compilation
12.1.1. ADTs Reviewed
12.1.2. Using #ifndef
12.2. Namespaces
12.2.1. Namespaces and using Directives
12.2.2. Creating a Namespace
12.2.3. Qualifying Names
12.2.4. Unnamed Namespaces

13. Pointers and Linked Lists

13.1. Nodes and Linked Lists
13.1.1. Nodes
13.1.2. nullptr
13.1.3. Linked Lists
13.1.4. Variations on Linked Lists
13.1.5. Linked Lists of Classes
13.2. Stacks and Queues
13.2.1. Stacks
13.2.2. Programming Examples: A Stack Class
13.2.3. Queues
13.2.4. Programming Examples: A Queue Class

14.1. Recursive Functions for Tasks
14.1.1. A Closer Look at Recursion
14.1.2. Stacks for Recursion
14.1.3. Recursion Versus Iteration
14.2. Recursive Functions for Values
14.2.1. General Form for a Recursive Function That Returns a Value
14.3. Thinking Recursively
14.3.1. Recursive Design Techniques
14.3.2. Case Study: Binary Search

15. Inheritance

15.1. Inheritance Basics
15.1.1. Derived Classes
15.1.2. Constructors in Derived Classes
15.1.3. The protected Qualifier
15.1.4. Redefinition of Member Functions
15.2. Inheritance Details
15.2.1. Functions That Are Not Inherited
15.2.2. Assignment Operators and Copy Constructors in Derived Classes
15.2.3. Destructors in Derived Classes
15.3. Polymorphism
15.3.1. Late Binding
15.3.2. Virtual Functions in C++
15.3.3. Virtual Functions and Extended Type Compatibility

16. Exception Handling

16.1. Exception-Handling Basics
16.1.1. A Toy Example of Exception Handling
16.1.2. Defining Your Own Exception Classes
16.1.3. Multiple Throws and Catches
16.1.4. Throwing an Exception in a Function
16.1.5. Exception Specification
16.2. Programming Techniques for Exception Handling
16.2.1. When to Throw an Exception
16.2.2. Exception Class Hierarchies
16.2.3. Testing for Available Memory
16.2.4. Rethrowing an Exception

17.1. Templates for Algorithm Abstraction
17.1.1. Templates for Functions
17.2. Templates for Data Abstraction
17.2.1. Syntax for Class Templates
17.2.2. Programming Example: An Array Class

18. Standard Template Library and C++11

18.1. Iterators
18.1.1. using Declarations
18.1.2. Iterator Basics
18.1.3. Kinds of Iterators
18.1.4. Constant and Mutable Iterators
18.1.5. Reverse Iterators
18.1.6. Other Kinds of Iterators
18.2. Containers
18.2.1. Sequential Containers
18.2.2. Container Adapters stack and queue
18.2.3. Associative Containers set and map
18.2.4. Efficiency
18.3. Generic Algorithms
18.3.1. Running Times and Big-O Notation
18.3.2. Container Access Running Times
18.3.3. Nonmodifying Sequence Algorithms
18.3.4. Container Modifying Algorithms
18.3.5. Set Algorithms
18.3.6. Sorting Algorithms
18.4. C++ Is Evolving
18.4.1. std::array
18.4.2. Regular Expressions
18.4.3. Threads
18.4.4. Smart Pointers

A. C++ Keywords

B. Precedence of Operators

C. The ASCII Character Set

D. Some Library Functions

E. Inline Functions

F. Overloading the Array Index Square Brackets

G. The this Pointer

H. Overloading Operators as Member Operators