• This calendar and related items are at www.portmain.com/ds.
• Office hours are listed at www.cs.colorado.edu/~main/hours.html
• Please review the grading policies at the bottom of this page, including the recording of a zero score for missed exams or quizzes.
• Quiz Friday in class
• First homework is due next Monday at 11:30pm. Please follow the style requirements. Submit to culearn.colorado.edu.
• Be sure to register for your csel account and access at sac.colorado.edu.
• Note: Some weeks we will get ahead of schedule and start the next week's material.

This Week's Topics:

• In Recitation: GNU Emacs and G++

• Precondition/Postcondition Contracts
• Introduction to C++ Classes
• The Throttle Example

• Parameters

• Operator Overloading
• Programming Style Requirements

• Chapter 1 Practice
• Sections 2.1-2.4 Practice
• Quiz on Friday: Through Section 2.4

• Please read 1.1, 1.2, 2.1, 2.2, 2.3 and 2.4 before this Friday's quiz.
• Please read Section 2.5 before next week's first lecture.
• Please read the Programming Style Guide
• Start Homework 1: The Statistician Class

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

This Week's Topics:

• In Recitation: Using GDB

• Container Classes
• The Bag Class with a Fixed Array
• Typedef Statements
• The size_t Type
• Static Member Constants
• The Value Semantics of a Class
• Implementing Some of the Bag Member Functions
• Using a Class Invariant in Your Design
• Using Meaningful Assertions in Your Implementation
• The C++ Standard Library Copy Function
• An Object Can Be a Parameter to Its Own Member Function
• Time Analysis for the Bag with Fixed Array

• Test Programs

• The Matrix Class
• A Simple Polynomial Class

• Section 2.5 Practice
• Sections 3.1 and 3.3 Practice
• Quiz on Friday: Sections 2.5, 3.1 and 3.3

• Please read 3.1 and 3.3 before this Friday's quiz.
• Please read Section 4.1 before next week's first lecture.

• Homework 1: The Statistician Class
  due at 11:30pm on Monday, Aug 31
  (submit to CULearn). For the first two homeworks, you may submit work up to 24 hours late with no penalty, but no work will be accepted after that.
