CS 14 - Lab
CS 14
Homepage
First Task - Lab Practical
You will have 1 hour and
40 minutes to complete the practical. You will turn in your lab using the electronic
turnin. WATCH THE TIME! Even though the turnin may still be available,
I will NOT accept any turns that are time stamped later than 1 hour and
40 minutes past the scheduled start time of your lab section and ASBOLUTELY NO LATE LAB
PRACTICALS WILL BE ACCEPTED NO MATTER WHAT THE REASON EVEN IF YOU ARE ONLY 1 SECOND
LATE. DO NOT TRUST THE CLOCK ON YOUR COMPUTER!!! IT IS NOT THE SAME AS THE
CLOCK ON THE TURNIN SERVER. MAKE SURE YOU OPEN A TURNIN PAGE AND REFRESH IT IF
YOU WOULD LIKE TO KNOW THE CURRENT TIME. REMEMBER THAT LAB PRACTICALS ARE 8%
OF YOUR GRADE. DO NOT PUSH THE TURNIN TIME BECAUSE IF YOU MISS THE TURNIN, YOU
ARE OUT OF LUCK..
You may not use ANY reference material at all and, should I even need
to specify that this includes web, IM, chat, email, book, previous code written
by you,
code written by anyone, etc. You may not look at ANY reference while
doing this lab practical. You may only look at this web page containing the
lab practical, electronic turnin,
and your code that you are currently writing for the practical.
Second Task - Mid-Quarter Evaluations
Please fill out an anonymous review of the course. The
link is available
here.
Please make sure you select cs14 in the "select course" drop down box.
We would like you to answer the following questions, so that
we can put on a better course for you:
- Comments for/about the instructor (Ann Gordon-Ross)
- Comments for/about your TA.
Please include your TAs name in your response.
- Do you attend the AEW workshop with Jimmy? If you do, give comments
about the workshop and Jimmy.
- Comments about the in-lab exercises
- Comments about the programming assignments
- Comments about the quizzes
- Comments about the lecture homeworks
- Comments about the in-class exercises
- When did you take CS 12 / attempt CS 14 before? If you took CS 12 at another
school, tell us what programming
language and development platform was used, and whether it was
difficult to make the transition.
- What grade are you hoping to earn in this course? (Please be honest, it
is perfectly alright to not expect to get an A in every course which is why
a D- is a passing grade)
When you are done, show your TA the "Thank you page" and you'll be marked
down for 1 point. The evaluation must be completed during lab time.
Third Task - The Standard Template Library - STL
For this lab you will be working alone. There is a lot to do during this lab
section and if you do not finish during lab time, you may finish outside
of lab. The lab is due 24 hours after your lab section ends. However,
try to finish during your scheduled lab time and demo your program during
lab.
STL is a template based library of generic C++ data structures and algorithms
that work together in an efficient and flexible fashion.
I can guarentee that STL will be your best friend throughout your
C++ programming career so please take a lot of time to become aquainted with
it. This lab will help you do that through 3 short exercises (you will be
writing 3 seperate programs but to make things quick, you may
write all of your code in the main function using 1 file and no makefile).
In this lab
you will learn about sequence containers, container adapters, and
iterators.
There is a fantastic reference for STL available online
here. You may want
to refer to this while working on your lab assignment.
Sequence Containers
Containers are objects that store other objects. You will be looking at the
vector, deque, and list containers. The declaration of a container
defines the type of object it will hold (much like the declarations
you have done previously for your own template classes).
Containers store user defined objects as data members. For example, you may
declare a lists like this:
list<int> intList.
list<Node> nodeList.
list<anyClass> anyList.
You choose the
appropriate sequence container based on what your program will be doing. You
will be looking at 3 sequence containers:
- vector<T> is a standard array that can change size transparently as
needed (any increase in size is added to the end of the vector).
Internally, it is a contiguous array of elements and you can
perform all operations on vectors that you would normally perform on
an array ([] accessing). Unlike traditional arrays,
vectors are good because their size can grow
transparently, however the size may only grow from the end. Because of this
vectors are good for any LIFO type application
- deque<T> is a queue data structure that efficiently inserts and removes
objects from either end. Like vectors, the elements are stored in
contiguous locations in memory. Unlike vectors that can only grow
efficiently when inserting at the end, a deque can efficiently expand from
the beginning
and the end. The deque may also be accessed through the [] operator
as with the vector container. Deques are good for any FIFO type
application.
- list<T> is a doubly linked list and is exactly like the lists we have
been studying in class.
The list can grow from any location by pointer manipulation except you
don't have to do the pointer manipulation. You
can't access elements in the list using the [] operator.
This will give you a graphical representation of how
the different containers are layed out in memory
When choosing a container, you must predict what types of operations you will
be doing and analyze the cost of each container. Here
is a table showing the costs of various operations for each container type.
Based on what you learned about the memory layout of each container type,
take some time to understand the costs in this table and why each operation
has the specified cost for each different container. If you don't understand,
make sure to ask your TA to explain because you will be quizzed on this
when you check out (you will need to do this before the end of
lab period.).
Every container type has many functions predefined for your use. For example,
the following declares a list of ints and inserts 2 numbers and removes them
(the function names are quite self explanatory):
list<int> a;
a.push_back(1);
a.push_front(5);
a.pop_front();
a.pop_back();
Iterators
When manipulating the contents of containers, you will find yourself heavily
dependent on iterators. Iterators fulfill the same role in your program
as pointers, and whereas they are not exactly the same as pointers, you may
use the concept of a pointer as an easier way to grasp the concept of
an iterator. Like pointers, they are defined in terms of what they do.
For instance a pointer to an item of type T is declared as "T* ptr"
and an iterator to a container is declared as
"container<T>::iterator i."
Like pointers, iterators are dereferenced using the * operator. Iterators are
used to get back the data that you have inserted into the list.
for (list<int>::iterator i = a.begin(); i != a.end(); ++i)
cout << *i << endl;
You can also insert and erase elements using iterators:
a.insert ( a.begin ( ), 6 );
a.erase ( a.begin ( ) );
Both the begin() and end() functions return an iterator. Begin() returns an
iterator to the first element in the list and end() returns an iterator that
is 1 location past the last element in the list. You WILL want to memorize
this.
Container Adaptors
Container adaptors are simply classes that act as a wrapper around another
class. Container adaptors are classes that encapsulate an existing container,
and provide a new user interface. You will look at the queue and stack
container adaptors. For instance, stacks and queues both have push
and pop functions that operate differently depending on whether or not you
are using a stack or queue. For that reason, the push and pop operators
are not included as functions for containers. However, a container adaptor
can define these functions for you. When declaring a container adaptor, you
may choose any container as you like for the internal representation. (Notice
the different and precise syntax of the following)
- Declaring a stack container adaptor using a vector container:
stack< int, vector<int> > a;
- Declaring a stack container adaptor using a list container:
stack< int, list<int> > a;
- Declaring a queue container adaptor using a vector container:
queue< int, vector<int> > a;
- Declaring a queue container adaptor using a list container:
queue< int, list<int> > a;
Now consider the following code. The push and pops will work
correctly based on the container adaptor. Other container adaptor
specific functions are implemented as well.
stack< char, list<char> > s;
queue< char, list<char> > q;
s.push(a);
s.push(b);
s.top(); // gets reference to b
s.pop(); // pops b
q.push(a);
q.push(b);
q.front(); // gets reference to a
q.back(); // gets reference to b
q.pop(); // pops a
For the most efficient program possible, you must choose your container
wisely depending on what your program operations will be.
First Lab Program - 3.5 points
Write a program using the STL list (remember to #include <list>). Call
your file "part1.cc" Your
program should read in integers from the standard input (using cin) until
the user presses Ctrl+D (to signify EOF). Store each value at the end of the
list. (If you don't know how to read until EOF, read
this.
Next, insert two more values to the list. Insert the value 10 at the head
of the list and insert the value -1 at the end of the list
Print the list
Pop the 10 and the -1 off the front and the back of the list.
Print the list again
Demo your program.
Second Lab Program - 2 points
Redo part on using a vector instead of a list (remember to #include
<vector>). Name your file "part2.cc"
Demo your program
Third Lab Program - Recognizing Palindromes - 2 points
A palindrome is a string of characters that reads the same from left to
right as it does from right to left. For example, noon and racecar are
palindromes. You should know by now that you can use a stack to
reverse the order of a occurances and you can use a queue to
preserve the order of occurances. With this you can use both
a stack and a queue to determine whether a word is a palindrome or not.
Write a program to determine whether or not a word is a palindrome. Name your
file "part3.cc" Your program will read in 1 word from the standard input
(using cin) and output whether or not it is a palindrome. You must read
in a string but remember that a string is an STL class and you may use
the [] operator to access each character. You will
use the queue and stack container adaptors to analyze the word.
Make sure to choose an ideal
container for your queue and stack. You will receive 1.5 points for
correctly determining whether or not a word is a palindrome. You
will receive .5 points for choosing the correct containers and being able
to explain why you used those containers. Insert a comment into
your code near your stack and queue declarations explaining your
container choice (we don't want you saying this answer out loud or else
you will give the answer away to others). To receive these points,
you MUST have the comment
For .5 points extra credit, make your program determine if a line of words
with spaces
is a palindrome (for example, "Race carrot or race car" is a palindrome.
To get this 1 point, your palindrome tester must be case insensitive which
means that you will need to figure out how to do this (your TA will
not tell you).
Point Breakdown For Lab Assignment
Since there was a lab practical this week and you are working alone, this lab is
due 24 hours after the end of your lab period.
Remeber to compile your code using the flags "-g -Wall -W -Werror -pedantic".
- 2 points - Attendance - Lab attendance will be 20% of the grade for each
lab. You will receive 1 point when the lab begins and 1 point when the lab
ends. Attendance will be taken during the first and last 5 minutes of the
lab period
- 3.5 points - First lab program - STL list
- 2 points - Second lab program - STL vector
- 2 points - Third lab program - Palindromes
- 1.5 points - Correctly determining if a word is a palindrome
- .5 points - Choosing the best container for the container adaptors
and being able to explain why
- .5 points - Quiz question over the runtime costs for various operations
for each container type listed here. You will need
to answer this question BEFORE the end of the lab period.
- +.5 points extra credit - Palindrome tester is case insensitive and works
for an entire line of words with spaces.
- Deductions:
- -1 point - If both partners turn in the code. There should
only one turnin per group
- -5 points - Turned into the wrong lab section.
- -1 point - No name on work turned in
- -5 points - Code not turned in at all. This deduction also applies to
turnins that do not contain a the partners name (only the name that is not
on the turnin will have 5 points deducted. The person that actually turned
the code in will only have 1 point deducted if their name is not on the
turnin).
- -5 points - If your currently assigned partner is in lab and you do not
work together.
