Algorithm Design: Foundations, Analysis, and Internet Examples
by M. Goodrich and R. Tamassia.
Office Hours: MWF 9:25-10:25am.
Other days and times
by appointment.
You are welcome to drop by my office at any time, but
be aware that there will be occasions on which I will be unable to see
students. Also, though I usually keep
my office door open during office hours, at other times I may
keep my door closed for either noise or climate control purposes. You
should be sure to knock before concluding that I am not in my office!
Course Summary: This is a 4 credit course on computer
algorithms. We will discuss and participate in the design and analysis of
algorithms and their associated data structures. This is among other things a
course in advanced problem solving. Algorithms will be motivated by examples
from several application domains, including (but
not
limited to)
operating systems, network coding, security, bioinformatics, and computational
geometry.
Specific
topics will not be revealed in advance, but instead will be revealed at
the time they are covered so that students gain a true problem solving experience.
(In English: If you read about these topics beforehand, then you're not really
solving the problem but instead just parroting the solution).
Pre-requisites: The pre-requisite for this
course is CMSC 222 (Discrete Structures for Computing).
In addition, a comfort with mathematical reasoning and the Java programming language are
essential.
I expect that you are familiar with the following data structures
and concepts covered in the data structures and discrete mathematics courses.
Data Structures
stacks
linked lists, doubly linked lists
dictionaries and hash tables
trees, including binary trees, search trees, and various balanced trees
heaps
merge sort, heap sort, insertion sort
Mathematics and Proof Techniques
basic probability (random variables, expected value, variance, conditional probability)
matrices and basic matrix operations (addition, multiplication)
induction (know it well!)
proofs by contradiction and proofs by contraposition
summation notation, arithmetic and geometric series
Most of these topics are covered in Chapters 1-3 and parts of Chapter 4 in the text. Though we will use two lectures
early in the semester to review some of the important concepts from this material, this will merely be review. I thus recommend that you take the time
to (re)familiarize yourself with any of these concepts with which you are not comfortable.
Class Formats: I use two basic class formats for this course. The first is expository: I present material from either PowerPoint slides
(which will be posted on the web page prior to lecture) or at the blackboard. The second involves problem solving.
Specifically, I will pose a problem (perhaps more than one), and
as a class we will develop and analyze potential solutions. Some of these problems will have relatively straightforward
solutions, some will have partial solutions, and some will be research problems that have no known solution (or solutions that
are unsatisfactory at present). You won't know which are which when we start the problems. (In a real world situation, you might
very well find yourself in such a situation.)
Attendance Policy:
Regular attendance for the entire class time is
expected! If you should miss a class due to illness,
you are responsible for obtaining class notes!
(That is, I will not give you a private encore of the lecture).
Labs:
There is no formal laboratory component to this course. Instead I will hold
a special office hour each week for the exclusive use of CS 315 students.
Grades:
Grade Component
Date
Percent of Grade
Exam 1
distributed February 15, due February 22
15%
Exam 2
distributed March 28, due April 4
15%
Quiz Avg.
N/A
15%
Programming Assignments Avg.
N/A
20%
Final Programming Project
due April 25
15%
Final Examination
distributed April 25, due May 2
20%
My Grading Philosophy: When it comes to the final course
grade, I am merely the scorekeeper. I feed the value of each
component of your grade into a computer program, and it gives me the
final average that determines your course grade.
If you have turned in (on time), say, three of five programming projects,
and done them well, my grading program will still give you a programming project
average of zero because you failed to turn in two
projects. I'm not
saying this to intimidate you, but to be clear that there are
consequences for failing to complete assignments, and you should be
aware of this up front.
My "Managerial" Philosophy
Some professors will chase you around reminding you that you have
failed to turn in an assignment or asking why you've missed class. This is not my style.
I treat you as the responsible adults that you are.
If you perform poorly on an exam, I
expect that you will come to my office hours (or make an appointment
for another time) to discuss any questions you may have on the material.
If you are having problems with a programming assignment, I expect that
you will bring these problems to my attention far enough in advance of
the
deadline so that you have time to absorb whatever advice or hints I give,
implement them, and still turn the project in on time. And it is not
my responsibility to be available for the entire afternoon before a
project is due because you waited until the last minute to work out
the kinks. So you are aware of this up front, MOST of the time
spent on your projects will be devoted to working out the kinks!
It's just the nature of the beast.
Also, I apologize to
the 99% of you who are responsible enough to know these things
and all of the similar rules on this page without me having to put them
down in writing. Unfortunately, every semester there seems to be
one student who needs this kind of clarification, and it is for them
that I spell things out.
Exams: All examinations in this class will be take-home.
There is
no limit on the amount of time you may spend working these exam,
provided you submit the completed exam on time. Unlike homework
and programming assignments, you may not receive any assistance
in solving the problems, with the exception of advice I may offer.
The Other Student Criteria : When grading tests and
homework, I use the Other Student Criteria
(OSC). All solutions must meet this. The Other Student Criteria
states that a solution should provide enough written explanation
so that another student in the class (who could not complete the
assignment) could read the submitted material and, without
asking questions, understand a correct answer.
My ``take-home exam discussion policy": Once a student has begun a take-home exam,
I will answer (for that student) only those questions that concern clarification of the intent of a problem. That is,
I will not answer questions that seek to determine whether the problem was done correctly, or whether a particular approach is
wise (or unwise).
Missing Exams :
On rare occasions a situation will arise where a
student cannot take a test during the specified time. In this case,
the student should contact me well before the scheduled exam time. In
the event of a sudden illness or emergency,
it suffices to notify me sometime prior to the examination time (all numbers
listed above are equipped with answering machines or voice mail, and
I do check them before exams).
Unless previously negotiated with me, any person who fails to turn in a take home exam by the assigned
due date and time will receive a zero grade for that exam. The only
exception is for extreme sudden illness or emergency.
Consulting Old Exams:Prior to the distribution of
take-home exams, you may consult old exams from any class (regardless
of professor). Once the take-home exams
have been distributed, old exams can no longer be consulted.
Quizzes: There will be short (about 10 minute) quizzes at the start of each
Friday class, with the exception of those weeks during which take home exams have been distributed.
(For this class this means no quiz on either February 22 or April 4).
Questions will be chosen from homework problems corresponding to the material covered the prior week (so, for example, the quiz on January 25 will cover material that we discuss the week of January 14-18). I create quizzes under the assumption that you
have completed all the assigned homework. Thus a problem that requires an hour of analysis, but only five
minutes of writing once the solution is understood, is fair game for a quiz.
Homework: I have listed, on the homework page of the class web, all assigned problems for each section in the
text. From time to time, additional questions may be assigned on a given topic. Though homework will be assigned each week, it
will not be collected or graded. You should do them all, however, since the quiz problems come directly from the homework, and since
all homework problems, no matter how difficult, are fair game for quizzes and exams.
Programming Assignments: There will be three programming assignments
in addition to the final programming project.
You will be required to write these programs using the Java programming language.
Unlike some of the
lower level CS courses, in this course (and any other senior level course)
a program must
both compile without errors and
run according to specification to receive any credit!
There are a number of
other factors that may influence the grade that a program receives. Here are
some of them:
Is the program "user-friendly"? That is, does the user have
to guess at how to use the program, or does the program somehow
provide this information to the user?
Is the code readable? (One letter variable names, other than for loop indices,
are strictly prohibited!)
Is the code well documented? Every program assignment grade will
have a significant documentation component. No one should have to dig through
poorly documented code (try it some time)!
Is the code "well-structured"?
Is the code robust? For example, how does the program
react if the user supplies the wrong number of command line arguments?
The good folks at Sun have written a nice document on Java
code conventions.
I suggest you take a good look at it. You should also be aware of the following:
When I grade your programs, I use the emacs editor. So when
I judge the code for readability, it is in this context. If you
choose to use an IDE such as Kawa or JBuilder, your code may
not look very good in other editors. Both of these have features that
allow you to reformat your code (so it will look good anywhere), and
I encourage you to use them (if you use an IDE). Regardless, if
you code using an IDE and it ends up looking bad in emacs, then
you get a bad style grade. That is, it is your responsibility to
ensure that your code looks good in emacs.
If you happen to submit an old version of your code by accident, or
you submit binaries instead of source code, or you've mistakenly misnamed
one of your classes the same thing as a Java built in class (which causes it
to fail to compile on my machine even though it compiles on yours) then
your code is graded accordingly. That is, if it doesn't compile on my
machine, it gets a zero grade. If it's an old version, that's what I grade.
If it's binary rather than source code, then it gets a zero grade.
Bottom line: You should consider me a client who is purchasing your code. As
the developer, it is your responsibility to ensure that I receive the latest
working version of
your
source code and
that
it compiles
correctly
on
my machine.
The version of the code you submit to me should have all debugging output
removed. This does not mean that you have to remove the debugging code from
the source. It does mean that when the code runs, I should not be getting
debugging output.
Using Java Swing classes:Some of the programming projects will require
that you are able to use some of the Java Swing classes. For those of you who
are
not
familiar with these, they are the classes that allow Java coders to
build graphical user interfaces. The Swing skill level required for the
project will not be terribly advanced, but it is a good idea to
get a jump on this now. The best source for introductory Swing information
is the text
The JFC Swing Tutorial: A Guide to Constructing GUIs by Kathy Walrath and
Mary Campione. As you can tell by the link, the entire text is available (for
free)
online. Also,
I have a hardcopy of it in my office, as well as a CD which contains the
entire text (and which you may borrow to copy or download). Unfortunately,
it seems that every Swing reference promotes a different technique for coding
using these classes. For this reason, one of our first lectures will discuss
a good consistent style to use when building relatively simple GUIs using Swing.
I expect that all students will follow this. You are free to use your own techniques
if you like (I know that some of you have used these classes for a while now)
but if you follow your own technique and get stuck, you're on your own!
Program Submission Procedure:
Programs are to be submitted to me via email (dszajda@richmond.edu). All
projects consisting of more than a single file must be sent
as a jar file. The jar file must include:
ALL source code you have written for the project.
ALL .java or .class files needed to build the executable,
including any source or class files that I may have given you to aid
in completion of the project.
The idea is that I should be able to unpack your jar file, compile
a single source file, and then run the program. I should not need to
add other files to get your project to compile.
The Final Programming Assignment:
The final programming project may or may not require that people work in groups.
I am well aware of the potential difficulties that may arise with such a format,
but
I feel that the benefits gained from implementing a substantial project outweigh
the potential costs of dealing with difficult group dynamics. If it is a group assignment, I will allow
you to (for the most part) form your own groups. Groups will be limited to
four members or less, with groups of size four optimal. You will not need to
choose groups until just before Fall Break, but be especially careful to
choose wisely, since I will not be sympathetic to any complaints at the end
of the semester about how your group-mates failed to do any of the work! Working
in groups is an essential part of computer science (whether working in academia
or industry), so consider this necessary career training.
The Programming Environment: We will be coding in the
Java programming language, and because of the relative portability
of Java, you are welcome to program using whatever operating
system, programming environment and/or editor you choose.
All programming assignments must satisfy and/or include the following:
They must be written in Java, and specifically in a version of
Java at or later than Java 1.5.
They must compile using the compiler provided with the
current Sun Java Standard Development Kit.
If a project consists of several source code files, then the
project must be submitted as a single zipped or tar file which
is structured so that all source files are in a single directory
(this saves me from having to fool with my classpath for every
potential class subtree I receive).
All files contained in the tar file, or the single
file you submit if there is just one source code file,
must be in ASCII format.
This should not be a problem, since you will only be submitting
source files as opposed to class files.
Programming Help: I am happy to discuss programming and debugging techniques, as well as the
semantics of particular functions calls. I am happy to direct you to appropriate packages. And I will
at times provide you with shell code (such as when using Swing for the first time) so that you can work
from a solid foundation. With regards to programming, I am in general happy to help you in whatever way
is necessary. I will not, however, debug your code for you! If you describe your programming issue
with me, I will be happy to suggest potentially useful debug strategies.
But debugging is an important part (and in fact the majority part) of the programming process. As such, you
need to be comfortable with doing it on your own!
General Assignment Policies:
It is computer
science department policy that No late homework/programming
projects are accepted! Do not test me on this (you won't like
the outcome). If, for example, you have spent the last 12 hours
working on an assignment and it's done beautifully, but you left it in
your dorm room, or brought the wrong notebook to class, or emailed it
to the wrong address, or any of a number of similar laments, then you
have just learned a valuable lesson on dealing with the consequences
of your actions (however unintentional they may be)!
At the end of the semester, any student who has missed
two or more programming assignments will receive a
programming component grade of zero for the course!Similarly, any student
who
has
missed two or more quizzes will receive a zero for the quiz average component of the course grade! Though
it's not an official policy, no student has passed my course
after receiving either a zero programming project component grade or a zero quiz average component grade.
Penmanship: If I have even the least bit of difficulty interpreting (because of poor handwriting or organization) your solution to a problem on any written assignment (including take-home and in-class exams), that problem will receive a grade of zero! If your penmanship is poor enough that this causes you concern (for many, it does), then I recommend you learn how to use a typesetting program (i.e. Latex or Word) and hand in only typeset solutions.
Collaborating on homework/programming assignments: Programming projects
and homework may be discussed with others subject to the
``Empty Hands'' policy---
you may freely discuss ideas and approaches with other students
subject to the restriction that each student must leave the discussion
without any written or otherwise recorded
material. In your homework write-up or source code, you must also
document any person or source that you consulted for that project.
Failure to comply with this policy will be treated as an Honor
Code violation.
Please also be aware that it is one thing to watch and understand
a person solving a problem and another thing to be able to solve
the problem yourself. Since it will be necessary to answer
test questions without the aid of books or notes, I highly recommend
that you write final homework solutions without using either.
One final note: some, but not all, of the programming assignments
for this semester will have been assigned in previous semesters.
While you may consult previous class members concerning projects,
you are not permitted, under any circumstances, to receive
or view either hard copies or electronic copies of all or parts
of their project submissions! You can use your friends to
get help, but they should not be providing you with their code
(just as in an English class, you might discuss the works of Dickens
with a friend, but should not use the paper that they submitted
as the basis for your own submission).
A Few Other Points:
READ THE TEXT!!!! I cannot stress this enough.
The text is both informative (at the appropriate level)
and readable. READ IT!!! I will sometimes only
touch on a topic in lecture,
while the text discusses it in great detail. Specifically,
if I mention that you are
to read a specific section of the text, you are responsible for all of
the material in that section regardless of whether I have even mentioned it
during lecture!READ THE TEXT!!!!
It's really a great way to learn.
Any lecture, no matter how polished or well prepared, will proceed at a pace
that is too fast for some in the audience, and too slow for others. When you
read a text, you are given the opportunity to absorb the material at your own
pace. READ THE TEXT!!!! You'll
do better in this course and gain a better grasp of the subject
if you do.
The Class Web Page: Obviously you know what it is or you wouldn't be
reading this. Nonetheless, I list it here for completeness.
The URL is http://oncampus.richmond.edu/~dszajda/classes/cs315/Spring_2008/main.html.
It is also accessible through my home page: http://oncampus.richmond.edu/~dszajda.
You are expected to the web page regularly, since I
often post announcements there. In addition, there
are some helpful links.
Class Discussion Group: I'll be setting
up a Blackboard account for this class so that you can use
the discussion board. I encourage you all to
use it to discuss programming difficulties and other course related
material and issues.
Blackboard: There is a blackboard page for this course. I use it to record your grades. I
mention this so that you are sure to check it from time to time, to make sure that the recorded grades
match the grades you received.
Academic Honesty:
I take it VERY seriously,
and so should you. If I even suspect that a student has violated the
University Honor Code, I will not hesitate to report this to the
appropriate authorities.
Syllabus: The topics are not listed in the order we will discuss them (nor is this an exhaustive list).
Asymptotic Analysis
Review of Basic Data Structures (heaps, balanced binary trees)
Selected topics concerning sorting
Fundamental Techniques: The Greedy Method
Fundamental Techniques: Divide-and-Conquer
Fundamental Techniques: Dynamic Programming
Fundamental Techniques: Backtracking and Branch-and-Bound
Graphs and graph traversals
Weighted Graphs
Network Flow and matching
Text Processing
Distributed Algorithms
Computational Geometry
NP-completeness
Approximation algorithms
Preliminary Calendar:
January
14
16
18 Programming Project 1 Assigned
21
23
25
28
30 Programming Project 1 due
February
1 Programming Project 2 Assigned
4
6
8
11 No class
13 No Class
15 Programming Project 2 due; Exam 1 distributed
18
20
22 Exam 1 due
25 Programming Project 3 Assigned
27
29
March
3
5
7
10 Spring Break
12
14
17
19
21
24 Programming Project 3 due
26 Final Programming Project assigned
28 Exam 2 distributed
31
April
2
4 Exam 2 due
7
9
11
14
16
18
21
23
25 Final Programming Assignment due; Final Exam distributed;
Last Class
Douglas
C. Szajda
