COM1201 Spring 2000 Course Syllabus and Calendar
This Syllabus has been updated as of Thursday, May 17th
Professor Futrelle
College of Computer Science, Northeastern U., Boston, MA
This is the version of the Syllabus, 5/7/2000.
The Syllabus is now in final form.
Note that readings due for a given day are listed on that day,
so keep looking ahead at what you need to do. This course will be similar to but not
identical to the course I taught in Winter 2000. You many want to refer to my
COM1201 Winter 2000 pages to get some ideas about what might be coming up.
URL of this page:
http://www.ccs.neu.edu/home/futrelle/teaching/com1201sp2000/syllabuscal.html
You can also look at the Northeastern University Academic Calendar
as well as the excerpt I've prepared
from it that covers important dates for this course this Spring Quarter.
There is also a very brief "pocket calendar"
Preparing for quizzes and exams:
It's important to come to every class meeting you possibly can because in class
I present things, often in simple ways, that I expect you to be able to deal with
on tests. I will do my best to point out specific material in the textbooks
that you are responsible for and will post material and send email outlining
what to focus on, but there's no substitute for coming to class, listening
and asking questions.

 Thurs. March 30
 The textbook and other resources.
 Lectures, homework, machine problems, quizzes, and exams.
 Machine problems and overall code/documentation structure.
 Major topic for today: The sample problem of Chapter 1: Computing the
connectivity of a collection of pairs of possibly connected items  the QuickFind
algorithm.


 Mon. April 3
 Homework #1 assigned, due Monday the 10th.
Details here.
 Finish discussion of the QuickFind and QuickUnion algorithms
of Chap. 1.
 Reading due today: Chapter 1, the connectivity computation sample problem,
focusing on pages 1 through to the middle of pg. 16.
 Thoroughly understand Programs 1.1 and 1.2. Remember to use the Lippman/Lajoie
book to help you understand the programs well.
 Only skim the remaining sections of Chapter 1 on the weighted version
of the algorithm and the pathcompression approaches.
 Reading due today: Begin reading Chap. 2 on the
Principles of Algorithmic Analysis, dealing
with complexity and "Big Oh" notation. Do your initial reading through Sec. 2.4.

 Tues. April 4
 Topics for today, related to Chap. 2:
Explain how certain recurrence relations are solved and
how they relate to simple algorithmic strategies such as binary search and
quicksort.
 Discuss how complexity can be estimated from algorithm run times for various
values of N. This is what you'll be doing in Lab #1, so pay close attention.
This is really not covered in the book, so come to class (of course).
 Reading due today: Chapter 2, reread through Sec. 2.4 and also read
Sec. 2.5 on Basic Recurrences, for computing
C_{N}, the total number of steps necessary for an algorithm to process
N data items.

 Thurs. April 6
 Topic for today: Finish discussion of Algorithmic Analysis, Chap. 2.


 Mon. April 10
 Homework #1 due.
 Topics for today: Elementary Data Structures, Chap. 3.
This material is review for many of
you, so you should read through the chapter quickly, reminding yourself
of what you already have worked with in previous classes.

 Tues. April 11

 Introduction to graphs. Graphs are complex structures
made up of a collection of vertices with some pairs
connected by edges.
 Reading due today: From the bottom of pg. 121 through pg. 125 in Chapter 3.
 Discussion of Lab #1 which will be held Wednesday.
Lab #1 is due handed in Tuesday, April 18th.
Details of Lab #1 here.

 Wed. April 12
 Lab #1 today, 2:50 or 4:05. Attendance is not mandatory, but
Ms. Zheng will be there to help you get started.

 Thurs. April 13
 Topic for today: Continuing our discussion of graphs.
 Reading due today on graphs: Chapter 5, Sec. 5.8 to end of chapter.
Whereas the material in Chapter 3 looked at the representation of a graph
as a data structure, this material in Chapter 5 describes how an algorithm can systematically
"visit" each vertex, normally as part of a search or to process the information
at each vertex. Program 3.19 on page 124 shows how an adjacency list representation
can be constructed for a graph from input.


 Monday. April 17
 Introduction to sorting: Stability (stable versus unstable sort),
Selection Sort, Insertion Sort.
 Simplifying Program 6.1 by removing templates and changing all "item"
to "int".
 Reading due today: Chapter 6, Elementary Sorting Methods, through Sec. 6.3.

 Tues. April 18
 Lab #1 due handed in today.
 Topic for today: More on sorting, especially improvements of Insertion Sort
as shown in Program 6.3.
 Discussion of the various diagrams showing the operation of sorts.

 Thurs. April 20
 Reading due today: Review the material we've covered in Chapters 1, 2,3, 5 and 6
on your own before coming to class for the review for Quiz #1, to be held
on Monday.


 Mon. April 24
 Quiz #1, one hour.
Closed book, closed notes, no calculators.
 This will cover all material trough April 20th.

 Tues. April 25
 Topic for today: Begin discussion of Quicksort.
 Reading due today: Chapter 7 through Sec. 7.5

 Thurs. April 27
 Go over results of Quiz #1.


 Mon. May 1

Go over Lab #2 code in detail.

 Tues. May 2

Show "dog/Woof!" example of how to split a single program file into files
for declarations (.h), definitions (.cpp) and the client or main() file (.cpp).


