CS 146: Data Structures and Algorithms, Spring 2006
Contact Information
Instructor: David Taylor
Office: MH212
Office Hours: Monday/Wednesday, 9:45-10:15, 13:20-14:05, 16:30-17:15,
20:15-20:45, or by appointment.
Email: taylor "at" cs.sjsu.edu
Phone: (408) 924-5124 (email works better)
http://www.cs.sjsu.edu/faculty/taylor
Course Website
The course website can be found at http://www.cs.sjsu.edu/faculty/taylor/term/spring06/CS146/.
This site contains a link to this greensheet, a schedule of
classes thus far, and a tentative schedule of future class topics,
along with other information and announcements.
Course Goal and Description
Goal: To examine various ways to represent data used by programs and to
compare these representations in terms of their memory requirements
and the resulting program execution times.
Topics covered will include advanced tree structures, directed and
undirected graphs, advanced searching and sorting techniques, priority
queues and heaps, dictionaries, and mathematical tools and techniques
(recursion, recurrence relations) useful for the design and analysis
of data structures and algorithms.
Prerequisite Courses
If you are already enrolled in the course, you should show me that
your prerequisites have been satisfied. Further, I will not give out
any add codes without first seeing prerequisite proof. If you do
not show me prerequisites by the end of the second week of classes,
you may be dropped from the course. You should show me grades
for CS46A, CS46B, Math31, and Math42, or their equivalents on a
San Jose departmental course equivalence form. You must have a C- or
better in each course.
Prerequisite courses and what they covered:
CS46A: Iteration and recursion
CS46B: Stacks and queues, lists, dynamic arrays, binary search
trees. Iteration over collections. Hashing. Seaching, elementary
sorting. Big-O notation. Standard collection classes.
Math31: Sequences and series.
Math42: Sets, logic, proofs, induction, combinatorics, probability,
and equivalence classes.
Textbooks
This textbook is very widely used, and I hope it will come in handy
beyond this course.
Introduction to Algorithms, 2nd Edition
Cormen, Leiserson, Rivest, and Stein
ISBN: 0-262-03293-7 MIT Press, 2001
You can find errata (bug reports) for the book
http://www.cs.dartmouth.edu/~thc/clrs-2e-bugs/bugs.php, for
whichever printing of the book you get.
Course Objectives
- To ensure that students are familiar with ways to implement
elementary data structures and their associated algorithms.
- To introduce students to the implementation of more complex data
structures and their associated algorithms.
- To acquaint students with advanced sorting techniques.
- To teach students how to determine the time complexity of algorithms.
- To introduce students to algorithm design techniques.
Student Learning Outcomes
Upon successful completion of this course, students should be able to:
- Understand the implementation of lists, stacks, queues, search trees,
heaps, union-find ADT, and graphs and be able
to use these data structures in programs they design
- Prove basic properties of trees and graphs
- Perform breadth-first search and depth-first search on directed as
well as undirected graphs
- Use advanced sorting techniques (heapsort, mergesort, quicksort)
- Determine the running time of an algorithm in terms of asymptotic
notation
- Solve recurrence relations representing the running time of an
algorithm designed using a divide-and-conquer
strategy
- Understand the basic concept of NP-completeness and realize that they
may not be able to efficiently solve all
problems they encounter in their careers
- Understand algorithms designed using greedy, divide-and-conquer, and
dynamic programming techniques
Class Participation
Class partiticipation and feedback are very important to keep the
course interesting. If I am covering material too slowly or
quickly, or if I am not clearly explaining things, you must let me
know. I prefer an interactive learning environment. If you
disagree with something I say, speak up. Argue with me in front of
the class. It will make the class better, and right or wrong,
constructive interaction will not not hurt your grade. If you are
correct, clearly my mistake should be corrected. If you are
incorrect, probably I have not explained something clearly anyway, and
at least half of the class is confused by it. Point it out right then
and there. I reserve the
right to improve a student's grade by up to 1/3 grade due to class
participation.
Grading
Homework: There will be weekly homework assignments, which may
include reading, written assignments, and programming assignments.
Written assignments:
Unless specified as an individual assignment, written assignments may be
done in groups of up to three, with one homework turned in per group,
and all names on the front page. Each of you should feel confident
that you understand everything on your group's submission. (If you
understand a question best among your group, nothing will make you
understand the material as well as teaching it to others.) The lowest
1/6 of homework grades for each person will be dropped for the
semester.
You are encouraged to start each written problem independently, and
spend some time on each question. Then, get together with your group,
discuss all questions, and write them up together. Your group may
change from homework to homework. No group should be larger than 3.
Most of your discussion should be with people in your group.
You may generally discuss problems with other students as well, but
not to the point of working out specific answers. Therefore, I
don't expect that any group answer will look too similar to another
group's answer.
Besides the given course textbook and me, all sources used to help
in the homework (other texts, other people) must be referenced
properly. Failure to properly reference is considered cheating.
When you discuss programming assignments with people,
this should be referenced on your written assignments too. Please
do not use web-sites to help you with your homework or programming
assignments, other than to find other references (papers, texts).
I realize that there are worthwhile sites on the web, but I have
sometimes found that students get into trouble, "borrowing" a bit too
much from other sites. So, please do not use other websites as
references. (If you think that you have good reason to, please
discuss it with me first.) You absolutely may not use the web to
directly find solutions to assigned questions.
Not all homework questions will be graded. The homework is a tool
for you to learn the material. It is given to help you prepare for
the tests, and for future classes. Some questions will be graded as
just "attempted" or "not attempted", others will be graded more
completely, and others not at all. In total, the written assignments
will be worth 10% of your grade. This is enough to help raise your
grade, but not enough to risk cheating. The
difference in your homework grade from doing it honestly vs. cheating
is probably not worth the risk of being caught, as people have been
caught before, and they have failed the course. Your course
performance will improve if you make a real attempt at the homework.
Late homework policy:
Please submit homework on time. If you have a real reason why the
homework is late, and I have not yet discussed solutions or handed
back homework, I will accept late homework, but once we have had
solution discussions, or homework is passed back (for either section),
it is too late.
Students should attend all meetings of their classes, not only because
they are responsible for material discussed therein, but because
active participation is frequently essential to insure maximum benefit
for all members of the class. Attendance per se shall not be used as
a criterion for grading.
Please do not ask me ahead of time if I will be passing out
solutions in a given class. I do not want to encourage anybody to
not turn in homeworks when due, I only want to encourage people to
work on homework in general. As of right now, I plan to have
solutions ready for every due date.
Programming assignments: The programming assignments are to
be done individually, unless otherwise specified. They can be
discussed, but should be implemented individually. More information
will be given at the time of the first programming assignment.
Never use any code you find on the web, unless it is given by
me.
Programming assignments will be worth 10% of your grade.
Additionally, you may be disqualified from getting an A/B/C/D unless
you get at least 4/3/2/1 program(s) to work, respectively. That
is, if you get only 2 programs working for the semester, you cannot
score higher than a C in the class, regardless of test performance.
Tests: There will be two tests during the semester, the first
worth 15% of your grade, the second 20%. Each test question will have
a point value and a ''default'' value of 30%. If the question is left
blank (or the default value clearly circled and the question crossed
out), you get the default value. The goal is to allow you to spend
your time correctly answering questions which you can best answer, and
concentrating on the questions which you find to be difficult but not
impossible. It will also help to avoid the practice of writing as
much random material for a question in hopes that the grader will pick
out the correct parts and give ''pity points'': answers with no
structure which seem nonsensical will receive 0%, even if somewhere in
them there is some partially correct statement. The default option
may be used for at most 50% of the total test points.
Final: The final exam will be worth 45% of your grade. If
you ace the final, it is worth 100% of your grade, subject to having
enough working programs to qualify for that grade. Do not count
on this option: the final will be more difficult than the other
exams, and will be normalized to have a lower average than the
midterms. You still need to get your programs running, as discussed
above in the programming assignments section.
Course grade: After computing numerical grades for each student, letter grades
are assigned on a curve. I generally look for gaps in which no
student has a grade to make changes to the letter grades assigned, to
avoid situations where just a few extra points over the entire
semester would change the grade of a student. I reserve the
right to improve a student's grade by up to 1/3 grade due to class
participation.
Academic Honesty
From the Office of Judicial Affairs:
Your own commitment to learning, as evidenced by your enrollment at
San Jose State University, and the University's Academic Integrity
Policy requires you to be honest in all your academic course work.
Faculty members are required to report all infractions to the Office
of Judicial Affairs. The policy on academic integrity can be found at
http://sa.sjsu.edu/judicial_affairs/index.html, available online
or in hardcopy in the University Catalog and the schedule of classes.
With the lenient homework policy, there is no reason to cheat.
Students caught cheating should expect to fail the course and be
reported to the Vice President for Student Affairs.
No homework assignment answers should be gotten from the web, or from
previous courses. All collaboration must be reported.
If you would like to include in your homework any material you have
submitted, or plan to submit, for another class, please note that SJSU's
Academic Integrity policy S04-12 requires approval by instructors.
Americans with Disabilites Act
If you need course adaptations or accommodations because of a
disability, or if you need special arrangements in case the building
must be evacuated, please make an appointment with me as soon as
possible, or see me during office hours. Presidential Directive 97-03
requires that students with disabilities requesting accommodations
must register with DRC to establish a record of their disability.
Other Information
You are responsible for understanding the policies and procedures
about add/drops, academic renewal, withdrawal, etc. found at
http://www.sjsu.edu/sac.
See Academic Senate Policy S90-5 for information on Student Rights and
Responsibilities, and expectations about classroom behavior.