**Official Description:** Covers advanced programming
techniques and data structures. Topics include recursion, algorithm
analysis, linked lists, stacks, queues, trees, graphs, tables,
searching, and sorting. **Overview:** In this course we
are going to cover a number of important data structures, such as
stacks, queues, linked lists, hash tables, trees and graphs;
algorithmic techniques, such as recursion; and program analysis. We
will discuss implementation details and efficiency analysis of these
data structures and basic algorithms. A basic level of Java
programming is assumed; however in this course we will try to cover
data structures and algorithms in an abstract way that is independent
of the language used to implement them. Therefore, although you will
have to implement all the data structures and techniques discussed in
the class in Java, it should be easy for you to re-implement the same
things in any other language of your choice.

**Class meeting time: **Tues/Thurs 12:30-2:00 PM,
CAS 313.

**Lab meeting times:** Thu 3:00-4:00 PM, 4:00-5:00 PM and Fri 2:00-3:00 PM
in the Undergraduate Teaching Laboratory, EMA 304.

**Class Web Page:
**http://www.cs.bu.edu/fac/gkollios/cs112f12/

**Instructor: Prof.
George Kollios**

Email: gkollios @ cs . bu . edu

Phone:
617-358-1835

**Office Hours:** Tue 2:00-3:30PM and Wed
9:30-11:00AM, held in MCS (111 Cummington St) Rm 283. (or any other time I
am in the office)

**Teaching Fellow: Haohan Zhu**

Email: zhu
@ cs . bu . edu

**Office Hours:** Tue 5:00-6:30PM and Wed 3:00-4:30PM in EMA (730 Commonwealth Ave.) Rm 309.

**Labs:** Click here for the lab
homepage.

**Prerequisites: ** The class assumes working
knowledge of CS 111, and a reasonable level of comfort with Java and
the dr. Java or the Eclipse platform. If you do not have significant previous
exposure to programming, then you are requested to transfer to CS
111. Please contact us as soon as possible if you think that your
programming skills may not be adequate for this course.

**Textbooks: ** The required textbook is:

__Algorithms, (4th 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

__Core Java 2, Volume I -- Fundamentals__by Cay S. Horstmann and Gary Cornell, or the reference you used for CS 111.And, of course, on-line resources, such as the Java API.

**Topics: ** This is a tentative plan that it is likely to change a little bit during the semester.
However, it is a good reference for a rough roadmap of the course.
:

Lectures 1-2: Binary search recursively and iteratively; introduction to

*O*-notation and logarithms in running timesLectures 3-6: Insertion sort, merge sort, quicksort; more detailed

*O*-notation and running time analysisLectures 7-10: Linked lists, stacks and queues; Java generics and iterators

Lectures 11-13: Trees, traversals, depth- and breadth-first search; expression trees; binary search trees

Lecture 14: Midterm exam

Lecture 15-16: More binary and balanced search trees

Lectures 17-18: Hash tables

Lectures 19-20: Heaps and priority queues

Lectures 21-23: Introduction to graphs and their representation, traversals and topological sort

Lectures 24-25: Prim's algorithm for minimum spanning trees

Lectures 26-27: Dijsktra's algorithm for shortest paths

**Workload: ** 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 substantial
programming assignments due approximately every other week.

**Grading: ** The course grade will break
down as follows:

50% homework assignments (tentatively due on every other Thursdays). The assignments will be mostly programming assignments, but there will be a few written assignments as well.

5% participation in class, lab, and on Piazza.

20% in-class midterm exam (most likely in-class on Tuesday, October 23).

25% comprehensive final.

**Exams: ** There will be one eighty minute
in-class midterm held during the middle of the semester in October.
The cumulative final will be held during the normal two-hour final
exam slot: Tuesday, Dec 18, 2012, 12:30 PM - 2:30 PM. Please make your
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: ** We
will have regular programming assignments due roughly every other
week. 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, usage of
which will be covered in lab. All assignments will be tested for
originality by an automated software tool.

**Attendance: ** It is expected that you will
attend the lecture and the lab section for this course and I will
often take attendance at the beginning of lecture. Material covered
in lecture and lab may not be covered by our textbook. 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 check the
attendance records before making a final determination.

**Late Policy: ** Programming assignments are
typically due Thursdays at 11:59PM. During the course, you will have two
opportunities to turn in an assignment up to 24 hours late with no
penalty. 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.

**Drop Dates: ** This semester, you may drop
without a W grade by Tuesday, October 9, 2012, and with a W grade by
Friday, November 9, 2012. After that, I am required to give you a
letter grade for the class.

**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 CAS
Academic Conduct Code -- please take the time to review this
document if you are unfamiliar with its contents.

**Collaboration Policy: ** The work that you
submit must be your own original work and it is an act of plagiarism
to represent the work of another as your own. You are welcome to
discuss the general nature of programming assignments with other
students in the course, but it is not acceptable to collaborate by
working side-by-side in the lab, nor by writing lines of code or
pseudo-code together, nor by sharing or copying code. Any discussion
or collaboration with other students in the course must also be
acknowledged in your submission. If you are uncertain whether an
action constitutes a violation of the collaboration policy, I will be
glad to discuss the matter with you.