CPSC 225: Intermediate Programming

   Department of Mathematics and Computer Science
   Hobart and William Smith Colleges

   Fall 2016.

   Instructor:  David J. Eck  (eck@hws.edu)

   Course Handout:  http://math.hws.edu/eck/courses/cpsc225_f16.html

   Monday, Wednesday, Friday, 11:15--12:10 PM
       Coxe 7.

   Lab: Tuesday, 1:30--2:55 PM
       Rosenberg 009.
   Office Hours in Lansing 313 (but also check the Lansing computer lab):

       Almost always:  MWF 10:00–11:00
                       Th  12:00–1:15

       Usually:  MWF 1:30–3:00
                 Tu   11:00–1:00

Lab Worksheets
Lab 1, September 1
Eclipse / Spellcheck
Lab 2, September 8
Sort and Search Times
Lab 3, September 15
Recursion Exercises
Lab 4, September 22
Linked Lists
Lab 5, September 29
Binary Tree Demo
Lab 6, October 6

Some Useful Links

First Week: August 29 and 31; September 2

Welcome to the course!

Read Chapter 8, Sections 1 through 3 in the textbook. Looking ahead, we will cover Subsection 8.4.1 but will not cover 8.4.2. (However, I encourage you to read all of Chapters 8 through 13 in the book, even the parts that are not an official part of the course.) On Monday, I will talk in general terms about Sections 1 and 2. We will cover Section 8.3 in some depth on Wednesday. That section is about exceptions and the try..catch statement. You have probably encountered exceptions already; this section adds detail. Please read Section 8.3 before class on Wednesday!

On Friday, after the Thursday lab, we might have to review some things from Introductory Programming. If not, or in any remaining time, we will talk about 8.4.1.

The required reading for the first week also includes the course handout and the style guide that will be handed out on the first class meeting. And you should read Lab 1 before coming to lab on Thursday.

Second Week: September 5, 7, and 9

It turns out that we didn't have time to talk about Section 8.4.1 (assertions), so we will leave that as a reading assignment only (and no, it won't be on the test).

On Monday, we will discuss Section 8.5, which is an introduction to the analysis of algorithms. The question here is how to talk about the run time efficiency of an algorithm, and how to compare the run times of different algorithms for performing the same task. This is a question that we ask about many of the the algorithms that we study later in the course. We will take a somewhat informal approach. If you take our algorithms class (CPSC 327), you will study the analysis of algorithms in a more detailed and mathematical way.

We will move on to Chapter 9 on Wednesday. You should read Section 9.1 before Wednesday's class. Section 9.1 discusses recursion. A recursive method is one that calls itself, either directly or indirectly. Recursion turns out to be a powerful tool for expressing algorithms. We will spend Wednesday and Friday on recursion.

Third Week: September 12, 14, and 16

The reading for the week is Section 9.2. This section introduces the idea of linked data structures. It concentrates on linked lists. A linked data structure is made up of "nodes." A node is an object. In a linked data structure, a node typically contains one or more pointers to other nodes of the same type. In a simple linked list, each node contains a pointer to the next node in the list. We will see that it is often possible to use recursion to process linked data structures, although recursion is usually used with more complicated data structures than linked lists.

Fourth Week: September 19, 21, and 23

The reading for the week is Section 9.3. This section introduces the important idea of Abstract Data Type (ADT). It uses stacks and queues as examples of ADTs. We will look at two implementations of the stack ADT, one using linked lists and one using arrays. We will implement the queue ADT using linked lists. We will also look at some applications of stacks and queues.

Fifth Week: September 26, 28, and 30

The reading for the week is Section 9.4. This section covers binary trees, binary sort trees, and expression trees. We will look at the structure of trees, how they can be created and how they can be processed recursively. In particular, we will see the difference between pre-order, in-order, and post-order traversals of a binary tree. We will also have to return to a topic from Section 9.3: postfix expressions and how they can be evaluated using a stack. It is possible that we might get a start on Section 9.5 by the end of the week.

Note that there is a test coming up next week, on Wednesday, October 5.

Sixth Week: October 3, 5, and 7

There is a test on Wednesday, October 5. A study guide is available, and copies were handed out in class on September 30.

Monday of this week should be mostly review for the test. We will go over some of the sample problems from the study guide. On Friday, we will talk about Section 9.5, which covers the recursive processing of ordinary infix expressions.