Version of 2/8/99, with details through to the Midterm Exam.

You can also look at the Northeastern University Academic Calendar

Preparing for quizzes and exams: When this syllabus states that you should "understand" a certain algorithm and its implementation as code, it means that you should be able to recognize the code when you see it and explain how the code operates or what a certain statement does. Apart from the code, if you are asked to perform certain manipulations such as inserting or deleting an item in a structure, you should be prepared to draw the steps on paper, much as the book does in its figures. When the syllabus says to "skim" or "be familiar with" a certain topic or chapter section, you should at least recognize the terms and be able to say what the topic involves, but you will not be asked any details of the data structures and algorithms.

Wed. Jan. 6

Introduction -- The three threads.

The textbook and other resources.

Lectures, homework, machine problems, quizzes, and exams.

Demonstration of code development in CodeWarrior on the Macintosh -- header files, source files, compiling, and running under the debugger.

Reading and foci: All of Chaps. 1 and 2 for general background. In Chap. 3 you should understand all the constructs used in the code, including struct (class with all public members), for , while, cout, cin, struct, class, private:, public:, new, delete, "->", etc. The specific concepts and code you should understand are the code on pgs. 20-22, the array implementation of pushdown stacks, code on pgs. 26-28, and the queue code, pg. 31. For the code, you should be able to discuss it when given it on tests and to write simple portions of it. This is a lot for the first assignment, but it should be essentially review.

 

Fri. Jan. 8

Trees, Chap. 4. Reading: Through the middle of pg. 44 (up to Traversing). Learn all the concepts and their terminology, including root, children, leaves, path length. You needn't memorize the properties 4.1-4.5, but you should learn the ideas and be able to indicate them or count them given a specific tree. Study/know the code, pg. 41. Know how forests can be represented with binary trees.

 

Tues. Jan. 12

Trees, Chap. 4. Reading: Finish the chapter. Traversal of trees is important. Understand the three types. Be able to do the traversals on paper when given a tree. Know the code on pgs. 45 and 48. Again, much of this should be review.

 

Wed. Jan. 13

Recursion, Chap. 5. This will not be a heavily emphasized chapter. Look over the entire chapter. Understand in detail how the code on pg. 61 works -- you should definitely work through applying it to a simple tree.

 

Fri. Jan. 15

Analysis of algorithms, Chaps. 6 and 7. Read all of both chapters. Chap. 6 is very important and the concepts will be referred to repeatedly throughout the course. So read it carefully and certainly more than once. Know the lgN notation. Understand the classification, pgs. 69-70 and be able to give examples or characterize one given to you. Understand how Figs. 6.1 and 6.2 are constructed. Be able to at least finish any of the proofs in Formulas 1-5, if given the first step or two. Also, given a recurrence, be able to explain what kind of process it refers to.

 

You will need to learn and be able to do numerical estimation, as it is needed for analysis in this course. As part of this you may not use calculators on the quizzes and exams in this course. I have posted a separate tutorial web page for you on estimation.

 

Tues. Jan. 19

Elementary sorts, Chap. 8. Quicksort, Chap. 9. I will briefly review the elementary sorts in Chap. 8. You should be able to a few steps of the selection and insertion sorts on paper when given a brief explanation of them. You're not required to know any of the code. Chap. 9 is important, because quicksort is so widely used. You should be able to do quicksort on paper, at least the first few partitions.

 

Wed. Jan. 20

Quicksort, continued. Be thoroughly familiar with the recursive code on pg. 116, and be familiar with the non-recursive implementation on pg. 122. You can read the material after pg. 122, but you will not be responsible for it.

 

Priority queues, Chap. 11. Priority queues deal with the orderly handling of collections of items that are ordered by some priority values, e.g., computer processes or messages that have priorities for being run or sent. They can be used in many applications. The heap data structure is particularly ingenious because it combines the generality of a tree with the efficiency of an array. Reading: For this lecture, read up to Heapsort on pg. 154, but do not study the code details yet.

 

Fri. Jan. 22

Priority queues, continued. Finish reading Chap. 11 and study the code carefully. Don't be concerned with the details of Property 11.2. You should be able to insert one or more items in an initially empty priority queue or one that already has elements in it and to remove items in order from the queue, using upheap and downheap as necessary.

 

Tues. Jan. 26

Review for Quiz #1

Mergesort and external sorting Chaps. 12 & 13 (overview only) You will not be asked about this material on any tests.

 