Discussion of
Quicksort, with readings:
Chap. 7 through Sec. 7.5. Pay careful attention to this material,
since it will be featured prominently
on the Midterm next week.

 Thurs. May 4

Continue discussion of Quicksort, including a brief discussion of medianofthree
and selection.

Brief mention of the importance of priority queues, e.g., in operating
systems job queues based on priorities.



Mon. May 8

Topic for the next two classes: Priority Queues (PQs) and the heap
data structure.
Pay careful attention to this material, since it will also be featured
prominently
on the Midterm on Thursday. Readings: Skim Chap. 9 through Sec. 9.1.
Then carefully
read Secs. 9.2 through 9.4. At this stage focus on understanding,
diagrammatically, how to do fixUp()
and fixDown() on a heap, Figs. 9.3 through 9.6.


We will introduce the
array representation
of the heap data structure, in preparation for tomorrow's discussion of
the code in Progs.
9.3 through 9.5.


Tues. May 9

Carefully study the code in Progs. 9.3 through 9.5 so that you understand
the relation
between heap operations and operations on the array that is actually used
to represent
the PQ. Brief discussion of heapsort in Figs. 9.7 and 9.8 as
well as the corresponding code in Prog. 9.6
(you need not learn the code in Prog. 9.6).


Thurs. May 11

Midterm Exam This will cover the entire course up
to this point, with special emphasis on the recent topics: Quicksort and Priority
Queues, especially heapbased priority queues.


Mon. May 15

Go over the results of the Midterm and discuss the answers to the questions.
This is another important class, since some of this material may appear on the Final Exam
and you want to be sure that you know the correct answers and approaches to the problems,
especially ones you might have had difficulty with.


Tues. May 16

The concept of Hashing, an O(1) search algorithm(!) Read Chap. 14
through Sec. 14.1. Skim Sec. 14.2. Since hashing is the topic of your third and
last machine problem, MP#3,
this material will be important and should be helpful to you.




Thurs. May 18

Hashing: Focus on Sec. 14.2, especially Prog. 14.3, which implements separate chaining.
This is the algorithm you'll implement for MP#3. I will also hand out the API and specifications
for MP#3, to be discussed in more detail as we proceed.
You will have to write your own hash functions for MP#3,
so pay careful attention to the examples in Progs. 14.1 and 14.2.
Briefly study Sec. 14.3 on your own and be ready
to do a problem on the Exam(s) that shows how linear probing works diagrammatically, as in Fig. 14.7. Introductory
discussion of MP#3 and some details of the assignment, so you can get started.


MP#3 is due on Thursday the 25th (Progress Report) and June 1st, so start now.
(This may take you longer to do than MP#2.
Remember: You can ask questions during the Recitation about machine
problems too.)


Mon. May 22

Topic for this week: Binary Search Trees (BSTs).
We will begin showing the structure and operations on BSTs diagrammatically,
including basic "<" and ">" organization, search,
insert, remove, delete and traversal. Read the Introduction to Chap.
12 and skim Sec. 12.1 to gain a basic understanding of symbol tables and
operations on them. You do not need to study the code in Prog.
12.3. Skim Sec. 12.5 in preparation for reading it more carefully
this week.


I will answer a few questions about MP#3, and a few more tomorrow.
You should also talk with the
TA, Ms. Zheng when you have questions about machine problems.


Tues. May 23

We will study the code for BST operations in Sec. 12.5. Learn the
code in Prog. 12.8 thoroughly. Removal of an entry from a BST
is more complex than the other basic operations, so we will
primarily study that via the diagrams in Figs. 12.18 and 12.19, and briefly
mention the code in Prog. 12.16.


Reprise of hashing
and the MP#3 assignment in preparation for lab meeting tomorrow.


Thurs. May 25

Progress Report for Machine Problem #3 due today  hardcopies.


BSTs only work well when they are balanced. We will study tree transformations,
and rotations in particular, as a mechanism for balancing trees.
Read Sec. 12.8 on insertion at the root, and
in particular, you should thoroughly understand and learn the code for
rotations as described in Progs. 12.12 and 12.13. Study Figs.
12.12 and 12.13 in conjunction with the code

Today we will also study one simple method of balancing a tree: Partitioning
it at the root and then recursively balancing the left and right daughter trees.
The code for partitioning a BST is given
in Prog. 12.14. You should thoroughly understand this code as well as
reading whatever of the text in that section
that you need to in order to understand it. The actual balancing code is
given in Chap. 13, so read the Introduction
to Chap. 13 as well as Sec. 13.1. Study and learn the code in Prog. 13.1.




Mon. May 29

Memorial Day. Holiday. No class.


Tues. May 30

MP#3 is due. Quiz #2 will be given today, 1/2
hour only. This will cover some of the basics of BSTs but no other topics.
The rest of the class will be taken with general discussion
and review.


Thurs. June 1

Final version of Machine Problem #3 due today 
floppies and hardcopies and
signed statement of team member contributions.


Quiz #2 will be returned and discussed and I will review for the Final
Exam, which will cover all the material in the entire course.


Week 11  Final Exam Week 
 Week of June 510
 FINAL EXAMS
Have a nice break!
Back to COM1201 Spring 2000 homepage.
Back to Professor Futrelle's homepage.