CAS CS 112 A1 - Fall 2012 - Introduction to Computer Science II

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.

Class syllabus.


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.