Data Structures (CS2) - Wheaton College, Norton, MA
[Back to cs2 Syllabus Home]


Data Structures
Wheaton College, Norton, MA
Jan | Feb | Mar | Apr | May

1M -- Mon, Jan 28

  • q0 -- covers everything in CS1 (just kiddin' ...); but usually we'll quiz each week
  • Welcome Back
  • Intro to Data Structures - where are we headed?
  • Abstraction
    • top-down design
    • variables names
    • functional abstraction
    • data abstraction
  • Abstract Data Types (ADT's)

  • READING
    • Headington, p.1-30
    • browse the ACM web page -- (Association for Computing Machinery)

    • Self-test -- can you do these? (see answers in the back of your text):
      1.4ac, 1.5acf, 1.6acf, 1.7

1T -- Tue, January 30

  • LAB 0: Yes, we will have lab this first week - A102, 3:30-5:30
    • review of using a deBUGGER
    • Intro to Expert Systems: TicTacToe (due next Mon, Feb. 4)

1W -- Wed, January 30

  • Assertions
  • Loop Invariants

  • Reading: Headington p31-37
  • Homework due in class on Friday, Feb 01, p. 47:
    • #1.1 b, d, f
    • #1.2 b, d, e
    • #1.3 b, d, e
1F -- Fri, Feb. 01
  • LECTURE
    • INVariants revisited
    • Function documentation: Pre- and Post-conditions

    • Discussion of Program #1: Rock, Paper, Scissors
  • READING
    • (catch up!)
  • DUE
    • today: Homework due in class
    • Monday: TicTacToe lab0 due
    • next Wednesday: Quiz1 -- covers Ch 1 (p1-18, 31-37; exercises 1.1, 1.2, 1.3, and 1.8, 1.9)
    • Fri, Feb 8: Program1

2M -- Mon, Feb 4

  • LECTURE
    • Comments on homework #1
    • FAQ on Rock,Paper,Scissors (program #1)

    • mathematically proving the correctness of loops

  • READING
    • Headington, p.18-30 (prepare for Lab tomorrow)
  • DUE
    • today: TicTacToe lab0 due
    • Wednesday: Quiz1 -- covers Ch 1 (p1-18, 31-37; exercises 1.1, 1.2, 1.3, and 1.8, 1.9)

    • Fri, Feb 8: Program1 - Rock, Paper, Scissors
    • Submit your folder by Sat, Feb. 9 by 5am with
      • a README file that explains the status of your program, e.g., "it compiles but it does not play the game correctly", or "it plays the game but it does not use the history from previous games" or "the game is fully functional."
      • all your .cpp and .h files
      • do NOT submit all your CodeWarrior (or other) project files, etc

      • submit your code to my dropbin (see spec for full pathname)
      • your folder should be called: "yourlastnameRPS", e.g., LeBlancRPS

2T -- Tue, Feb 5

  • Lab1 -- Runtime asserts(), Invariants && Pre- and Post-conditions;
    Brutus needs a Roman Numeral Calculator! (see Headington, p.18-30)

2W -- Wed, Feb 6

  • LECTURE
    • Quiz1 - covers Ch 1 (p1-18, 31-37; exercises 1.1, 1.2, 1.3, and 1.8, 1.9)

    • Specification (.h) vs. Implementation (.cpp)
  • DUE
    • a1 - Rock-Paper-Scissors program due on Friday
    • Monday: Lab1 - Roman Numeral Calculator
  • READING
    • Headington: p57-73, 87-98
    • Self Test -- try exercises starting on p. 99 (see answers in the back of your text):
      2.1ab, 2.8ace, 2.9ae, 2.10a
2F -- Fri, Feb 8
  • LECTURE
    • Introduction to Abstract Data Types (ADT)'s
  • DUE
    • a1 - Rock-Paper-Scissors program due today

    • By MON: Lab1 - Roman Numeral Calculator
    • MON: Quiz2 - more INVariants, ASSERTs and PRE/POST conditions
  • Reading
    • Headington: p. 110-113
3M -- Mon, Feb 11
  • LECTURE
    • Quiz2 - more INVariants, ASSERTs and PRE/POST conditions

    • More Abstract Data Types (ADT)'s
    • Introduction to Class(es)
    • Give me a class, any class, how about: the randGen class
  • Reading -- Headington: p. 114-126 and 127-130 (needed for lab tomorrow)

  • DUE
    • today: Lab1 - Roman Numeral Calculator

3T-- Tue, Feb 12

  • Lab2 -- randGen class
  • Make sure you read p.127-130 before lab

3W -- Wed, Feb 13

  • LECTURE
    • Do you REALLY understand the C++ Class mechanism? Spend some time in the text ... (see Monday's and today's reading)
  • DUE
    • Fri: (stapled) source code and labeled Excel spreadsheet
  • READING
    • Headington: RE-READ p110-130;
    • can you do exercises at the end of Ch. 3, p.157 #3.2, 3.3, 3.6 ??
3F -- Fri, Feb 15
  • LECTURE
    • A review of setting up "experiments" for random number generators
  • DUE
    • today: Lab2 (RandGen) -- (stapled) source code and labeled Excel spreadsheet

    • Monday: Quiz3 - covers the RandGen class and
      exercises 2.1ab, 2.8ace, 2.9ae, 2.10a, 3.2, 3.3, 3.6
  • READING
    • Catch up!

4M -- Mon, Feb 18

  • LECTURE
    • Quiz3 - covers the RandGen class and
      exercises 2.1ab, 2.8ace, 2.9ae, 2.10a, 3.2, 3.3, 3.6

    • Introduction to STACKS
    • class CharStack - "looking under the hood"
  • READING
    • Headington: p166-174, 177-181; try #4.3 on p191

4T -- Tue, Feb 19

  • Lab3 -- Stacks
    • Part I: "patching" cStack.cpp -- the implementer's perspective
    • Part II: starting a2 -- Writing a Compiler v0.005

    4W -- Wed, Feb 20

    • LECTURE
      • more Stacks ...
      • discuss a2 specification

    • DUE
      • a2 Writing a Compiler v0.005, due Tuesday, Feb. 26
    4F -- Fri, Feb 22
    • LECTURE
      • Introduction to Queues
    • READING
      • Headington: p181-185, try exercises #4.4, #4.6 on p192
    • DUE
      • a2 Writing a Compiler v0.005, due Tuesday, Feb. 26
    5M -- Mon, Feb 25
    • LECTURE
      • Quiz4 -- Stacks and Queues (see assigned reading and suggested exercises above) + (there will be one more question on PRE/POST using arrays passed to a function)

      • more Queues (the client view)

    • DUE
      • a2 Writing a Compiler v0.005, due tomorrow, Tuesday, Feb. 26;
      • a stapled hardcopy (printed in landscape) of all your .cpp and .h files also due (NOTE: you do not need to print out CharStack.cpp and CharStack.h)
      • your folder should contain a README
      • your folder should contain a file that summarizes your test suite

    5T-- Tue, Feb 26

  • a2 is due today

  • LAB
    • Lab4 -- Queue simulations
    • "under the hood" of CharQueue

    5W -- Wed, Feb 27

    • LECTURE
      • Queues revisited (or getting in line for queues again)
      • discuss a3 specification: simulation of a time sharing queue

    • DUE
      • Lab4 due Friday, March 01 -- a hardcopy of the print() method that you added to the class CharQueue
      • a3Time sharing QUEUE, due before you leave for break, Friday, March 8

    Feb | Mar | Apr | May

    5F -- Fri, March 01

    • LECTURE

    • DUE
      • Lab4 due today -- a hardcopy of the print() method that you added to the class CharQueue

      • a3 Time sharing QUEUE, due before you leave for break, Friday, March 8

    6M -- Mon, March 4

    • LECTURE
      • (next quiz is after Spring Break)

      • FAQ on the Queue SIMulation (program a3); discussing the steps of developing the software

      • Introduction to Recursion
    • READING
      • Recursive Functions
      • p237-241, 244-252, 260-274
      • try exercises: 6.5b, 6.9, 6.10, 6.11 on p276

    • DUE
      • a3 Time sharing QUEUE, due before you leave for break, Friday, March 8

    6T -- Tue, March 5

  • Lab5 -- Recursion, Recursio, Recursi, Recurs, Recur, Recu, Rec, Re, R, nil

    6W -- Wed, March 6

    • LECTURE
      • iteration(loops) vs. recursion
      • Recursive Definitions: Fibonacci numbers
      • Recursion Definitions: BNF syntax notation

    • DUE
      • a3 Time sharing QUEUE, due before you leave for break, Friday, March 8

    6F -- Fri, March 8

    • LECTURE
      • more recursion, again
      • Recursion Definitions -- BNF syntax notation
      • Reading: p241-243, also see Appendix K
      • try exercises: 6.3 on p275
      • recursive-heavy languages -- a peak at LISP and PROLOG
    • READING
      • Recursive Functions
      • p237-241, 244-252, 260-274
      • try exercises: 6.5b, 6.9, 6.10, 6.11 on p276

    • DUE
      • a3 Time sharing QUEUE, due today

    March 11-15
    • SPRING BREAK....
    7M -- Mon, March 18
    • LECTURE
      • pass out Quiz #5 -- Recursion (take home)

      • Introduction to Pointers
    • READING
      • p287-293; try #7.1 and #7.2 on p335
    • DUE
      • Friday, March 22: Quiz #5 -- Recursion (take home)

    7T -- Tue, March 19

  • LAB6
    • Pointers pointers, everwhere ->

    7W -- Wed, March 20

    • LECTURE
      • Pointer arithmetic
      • Arrays as pointers
    • READING
      • p293-298; try #7.6 on p337
    • DUE
      • Friday, March 22 in class: Quiz #5 -- Recursion (take home)
    7F -- Fri, March 22
    • LECTURE
      • Pass-by-reference vs. pointers
    • READING
      • p. 301-303
    • DUE
      • today: Quiz #5 -- Recursion (take home)
    HERE

    8M -- Mon, March 25

    • LECTURE
      • ahhh, that good ole' heap and dynamic memory: new() and delete()

    • READING
      • p.312-316 (five serious pages of reading!)
      • try #7.3, 7.4, 7.5, on p336

    8T -- Tue, March 26

  • LAB
    • Lab7: Experiments in Dynamic Memory Allocation
    • due in class this Friday, March 29

    8W -- Wed, March 27

    • LECTURE
      • Review of Lab7: Experiments in Dynamic Memory Allocation
    • DUE
      • Friday, March 29: Lab7

    8F -- Fri, March 29

    • LECTURE
      • Dangling Pointers, Memory Leaks, Segmentation Faults and other HEAPs of fun ...
    • DUE
      • TODAY, in class: Lab7

    Feb | Mar | Apr | May

    9M -- Mon, April 1 (no fooling)

    • LECTURE
      • pick up Quiz #6 takehome (due in class on Wed., April 03)

      • class vector -- under the hood with gloves off this time
      • CTOR's, DTOR's and copy constructors
    • READING
      • (see previous readings on pointers as you work on Quiz6)

      • CTOR and DTOR, Class Vector: p320-334
      • You really must read through these pages before lab tomorrow!
    • DUE
      • Quiz #6 -- Pointers (take home): due on Wed, April 3 in class

  • LAB
    • Lab8 -- Design of a C++ class for mathematical Vectors
    9W -- Wed, April 3
    • LECTURE
      • more Vector class ...
      • overloading operators
    • READING
      • p144-147 (operator overload review), p305-311 (IO friends), p320-334 (class IntVec)
    • DUE
      • TODAY in class: Quiz #6 -- Pointers

      • Saturday, April 13, 5am -- a4: Vector class

    9F -- Fri, April 5

    • LECTURE
      • oh the scary things that happen when you leave out operator=(), et al.
    • READING
      • (see previous readings on IntVec as you work on a4)
    • DUE
      • next Saturday, April 13, 5am -- a4: Vector class

    10M -- Mon, April 8

    • LECTURE
      • ADVISING WEEK

      • FAQ on cross-product and dot-product (a4 specification)
      • 3-D vector transformations in computer graphics
    • DUE
      • Saturday, April 13, 5am -- a4: Vector class

    10T -- Tue, April 9

  • LAB
    • Lab9 -- Continued work and help on your class Vect

    10W -- Wed, April 10

    • LECTURE
      • Intro to Linked Lists
    • READING
      • review Records, p. 172-174
      • general overview of Lists, p. 174-176
      • Linked Lists, p. 341-359
      • try exercises #8.1, 8.2, 8.3 on p377
    • DUE
      • Saturday, April 13, 5am -- a4: Vector class

    10F -- Fri, April 12

    • LECTURE
      • Inserting and Deleting nodes from a linked list
    • READING
      • see Wed's pages (catch up!)
    • DUE
      • TODAY (or Sat by 5am) -- a4: Vector class

    11M -- Mon, April 15
    • LECTURE
      • Designing with Wisdom -- Implementing a List with a Linked List
      • Nuts and bolts of the List::List class
    • READING
      • review: p364-376 (this is critically important material)

    11T -- Tue, April 16

  • LAB
    • Lab10 -- Linked Lists

    11W -- Wed, April 17

    • LECTURE
      • Doubly-linked lists
    • READING
      • p359-361 -- Doubly-linked lists

    11F -- Fri, April 19

    • Quiz7
      • the List::List class and associated behaviors (methods: isEmpty(), insertNode(), deleteNodeWithThisName(), etc)

    12M -- Mon, April 22
    • LECTURE
      • Introduction to trees
      • Tree hugging and other crunchies: Trees, branches, leaves and roots
    • READING
      • Intro to Trees
      • p602-610, 621-624 (read this!)
      • try #1,2a-h,3a-h,4 on p651

    12T -- Tue, April 23

  • LAB
    • Lab11 -- Trees: Implementing the game '20 Questions'
    12W -- Wed, April 24
    • LECTURE
      • Tree traversal: preorder, inorder, postorder
      • ~Tree() -- destroying a tree correctly
    • DUE
      • Fri, May 3: Hardcopy of source and electronic submission for your game '20 Questions'

    12F -- Fri, April 26

    • LECTURE
      • Log base 2
      • Worse case searching in a binary tree
    • DUE
      • Fri, May 3: Hardcopy of source and electronic submission for your game '20 Questions'

    13M -- Mon, April 29
    • LECTURE
      • Quiz8 - Trees

      • Search: in arrays(linear and binary) and in Binary Trees
      • Big Oh notation
    • READING
      • p 542-551, p.556-562; also see Fig. 12.3 and Table 12.4
    • DUE
      • Fri, May 3: Hardcopy of source and electronic submission for your game '20 Questions'

    13T -- Tue, April 30

  • LAB
    • Lab12 -- HELP with Trees: Implementing the game '20 Questions'
    13W -- Wed, May 1
    • LECTURE
      • bitwise operators and masking
    • READING
      • Appendix A: pA134-A136
    • DUE
      • Fri, May 3: Hardcopy of source and electronic submission for your game '20 Questions'

    13F -- Fri, May 3

    • LECTURE
      • Last day of classes
      • Evaluations
      • Demo's of your Twenty Questions game

    Tuesday, May 7

    • FINAL EXAM - 2-5pm (A102)

    Jan | Feb | Mar | Apr | May

    [Back to cs2 Syllabus Home]

    •     Maintained by: Mark LeBlanc
        Dept of Math & Computer Science
        Wheaton College, Norton, Massachusetts