UCR CS 141: Intermediate Data Structures
and Algorithms
Summer Session I 2004: June 21st - July 23rd
Overview
The intent of CS 141 is to formalize and solidify the knowledge you
have gained in CS 10/12/14. CS 141 focuses mainly on two areas:
algorithms/proofs/theory/logical thinking, and programming fluency.
Basic Information
Lecture Information
Grading System
Topic Schedule
Assignments
Course Policies
Basic Information
Instructor:
Titus Winters (titus@cs.ucr.edu)
Office:
Surge 281
Office hours: T 12:45-1:45, R 3:30-4:30
I am online much of the time, and most questions can be answered via
email, so please do not hesitate to ask me questions this way. If you
need to speak in person and cannot make scheduled office hours, please
let me know so we can make an appointment.
Teaching Assistant:
Luke Keppler
(lkeppler@cs.ucr.edu)
Office hours: TBA
Lecture:
Monday - Thursday, 2-3:30pm in Olmsted 1122.
Please note that attendance is strongly recommended, as 5% of
your course grade will be based on brief pop quizzes held at the
beginning of the period.
Lab:
Monday 5-8pm - Surge 283
Textbook:
Michael T. Goodrich & Roberto Tamassia:
Algorithm Design: Foundations, Analysis, and Internet Examples
Wiley and Sons, 2002.
Course Mailing List: CS 141 Mailing
List
You are responsible for everything that is sent to the course mailing
list, and are expected to check your email no less than once every 24
hours, every day.
Course Grading:
Grading for this course will be as follows:
- Final - 30% - The final will be held from 1:30-3:30 pm on Friday
the 23rd of July, and will be cumulative
- Midterm - 15% - There will be one midterm, held in class on July
8th (end of the 3nd week).
- Programming Projects - 20% - There will be four programming
projects, due every Tuesday (except the first week) at 8pm. Check the
policy on late submissions.
- Labs - 10% - Lab assignments will help you understand hands on
much of the material for the course. Labs will generally be done in
partners and will normally be a short programming assignment. Lab
attendance is mandatory. When you finish your lab assignment, you may
work on other CS 141 related work.
- Pop quizzes - 5% - Pop quizzes will be used to encourage punctual
lecture attendance. The lowest two grades here will be dropped, which
is intended to allow you some time for sickness, family emergencies,
and the like. I will not allow these to be made up, or excused,
without a written excuse from a doctor or someone higher in the
University food chain than I.
- Written Homework - 10% - Written homeworks will be assigned every Monday,
and will be due the following Thursday. These will be turned in
digitally through the online turnin system. The only file formats
we will accept are plain text (.txt), PostScript (.ps), and PDF. It
is highly recommended that you figure out how to generate one of these
file formats when starting your assignment, rather than 5
minutes before it is due.
- Quizzes - 10% - There will be brief (~20 minute) quizzes throughout
the quarter. You will be given at least 24 hours notice of these
quizzes.
Letter grades will be assigned roughly according to the regular
90/80/70/60 scale. +/- grades will be given.
Topic Schedule:
Very much subject to change as the quarter progresses.
- Lectures 1/2: Introduction, course policies and organization.
What is proof? C++ refresher / review.
- Lectures 3/4: Oh, Theta, Omega. Recurrence
relations, beginnings of Divide and Conquer.
(closestPair)
- Lecture 5: Quiz 1 (Solution)
- Lectures 5/6: Divide and Conquer / Exponential algorithms (divideCoins.cc merge.cc rook.cc)
- Lecture 7: Greedy algorithms.
- Lecture 8: Dynamic Programming
- Lecture 9: 4th of July Holiday, no lecture
- Lecture 10: Dynamic Programming (cont)
- Lectures 11/12: Midterm Review (lcs.ss), Midterm
(Study Guide) (Solutions)
- Lecture 13: Midterm Recap
- Lecture 14: Graphs: terminology and representation,
Search.
- Lectures 15/16: Network Flow, more graph problems
- Lectures 17/18: Skip Lists (skiplist.cc),
Splay Trees (splay.cc), and other Unusual Data
Structurs
- Lecture 19: Basic Ciphers and Cryptography
- Lecture 20: Final review (Study Guide)
Assignments
Lab Schedule
Course Policies
- Material Covered: You are responsible for all material
covered in lecture, assigned reading, lab, programming projects, and
on the mailing list.
- Academic dishonesty and collaboration policy: I enjoy
catching cheaters, I usually get at least 10-20% of the class on
cheating each quarter, and when I
do I almost always fail them in the course. So, simple rules:
don't cheat, plagiarize, or collaborate without permission, or you
will be dealt with strongly.
If you suspect someone in the class of cheating, please help us rid
the world of this scourge by reporting it anonymously at https://www.cs.ucr.edu/cheating/.
The rules regarding collaboration are as follows:
- Midterm, final, quizzes: No collaboration. Duh.
- In-lab exercises: Discussion allowed and encouraged, helping one
another debug strongly encouraged. You should be working with a
partner, but you are encouraged to help everyone that you can.
- Programming projects: Discussion allowed, but stay away from one
another's code. When discussing the a problem, avoid talking in code,
and avoid taking notes. If you filter the discussion through your own
memory, you are very unlikely to submit code that "accidentally"
indicates you collaborated. This is for your own protection.
- Written homework: Study groups are highly encouraged, but write
out your own solutions. Your work should not be identical to one
another's.
- Regrade Policy: Regrade requests must be submitted in
writing within two lectures of the material being returned (or
available for pick up, in case you don't pick up your results.) Any
clerical errors in posted grades should also be reported within one
week of posting if possible, and certainly before the last week of class.
- Cell Phones: Turn off your cell phone. I reserve the right
to dock the grades of or publicly embarrass repeat offenders
- Time Requirements: This is a four unit course, running at
double-speed, and WILL take up the alloted 24 hours / week that
entails. I will try to prevent it from being significantly more than
that on average, but in the end it is up to you to manage your
time.
- Lab: Lab is required (we will be taking attendance at the
beginning and end of each period), however, the lab assignments will
be vastly easier if you attend.
- Early/Late Policy: For programming work, we will accept
work up to 2 days late for 5% / day. Thus it is much better to finish
up a nearly-complete assignment than to turn in unfinished work. For
each day EARLY, you get 3% bonus up to 9%.
- Style: Style and documentation will count for about 30% of
your programming project grades. More information on this can be
found in the course style guide.
UC
Riverside Department of
Computer Science & Engineering. All rights
reserved.