CS310: Advanced Data Structures and Algorithms

 Fall 2017

Mo We 4-5:15, Y-2-2110

 

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 2:30-3:45pm 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. 6, 2017 Sep. 18, 2017, in class   Solution
Homework #2 Sep. 18, 2017 Sep. 27, 2017, in class   Solution
Programming assignment #1 Sep. 27, 2017 Oct. 11, 2017 by midnight,
in your unix account
Introduction to PA1 Solution
Homework #3 Oct. 11, 2017 Oct. 23, 2017, in class Solution
Programming assignment #2 Oct. 23, 2017 Nov. 6, 2017, by midnight,
in your unix account
Grid
TinyEWD2.txt
Solution
Homework #4 Nov. 6, 2017 Nov. 15, 2017, in class midterm Solution
Midterm Solution
Programming assignment #3 Nov. 15, 2017 Nov. 27, 2017, midnight,
in your unix account

Solution
Homework #5 Nov. 27, 2017 Dec. 6, 2017

 


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 11

Finish up intro,
Stable matching

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

Wednesday,
September 13

Runtime

Runtime

Runtime Notes

3

Runtime
Collections

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

Monday,
September 18

Finish up Runtime

S&W, Ch. 1

Wednesday,
September 20

Collections

Collections

Collections notes

4

Maps
Hashing

S&W, Ch. 3.4

Monday,
September 25

Maps
Hash functions, collisions

Hash notes from S & W

Wednesday,
September 27

Collisions, deletions,
rehashing

Intro to PA1

5

Hashing,
Intro to Graphs

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

Monday,
October 2

Rehashing,
Undirected graphs

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

Wednesday,
October 4

Same

6

Graphs

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

Monday,
October 9

No class
(Columbus day)

Wednesday,
October 11

Undirected Graph traversal

Same

7

Graphs

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

Monday,
October 16

BFS, 2-Coloring
Directed graphs

Same

Wednesday,
October 18

Directed Graphs, DAGS

S&W Directed Graph slides

8

Directed graphs
Greedy algorithms

S&W Ch. 4.2-4.4
K&T Ch. 3-4

Monday,
October 23

Strong Connectivity
Intro to Greedy algorithms

S&W MST slides
K&T Greedy I slides

Wednesday,
October 25

Greedy Algorithms

Practice midterm

9

Greedy Algorithms
Midterm

Monday,
October 30

Dijkstra's Algorithm
Midterm review

Midterm intro

Midterm practice (solved)

Wednesday,
November 1

Midterm

10

Greedy
Dynamic Programming

S&W Ch. 4.4
K&T Ch. 4, 6

Monday,
November 6

Greedy Algorithms

S&W Shortest paths
Arbitrage formalism

Wednesday,
November 8

Dynamic Programming

K&T DP I
My old DP notes

11

Greedy
DP

K&T Ch. 6

Monday,
November 13

Scheduling Problems

K&T Greedy I

Wednesday,
November 15

Dynamic Programming

12

Compression

S&W Ch. 5.5

Monday,
November 20

Tries
Huffman coding

S&W Tries (for completion)
S&W Compression

Wednesday,
November 22

13

Network Flow

K&T, Ch. 7
S&W, Ch. 6.4

Monday,
November 27

Cuts, Flows

S&W Flows
K&T Flows I

Wednesday,
November 29

Max Flow algoritms

 

14

Reductions and NP

K&T Ch. 8

Monday,
December 4

Polynomial Reductions

K&T Reductions I

Thursday,
December 8

Reductions
NP completeness

K&T Reductions II
Practice final

 


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/