January 16, 2001 (Tuesday) Introduction to the Course: Goals and Topics to Be Covered. Beginning of course questionnaire. Waterfall, spiral, and RUDE program development methodologies. Preconditions and postconditions: Main's transparencies. Section 1.1 [M]. No homework assigned.
January 18, 2001 (Thursday) Time complexity analysis. Section 1.2 [M]. No homework assigned. Reading assigned: Ch. 1 [M].
January 23, 2001 (Tuesday) Quiz 1. Average case analysis of linear search under different assumptions (target never in list, target in list with probability p): good questions from students. Beginning of Chapter 2: Abstract Data Types and Java Classes. General introduction, ADTs as general purpose classes based on mathematical abstractions (e.g.: set). Access control for data members and methods: public, protected, default or friendly or package, private. (Most students only knew public and private; I explained why protected is a good choice to encourage reuse in derived classes---this was a detour on an advanced topic.) The Throttle class, up to p.41. No homework assigned. Reading assignment: Ch. 2.
January 25, 2001 (Thursday) Quiz 2. First programming assignement: the Statistician class, programming project 2 on p.89 [Main]. See the programming assignment web pages in the CSCE 146 web site. Heads-up on web access problems in SUM 361: e-mail exchange with Matthew Byrd, systems administrator. Throttle class example continued: all methods with programming tips and pitfalls. Using a class. Reference variables, cloning, different types of equality. Terminology: "Throttle t" vs. "The Throttle that t refers to." Packages: declaring, using a package or a class within it, the java.text package, access. No homework assigned. Students were again asked to read ch.2, esp. the specification of the Location class.
January 30, 2001 (Tuesday) No quiz. Completion of Chapter 2 of textbook: parameters, equal methods, and clones. Running example: the Location class.
February 1, 2001 (Thursday) Quiz 3. Clones, the equals method, parameter passing (topics to be reinforced from chapter 2). Container classes: the Bag part of Main's lecture for chapter 3, Powerpoint available from Main's site. Laptop used for Powerpoint (only, so far).
February 6, 2001 (Tuesday) Quiz 4. Discussion of PR1. IntArrayBag. Laptop used for Powerpoint (only, so far).
February 8, 2001 (Thursday) No quiz. Discussion of lab. PR1 collected. More on IntArrayBag.
February 13, 2001 (Tuesday) Quiz 5. Announcement of Herbert Simon's death on February 9. (Obituary is linked to my academic home page.) DoubleArraySequence. Applets---example on laptop explained. Brief introduction to linked lists. PR2 (implementation of DoubleArraySequence) is now announced on the syllabus page.
February 15, 2001 (Thursday) No quiz. Suggestions for midterm preparation: do self-test exercises; work out sample questions on Dr. Michael Main's site. (Link to the latter is on course page.) Test will be on materials up to page 187. Basics of linked lists: the IntNode class, how to insert a node at the beginning of a list, how to remove a node from the beginning of a list, how to insert a node anywhere in a list. (Sections 4.1 and 4.2; Powepoint slides from Dr.Main's site also used.)
February 20, 2001 (Tuesday) Midterm Exam.
February 22, 2001 (Thursday) Linked lists: Review of topics from 4.1 and 4.2; much of 4.3. Some topics concerning the implementation of the Bag ADT using linked lists.
February 27, 2001 (Tuesday) Quiz 6. Review of midterm. Q&A on second programming assignment.
March 1, 2001 (Thursday) Programming Assignment 2 collected. Linked lists: two methods for deletion. Review of lab work. Run-time analysis: trade-off between linked lists and arrays. Chapter 4 completed. Chapter 5 begun: java objects, the eight primitive data types, wrapper classes.
March 6, 2001 (Tuesday) Quiz 7
March 8, 2001 (Thursday) PROGRAM 3 ASSIGNED: DoubleLinkedSeq Implementation (see elsewhere on web site) per description in Section 4.5 of text.
March 20, 2001 (Tuesday) Stacks: introduction, examples thorugh balanced parentheses.
March 22, 2001 (Thursday) Program 3 collected. Stacks: Applications, array implementation, linked list implementation (Chapter 4 through Section 6.3).
March 27, 2001 (Tuesday) Stacks. Chapter 6 completed, except for correctness argument of infix to postfix conversion algorithm. Complexity argument for the same algorithm (with observation that total number of pop operations may not exceed total number of push operations) given.
March 29, 2001 (Thursday) Correctness argument of infix to postfix done. Queues (Ch.7) started: introduction, echoing, palindromes.
April 3, 2001 (Tuesday) Queues: car wash (discrete event) simulation. Array implementation of queues: efficiency issues, benefits of circular arrays.
April 5, 2001 (Thursday) Detailed discussion of PP4: n-queens with a stack and backtracking. Array implementation of queues completed. Brief comments on linked list implementation of queues.
April 10, 2001 (Tuesday) Second midterm will be in one week and will cover chapters 4 through 7. PP4 is also due in one week. Chapter 7 (queues) completed. Chapter 8 (recursive thinking) started, with power example in class: 3^n = 3^(n-1) * 3, with rows acting as activations of the recursive procedure and base case 3^0 = 1. Also, brief discussion of 3^n = 3^(n/2) * 3^(n/2). Computing combinations recursively.
April 12, 2001 (Thursday) More examples of recursive procedures. Recursive computation of 3^n in log n time. Question on odd n leads to general form. Recursive computation of combinations revisited. The writeVertical and superWriteVertical methods from the book (displayed using the computer). Activation records and the execution stack.
April 17, 2001 (Tuesday) Midterm 2
April 19, 2001 (Thursday) More examples of recursive procedures: factorial, tail-recursive factorial with accumulator, sum of reciprocals (PP5), sum of reciprocal with accumulator.
April 24, 2001 (Tuesday) Projection equipment is down. Call to support services reveals that an overload tripped a fuse and equipment will not be fixed until 2pm. (Thanks to a student who had the phone number.) Discussion of binary search starting from PP10 in Ch.8 (tomorrow's lab, "guessing a number) and going on to analysis as in Ch.11 Section 1. Introduction to binary trees: taxonomies, binary search trees, family trees, some terminology.
April 26, 2001 (Thursday) Many examples of binary trees from Goodrich and Tamassia (ch.5). Definitions. Complete binary tree presentation from Main's web site. Representation of complete trees by using arrays. Representation of trees by linked structures: the BTNode class. Traversal methods were described very briefly.
May 1, 2001 (Tuesday) A handout prepared by Dr. Dobbins with some sample final exam questions was handed out. The recursive "quiz" program and a variant were analyzed. The notion of call tree was introduced. Recurrence relations were set up and solved. A (rather general) divide-and-conquer recurrence relation was presented. Binary search trees were introduced at the specification and design level, with examples of insertion and deletion. Good questions. Student evaluation was *not* carried out because only forms for section 510 were received and the department did not have enough forms. I called Ms. Knotts in the CoEIT office, and forms were in my mailbox after the class finished. I will do the evaluations in lab.