This page describes approximately what topics will be covered in lectures (topics, and timings may vary somewhat from section to section). The schedule will likely slip and topics modified somewhat as the course progresses.

Please remember to reload this page occasionally since it will be updated frequently.

Besides the textbook you should acquaint yourself with the contents of the files in the following directories and their subdirectories on ariel.

• ariel:/cs/course/1030/notes -- contains files and subdirectories with notes on different topics in the course.
• ariel:/cs/course/1030/text-code -- all of the programs in the course text book are available
• ariel:/cs/course/1030/text-code-modified -- variations on the textbook of stacks, queues, trees and address book
• ariel:/cs/course/1030/examples -- contains interesting examples as to "why a math book is not enough" when programming mathematics.

Contents

• Week 1 Jan 6 - 10
• Week 2 Jan 13 - 17
• Week 3 Jan 20 - 24
• Week 4 Jan 27 - Jan 31
• Week 5 Feb 3 - 7
• Week 6 Feb 10 - 14
• Week 7 Feb 17 - 21
• Reading Week Feb 24 - Feb 28
• Week 8 Mar 3 - 7
• Week 9 Mar 10 - 14
• Week 10 Mar 17 - 21
• Week 11 Mar 24 - 28
• Week 12 Mar 31 - Apr 4
• Week 13 Apr 7 - last day of classes

• Introduction to the Course
• Introduction to Software Engineering
• Software Life Cycle
  • Marketing => Requirements
  • Analysis => Specification
  • Design => Architecture / Pseudo code (Top down design / successive refinement)
  • Implementation => Software (program)
  • Testing => Product
  • Release => Maintenance
  (Repeating Analysis thru Testing as necessary)
• Introduction to Validation and Verification
  • Assertions
  • Pre and post conditions
  • Loop invariants
• Testing
  • Black box
  • White box (path and branch)
  • Bottom Up
  • Top Down
• Assignment 1
  Testing -- writing stubs and drivers; use of assertions for minimal input/output test drivers; use of debug statments and debug flags.
• Readings
  • Adress book module implementation with example minimal test driver and output.
  • ariel:/cs/course/1030/notes/onDesign/*.xfig files
  • ariel:/cs/course/1030/notes/onDesign/testingWhiteBox.text
  • ariel:/cs/course/1030/notes/abstractDataTypes/classes.ps -- Section 9
  • Dale & Lily text book on reserve in Steacie

• Formal Specifications (using pre and post conditions)
• Mathematical Induction
• Proving a Subprogram Correct
• Assertions
• Pre and post conditions
• Loop invariants
• Induction
• Running Time (Big O Notation)
• Readings
  • Chapter 3 of the text
  • ariel:/cs/course/1030/notes/onDesign/topDownDesign.xfig
  • ariel:/cs/course/1030/notes/onDesign/verificationQuestions.ps
  • ariel:/cs/course/1030/notes/onDesign/BigO.ps
  • ariel:/cs/course/1030/notes/onDesign/justifyTopDown* -- example of incremental top down development. The DIRECTORY.INDEX file describes how to view each type of file.

(Assignment 1 Due)

• Objects and Classes (Chapter 8.1 - 8.3)
• Abstract Data Types
• Readings
  • ariel:/cs/course/1030/notes/abstractDataTypes/*. The DIRECTORY.INDEX file describes the files.

• Pointers
• Introduce Linked Lists
• Give lots of examples of indirection and different linked structures

• Non-data structure examples: Towers of Hanoi, Fibonacci, Power (e.g., X^Y), Factorial - complexity.
• Merge Sort, Binary Search, Linked Lists
• Recursive versus Iterative Solutions
• How recursion uses memory. Use a simple example to illustrate e.g. factorial. (Probably need to describe a stack first.)
• Reinforce recursion by using recursive examples throughout the course.

• What are Stacks?
• Motivation for Stacks
• Array and Pointer Implementations
• Stress Information Hiding, Abstraction, Encapsulation
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified

(Midterm)

• Catching up
• Review
• Midterm Exam

• Skiing
• Fun
• Sun
• Oh yeah ... reading :-)

• Handing back and taking up the midterm exams.
• What are Queues?
• Motivation for Queues
• Sequences
• Array and Pointer Implementations
• Stress Information Hiding, Abstraction, Encapsulation
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified

• Queues
• Priority Queues (linked and array implemenations)
• Circular Lists
• Doubly Linked Lists
• Dictionary
• Introduction to Hashing
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified

(Assignment 3 Due)

• What is a tree?
• Definitions: root, parent, child, ancestor, descendant, height, level, etc.
• Binary Trees
• Binary Search Trees (BST's)
• Adding to and Deleting from BST's
• Using Trees to Implement Abstract Data Types
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified

• Implementation using Arrays and Pointers
• Tree Operations
• Tree Traversal
• Complexity
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified

• What is sorting / Sequences of Values
• Exchange Sorts - O(n**2)
  • Insertion Sort
  • Selection Sort
  • Bubble Sort (optional)
• Efficient sorts - O(n log n)
  • Heap Sort
  • Quicksort
  • Mergesort
  • Radix Sort (optional)
• STUDY THE CODE FOR THESE in the text and the files in ariel:/cs/course/1030/text-code and .../text-code-modified