SIMS 255: Foundations of Software Design

Lectures, Labs, and Assignments 


 
 

Lectures & Assignments 

Labs

Administrivia  

Online Resources 

This schedule is subject to change. Readings are meant to be read in advance of the lecture for which they are shown.  Assignments will be posted as the semester progresses.

Go directly to the current week.


Week 1: 

Tues Aug 28
Lecture: Course Overview

Wed Aug 29
Lab:
Placement Exam

Answer Key for Placement Exam

Thurs Aug 30
Lecture: How Computers Work -- Data representation, CPU, logic gates, instructions
Readings: Machine Architecture (http://courses.cs.vt.edu/~csonline/MachineArchitecture/Lessons/index.html) Optional (if you need review): Number Systems
Assignment: Get comfortable with your SIMS computer account


Week 2: 

Tues Sep 04
Lecture: How Computers Work -- CPU (continued), instructions, code vs. data,
Readings: Operating Systems (http://courses.cs.vt.edu/~csonline/OS/Lessons/index.html)

Wed Sep 05
Lab: Using VisualCafe for Java programming
First time usage;   How to use VisualCafe

Thurs Sep 06
Lecture: How Computers Work -- Operating Systems: Resources, Processes
Assignment 1: Due Thurs Sept 13.


Week 3: 

Tues Sep 11
Lecture: Memory Management, cont., and Object oriented design -- what is it and why do it?
Readings: UML Distilled: Preface, Chapter 1 and pages 75-77 (on CRC diagrams)

Wed Sep 12
Lab: Java practice using VisualCafe

Thurs Sep 13
Lecture: Object oriented design -- in class practice
Readings: UML Distilled, Chapters 2, 3 and 4


Week 4: 

Tues Sep 18
Lecture: Object oriented design -- in class practice
Readings: DSAJ: Chapter 2.

Wed Sep 19
Lab: Object-oriented design exercise

Thurs Sep 20
Lecture: Object oriented design, cont.
Assignment 2: due Tuesday Oct 2
 


Week 5: 

Tues Sep 25
Lecture: Math review
Readings: DSAJ: Chapter 3, sections 3.1-3.4
(Optional): Math Review: Logarithms and Exponential Functions

Wed Sep 26
Lab: Java review  

Thurs Sep 27
Lecture: Analysis of Algorithms
Readings: DSAJ: Chapter 3, sections 3.5-3.7


Week 6: 

Tues Oct 02
Lecture: Analysis of Algorithms, cont.
Readings: DSAJ: Chapter 4, sections 4.1, 4.2, and 4.5
Optional: Review of Arrays   Review of multidimensional arrays
Assignment 3, due Oct 11

Wed Oct 03
Lab: Analysis of algorithms exercise

Thurs Oct 04
Lecture:
Asymptotic analysis redux.   Go over OO Design assignment.


Week 7: 

Tues Oct 09
Lecture: Stacks and Queues
Readings: DSAJ: Chapter 5, Section 5.1 only; Chapter 6, Sections 6.1 and 6.2
Optional Reading: The Lean, Mean Java Virtual Machine

Wed Oct 10
Lab: Stack exercise

Thurs Oct 11 
Lecture: Recursion, Queues
Readings: DSAJ: Chapter 6, Sections 6.3 and 6.4


Week 8: 

Tues Oct 16
Lecture: Vectors, Trees
Code for making a queue from a vector
Code for making a simple binary tree
Readings: DSAJ: Reread Chapter 6, Sections 6.1-6.4

Wed Oct 17
Lab: Go over assignment 3

Thurs Oct 18
Lecture: Tree Algorithms
Readings: DSAJ: Section 9.0, 9.1
Assignment 4: Due Tues Oct 30.  


Week 9: 

Tues Oct 23
Lecture: Hash Tables
Readings: DSAJ: Chapter 8, Sections 8.1-8.3, 8.5

Wed Oct 24
Lab: Discuss Assignment 4

Thurs Oct 25
Lecture: B-trees and External Searching
Readings: DSAJ: Sections 9.3, 9.4, and 9.6
 


Week 10: 

Tues Oct 30
Lecture: Sorting
Readings: DSAJ: Sections 5.4.1, 10.1, 10.3, 10.4, 10.6
Papers on Pair Programming (if you haven't read them yet)

Wed Oct 31
Lab: Go over assignment 4

Thurs Nov 01
Lecture: Finish Sorting; Begin Graphs
Readings: DSAJ: Sections 12.1, 12.2, and 12.3
 


Week 11: 

Tues Nov 06
Lecture: Graphs, Directed Graphs, BFS, DFS
Readings: DSAJ: Sections 12.4 and 12.5
Assignment 5: Due Tues Nov 13.

Wed Nov 07
Lab: Programming exercise

Thurs Nov 08
Lecture: Weighted graphs, shortest paths, MSTs
Readings: DSAJ: Sections 12.6 and 12.7
Mini-Project Information


Week 12: 

Tues Nov 13
Lecture: Overview of Compilers Regular expressions
Readings: Jurafsky & Martin: Chapter 2 (handed out in class)
Assignment 6: Due Tues Nov 20

Wed Nov 14
Lab: Go over A6

Thurs Nov 15
Lecture: Finite automata


Week 13: 

Tues Nov 20
Lecture: Context-free grammars
Assignment 7: Due Thurs Nov 29
Readings: (Optional) Compilers and JavaCC, More on JavaCC

Wed Nov 21
Lab: Regular expressions exercise

Thurs Nov 22 -- Thanksgiving, no class.


Week 14: 

Tues Nov 27
Lecture: Text Processing, Tries, and Dynamic Programming
Readings: DSAJ: Section 11.1 and 11.2

Wed Nov 28
Lab: Go over assignment 8

Thurs Nov 29
Lecture: Complexity and NP-completeness   Guest lecture by Matt Welsh
Readings: A short intro to NP Completeness
These two are optional: Computability and Complexity    The Complexity Class NP

Assignment 8: Due December 14.


Week 15:

Tues Dec 04
Lecture: Student Mini-project presentations

Wed Dec 05
Lab: Student Mini-project presentations

Thurs Dec 06 
Course Wrap Up; Computability; The Deepest Question Wrap-up; Course evaluations
Readings: What Computers Can't Do     Information on Turing Machines     A Virtual Turing Machine web page applet