CAS CS 112 B1 - Spring 2012 - Introduction to Computer Science II
Official Description: Covers advanced programming techniques and
data structures. Topics include recursion, algorithm analysis, linked
lists, stacks, queues, trees, graphs, tables, searching, and sorting.
Detailed Overview This course starts by quickly revisiting, and then building upon,
advanced programming concepts
in Java taught at the end of CS 111, such as recursion.
Then, the main focus of the course is on the design, analysis and implementation
of fundamental data structures used throughout computer science. These include linked lists,
stacks, queues, trees, hash tables, graphs, as well as specialized methods for searching
and sorting. All of our implementations will be in Java.
The emphasis in teaching this course centers around the following:
- Developing elegant and efficient code from an abstract specification;
- Literate programming (writing programs that can be read by humans as well as machines);
- Developing a toolbox of advanced data structures for use in your future programming tasks, and an
awareness of various design patterns that recur frequently in advanced programming;
- Critical thinking about programs and the programming process, which involves:
- Thinking about the best way to plan out the design using object-oriented design and appropriate features of Java;
- Methodical and efficient development of the implementation using step-wise refinement and incremental testing and debugging (using appropriate debugging tools);
- Being able to convince yourself of the correctness of the implementation by mathematical reasoning;
- Analyzing the running time (efficiency) of programs by inspection and mathematical reasoning; and
- Evaluating the efficiency and correctness of programs empirically, by using various tools in properly designed experiments.
Class meeting time: Tues/Thurs 12:30-2:00,
Lab meeting times:
Mon 1-2, Mon 2-3, and Mon 5-6 in the Undergraduate Teaching Laboratory, EMA 304.
Prof. John W. Byers
Email: byers @ cs . bu . edu [preferred]
Phone: 617-353-8925 [do not leave voice-mail; use e-mail instead]
Office Hours: Mon 9:30 - 11 and Thurs 11-12:30, held in MCS 270
Teaching Fellow: Chong Wang
Email: wangch @ cs . bu . edu
Office Hours: Mon 4-5 and Wed 3-5 in EMA 302 (CS Undergrad lab).
Here is the lab homepage.
This course is designed for students who already program with a CS 111 level of
proficiency in Java and a Java IDE (Integrated Development Environment), such as
Dr. Java or Eclipse. If you do not have significant previous
exposure to programming, then you are requested to transfer to CS 111. Please speak to us
right away if you are not sure if your programming background is adequate.
The required textbook is:
Algorithms, (Fourth Edition) by Robert Sedgwick and Kevin Wayne (Addison Wesley, 2011),
ISBN #1-256-46039-7. We will be using a Custom Edition for Boston University tailored for CS 112
that contains most, but not all, of the material in the non-custom version of the textbook, and as a
result, is priced at a discount. Please purchase it from the BU bookstore.
The regular, non-custom version of the textbook is also fine.
- Also recommended is a good Java reference book, such as Building Java Programs
by Stuart Reges and Marty Stepp (Addison Wesley, 2010), or the reference you used for CS 111.
- And, of course, on-line resources, such as the Java API.
We will no doubt drift from any formalized plan, but a
rough schedule of where we are headed is provided in the roadmap below. A more
detailed and continually updated schedule will be maintained on the main course homepage.
- Lectures 1-2: Review of recursion, arrays, and Java basics.
Binary search recursively and iteratively. ADTs, APIs, and data structures.
- Lectures 3-7: Stacks, queues and bags. Java generics.
Linked list data structures. Introduction to O-notation and logarithms
in running times.
- Lectures 8-11: Analysis of algorithms. Sorting.
Elementary sorts, merge sort, quicksort.
- Lectures 12-14: Priority queues and applications.
Searching via symbol tables and dictionaries.
- Lecture 15 (Mar 8): Midterm exam. Do not leave for Spring Break before this date!
- Spring Break
- Lecture 16-18: Trees, binary search trees, balanced search trees
- Lectures 19-20: Hash tables
- Lectures 21-23: Introduction to graphs and their
representations, traversals and topological sort.
- Lectures 24-25: Minimum spanning trees
- Lectures 26-27: Shortest path algorithms
Be forewarned -- the workload in this course will be heavy.
To master the conceptual material covered in lecture and to become expert at
implementing applications built upon basic data structures, there will be
assignments due approximately every week. We will alternate between assignments
covering written and short programming exercises, and longer programming
The course grade will break down as follows:
35% programming assignments.
15% written exercises.
5% participation in class, lab, and on Piazza.
20% in-class midterm exam (most likely in-class on Thursday 3/8).
25% comprehensive final
There will be one eighty minute in-class midterm held during the
middle of the semester in early March, probably Thursday, March 8. The
cumulative final will be held during the normal two-hour final exam slot,
Thurs, May 10 from 9-11AM. Please make your spring break and end-of-semester
travel plans accordingly. In the event of serious illness documented by a
doctor's note, makeup examinations will be given orally.
Homework Assignments and Submission:
Assignments will be due every Thursday. We will alternate between larger
programming assignments and shorter problem sets of written exercises, with
the assignments worth a total of 50% of the grade.
We will post general guidelines
that we will use to grade your assignments. Other
specific guidelines will be provided on a per-assignment basis.
To submit your assignments you must use the WebSubmit program, as in CS 111,
usage of which will be covered in lab.
All assignments will be tested for originality by an
automated software tool.
It is expected that you will attend lecture and the
laboratory section for this course and I will sometimes take attendance at the beginning
of lecture. Some material covered in lecture and lab will not be covered by our textbooks.
I also ask that you arrive in class on time,
since it is highly disruptive to have students flowing in throughout the class
period. Moreover, when students are at a borderline between grades, I will
factor in attendance before making a final determination.
Programming assignments will typically be due Thursdays at 10PM.
Written exercises will typically be due Thursdays at the beginning of class (12:30).
During the course, you will have three opportunities to turn
in an assignment up to 24 hours late with no penalty. At most TWO of these
may be used for programming assignments. No additional time
will be granted, nor will additional late submissions be granted. As you
likely already know, programming a fully functional solution to an assignment
(even after you have mastered the key concepts) can take more time than you
expect, so plan to finish a day or two early.
CAS Academic Conduct Code:
Academic standards and the code of academic conduct are taken very seriously
by our university, the College of Arts and Sciences, and the Department of
Computer Science. Course participants must adhere to the
Conduct Code -- please take the time to review this document if you are unfamiliar
with its contents.
The collaboration policy for this class is as follows.
The last point is particularly important: if you don't make an honest effort
on the homework but always get ideas from others, your exam scores (accounting
for half of your grade) will reflect it.
- You are encouraged to
collaborate with one another in studying the textbook and lecture material.
- As long as it satisfies the following conditions, collaboration on the homework assignments is permitted and will not reduce your grade:
- Before discussing each homework problem with anyone
else, you must give it an honest half-hour of serious thought.
- You may discuss ideas and approaches with other students in the class, but not share actual code.
In other words, the code you write must be entirely your own, which you must write and debug
without looking at other people's code.
You must also acknowledge clearly in the appropriate portion of your solutions
(e.g., in the comments of your code) people with whom you discussed ideas for that portion.
- You may get help from TFs and Java tutors in the lab for specific problems with
writing and debugging your code. Don't expect them to do it for you, however.
- If you get really stuck with a bug (defined roughly as over an hour of frustration),
you are allowed to get help from a friend as long as you acknowledge that help clearly in your
solutions (e.g., in the comments of your code).
- You may not work with people outside this class (but come and talk to us if you
have a tutor), seek on-line solutions, get someone else to do it for you, etc.
- You are not permitted to collaborate on exams.