BU CAS CS 112 A1 Fall 2007

Boston University CAS CS 112 A1 Fall 2007

Professor Reyzin's office hours on Thursday 11/29 will be 12:20-1:50 instead of the usual time. On Tuesday 12/4 they will be 1:00-2:30 instead of the usual time.

The Course Syllabus

Lectures

Note: Some lecture topics will have links to code developed in class, which is posted to reduce the need for notetaking. However, please be aware that this code, because it is developed in real-time during a lecture, is not necessarily well-documented or even fully functional. Do not view it as examples of good coding style (examples of good coding style can be found in problem set solutions and textbooks).

Lecture 1 (9/4): Recursive recursive binary search and number of ways to walk a tiled floor
Lecture 2 (9/6): Cleaner number of ways to walk a tiled floor; tail recursion and iterative binary search; running times and definition of O
Lecture 3 (9/11): o, Θ, and O; insertion sort and its running time
Lecture 4 (9/13): Merge sort and its running time
Lecture 5 (9/18): Quicksort, its worst-case, average-case and randomized running time
Lecture 6 (9/20): Randomized Quicksort analysis; comparison sorting must take Ω(log n); ω and Ω (see the Greek alphabet); start linked lists (Movie.java MovieList.java)
Lecture 7 (9/25): Linked lists with dummy first node MovieListWithDummyNode.java. Generics GenericList.java ListDriver.java
Lecture 8 (9/27): Generics with constraints: list with inner keys GenericListWithInnerKeys.java HasKey.java Movie.java ListDriver.java; wildcards with constraints MergeSort.java Student.java CSStudent.java StudentSort.java. Stacks for recursion; infix, prefix and postfix (aka RPN); stacks for RPN evaluation; list-based stack implementation ListBasedStack.java
Lecture 9 (10/2): Solutions to HW2; parenthesis matching as an application of stacks; queues and their implementation using linked lists and arrays; start trees (mainly terminology)
Lecture 10 (10/4): Preorder and postorder traversals using recursion; preorder traversal (depth-first-search) using stacks; level-order traversal (depth-first) using queues ListBasedQueue.java Tree.java
Lecture 11 (10/11): Binary trees. Expression trees, their traversals and evaluation. Number of nodes in a full binary tree. Binary search trees: insertion, search.
Lecture 12 (10/16): Inorder traversal of binary search trees. Binary search tree insertion (recursively and iteratively) and deletion (iteratively). BinarySearchTree.java
Lecture 13 (10/18): Finish the code for tree deletion. Pre-midterm Q&A. Running time of binary search tree operations. AVL trees.
Lecture 14 (10/23): Midterm exam
Lecture 15 (10/25): Iterators GenericList.java ListDriver.java Movie.java (note that the book's presentation of list iterators is buggy -- see errata for p. 081)
Lecture 16 (10/30): Hashing with chaining; analysis of average-case find
Lecture 17 (11/1): Hashing vs. BSTs; universal hashing; open addressing
Lecture 18 (11/6): Binary Heaps
Lecture 19 (11/8): BuildHeap and HeapSort. Definitions of graphs. Start topological sort (see BU CS Course Map )
Lecture 20 (11/13): Topological sort of a graph using the adjacency matrix representation (in cubic time first, then improved to quadratic time) and the adjacency list representation (in quadratic time)
Lecture 21 (11/15): Topological sort in optimal time Θ(|V|+|E|); Solutions to HW04; begin BFS and DFS on graphs
Lecture 22 (11/20): Solutions to HW05; BFS with path constructions, and BFS running times
Lecture 23 (11/27): Prim's algorithm for minimum spanning trees: correctness, and Θ(|V|³) implementation
Lecture 24 (11/27): Prim's algorithm continued: Θ(|V|²) implementation; O(|V| log |V| + |E| log |V|) implementation using heaps
Lecture 25 (12/4): Dijstkra's algorithm for shortest paths in graphs with nonnegative costs on edges; course evals
Lecture 26 (12/6): Gale-Shapley algorithm for the stable marriage problem
Lecture 27 (12/11): Solutions to HW06; software and copyright (warning: politically biased links: Free Software Foundation advocates use of copyright law to free software from many incumberances; Electronic Frontier Foundation is concerned about restrictions DMCA and other intellectual property laws put on our freedoms)

Labs Page

Helpful info, tutorials and examples.

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. We encourage you to work in the lab; in addition to the course staff (whose office hours are listed on the syllabus ), help is available from other CS TFs and from terminal assistants who are also Java tutors.

Due Monday, Sept 17 at 11:59 pm: hw1.pdf, MysteryInt.java, MysterySearchDriver.java.
Due Monday, October 1 at 11:59 pm: hw2.pdf, GiftArrangement.java
Due Monday, October 15 at 11:59 pm: hw3.pdf,
Due Monday, November 5 at 11:59 pm: hw4.pdf,
Due Monday, November 19 at 11:59 pm: hw5.pdf, TWL06.txt
Due Monday, December 10 at 11:59 pm: hw6.pdf, TWL06.txt, Doublets.java, WordGraph.java, BetterBinSearch.java
Electronic submission instructions:
1. Go to the link: http://azs.bu.edu/websubmit?COURSE=cs112
2. Log in using your BU Kerberos username and password (could be different from the cs account password)
3. Click the appropriate buttons to submit files
4. If you do not get a confirmation email (which means something is wrong), contact the course staff