Boston University CAS CS 112 B1 Fall 2011
The Course Syllabus
The place to ask questions and get help: Piazza
I highly recommend using Eclipse for its more advance debugger and powerful automation/completion. Download here (select "Eclipse IDE for Java Developers"). Watch an excellent short video tutorial by Sami Rollins to get started.
Midterm Announcement (Nov 10 for the B section, Nov 11 for the A section)
For the final exam (Wed 12/21 at 9am), you are allowed to bring two double-sided letter-size (8.5x11 inches) sheets of paper with whatever information you want on them, subject to the following restriction: these sheets must be handwritten by you personally. Photocopied, typewritten, computer printed, etc., sheets are not allowed. The restriction is designed to make sure you reap the learning benefit of preparing the sheets. I will be checking that this restriction is adhered to, but will not check the contents of these sheets otherwise. It's entirely up to you what to put on them. You are allowed to use these sheets and nothing else during the exam--no books, no lecture notes, no calculators. Please also bring two pens/pencils that work.
Everything we studied during the semester (including homeworks and solutions) is fair game for the exam. However, naturally, the focus will be on fundamental concepts and more on the second half of the course. Note that we covered some material that was not on the assignments, especially toward the end of the course. This material is also fair game. Thus, for example, be sure to understand how heaps operate or how to execute Dijkstra's algorithm on a given graph.
Professor Snyder has kindly provided his final from last year as a practice exam. (Note that my exam will probably have more coding problems and a different format, but the sample problems are still valuable.)
Lectures
Note: the code posted here was written live in lecture and is therefore rushed, underdocumented, and sometimes even buggy.
- Tue Sep 6: Binary search buggy code that we started
- Thu Sep 8: Fixing recursive binary search; making it iterative (tail recursion). Thinking about running times. fixed code from last time; more elegant code; iterative code
- Tue Sep 13: Local, static, and dynamic variables; static vs. instance methods; public vs. private; memory allocation and garbage collection.
- Thu Sep 15: Java interfaces. Example:
Date.java interface; GregorianDate.java implementation and (unfinished) UnixDate.java implementation; simple usage example in BirthdayList.java. Abstract data types with Stack as an example.
- Tue Sep 20: Array-based stack with resizing and application to parenthesis matching StringStack.java CharStack.java ParenMatch.java
- Thu Sep 22: Generics GenericStack.java GenericStackClient.java. Queues. Linked-list-based stacks LinkedListBasedStack.java
- Tue Sep 27: Cleaning up and making generic linked-list-based stack GenericLinkedListBasedStack.java; linked-list-based queue
LinkedListBasedQueue.java
and
LinkedListBasedQueueWithHeaderNode.java
; client code
QueueClient.java
- Thu Sep 29: Inserting/removing/printing an ordered list, recursively and iteravely.
OrderedList.java. Notes on Linked Lists by Wayne Snyder
- Tue Oct 4: Generics with bounds and inheritance; start recursion
- A list whose elements can be incremented, with two examples of elements:
- Same list, but implemented as a superclass:
- Generic ordered list and a client of all of it:
- Thu Oct 6: Recursion (continued from last time):
StairClimbing.java,
EightRooks.java,
EightQueens.java.
Start O-notation (aka asymptotic notation).
- Tue Oct 11: O-notation (click to see notes); selection sort
- Thu Oct 13: Selection sort (cont.); insertion sort; merge sort. Learn Sorthing Algorithms thorugh Dance!
- Tue Oct 18. Merge sort; begin quicksort. (A note on generic method declarations.)
- Thu Oct 20: Quicksort.
- Tue Oct 25: Trees. Tree.java
- Thu Oct 27: Binary Trees, Expression Trees, and Binary Search Trees. BinarySearchTree.java
- Tue Nov 1: Binary Search Trees: inorder traversals and deletion. BinarySearchTree.java
- Thu Nov 3: 2-3 and Red-Black trees. Slides
- Tue Nov 8: Hash tables
- Thu Nov 10: Midterm
- Tue Nov 15: Midterm review; wrap up hash tables
- Thu Nov 17: Heaps and HeapSort
- Tue Nov 22: Graphs: basic notions
- Tue Nov 29: Graphs: depth-first search, breadth-first search, begin topological sort
- Thu Dec 1: Wrap up topological sort to get from
O(V3)
to
O(V2)
to
O(V+E)
.
Start Prim's algorithm.
- Tue Dec 6: Prim's and Dijsktra's algorithms
- Thu Dec 8: Illegal Software
Labs Page by Ian Denhardt and
Another section of the same course by Wayne Snyder
Assignments
Please read and follow the collaboration policy on the course syllabus.
In doing your assignments, you will likely find the Java API Spec useful. Make sure
your code is readable and well-documented; our code tries to provide
good examples of that.
In addition to the course staff, homework help
is available from TFs helping as tutors
in the undergrad lab.
Submit your homework here.