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

Class meeting time:   Tues/Thurs 9:30-11:00,   PSY B53.

Lab meeting times:    Wed. 1-2 and Wed. 2-3 PM in the Undergraduate Teaching Laboratory, EMA 304. Labs will not be held on January 16.

Class syllabus.

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

Office Hours:    Tues 11-12:30 and Thurs 2-3:30, held in MCS 270

Teaching Fellow:  Joseph Akinwumi

Email: akin @ cs . bu . edu

Office Hours:    Wed 4-6 and Fri 10-11 in EMA 309.

Labs:    Wed 1-2 and 2-3, held in EMA 304. Click here for the lab homepage. Labs will not be held on January 16.

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:    

January 16: Homework 1, Due January 31. Homework 1 Solutions.
February 1: Homework 2, Due February 14. Homework 2 Solutions.
February 14: Homework 3, Due February 28. Homework 3 Solutions (zipped archive of .class files).

March 2: Practice Midterm Questions.

March 7: Homework 4, Due March 27. Homework 4 Solutions.
April 1: Homework 5 + TWL.txt, Due April 15.
April 16: Homework 6 + network.txt + network2.txt, Due May 1.

May 3: Sample final (from 2005). Was written in C++, but syntax used (2 places) is readable to Java programmers. Two hand-drawn figures were not special in any way: any random 6-node graph/tree will do. No written answers, but Joseph or I will provide them verbally in office hours.

Lectures:    

Lecture 1 (1/17): Review of syllabus. Binary search algorithm, recursive implementation.
Lecture 2 (1/22): Running time analysis. Big-O notation. Naive Fibonacci implemenation is exponential time. Computing x^n efficiently (exponentiation).
Lecture 3 (1/24): Sorting. Insertion sort (variant of code on p. 249). Quadratic running time and lower bound. Mergesort description.
Lecture 4 (1/29): Mergesort algorithm, code (see Chapter 7.6 in textbook), and analysis.
Lecture 5 (1/31): Quicksort algorithm, code, and analysis. Comparison-based sorting requires Omega(N logN) comparisons.
Lecture 6 (2/5): Abstract data types (ADTs). List ADT. Array-based and linked list overview.
Lecture 7 (2/7): Containers, lists, and iterators in Java (Section 3.3). ArrayBasedList class.
Lecture 8 (2/12): ArrayBasedList Iterator. Node class + linked list class. Traversing and adding to a linked list.
Lecture 9 (2/14): Removal from a linked list and linked list iterators. Stack ADT. Stack implemented as a linked list or as an array. Application of balancing parentheses and braces.
Lecture 10 (2/21): Evaluating postfix expressions with a stack. Queue ADT. Queue as a linked list or circular array. Trees.
Lecture 11 (2/26): Binary search tree: concepts, ADT, and implementation. Inorder, preorder and postorder traversals. BST lookup and BST insertion routines.
Lecture 12 (2/28): Binary search deletion. Running time analysis of BST operations. Introduction to AVL trees.
Lecture 13 (3/4): Midterm review: reversing a list (iteratively, recursively, using a stack); level-order traversal using a queue; sorting via use of a binary search tree.

Midterm (3/6). Spring Break (3/11, 3/13).

Lecture 14 (3/18): Answers on the midterm. Overview of Homework #4. Revisiting binary search tree and AVL tree insertion concepts.
Lecture 15 (3/20): Code for AVL tree insertion, rotation, double rotation. Motivation for and introduction to B-Trees.
Lecture 16 (3/25): B-Tree layout, insertion, deletion, and running times.
Lecture 17 (3/27): Hashing concepts: hashing integers and strings. Design of open hash tables with separate chaining.
Lecture 18 (4/1): Implementation of open hash tables. Load factor and performance. Closed hash tables via arrays and methods for collision resolution.
Lecture 19 (4/3): Priority queue ADT. Binary heap implementation. Insertion and DeleteMin in O(log N) time.

Class was cancelled on April 8.

Lecture 20 (4/10): Heapsort very briefly. Introduction to graphs. Terminology and representations. Edge lists, adjacency matrices (AMs), and adjacency lists (ALs).
Lecture 21 (4/15): Adjacency lists using a HashTable (or HashMap) on Vertices, with adjacencies stored in a linked list. Topological sort algorithm and running time analysis with AM vs. AL representation.
Lecture 22 (4/17): Shortest path algorithms. Breadth-first search to build shortest-hop paths. Dijkstra's algorithm for graphs with positive edge weights.
Lecture 23 (4/22): Shortest paths (cont). Dijkstra's algorithm, running time analysis and implementation. Brief discussion of all pairs shortest paths. Discussion of HW #6.
Lecture 24 (4/24): Minimum spanning trees. Concepts and algorithms. Analysis of Prim's and Kruskal's + a mention of UNION-FIND data structure.
Lecture 25 (4/29): Skip lists. Design and implementation sketch.
Lecture 26 (5/1): Class review for the final exam.

The final will be held on Thursday, May 8 from 9-11 AM in PSY B53.


See the syllabus for a tentative gameplan of upcoming material.