CAS CS 112 B1 - Spring 2012 - Introduction to Computer Science II

Class meeting time:   Tues/Thurs 12:30-2:00,   CAS 324.

Lab meeting times:    Mon 1-2, Mon 2-3, and Mon 5-6 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. John W. Byers
Email: byers @ cs . bu . edu [preferred]
Phone: 617-353-8925 [do not leave voice-mail; use e-mail instead]

Office Hours:    Mon 9:30 - 11 and Thurs 11-12:30, held in MCS 270

Teaching Fellow:  Chong Wang
Email: wangch @ bu . edu

Office Hours:    Mon 4-5 and Wed 3-5 in EMA 302 (CS Undergrad lab).

Labs:    Here is the lab homepage.

Homework Assignments and Other Handouts:    

January 17: Homework 1 (pdf), (latex source). Due at the beginning of class on January 26. Please turn in a listing of your source code and output on test cases for programming problems.
Class average: 33/40.

January 24: Programming Assignment 1. Due via WebSubmit by 10PM, February 2.
Class average: 58/75.

February 2: Homework 2 (pdf), (latex source). Due at the beginning of class on February 9. Please turn in a listing of your source code and output on test cases for programming questions.
Class average: 32/40.

February 11: Programming Assignment 2. Due via WebSubmit by 10PM, February 16.
Class average: 59/70.

February 21: Programming Assignment 3. Due via WebSubmit by 10PM, March 1.
Class average: 66/90.

March 1: Homework 3 (pdf). Please submit these practice problems for the midterm in-class on Thurs, March 8 (at the beginning of the exam).

March 19: Programming Assignment 4 (pdf), (latex source). Due via WebSubmit by 10PM, March 29.

April 1: Homework 4 (pdf). Due in class on Thurs, April 4 (at the beginning of class).

April 5: Programming Assignment 5 (pdf), (latex source). TWL word list. Due via WebSubmit by 10PM, April 12.

April 22: Homework 5 (pdf), (latex source). Due at the beginning of class on April 26. Please turn in a listing of your source code and output on test cases for Question 2.

April 23: Programming Assignment 6 (pdf), (latex source). Co-authorship data (graph.txt). Due via WebSubmit by 10PM, May 3.

May 2: Practice final (pdf).


Lecture 1 (1/17): Course overview and syllabus. Motivation for study of algorithms and data structures. Recursive implementation of binary search. Also, here's a demo of binary search in action.

Lecture 2 (1/19): Survey of external libraries for this class (p. 27). ADTs, APIs, and data structures. Moving from specifications to instantiations. Quick tour of Counter API, usage, and implementation. Whitelisting via static sets (to be completed in Lab 1). [Reading: Chapters 1.1 (mostly review) - 1.2].

Lecture 3 (1/24): Stacks and queues: motivation, examples, and APIs. Linked-list and array-based implementations of stack; array resizing. [Slides for the next couple lectures].

Lecture 4 (1/26): Linked-list implementation of queue. Discussion of array-based implementation (you get to implement it in lab). Java generics: interface declarations, usage, and class implementation.

Lecture 5 (1/31): Iterators: usage and implementation. Applications of stacks: Dijkstra's two-stack method for expression evaluation [Demo].

Lecture 6 (2/2): Code for Dijkstra's method. Postfix notation. Applications of queues. Linked list reversal: iterative and recursive approaches (see code on pp. 165-6).

Lecture 7 (2/7): Analysis of algorithms. Applying the scientific method to modeling running time via wall-clock evaluation, use of Stopwatch class. Introduction to mathematical modeling of worst-case running times using tilde notation. We covered some of the slides for Chapter 1.4 to get started. We'll learn much more about big-O notation later as the class goes on.

Lecture 8 (2/9): Introduction to sorting. Rules of the game, running time evaluation. Basic sorts. [slides for Chapter 2.1]

Lecture 9 (2/14): Insertion and selection sort, demos, implementation and running time analysis.

Lecture 10 (2/16): Mergesort: divide and conquer approach, walkthroughs, top-down recursive implementation and running time analysis (several ways). [slides (we'll cover up through the material on complexity of sorting].

No lecture (Tues, 2/21): BU is on a Monday schedule. Monday labs will be held at the usual time and place.

Lecture 11 (2/23): Bottom-up iterative mergesort. Complexity of comparison-based sorting & lower bounds. Quicksort: design and implementation. [slides, partitioning demo, ]

Lecture 12 (2/28): Quicksort analysis. Achieving linearithmic running time in expectation through randomization. Randomized selection. Intro to priority queues. [slides]

Lecture 13 (3/1): Binary heap realization of priority queue. Array-based implementation and logarithmic running times for PQ operations. Heapsort.

Lecture 14 (3/6): Introduction to symbol tables: motivation and API. Unordered list and ordered array implementation. Binary search tree outline. [slides]

Thursday, 3/8: In-class midterm. Closed book and notes.

3/10 - 3/18: Spring Break! Also, no lab on Monday 3/19.

Lecture 15 (3/20): Binary search trees: definitions, invariants, and data structures. Lookups and insertions. [slides]

Lecture 16 (3/22): Binary search trees (ii). Recursive routines: size(), rank(). Tree traversals. DeleteMin() and delete() [Hibbard deletion].

Lecture 17 (3/27): Balanced search trees: 2-3 trees, red-black trees. Conceptualization. [slides]

Lecture 19 (3/29): Red-black tree: implementation and analysis. B-Trees.

Lecture 20 (4/3): Hashing and hash tables. [slides]

Lecture 21 (4/5): Hash tables, part ii.

Lecture 22 (4/10): Introduction to graphs. Definitions, applications, and data structures. [slides]

Lecture 23 (4/12): Graph data structures and graph traversals. Depth-first search.

Lecture 24 (4/17): Applications of DFS. Breadth-first search.

Lecture 25 (4/19): Class cancelled -- no lecture.

Lecture 26 (4/24): Directed graphs, and directed acyclic graphs (DAGs). Topological sorting algorithms. Transitive closure. [slides].

Lecture 27 (4/26): Weighted graphs. Minimum spannning tree concepts and algorithms. Cut and cycle properties. Prim's and Kruskal's algorithm. [slides].

Lecture 28 (5/1): Shortest-path algorithms. Dijkstra's algorithm. [slides]. Course wrap-up.