Class meeting time: Tues/Thurs 11:00-12:30, KCB 107.
Lab meeting times: Tues 1-2 PM and Tues 5-6 PM in the Undergraduate Teaching Laboratory, EMA 304.
Instructor: Prof.
George Kollios
Email: gkollios @ cs . bu . edu
Phone:
617-358-1835
Office Hours: Tues 3-4:30 and Thurs 2-3:30, held in MCS 288 or MCS 279 (or any other time I am in my office)
Teaching Fellow: Tadeusz Jordan
Email: ttjordan
@ cs . bu . edu
Office Hours: Mon and Wed 11:15-12:15 in EMA 302.
Labs: Tues 1-2 PM and Tues 5-6 PM in EMA 304. 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 8: Homework
1. Due: Thursday 10PM, September 17, 2009.
Solutions:
Sqrt.java,
Partition.java,
BigO.AVERAGE: 71, MEDIAN 86.
September 22: Homework 2.
Due: Thursday 10PM, October 1, 2009.
Solutions:
MergeSort.java,
QuickSort.java.
October 10: Homework 3.
Stack.java,
Due: Friday 10PM, October 23, 2009.
October 28: Homework 4.
TextAnalyzer.java,
BSTWithDuplicates.java,
CountingTree.java,
Odyssey.txt,
Due: Saturday 10PM, November 7, 2009.
November 12:: Homework 5.
TWL.txt,
Due: Monday 10PM, November 23, 2009. Problem 2, question (c) is optional and will be graded as extra credit question.
To submit your programs you should use gsubmit to cs112
from csa2.bu.edu (using your cs account)
Midterm
You can find details about the midterm and a few practice examples here:
midterm.
Lectures:
Lecture 1 (9/3): Review of syllabus. Recursive functions and
the recursive binary search algorithm.
Chapter 1, Sections 1.1-3.1.
Lecture 2 (9/8):Iterative version of binary search , asymptotic bounds and analysis of algorithms.
Chapter 2, Sections 2.1, 2.2, 2.4, 2.4.1, 2.4.2, 2.4.4, 2.4.5
Lecture 3 (9/10): More on asymptotic bounds and analysis of algorithms. Tail and non-tail recursion (Example for
Fibonacci).
InsertionSort and its running time analysis. Chapter 7, 7.1-7.2.
Lecture 4 (9/15): More on
InsertionSort Test. Merge-Sort. Chapter 7, 7.3.
Lecture 5 (9/17): Merge-Sort and its analysis. Chapter 7, 7.6.
Lecture 6 (9/22): QuickSort. Chapter 7, 7.7.
Lecture 7 (9/24): Analysis of QuickSort. Chapter 7, 7.7 (only best and worst case analysis).
Lecture 8 (9/29): Lower bound for sorting with comparisons, Omega(NlogN). Chapter 7, 7.8. ADT, Lists. Chapter 3, 3.1,3.2.
Lecture 9 (10/1): ADTs, Linked List implementation. Generics.
Chapter 3, 3.1,3.5. Chapter 1, 1.4, 1.5.
CD.java,
CDList.java,
GenericList.java,
ListDriver.java.
Lecture 10 (10/6): ADTs. More on Generics, Linked Lists.
HasKey.java,
GenericListWithInnerKeys.java,
CD2.java,
ListDriver2.java.
Lecture 11 (10/8): Stacks and Postfix notation. Chapter 3, 3.6.
Stack.java,
ListBasedStack.java.
Lecture 12 (10/15): Queues. Trees and tree traversals: post-order, pre-order, and level-wise.
Chapter 3, 3.7. Chapter 4, 4.1.
ListBasedQueue.java.
Lecture 13 (10/20): Midterm Review. Trees and tree traversals: post-order, pre-order, and level-wise.
Chapter 4, 4.1.
Tree.java.
Lecture 14 (10/22): Midterm.
Lecture 15 (10/27): Discussion of Midterm Solutions. Binary trees and Expression trees.
Chapter 4, 4.2.
Lecture 16 (10/29): Binary Search Trees.
BinarySearchTree.java.
Chapter 4, 4.3.
Lecture 17 (11/3): Binary Search Trees Insertion and Deletion.AVL-trees.
Chapter 4, 4.3-4.4.
Lecture 18 (11/5): Insertion for AVL-trees. Single and Double rotation.
AVLTree.java.
Chapter 4, 4.4.
Lecture 19 (11/10): Hashing and Hash Tables. Chapter 5, 5.1-5.3.
Lecture 20 (11/12): Hashing: chaining, linear probing, quadratic probing, double hashing, rehashing. Chapter 5, 5.3-5.5.
Lecture 21 (11/17): Priority Queues, Binary Heaps. Chapter 6, 6.1-6.2.
Lecture 22 (11/19): Binary Heaps. Graphs (definitions). Chapter 6, 6.3, Chapter 9, 9.1.
BinaryHeap.java. (Book's implementation.)
See the syllabus
for a tentative schedule of the upcoming material.