CAS CS 112 A1 - Spring 2011 - Introduction to Computer Science II

Course Overview

• 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 11:00-12:30,   COM 217.

Lab meeting times:    Mon 10-11, Mon 11-12, and Fri 2-3 in the Undergraduate Teaching Laboratory, EMA 304.

Instructor:  Prof. John W. Byers
Email: byers @ cs . bu . edu
Phone: 617-353-8925

Office Hours:    Mon 9:30-11 and Thurs 2:30-4, held in MCS 270

Teaching Fellow:  Diane Theriault

Email: deht @ cs . bu . edu

Office Hours:    Mon 4-5:30 and Wed 12:30-2 in EMA 302 (CS Undergrad lab).

Labs:    Mon 10-11 and 11-12, held in EMA 304. Click here for the lab homepage.

Prerequisites:     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.

Textbooks:     The required textbook is:

• The preliminary edition of Algorithms, by Robert Sedgwick and Kevin Wayne (Addison Wesley, 2011), ISBN #0321751841. Note that this is a preprint of the textbook that is not yet publicly available, so you will have to get it from the BU bookstore. We will be providing a PDF of the 200+ page first chapter in class, which is not in this preliminary edition.
• 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.

Topics:     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 (Jan 18-20): Review of recursion, arrays, and Java basics. Binary search recursively and iteratively. ADTs, APIs, and data structures.
• Lectures 3-7 (Jan 25-Feb 8): Stacks, queues and bags. Java generics. Linked list data structures. Introduction to O-notation and logarithms in running times.
• Lectures 8-11 (Feb 10-Feb 24): Analysis of algorithms. Sorting. Elementary sorts, merge sort, quicksort.
• Lectures 12-14 (Mar 1-Mar 8): Priority queues and applications. Searching via symbol tables and dictionaries.
• Lecture 15 (Mar 10): Midterm exam
• Spring Break
• Lecture 16-18 (Mar 22-29): Trees, binary search trees, balanced search trees
• Lectures 19-20 (Mar 31 - Apr 5): Hash tables
• Lectures 21-23 (Apr 7-14): Introduction to graphs and their representations, traversals and topological sort.
• Lectures 24-25 (Apr 19-26): Minimum spanning trees
• Lecture 26 (Apr 28): Class cancelled.
• Lectures 27-28 (May 3-5): Shortest path algorithms

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 Thursdays 2/3, 2/17, 3/3, 3/31, 4/14, and 4/28).
• 20% in-class midterm exam (most likely in-class on Thursday 3/10).
• 30% comprehensive final

Exams:     There will be one eighty minute in-class midterm held during the middle of the semester in early March, probably Thursday, March 10. The cumulative final will be held during the normal two-hour final exam slot, Wed, May 11 from 9-11AM. 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 gsubmit 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 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.

Late Policy:     Programming assignments are typically due Thursdays at 10PM. 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 few days 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 CAS Academic Conduct Code -- please take the time to review this document if you are unfamiliar with its contents.

Collaboration Policy: The collaboration policy for this class is as follows.

• 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:
  1. Before discussing each homework problem with anyone else, you must give it an honest half-hour of serious thought.
  2. 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.
  3. 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.
  4. 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).
  5. 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.