COM1201 Winter 2000 Course Syllabus and Calendar
Major Revision: Version of 2/12/2000.
Further updates 2/22/00.
Note: This Syllabus underwent
a major revision on February 12th to bring it into
line with the actual progress of the course to date and its projected progress.
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 Winter Quarter.
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. Jan. 6
- 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 Quick-Find
- Reading to do: Chapter 1, the connectivity computation sample problem,
focusing on pages 1 through to the middle of pg. 16 (today's topics).
- Mon. Jan. 10
- Homework #1 assigned, due Thursday the 13th.
- Finish discussion of the Quick-Find and Quick-Union algorithms
of Chap. 1.
- Reading due today: Finish reading Chap. 1 but only skim the sections on the weighted version
of the algorithm and the path-compression approaches.
- Reading due today: Begin reading Chap. 2 on the Principles of Algorithmic Analysis, dealing
with complexity and "Big Oh" notation. Read through Sec. 2.4.
- Tues. Jan. 11
- 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
- Discuss how complexity can be estimated from algorithm run times for various
values of N.
- Reading due today: Chapter 2, Sec. 2.5 on Basic Recurrences, for computing
CN, the total number of steps necessary for an algorithm to process
N data items.
- Thurs. Jan. 13
- Topic for today: Finish discussion of Algorithmic Analysis, Chap. 2.
- Homework #1 due.
- Mon. Jan. 17 NO CLASS
- Martin Luther King, Jr. Day. University holiday.
- Tues. Jan. 18
- 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.
- SPECIAL TOPIC, WHICH WILL BE ON THE FIRST QUIZ: A new and interesting and important topic,
which few, if any of you have seen, is data structures to represent graphs,
which are made up of a collection of vertices with some pairs
connected by edges.
For this special topic, be sure to read from the bottom of pg. 121 through pg. 125.
- Discussion of Lab #1 which will be held this Thursday, the 20th and is due
handed in on Tuesday, the 25th.
- Thurs. Jan. 20
- Topic for today: Continuing our discussion of graphs.
- Reading due today on graphs: Chapter 5, Sec. 5.8 to end of chapter.
- Monday. Jan. 24
- Topic for today: Finishing the discussion of graphs.
- Tues. Jan. 25
- Review for Quiz #1 to be given Thursday.
- Reading due today: Review Chapters 1 through 3 on your own before coming
to class for the review:
- Thurs. Jan. 27
- Quiz #1This will cover all material through January 24th that was
stressed in Chapters 1 through 3.
Full details and a copy of the Quiz are here.
- Mon. Jan. 31
- Go over Quiz #1 results and answers.
- Tues. Feb. 1
- Topics for today: Finish going over Quiz #1, especially, Problem 5 that
has to do with complexity for a search problem.
- Introduction to sorting: Stability (stable versus unstable sort),
Selection Sort, Insertion Sort.
- Simplifying Program 6.1 by removing templates and changing all "item"
- Reading due today: Chapter 6, Elementary Sorting Methods,through Sec. 6.3.
- Thurs. Feb. 3
- 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.
- Mon. Feb. 7
- Brief demonstration of code development in Visual C++ on the PC using
a simple console project. Documentation requirements -- how you must
structure your machine problem assignments.
Includes, header files, source files, compiling,
and running under the debugger.
- Posted and handed out source listing for key-based sorting of records.
Discussed the design and operation of the code.
- Tues. Feb. 8
- Topic for today: Begin discussion of Quicksort.
- Reading due today: Chapter 9 through Sec. 9.4.
- Thurs. Feb. 10
- Lab #2 today, due Tuesday, February 15th. Supervised by Mr. Meda.
- Topic for today: Finish our discussion of Quicksort as well as comparing
the performance, space requirements and stability of Insertion Sort,
Mergesort, and Quicksort.
- Explain Priority Queues, such as in operating systems, to motivate the
discussion of Heapsort that will begin Monday.
- Reading due today:
- Mon. Feb. 14
- Topic for today: Priority Queues and Heapsort.
- Reading due today: Skim through Sec. 9.1. Carefully read Secs. 9.2, 9.3
and 9.4. You should understand how to do the operations fixUp and fixDown
and be able to do them on paper for the Midterm, how the tree changes as
insert and remove maximum operations are done. This will be on Midterm.
(We will discuss the array representation later.)
- Tues. Feb. 15
- Lab #2 due today.
- Review for the Midterm. Details here.
- The exam will cover all material we've discussed or had on homework or
in the labs from the beginning of the course through the material in
Chapter 9 (Feb. 14th). Greater emphasis will be given to material not included
in the first quiz, as well as to any material from the first quiz that appeared
to not be well understood by most of the class and needs further work.
- Thurs. Feb. 17
- Midterm Exam
- Held in our regular classroom, for the full period. Closed book, closed
notes, no calculators.
- Mon. Feb. 21
- Go over Midterm Exam
- Tues. Feb. 22
- Topic for today: Finish going over the Midterm. Also, finish our
discussion of Heapsort, especially the relation between the tree representation
of the heap and the efficient array representation exploited by the code
(and that was not covered on the Midterm).
- Reading for today: Reread the same sections of Chap. 9 as before, but
concentrate on the array representation and how it relates to the tree representation
of the heap.
More specifically, be sure you understand the tree/array relation
shown in Fig. 9.2 as well as the Heapsort code in Prog. 9.7.
- You should study Heapsort in Sec. 9.4, but only pgs. 389 to the top of pg. 392.
Also, the heap construction technique used in Prog. 9.7 and explained on pg. 390
and shown in Fig. 9.9.
- Thurs. Feb. 24
- Binary Search Trees. Lecture #1 of two lectures.
Reading due today: Sec. 12.5, pgs. 515-520.
- Homework #2. on Binary Search Trees. Due Monday, Feb. 28th.
A copy of the assignment can be accessed here
- Mon. Feb. 28
- Topic for today: Lecture #2 of two lectures. More on Binary Search Trees and a
brief discussion of the creation and properties of balanced trees.
Reading due today: Sec. 12.6, pgs. 521-524.
- Tues. Feb. 29
- Review for Quiz #2. Topics to be covered focus on the recent ones of
the heap array data structure and binary search trees.
Details about Quiz #2 here (IN PREPARATION).
- Quiz #2 will cover only two topics: (1) The relation of the array and tree
representations for heaps. (2) Binary search trees.
- Thurs. Mar. 2
- Quiz #2 This will be a half-hour quiz.
- Mon. Mar. 6
- Go over Quiz #2.
- Tues. Mar. 7
- Topic for today: Hash tables.
Why they are blindingly fast and commonly used.
- Reading for today: Skim the introduction and Sec. 14.1 of the Hashing
chapter and read Sec. 14.2 carefully. Separate chaining will be covered on
the Final Exam.
- Thurs. Mar. 9
- Review for the Final Exam. The exam will be comprehensive, covering
all the material in the course. There will definitely be a question on
hashing with separate chaining, since that was covered only in the class
since Quiz #2.
Details about the Final Exam here (IN PREPARATION).
Week 11 -- Final Exam Week|
- Week of Mar. 13 -- 17
- FINAL EXAM TO BE GIVEN WEDNESDAY, MARCH 15th, 1pm.
- Have a nice break!
- Back to COM1201 Winter 2000 homepage.
- Back to Professor Futrelle's homepage.