CS310 Advanced Data Structures and Algorithms
Syllabus
Fall 2009

Nurit Haspel (nurith@cs.umb.edu)

Course Description

A systematic study of the methods of structuring and manipulating data in computing. Application programming interfaces (APIs), data abstraction, and the encapsulation of implementations. The Java Collection Classes. The design and analysis of algorithms. Advanced techniques for program development and organization.

Prerequisites

• CS110 and CS210 (or one year of higher-level language instruction in Java, C, C++ or similar computer language, and fluency in Java).
• CS240 (or knowledge of C).
• Knowledge of stacks, queues, binary search trees, sorting (covered in CS210).
• Static and dynamic memory allocation, the stack and the heap (covered in CS240)
• MA140 (or one term of calculus).

Textbook

M. A. Weiss, Data Structures and Problem Solving using Java, 3^rd Edition, Addison Wesley, 2006.

Topics

• Review of and advanced algorithm analysis: Big O. The tyranny of growth rates. Weiss, Chap. 5.
• Collection classes, continued from CS210. Maps and Sets and the search for O(1). Looking for fast insertion and retrieval algorithms in various contexts. Hash tables. Memory allocation questions, pointer, shallow and deep copy. Simple array and linked list storage schemes, bitmaps, various kinds of trees, priority queues. Recognizing the right collection for an application. Weiss, Chap. 6, 20, 15 - 19, 21.
• Sorting (also continued from CS210): Heapsort, mergesort, proof that sorting is Omega(n log(n)) Chap 21, 8.
• Algorithm techniques: Divide-and-conquer, dynamic programming, greedy, and backtracking. Games. Chap 7, 10.
• Graph algorithms: Graph API and implementations. traversals, shortest paths; spanning trees. Chap. 14.

Assignments and Grading

The following grading scheme is subject to change with or without notice:

• Homework and Programming Assignments - 15% of your final grade for each type of assignment (30% total)

• Midterm - 30 % of your final grade

• Final exam - 40% of your final grade

You must have a documented reason to schedule a makeup exam. I must know that you need a makeup exam within 2 days after the exam date.

• Final Grade

Your final grade will be calculated using the following table. The minimum standard for passing the course is a percentage score of 40%. You also must pass the final exam (score at least 40% in the final exam). Keeping this in mind, your grade for the course will be calculated using the following table. Assume your final percentage score for the course is P:

P > 95	A+
95 ≥ P > 90	A
90 ≥ P > 85	A-
85 ≥ P > 80	B+
80 ≥ P > 76	B
76 ≥ P > 72	B-
72 ≥ P > 69	C+
69 ≥ P > 65	C
65 ≥ P > 61	C-
61 ≥ P > 55	D+
55 ≥ P > 50	D
50 ≥ P ≥ 40	D-
40 > P	F

Accommodations

Section 504 of the Americans with Disabilities Act of 1990 offers guidelines for curriculum modifications and adaptations for students with documented disabilities. If applicable, students may obtain adaptation recommendations from the Ross Center for Disability Services, M-1-401, (617-287-7430). The student must present these recommendations and discuss them with each professor within a reasonable period, preferably by the end of Drop/Add period.

Student Conduct

Students are required to adhere to the University Policy on Academic Standards and Cheating, to the University Statement on Plagiarism and the Documentation of Written Work, and to the Code of Student Conduct as delineated in the catalog of Undergraduate Programs, pp. 44-45, and 48-52. The Code is available online at www.umb.edu/student_services/student_rights/code_conduct.html

UNIX accounts, class email

You can do all your work on the Department's network of Unix systems, or you can work on your home computer and deliver projects to the Department’s systems, but be sure to test them there. Either way, you need an account at our site.

• Apply for an account as soon as possible, following the instructions posted in the Unix lab (S-3-158). When your application for a course account has been approved you will have been added to the cs310 mailing list.
• You should arrange to read mail sent to your account by logging in every day or so and running pine (say), or setting up forwarding to your off-site mailbox (put your other mailbox address in file .forward in your login directory, for example user@yahoo.com). Mail sent to the class will be archived for reference.
• Look for the line “module load …” in your UNIX .cshrc file and add “ java” to the end of it, so you will be using a current Java distribution

Homepage

The course home page is http://www.cs.umb.edu/cs310. This directory is visible in the filesystem of our UNIX machines as /data/htdocs/cs310. All material for this course will be kept in this area, which may sometimes be called “$cs310”.