CAS CS 112 A1 - Spring 2011 - Introduction to Computer Science II

Class meeting time:   Tues/Thurs 11:00-12:30,   COM 217.

Lab meeting times:    Mon 10-11, Mon 11-12, and Fri 2-3 in the Undergraduate Teaching Laboratory, EMA 304.

Class syllabus.

Instructor:  Prof. John W. Byers
Email: byers @ cs . bu . edu
Phone: 617-353-8925

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

Teaching Fellow:  Diane Theriault

Email: deht @ cs . bu . edu

Office Hours:    Mon 4-5:30 and W 12:30-2 in EMA 302 (CS Undergrad lab).

Labs:    Mon 10-11 and 11-12, held in EMA 304. Click here for the lab homepage.

Course Overview:     This course starts by quickly revisiting, and then building upon, advanced programming concepts in Java taught at the end of CS 111, such as recursion. Then, the main focus of the course is on the design, analysis and implementation of fundamental 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. The emphasis in teaching this course centers around the following:

• Developing elegant and efficient code from an abstract specification;
• Literate programming (writing programs that can be read by humans as well as machines);
• Developing a toolbox of advanced data structures for use in your future programming tasks, and an awareness of various design patterns that recur frequently in advanced programming;
• Critical thinking about programs and the programming process, which involves:
  • Thinking about the best way to plan out the design using object-oriented design and appropriate features of Java;
  • Methodical and efficient development of the implementation using step-wise refinement and incremental testing and debugging (using appropriate debugging tools);
  • Being able to convince yourself of the correctness of the implementation by mathematical reasoning;
  • Analyzing the running time (efficiency) of programs by inspection and mathematical reasoning; and
  • Evaluating the efficiency and correctness of programs empirically, by using various tools in properly designed experiments.

Homework Assignments and Other Handouts:    

1/20: A hardcopy of Chapter 1 of our text was distributed in class.
1/22: Homework 1. Due February 3. Submission instructions are now available.
2/3: Homework 2. Due February 17.
2/24: Homework 3. Due March 8.
3/3: Practice midterm questions. (Midterm March 10).
3/18: Homework 4. Due March 31. (Now updated with a few short-answer questions about heaps).
4/1: Homework 5. Due April 14.
4/19: Homework 6. Due May 3. (newgraph.txt (updated as of April 29) and short answer questions are now available.)
5/9: Practice final. (Final: May 11).

Lectures:   

Lecture 1 (1/18): Review of syllabus. Binary search algorithm, recursive implementation.
Lecture 2 (1/20): APIs, ADTs, and data structures. Quick look at Counter ADT (Text pp. 65-68). Problem-solving: whitelisting transactions using a Set abstraction. Sorted array implementation and iterative binary search. (Code in text p. 99).
Lecture 3 (1/25): New Java concepts: "Iterable" interface, interface inheritance, Generics, wrapper types. Intro to Bag, Queue and Stack ADTs and APIs.
Lecture 4 (1/27): Using a Stack: Dijkstra's two-stack algorithm for evaluating an expression (pp. 128-31). Implementing a Stack: Fixed-capacity array-based implementation (pp. 132-5).
Lecture 5 (2/1): Array-based implementation of a Queue (not in text). Resizing and implementing iteration for Queue (similar to code in text for Stack).
Lecture 6 (2/3): Intro to linked lists. Node class and memory management issues. Adding and deleting from beginning and end of a list. Realizing stack and queue operations via a linked list implementation.
Lecture 7 (2/8): Linked list traversals. Reversing a list iteratively and recursively. See code on pp. 166-167 for Question 1.3.30.
Lecture 8 (2/10): Running time analysis. Measuring running times programmatically. From log-log plots to power laws to running time hypotheses. Logarithms in running times. Common patterns and algorithmic running times.
Lecture 9 (2/15): Big-O notation and asymptotic running times. Using limits and l'Hopital's rule to compare running times. Algorithms for finding triples in an array that sum to zero.
Lecture 10 (2/17): Basic sorts. Rules of the game. O(n^2) sorts: selection sort and insertion sort. Notion of program invariants.
Lecture 11 (2/24): Faster sorts. Top-down recursive mergesort. Analysis of O(n log n) running time.
Lecture 12 (3/1): Quicksort. Avoiding worst-case running time with randomization or use of heuristics. Lower bounds for comparison-based sorting.
Lecture 13 (3/3): Priority queue ADT and applications. Naive realizations. Introduction to binary trees and heap-ordered binary trees.
Lecture 14 (3/8): Array-based implementation of binary heaps. Introduction to dictionary and symbol table abstraction and ADT.
Lecture 15 (3/10): The in-class midterm was held on 3/10.
Lecture 16 (3/22): Answers to midterm questions. Binary search tree data structure: basic definitions and implementation of get().
Lecture 17 (3/24): Binary search trees: implementation of put(), delete(), and range queries. Tree traversals: inorder, preorder, and postorder. Running time analysis.
Lecture 18 (3/29): Balanced binary search trees. 2-3 trees and concepts. Red-Black BSTs: 2-3 tree equivalence and implementation overview (details in text).
Lecture 19 (3/31): Hash tables as realization of symbol table abstraction. Hash function principles and design. Hashing w/ separate chaining, hashing w/ linear probing.
Lecture 20 (4/5): Problem-solving session. Anagram solver ( near complete solution we developed in class).
Lecture 21 (4/7): Introduction to graphs. Terminology and basic data structure representations. Edge lists, adjacency matrices, adjacency lists.
Lecture 22 (4/12): Adjacency list implementation via array of lists (of edges). Basic problems on graphs: connectivity, reachability. Motivation for graph exploration.
Lecture 23 (4/14): Depth-first search (dfs) implementation, walkthrough, correctness, and running time.
Lecture 24 (4/19): Breadth-first search (bfs) implementation. Intro to directed graphs and DAGs. Discussion of mark-and-sweep garbage collection.
Lecture 25 (4/26): Topological ordering on DAGs. Preorder and postorder traversals of graphs. Intro to weighted graphs. Problem statement for minimum spanning tree (MST).
Lecture 26 (4/28): Class cancelled.
Lecture 27 (5/3): Minimum spanning trees (MSTs). Cut and cycle properties. Prim's algorithm, correctness and running time.
Lecture 28 (5/5): Kruskal's algorithm for MSTs, briefly. Single-source shortest-paths problem. Dijkstra's algorithm, sketch of correctness and running time.