CPSC 211, Sec 201-203: Exam 1 Review
Spring 2004
The exam will emphasize concepts, algorithms, and analysis, as opposed
to programming language syntax. You must know Java and C sufficiently
to understand a Java or C program or program fragment provided, and to
write an approximation to a correct program. However, you will
not be tested on syntax details.
Review the following:
- lecture notes through Feb 25 (Deqs): Slides 1-194
- assigned readings through Feb 21: Standish Chs 1-6 and App A-B,
Kelley/Pohl Chs 1-13 (skim for the test, use as a reference for
programming)
- Quizzes 1 through 6 and their solutions (given in class)
- Programs 1-4
- lab activities through Mar 3
Topics to focus on:
- Be able to write a recursive method/function. Review the recursive
parsing algorithm for arithmetic expressions.
- Understand what happens with memory during the execution of Java
programs, particularly concerning primitive types vs. reference types,
and method invocations.
Understand what happens with memory during the execution of C
programs, particularly concerning structs, arrays, method invocation,
and the use of malloc.
Be able to draw memory diagrams (stack and heap) corresponding
to fragments of Java and C code.
- For each of the abstract data types Priority Queue, Stack,
FIFO Queue, and Deq (double-ended queue), know
- the specification (using the abstract state style)
- the array implementation(s)
- the linked list implementation(s)
- the pros and cons of the different implementations (including
big-oh analyses of space usage and time of the various operations)
- Know these ADT applications:
- Priority Queue: sorting
- Stack: postfix evaluation, infix-to-postfix conversion
- FIFO Queue: infix-to-postfix conversion, discrete event simulation
- Deq: stock purchases and sales
More specific hints and practice problems:
- Compare and contrast what happens with memory with the following
code fragments.
First, Java:
class Photo {
String caption;
int category;
Photo(String s, int cat) {
caption = s;
category = cat;
}
}
...
Photo[] myPhotos;
Photo[] yourPhotos = new Photo[10];
Now, C:
typedef struct{
char caption[80];
int category;
} Photo;
...
Photo myPhotos[10];
Photo* yourPhotos;
Photo* hisPhotos[10];
- For short answer questions, focus on why data structures are useful,
asymptotic analysis, big-oh notation, running time of algorithms,
stack frames, distinction between specification and implementation
of an abstract data types, etc.
- Also study the recursive parsing algorithm, infix and postfix,
memory diagrams, and implementations of Priority Queue, Stack, FIFO Queue,
and Deq.