Fundamentals of Computer Science

Our final exam is scheduled (by vote of the class) for 2:00-5:00pm this upcomng Saturday, December 5th.

Here is a study guide for the final exam.

Here are the keys for all of the normal (non-makeup) tests: Test 1, Test 2, Test 3

Here are the keys for all of the homeworks: Homework 1, Homework 2, Homework 3, Homework 4, Homework 5

In lecture today, the following topics were covered:

• Answering of questions about lab 11, including the meaning of deep & shallow copy
• Discussion of the use of stacks in evaluating postfix expressions and in translating infix expressions to postfix expressions

Here is the code for a postfix evaluator, using the Stack code from Monday: PostfixEvaluator.cpp

Here is a PDF with the powerpoint slides from today.

The lab for today is to continue working on Lab 11 (originally assigned on 11/16).  It is due on Wednesday, 12/2 at 5:00pm.

In lecture today, the following topics were covered:

• General definitions of 2 new linear data structures, Stacks and Queues, and discussion that these data structures are essentially restrictions on how additions and deletions are defined for a container.
• Definition of common Stack operations
• A discussion of implementing Stack operations using an array and using a LinkedList (LinkedList being the better choice)
• Discussion of some real-world examples of uses of Stacks

Here is a Stack implementation built on top of a LinkedList: Stack.h, Stack.cpp, stackMain.cpp (These files assume that LinkedList has all the functions needed implemented (such as empty, getDataAtIndex - they do on my computer, but they don’t necessarily in your lab LinkedLists, etc).

Here is a PDF of the powerpoint slides from today.

In lecture today, the following topics were covered:

• Test 3 was handed back and reviewed.  The key will be posted here soon.
• A few variations of LinkedLists were discussed, such as Circular Linked Lists, Tail-Pointer Based Linked Lists, and Doubly Linked Lists (using prev and next pointers in each Node).

In lecture today, Test 3 was taken.

Here are documents helpful for reviewing for the upcoming test, which is to be held this Friday, November 20th:

• Homework 5 Key
• Test 3 Study Guide
• Test 3 Practice Problems

In lecture today, the following topics were covered:

• the LinkedList destructor
• the utility of re-using other methods (such as deleteFirst() in the destructor)
• the idea of iterators
• the beginning of a class definition for a LinkedList iterator

Source code for the iterator will be uploaded over the next few days.

The lab for this week is to implement a string-data LinkedList container. You are not required to use templating.

Here are the lab documents:

• Lab 11 description document
• Lab 11 gradesheet

Planned due date for this lab is Wednesday, December 2nd at 5:00pm.