**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.

**Have questions?** Please ask on Piazza.

This is the primary place that questions will be answered and any announcements will be posted.

Getting clarification on questions you
have about material covered in the class or on the assignments is encouraged!

Click here to access our Piazza
course page.

**Instructor: Prof.
George Kollios**

Email: gkollios @ cs . bu . edu

Phone:
617-358-1835

**Office Hours:** Tues 2:00-3:30PM and Wed 9:30-11:00AM, held in MCS 283 (or any other time I am in my 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 309.

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

**Course Overview: ** The main focus of the
course is on the design, analysis and implementation of basic 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.

**Homework Assignments and Other Handouts: **

September 6: Homework 1, Due via
WebSubmit by 11:59, September 20.

September 25: Homework 2, Due via
WebSubmit by 11:59, October 4.

October 12: Homework 3, Due via
WebSubmit by 11:59, October 25.

November 8: Homework 4, Due via
WebSubmit by 11:59, November 15.
TextAnalyzer.java,
BSTWithDuplicates.java,
CountingTree.java,
Odyssey.txt.

November 20: Homework 5, Due via
WebSubmit by 11:59, November 30.
TWL.txt.

December 4: Homework 6, Due via
WebSubmit by 11:59, December 12.
graph.txt.
small-graph.txt.
**Lectures: **

Lecture 1 (9/4): Review of syllabus. Recursive functions and
the recursive binary search algorithm.

Lecture 2 (9/6): More on recursion and iterative methods. Iterative version of binary search , Tail and non-tail recursion (Example for Fibonacci).

Chapter 1, section 1.1.

Lecture 3 (9/11): Analysis of Algorithms, Asymptotic bounds, Big-O notation, Analysis of Binary Search.
Prof. Reyzin's notes on Asymptotic Notation.

Chapter 3, page 383, proposition B. Chapter 1, pages 186-188. part of Analysis of Algorithms.

Lecture 4 (9/13): Analysis of Algorithms (Cont.) Sorting. InsertionSort

Lecture 5 (9/18): Analysis of Insertion Sort. Selection Sort. Introduction to Merge Sort.

Lecture 6 (9/20): MergeSort. Analysis of MergeSort.

Lecture 7 (9/25): Lower bound for comparison based sorting. Quicksort. Analysis of Quicksort.

Lecture 8 (9/27): More on sorting and quicksort. Summary of sorting.

Lecture 9 (10/2): Abstract Data Types (ADT). Lists with examples:
CD.java.
CDList.java.
GenericList.java.
ListDriver.java.

Lecture 10 (10/4): More on ADT. Generics.
HasKey.java.
CD2.java.
GenericListWithInnerKeys.java.
ListDriver2.java.
MergeSortGeneric.java.
Prof. Reyzin's notes on Generics.

Lecture 11 (10/11): Queue and Stack ADTs. Examples of algorithms that use Stacks.
Infix and Postfix notations.
InfixToPostfix.

Lecture 12 (10/16): PostfixEvaluation.txt.
Linked List based Stack.
ListBasedStack.java.

Lecture 13 (10/18): Array based implementation of Stack with the Iterable iterface.
ArrayStack.java.
Queue implementation using Linked List.
ListBasedQueue.java.

Lecture 14 (10/23): Trees. Preorder and postorder traversals. Level-wise traversal.

Lecture 15 (10/25): Implementation of Trees and traversals. Two Tree versions to store pointers to children:
using an array
TreeA.java, and using a linked list
TreeL.java.

Lecture 16 (10/30): Binary Trees. Expression Trees. Binary Search Trees.
Binary Trees.
Expression Trees.
Binary Search Trees.
Tree Traversals.

Midterm Exam.New Date: Nov 1st, 2012.
Study Guide.

Lecture 17 (11/6): Discuss Midterm. Binary Search Trees. Insertion. Search.

Lecture 18 (11/8): Binary Search Trees. Deletion. Balanced binary search trees.
BinarySearchTree.java

Lecture 19 (11/13): 2-3 trees. Red-Black Trees.

Lecture 20 (11/15): Insertion into Red-Black Trees. (Guest lecture by Haohan Zhu.)

Lecture 21 (11/20): Hash Tables.

Lecture 22 (11/27): More Hash Tables. Separate Chaining and Linear Probing.

Lecture 23 (11/29): Introduction to Graphs. DFS and BFS.

Lecture 24 (12/4): DFS and BFS algorithms. Topological Sort.

Lecture 25 (12/6): Topological Sorting.
AdjacencyMatrixGraph.java.
AdjacencyMatrixGraph2.java.
AdjacencyListGraph.java.
toy.txt.

Lecture 26 (12/11): Shortest Paths, Dijkstra's algorithm.

Final Exam. December 18, 2012, in CAS 313 at 12:30PM-2:30PM.
Final Exam Study Guide.

See the syllabus
for a tentative schedule of the upcoming material.