Wed. Jan. 27

Quiz #1 -- first half of class, covering all the material through Jan. 22nd.

Randomness, Chap. 35. Omit the sections on the additive congruential method and only skim the section on testing randomness. You should be able to iterate a few steps of a linear congruential random number generator when given an example with small values for b and m (like the example of b=19, m=381 on pg. 512). This means understanding how the mod operation "%" works.

 

Fri. Jan. 29

Go over Quiz #1

Hashing, Chap. 16. You should be understand enough about the mapping between codes and bytes and bits to compute hash functions for simple keys, e.g., using the 2 lowest order bits of two characters. You should be able to show how both linear chaining and linear probing work for a simple example. Skim the section on double hashing.

 

Tues. Feb. 2

Hashing, continued.

 

Wed. Feb. 3

Elementary searching methods, including tree-search, Chap. 14. Tree search is fundamental so you need to be sure that you can insert and find and delete elements in a binary tree, possibly starting with an empty tree. Understand how and why sentinels are used in linear search and how a sentinel in the "z" node is used to make the search code more efficient. You should understand how the complexity estimates arise for these elementary searches and what number of steps are required for successful and unsuccessful searches in arrays, sorted arrays, and binary trees. Know what it is for a tree to be balanced or unbalanced and how that affects performance.

 

Fri. Feb. 5

Tree search and balanced trees, Chap. 15. In this chapter, only study through pg. 219, but learn this material well, since it is not simple. Understand how insertion is done within nodes, not by adding additional leaves. Understand how nodes are split with the middle item sent to the parent. Also understand how 4-nodes are split when they are found on the path to an insert point. And finally, realize that if the root of the tree is split, the depth of the tree increases by 1.

 

Tues. Feb. 9

String search, Chap. 19. We have already used the brute force string search algorithm in Machine Problem 1, but you need to study it in this chapter nonetheless. We will study the first of the more efficient algorithms in the chapter, the Knuth-Morris-Pratt algorithm, pgs. 281-286. You should understand how to produce a diagram such as in Fig. 19.5 which shows how the search can "skip ahead" at certain points.

 

Wed. Feb. 10

String search, continued. In the section on the Knuth-Morris-Pratt algorithm in Chap. 19, a new concept is introduced, the finite-state machine (FSA). You should study this material closely because it will be used extensively in Chap. 20. Study the two examples of the FSA in figures 19.3 and 19.4.

 

Pattern matching, Chap. 20. In analyzing our HTML files, we'd like to be able to recognize sequences such as '<' followed by any number of characters followed by a '>'. This can be represented as the pattern "<*>" and the pattern matching algorithm of this chapter, based on FSAs, can perform this task.

 

Fri. Feb. 12

Some or all of this class will be devoted to exercises to help you prepare for the Midterm exam, so be sure to attend!

Pattern matching, continued. You'll need to learn how the simple machines (FSA) that represent certain basic patterns can be represented and how they are combined when patterns are combined.

 

Tues. Feb. 16

Additional review for midterm exam. Coninuation of discussion of pattern matching, especially how a FSA can be represented and simulated.

 

Wed. Feb. 17

Midterm Exam -- full class period, covering all the material from the beginning of the course through string search, since we will not have had time to fully cover and absorb the material on pattern matching at this point.

 

Fri. Feb. 19

Go over Midterm Exam (it is possible that this will be delayed until Tuesday the 23^rd, with more material on pattern matching and an introduction to parsing covered in this class.)

 

Tues. Feb. 23

Parsing, Chap. 21.

 

Wed. Feb. 24

Compression, Chap. 22.

 

Fri. Feb. 26

Cryptology, Chap. 23.

 

Introduction to graphs, Chap. 29.

 

Tues. Mar. 2

Review for Quiz #2

 

Graphs, continued.

 

Wed. Mar. 3

Quiz #2 -- first half of class, covering material from .... through ....

 

Graphs, continued.

 

Fri. Mar. 5

Go over Quiz #2.

 

Connectivity (of graphs), Chap. 30.

 

Tues. Mar. 9

Weighted graphs, Chap. 31.

 

Wed. Mar. 10

Final topics, to be determined.

 

Fri. Mar. 12

Review for final exam.

 

Week of Mar. 15 - 19

FINAL EXAM WEEK.

 

Have a nice break!

 

Back to COM1201 Winter 1999 homepage.

 

Back to Professor Futrelle's homepage.