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

Class meeting time:   Tues/Thurs 11:00-12:30,   GCB 209.

Lab meeting times:    Mon 10-11 and Mon 11-12 PM in the Undergraduate Teaching Laboratory, EMA 304. Labs will not be held on January 19 (holiday).

Class syllabus.

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

Office Hours:    Tues 3-4:30 and Thurs 1:30-3, held in MCS 270

Teaching Fellow:  Ashwin Thangali

Email: tvashwin @ cs . bu . edu

Office Hours:    Mon and Wed 4-5:30 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 and algorithms used throughout computer science. Data structures include linked lists, stacks, queues, trees, hash tables, and representations of graphs. Efficient algorithms for searching, sorting, and exploring graphs will be covered. 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 15: Homework 1, Due January 29.
Please use gsubmit to submit questions 1 and 2. Please use "cs112a1" as the class name in step 3 of these instructions.

January 30: Homework 2, Due February 12.
Extra credit Question 4 (required for Honors students): Question C-11.31 on p. 537.

February 12: Homework 3, Due February 26.

February 24: Sample Midterm. There are some missing pictures on Q2 (and Q4). On Q2, the stack should start with two elements: 55 and 10.
The queue should use an array of size 5, have elements 55, 10, and 7 at indices 0, 1, and 2, and initially front = 0, back (rear) = 3.
Last year we had covered BSTs at this point (Q4), but that will not be on this year's midterm.

March 5: Homework 4, Due March 26.

March 27: Homework 5 + TWL.txt, Due April 9.

April 14: Homework 6. Due Friday, April 24. + small-subgraph.txt + graph.txt.

May 1: Sample Final from 2008. Some figures from that exam are missing, but see notes within the exam on how to proceed.

Homework Solutions:   

Homework 1 Solutions. Click here for instructions on retrieving your grades.

Homework 2 Solutions.

Homework 3 Solutions.

Homework 4 Solutions.

Homework 5 Solutions.

Lectures:   

Lecture 1 (1/15): Review of syllabus. Binary search algorithm, recursive implementation.
Lecture 2 (1/20): Binary search iteratively. Logarithms in running times. Running time concepts. Big-O notation.
Lecture 3 (1/22): Properties of logarithmic, polynomial, and exponential functions. Big-O, Omega, and Theta. Naive Fibonacci implementation is exponential time.
Lecture 4 (1/27): Computing x^n efficiently (exponentiation). Intro to sorting. Insertion sort, and analysis of its running time (quadratic).
Lecture 5 (1/29): Mergesort algorithm, analysis, and implementation.
Lecture 6 (2/3): Quicksort algorithm, analysis, and implementation. Omega(n log n) lower bound for comparison-based sorting.
Lecture 7 (2/5): ADTs, APIs, and data structures. Stack ADT. Array-based implementation.
Lecture 8 (2/10): Balancing braces via stacks. Intro to linked lists. Linked list implementation of stacks.
Lecture 9 (2/12): Queues. Array-based and singly-linked list implementations. Intro to doubly linked lists.
Lecture 10 (2/19): Linked list implementations. Position-based list. Java collections version. Iterators.
Lecture 11 (2/24): Tree terminology. ADT and API for general trees. Binary trees. Depth and height methods.
Lecture 12 (2/26): Midterm review. Tree traversal algorithms: preorder and postorder. Use of postorder to compute diskspace of files in a folder. Intro to binary tree methods.
Lecture 13 (3/3): In-class midterm.
Lecture 14 (3/5): Midterm answers. Storing arithmetic expressions as binary trees and evaluating them via postorder traversal.
Spring Break
Lecture 15 (3/17): Priority queue ADT. Implementation via a linked-list (brief) and as a heap. Heap implementation as an array-based binary tree, heap insertion and deletion.
Lecture 16 (3/19): Problem solving session. Devising a solution to Project problem P-8.10 on p. 366 of our text.
Lecture 17 (3/24): Brief discussion of Comparable interface. Intro to hashing. Buckets, hash codes and compression functions.
Lecture 18 (3/26): Hashing and hash tables. Horner's rule. Collision resolution by chaining (linked lists) and by probing (array-based). Basic hash table implementation.
Lecture 19 (3/31): Maps and dictionaries. Concept of a range query. Skip list implementation of a dictionary.
Lecture 20 (4/2): Binary search tree implementation of a dictionary. Balanced binary search trees ensuring logarithmic height. AVL tree invariant and maintaining the invariant during insertion.
Lecture 21 (4/7): Graphs. Motivation, terminology, ADT. Defining Node and Edge classes. Edge list and adjacency list implementations.
Lecture 22 (4/9): Adjacency matrix implementation. Intro to graph algorithms. Depth-first search (DFS).
Lecture 23 (4/14): Discussion of homework #6. Directed acyclic graphs (DAGs). Topological sort.
Lecture 24 (4/16): Breadth-first search (BFS). Discussion of weighted graphs and motivation for shortest path algorithms. Dijkstra's algorithm, part 1.
Lecture 25 (4/21): Dijkstra's algorithm, part 2. Minimum spanning tree (MST) algorithms: motivation and basic MST facts.
Lecture 26 (4/28): MST algorithms: Kruskal's and Prim's. Motivation for UNION-FIND data structure. Stable matching algorithm.
Lecture 27 (4/30): Comprehensive course review.

See the syllabus for a tentative gameplan of upcoming material.