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/syllabus-cal.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.

Week 1

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 Quick-Find algorithm.

 

Week 2

Mon. April 3

Homework #1 assigned, due Monday the 10th. Details here.

Finish discussion of the Quick-Find and Quick-Union 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 path-compression 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, re-read 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.

 

Week 3

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.

 

Week 4

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.

 

Week 5

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.

 

Week 6

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 median-of-three and selection.

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

 

Week 7

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 heap-based priority queues.

 

Week 8

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

 

Week 9

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.

 

 

Week 10

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

FINAL EXAMS

Have a nice break!

Back to COM1201 Spring 2000 homepage.

Back to Professor Futrelle's homepage.