CS310: Advanced Algorithms and Data Structures
Spring 2012

Department of Computer Science
UMass Boston

Class: TuTh 4:00-5:15 in W-2-125

Instructor: Elizabeth (Betty) O’Neil
email: eoneil@cs.umb.edu
Office: S-3-169
Office hours: TuTh 2:30-3:45, 6:15-6:45

Grader: Weiwei Gong, email: wwgong

Course Description: A systematic study of the methods of structuring and manipulating data in computing. Application programming interfaces, data abstraction, and the encapsulation of implementations. The design and analysis of algorithms. Advanced techniques for program development and organization.

See the course syllabus for a detailed list of topics.

Prerequisites CS210, CS240, Math 140. There will be a qualifying programming assignment given on the first day of class (and posted on this page) that will allow you and me to determine how well you're prepared for the course.


Homeworks and programming assignments

Late days on programming assignments:  Each student has 5 late days for use over the programming assignments (the pa’s, not the hw’s).  Any number of days can be used on each assignment, totaling no more than 5 over the term.  Write a note in your README file saying you are using 2 late days, or whatever, so I’ll know when everyone’s done.

hw1 Review Topics, due Thurs, Feb. 2 at class start (hw1 Solution)
pa1 Using Collection Classes, due Fri., Feb. 17  Solution to qualifying assignment pa1 Solution (zip)
hw2 Collection Classes, due Tues., Feb 14 (hw2 Solution)
hw3 Hashing, Inner classes, more on Maps, due Thurs., Feb. 23 hw3 Solution
pa2 pa2setup (zip) Hashing, due Wed, Mar. 7 
pa2 Solution (zip)
hw4 Sorting, Sets Apps and Priority Queues, due Tues., Mar. 20 (hw4 Solution)
pa3 Greedy Algorithms and Recursive Search, due Fri., Mar. 23 (only 2 late days can be used, deadline Sun., Mar. 25) pa3 Solution (zip)
games (zip) (API) Games Project, for pa4 and hw5
hw5 Intro to the Games Project, due Thurs., Apr 5 in class. hw5 Solution
pa4 Backtracking and Dynmic Programming with the Games Project, due Mon., Apr. 16 pa4 Solution (zip)
hw6
Prefix Codes, Character codes, and Intro to Graphs, due Thurs, Apr. 19 in class hw6 Solution
jgrapht (zip) (APIJGraphT open source graph library, for pa5 and pa6
pa5 Graph implementations and Graph algorithms, due Monday, Apr. 30 pa5 Solution (zip)
hw7 Graph Algorithms, due Thurs, May 3 in class hw7 Solution
pa6 Graph Algorithms (optional, can read solution), due Monday, May. 7

Class Notes: finalized after class

Tu, Jan. 24 notes Intro to qualifying assignment, review of encapsulation, APIs. Qualifying Assignment, due at class Thursday, Jan 26 SinglyLinkedList.java
Th, Jan. 26 notes Algorithm Analysis, Big-Oh and Big-Omega, including recursive cases
Tu, Jan. 31 notes Terminology, Collection classes: start Chap. 6

Note: Join our new Google group (email): your invitation has been sent to your cs.umb.edu address.
Th, Feb. 2 notes Collection Classes (handout on UML), specifically Lists
Tu, Feb. 7 notes Lists, Sets
Th, Feb. 9 notes Tokenizer for pa1, Maps
Tu, Feb. 14 notes  Map of String to List (for pa1), Intro Hashing (Chap. 20)

Th, Feb. 16 notes Hashing
Tu, Feb. 21 notes Hashing, inner classes
Th, Feb. 21 notes (handout on UML, Set API on back) HashSet implementation, bulk Set/Collection operations

Tu, Feb. 28 notes Set thinking, more on private inner classes (handout)

Th, Mar. 1 notes Set app for movie suggestions, bitmaps for Sets, performance comparison, Priority Queue

Tu Mar 6 notes Simulation (Sec. 13.2), JDK Collections class (Sec. 6.4), divide and conquer (Sec. 7.5, 7.6)

Th Mar 8 notes Dynamic Programming (Sec. 7.6) (handout)
Tu Mar 20 notes Intro to the Games Project (handout)
Th Mar 22 notes Midterm Review

Midterm Exam Tu, Mar. 27 Practice Midterm Exam Practice Midterm Solution
Note: makeup midterm Tu, Apr. 3, max score 85, see Mar 29 notes.
Th Mar. 29 notes Games Project
Tu Apr. 3 notes  UML for Games (handout) Observer pattern (paper handout), findbest for pa4

Th Apr. 5 notes
Finish up Games (handout), Start on Prefix Codes

Tu Apr. 10 notes Prefix codes, also Unicode and other important character encodings (handout)
Th Apr 12 notes Intro to Graphs (handout)
Tu Apr 17 notes Undirected Graphs, SimpleGraph1 implementation
Th Apr 19 notes
Topological Sort, DFS (handout)
Apr 24 notes DFS, BFS, start on shortest paths (Sec. 14.2)
Apr. 26 notes Shortest Path Algorithms (handout)
May 1 notes Dijkstra's Algorithm, Min-cost spanning trees
May 3 notes
Min-cost spanning trees, transitive closure
May 8: notes  Final Review

Final Exam Thurs, May 17 3pm-6pm, M-2-209  Practice Final Practice Final Solution
 

 

Textbooks

Required:

Mark Allen Weiss, Data Structures and Problem Solving in JAVA  (4th Edition), Addison Wesley 2010). The source code is available on line.

Recommended supplement to help with JAVA.

Core Java 2, Volume I--Fundamentals, by Cay Horstmann and Gary Cornell, Sun/Prentice Hall, 7th or 8th edition, ISBN 0-13-148202-5 or 0-13-235476-4, at Amazon (note good reviews here.) Follow book's link for code downloads (either edition). The 8th edition has chapters on the Collection classes and threads in Volume I, a definite plus over the 7th edition, but for basic Java, it doesn’t matter which edition you have, and has useful side notes on C/C++ vs. Java. Editions prior to the 7th are too old to be useful (pre-generics).

You can do all your work on the Department's network of UNIX/Linux systems, or deliver working code there. Apply for an account as soon as possible, following the instructions posted in the Unix lab (S-3-158). You need to apply for cs310 even if you already have a UNIX account here.

 


 

email

When your application for a course account has been approved you will have been added to the cs310 mailing list. You should check for email at least several times per week.  If you wish, you can put a .forward file in your home directory to forward your email to another mailbox.  This file simply contains your other mail address, such as user@gmail.com.

On line material

All material for this course will be kept in /courses/cs310/public_html, which we will abbreviate as $cs310. It is visible from our Unix/Linux network and on the Web as http://www.cs.umb.edu/cs310. This file is $cs310/index.html .

Written work

There will be about 6 programming assignments and about 5 written homeworks, a midterm and a final exam. For more information, see the syllabus.

Honesty

You must do your own work in this course. You are encouraged to discuss problems/projects with classmates, or to ask for help with debugging. When you do share ideas or get help you must acknowledge that help in writing. However IT IS NOT ALLOWED TO USE ANOTHER STUDENTS CODE IN ANY WAY WHILE DOING YOUR HOMEWORK, even if you acknowledge that.

Working from home

All the software you need to work from home is available for free.  We have written a primer on setting up your home pc here. Warning: In the past, many students have had problems setting up their home computers. We will provide some informal help with this task (and some of you may be able to help others) but we cannot provide technical support for your home computer. Difficulties you encounter working from home will not be accepted as excuses for late assignments.  You may bring your laptop to office hours for some help (no guarantees!)

working from home

Resources