MCS2514: Computer Science 2

Lecture Notes

• Chap1

  • PreCondition and PostCondition (MS PowerPoint Slides, 294KB)

  • Assert: assert.cpp

  • Running Time Analysis (Big-O Notation) - How many "Wow"s?: 1 , 2 , 3 , 4

  • Testing and Debugging: Test boundary values! To ensure that your test cases are fully exercising the code.

• Chap2: ADT / Classes and Objects

  1. Basics: point1.cpp | Expected Output

  2. Friend Function and Default Arguments: point2.cpp

  3. Operator Overloading: point3.cpp | Expected Output

  4. Overloading Output and Input Operators: point4.cpp

  5. Application: How many rotations? (Page 65) point5.cpp

  6. Automatic assignment op. and Copy Constructor: point6.cpp

• Chap3: Container Classes

  1. More C++ Features

     • sizeof() and size_t data type: sizeof.cpp

     • enumeration type: enumtst.cpp

     • static member constants: staticconst.cpp

     • typedef: typedef1.cpp

     • File stream I/O and Output Formatting format.cpp

  2. bag1 + bag2, bag += bag: bagtst1.cpp

  3. List: list.cpp

• Chap4: Pointers and Dynamic Arrays

  1. Review Pointers: pointer1.cpp

  2. Value Parameters that are pointers, Array Parameters, and Reference Parameters that are pointers: pointer2.cpp

  3. Memory Leak, Dangling Pointers: pointer3.cpp
  4. Exception Handling: excepthand.cpp
  5. Difference Between References and Pointers: pointer4.cpp
  6. Pass by value, reference, and pointer: swaps.cpp

  7. The bag ADT with a dynamic array: dynmbag.cpp

  8. Returning by Reference: retbyref.cpp

  9. Overloading subscript [] operator: safearray.cpp

• Chap5: Linked List

  1. Fundamentals of Linked List using "struct": linklist0.cpp

  2. Class node, everything for OO Linked Lists: node1.h
  3. Everything for Linked List using struct, non-OO: linklist.h

  4. Bag class using linked list: bag3main.cpp | node1.h

  5. Doubly linked list using "struct": doublelink.cpp

• Chap6: Software Reuse with Templates

  1. Function Tempaltes

  2. Class Templates I

  3. Class Templates II, member functions are outside of class def.

  4. Bag 4 using templates: bag4.h , bag4.cpp

  5. Template Version of Linked List Toolkit: link2.h

• Chap7: Stacks

  1. LIFO, Stack underflow, overflow

  2. Stack application: Evaluating Arithmetic Expressions - link2.h, stack2.h, calc2.cpp

• Chap14: Software Reuse with Derived Classes

  1. Intro to Inheritance, Class Hierarchy

  2. Derived class: A simple sample program .

  3. Overring Member functions

  4. Derived Class Constructor

  5. Private and Public Inheritance - see page 649

     • With a public base class, all the public members of the base class are inherited as public members of the derived class.

     • With a private base class, all the public members of the base class are inherited as private members of the derived class.

  6. Multiple Inheritance - Not covered

  7. Virtual functions - Not covered in CS2

  8. istream and ifstream: inherit0.cpp and inherit1.cpp .

• C++ topics

  1. Managing a file with Objects, seekg: rwobj.cpp

• Chap8: Queues

  1. FIFO, Queue underflow, overflow

  2. Queue application: Recognizing Palindromes - queue1.h(using a circular array), stack1.h, pal.cpp

  3. Queue application: Recognizing Palindromes (using linked lists) - queue2.h, stack2.h, link2.h pal2.cpp

  4. Priority Queues (p410): (1) Using a tree data structure (2) Linked List (3) ...

• Chap9: Recursive Thinking

  1. A first example of recursive thinking: write_vertical; an iterative solution , recursive solutions

  2. Tower of Hanoi Problem: hanoi.cpp

  3. Maze Problem: maze.cpp

  4. One level recursion, p442

  5. Becareful: Infinite recursion, inf_recur.cpp

  6. What's wrong?: powx.cpp

• Chap10: Trees

  1. Constructing Binary trees; Tree Traversals (pre-order, in-order, and post-order) bintree2.h, testtrav.cpp, output

  2. Binary Search Trees: Insert, Search, and Remove - bst.cpp

• Chap12: Searching
  1. Serial (Sequential) Search
  2. Binary Search: search.cpp
  3. Binary Search Tree Search
• Chap13: Sorting
  1. Selection
  2. Insertion
  3. Bubble
  4. Merge
  5. Quick
  6. Binary Search Tree Sort
  7. Many more: such as Shell, Heap, Radix, ...

Copyright (C) 2000- by Chung