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.
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).
Lectures:
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.