• Start Homework 2: Container Classes

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Pointers (http://wikidir.portmain.com/cgi-bin/view/Main/PointerExercise)

• Introduction to Pointers
• Pointers and Assignment Statements
• The New Operator
• Dynamic Arrays
• Running Out of Memory
• The Delete Operator
• Pointer Type Definitions

• Pointers as Parameters
• Arrays as Parameters

• Dynamic Arrays as Members of a Class
• Memory Management in a Class with Dynamic Arrays
• Documentation in a Class with Dynamic Memory
• Dynamic Value Semantics
• The Bag Class with a Dynamic Array

• Prescription for a Class with Dynamic Arrays

• Chapter 4 Practice
• Quiz on Friday: Sections 4.1 through 4.4

• Please read 4.1 through 4.4 before this Friday's quiz.
• Please read Section 4.5 and 4.6 before next week's first lecture.
• Homework 2: Container Classes
  due at 11:30pm on Monday, Sep 7
  (submit to CULearn). For the first two homeworks, you may submit work up to 24 hours late with no penalty, but no work will be accepted after that.
• Start Homework 3: Dynamic Arrays

• First Exam in Class on Friday, Sep 18. The exam will cover all assigned reading, lectures, homework, the debugger and makefiles.
• We will have exam review during recitation this week.
• Extra exam review Wednesday at 5:00pm to 6:00pm in the CSEL.

• In Recitation: Exam Review Chapters 1-4

• A Matrix Class that Uses a 2-Dimensional Dynamic Array
• Discussion of the String Class
• Strings that Share Dynamic Memory
• (if time permits) More Dynamic Arrays

• Exam on Friday

• No new reading this week
• Homework 3: Dynamic Arrays
  due at 11:30pm on Wednesday, Sep 16
  (submit to CULearn). Work is accepted with a 10% penalty up to 24 hours late.

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Linked List Practice (Part 1) (http://wikidir.portmain.com/cgi-bin/view/Main/LinkedListExercise)

• Introduction to Linked Lists
• A Simpler Linked List Node Using Struct
• The Member Selection Operator
• Const Member Functions for Nodes
• Why We Need Two Versions of a Function
• Never Dereference the Null Pointer
• The Length Function
• Pattern to Traverse a Linked List
• More Linked List Design Patterns
• Inserting a Node
• The Proper Use of New and Delete
• Searching a Linked List
• Discussion of a Node for Your New String Class

• Sections 5.1/5.2 Practice
• Quiz on Friday: Pages 211 to 238

• Please read Pages 211 to 238 before this week's quiz.
• No homework due this week
• Start Homework 4: Linked String Class

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Linked List Practice (Part 2) (http://wikidir.portmain.com/cgi-bin/view/Main/LinkedListExercise)
• Copying a Linked List
• Removing Nodes from a Linked List
• Clearing a Linked List
• Discussion of a Functions for Your String Class Node

• Section 5.2 Practice
• Quiz on Friday: Section 5.2

• Please read the rest of Section 5.2 before Friday's quiz.
• Homework 4: Linked String Class
  due at 11:30pm on Wednesday, Sep 30
  (submit to CULearn). Work is accepted with a 10% penalty up to 24 hours late.
• Start Homework 5: Extensions

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Make Utility and (if you have extra time) you may do Part 3 of the Linked List Practice

• More linked list examples
• The Bag Class with a Linked List
• Volatile Member Variables
• Doubly-Linked Lists

• Section 5.3 and 5.5 Practice
• Quiz on Friday: More linked lists

• Please read Sections 5.3 and 5.5 before Friday's quiz.
• You may skip Section 5.4
• Homework: Extensions
  due at 11:30pm on Wednesday, Oct 7
  (submit to CULearn). Work is accepted with a 10% penalty up to 24 hours late.
• Start Homework 6: TBA

• Second Exam in Class on Friday, Oct 16. The exam will cover Chapter 5 plus Sections 6.1 and 6.3
• We will have exam review during recitation this week.
• Extra exam review Wednesday at 5:00pm to 6:00pm in the CSEL.
• We didn't cover all this material in class, so we'll hit it next week. I did do some more examples on Wednesday, and they are posted online.

• In Recitation: Templates (http://wikidir.portmain.com/cgi-bin/view/Main/TemplateExercise)
  and Exam Review Mostly Chapter 5

• Template Functions
• Standard Template Classess
• The Multiset Class
• Iterators and the [...) Pattern
• Do Not Dereference the End Iterator
• Invalid Iterators
• Standard Categories of Iterators
• Iterators for Arrays
• STL Iterator Algorithms
• Building Your Own Template Classes

• Exam on Friday

• Please read Sections 6.1 and 6.3 before the exam.
• You may skip the rest of Chapter 6.
• Homework 6: Practice Exam
  due at Noon (in class) on Wednesday, Oct 14. You may work with other students however you like. Just learn the material! No late work accepted without prior arrangement.

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Quantum Telepathy Homework Discussion

• Introduction to Queues
• The STL Queue

• Evaluating Arithmetic Expressions
• Array Implementation of a Stack
• Linked List Implementation of a Stack
• Converting Infix to Postfix
• Building a Postfix Calculator
• Backtrack algorithm with a stack

• Array Implementation of a Queue
• Linked List Implementation of a Queue

• Chapter 7 Practice
• Section 8.1 and 8.3 Practice
• Quiz on Friday: Chapter 7 and Sections 8.1 and 8.3

• Please read Chapter 7 plus Sections 8.1 and 8.3 before Friday's quiz.
• Start Homework 7: Verification of a Quantum Computer Program

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Recursion Practice

• First Recursion Example: Digits
• Tracing Recursive Calls
• Pattern for Recursive Thinking
• Fractal Example
• 3D Fractal Example
• Backtrack Searching
• Recursive Functions with Return Values

• Sections 9.1 and 9.2 Practice
• Quiz on Friday: Sections 9.1 and 9.2

• Please read Sections 9.1 and 9.2 before Friday's quiz.
• You may skip Section 9.3
• Homework: Verification of a Quantum Computer Program
  due at 11:30pm on Wednesday, Oct 28
  (submit to CULearn). Note: If you have not finished by Wednesay, you may submit late work before 11:30pm on Thursday for 10% penalty. No work will be accepted after that.
• Start Homework: Fun with Recursion

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Binary Tree Practice

• Binary Trees
• Taxonomy Tree Example
• Complete Binary Trees
• Binary Tree Node Class
• Tree Traversals
• Functions as Parameters
• The Apply Function
• General Tree Traversal Functions

• Sections 10.1 to 10.5 Practice
• Quiz on Friday: Sections 10.1 to 10.4

• Please read Sections 10.1 to 10.4 before Friday's quiz.
• Homework: Fun with Recursion
  due at 11:30pm on Wednesday, Nov 4
  (submit to CULearn). Work is accepted with a 10% penalty up to 24 hours late.
• Start Homework: Trees

• Third Exam in Class on Friday, Nov 13. The exam will cover Chapters 7 through 10.
• We will have exam review during recitation this week.
• Extra exam review Wednesday at 5:00pm to 6:00pm in the CSEL.

• In Recitation: Exam Review Chapters 6-10

• Biunary Search Trees
• The Bag with BST
• BST Search
• BST Insertion
• BST Removal
• BST Union

• Exam on Friday

• Please read Section 10.5 before Friday's exam.
• Homework: Continue working on Trees
  due at 11:30pm on Monday, Nov 16
  (submit to CULearn).

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Get Started on B-Tree Homework

• Heaps
• Unbalanced Search Trees
• B-Trees
• Set with a B-Tree
• B-Tree Search
• B-Tree Insertion
• Top-Down Design and Testing

• Sections 11.1 and 11.2 Practice
• Quiz on Friday: Pages 534-556

• Please read Pages 534-556 before Friday's quiz.
• Homework: Complete Trees
  due at 11:30pm on Monday, Nov 16
  (submit to CULearn). Work is accepted with a 10% penalty up to 24 hours late.
• Start Homework: Balanced Tree (Part A, Homework 10) Read Robert's B-Tree Blog.

• Quiz Friday in class
• Review and homework session Friday at 5:00pm to 6:00pm in the CSEL

• In Recitation: Sorting Exercise (http://wikidir.portmain.com/cgi-bin/view/Main/SortingAlgorithms1)

• B-Tree Removal

• Selection Sort
• Insertion Sort
• Merge Sort
• Quick Sort
• Heap Sort
• Radix Sort
• Shuffle Sort

• Section 11.2 Practice
• Chapter 13 Practice
• Quiz on Friday: The rest of Section 11.2 and all of Chapter 13

• Please read the rest of Section 11.2 and Chapter 13 before Friday's quiz.
• Homework: Balanced Trees (Part A, Homework 10)
  due at 11:30pm on Thursday, Dec 3
  (submit to CULearn). Late work is accepted up to 96 hours late with a penalty of 10%
• Start Homework: Balanced Trees (Part B)

• Extra Final Exam Review Friday, Dec 11, 5:00pm - 6:00pm in the CSEL.
• Final Exam will be Wednesday, Dec 16, at 4:30pm-7:00pm in the usual lecture room

• In Recitation: Timing Exercise (http://wikidir.portmain.com/cgi-bin/view/Main/SortingAlgorithms2)

• Serial Search
• Binary Search
• Open-Address Hash Tables
• Chained Hash Tables

• Chapter 12 Practice

• Please read Chapter 12 before the final exam.
• Homework: B-Tree (Part B)
  due at 11:30pm on Friday, Dec 11
  (submit to CULearn). No late work is accepted.

• The final exam will have two parts. Part 1 (250 points) will cover Sections 11.1, 11.2 plus all of Chapters 12 and 13. Part 2 (100 points) will be a comprehensive exam covering the entire semester.
• The exam will be in our usual lecture room from 4:30pm to 7:00pm on Wednesday, Dec 16.