|
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
|
