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.

URL: http://www.ccs.neu.edu/home/futrelle/teaching/com1201w2000/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 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.

Week 1

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

Reading to do: Chapter 1, the connectivity computation sample problem, focusing on pages 1 through to the middle of pg. 16 (today's topics).

 

Week 2

Mon. Jan. 10

Homework #1 assigned, due Thursday the 13th. Details here.

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

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 C_N, 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.

 

Week 3

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. Details here.

 

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.

 

Week 4

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.

 

Week 5

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" to "int".

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.

 

Week 6

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. Details here.

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:

 

Week 7

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.

 

Week 8

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 .

 

Week 9

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.

 

Week 10

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.