CS310: Advanced Data Structures and Algorithms

 Fall 2018

Mo We 4-5:15, S-1-006

 

Instructor

Course Description

Textbook

Evaluation

Late Day Policy

Homework and Programming assignments

Coursework (Summary notes and PDF slides are posted here)

Resources

Accommodations

Student Conduct

 


Instructor  

Nurit Haspel
Office: S-3-071
Office Hours: Monday, Wendesday 1:30-2:50pm or by appointment
Office Phone: 617-287-6414
e-mail: nurit.haspel@umb.edu
Homepage: http://www.cs.umb.edu/~nurith
TA: Ramin Dehghanpour, e-mail: ramin.dehghanpoor001@umb.edu


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 are CS210 (Intermediate Computing), CS240 (C/Unix) and MATH 140 (Calculus I) or permission from the instructor.


Textbook

Required:

Algorithms (4th Edition), by Robert Sedgewick and Kevin Wayne,
Addison-Wesley, ISBN-13: 978-0321573513 ISBN-10: 032157351X

Algorithms Design, by Jon Kleinberg and Eva Tardos
Pearson, ISBN-13: 978-0321295354 ISBN-10: 0321295358

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 at Amazon

Recommended supplement to help with Algorithms:

Introduction to Algorithms, Third Edition
by Cormen, Leiserson, Rivest, and Stein
MIT press, 2009

Another Recommended Supplement:

The Algorithm Design Manual, Second Edition
by Steven S. Skiena
Springer-Verlag, 2008


Grade Evaluation

Homework assignments: 15% (3-4 homework assignments will be given)
Programming assignments: 15% (3-4 programming assignments will be given)
Midterm Exam: 30%
Final Exam: 40%

Late day policy

Homework assignments: No late submission without permission (points will be taken off)

Programming assignments: Five late days are allowed in total. Any number of days can be used on each assignment, totaling no more than 5 over the term. Write a note in your README or memo.txt file saying you are using late days so I will know. Points will not be taken off for authorized use of late days. Points will be taken off you submit late without notice, or exceed your 5 late days.


Homework/Programming assignments

Assignment (PDF) Posted/Given on Due Date Handouts Sample Solution
Homework #1 Sep. 5, 2018 Sep. 19, 2018, in class   Solution
Homework #2 Sep. 19, 2018 Sep. 26, 2018, in class   Solution
Programming assignment #1 Sep. 26, 2018 Oct. 10, 2018 by midnight,
in your unix account
Introduction to PA1
Homework #3 Oct. 10, 2018 Oct. 22, 2018, in class

 


Syllabus

Week

Topic

Book Chapters

Session Dates

Session Info

Slides/notes

1

Introduction

K&T, Ch. 1-2

Wednesday,
September 6

Introduction

Introduction

Intro. Notes

Matching notes from K & T

2

Intro
Runtime

K&T, Ch. 1-2

Monday,
September 10

Stable matching

K&T, Ch. 2
S&W, Ch. 1.4

Wednesday,
September 12

Runtime

Runtime

Runtime Notes

3

Runtime
Collections

K&T, Ch. 2
S&W, Ch. 1.4

Monday,
September 17

Finish up Runtime

S&W, Ch. 1

Wednesday,
September 19

Collections

Collections

Collections notes

4

Maps
Hashing

S&W, Ch. 3.4

Monday,
September 24

Maps
Hash functions, collisions

Hash notes from S & W

Wednesday,
September 26

Collisions, deletions,
rehashing

Intro to PA1

5

Hashing,
Intro to Graphs

S&W Ch. 3.4, 4.1
K&T Ch. 3

Monday,
October 1

Rehashing,
Undirected graphs

Intro to Induction
K&T Undirected Graph slides
S&W Graph slides

Wednesday,
October 3

Same

6

Graphs

S&W Ch. 4.1
K&T Ch. 3

Monday,
October 8

No class
(Columbus day)

Wednesday,
October 10

Undirected Graph traversal

Same

7

Graphs

S&W Ch. 4.1, 4.2
K&T Ch. 3

Monday,
October 15

BFS, 2-Coloring
Directed graphs

Same

Wednesday,
October 17

Directed Graphs, DAGS

S&W Directed Graph slides

 


Resources


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, Campus Center, UL Room 211, (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. The Code is available online at: http://www.umb.edu/life_on_campus/policies/code/