CSE/MAT 373 Spring 2016. Algorithms

Lecturer: Rob Johnson
TAs: Chai Zhi, Timothy Barron
Location: 104 Frey Hall
Time: TuTh 2:30pm-3:50pm
Rob's Office Hours: Tu 4:00pm-5:30pm, Th 1:00pm-2:00pm, 368 Computer Science Building
Tim Barron's Office Hours: We 4-5pm 2217 OLD Computer Science Building
Sarthak Ghosh's Office Hours: Mo 12:15-2:15pm, 2217 OLD Computer Science Building
Ziqiao Guan's Office Hours: We 3-5pm, 2217 OLD Computer Science Building
Yeseul Lee's Office Hours: Mo 4:30-6pm, 106 NEW Computer Science Building
Fumi Honda's Office Hours: Fr 9-10am, 2217 OLD Computer Science Building
Leixiang Wu's Office Hours: Mo 2-3pm, 2217 OLD Computer Science Building
Yuren Huang's Office Hours: Th 2:30-3:30pm, 2217 OLD Computer Science Building
Chai Zhi's Office Hours: We 2:30-3:30pm, 2217 OLD Computer Science Building
Geoffrey Churchill's Office Hours: Fr 2:30-4:30pm, 2217 OLD Computer Science Building

News

Overview

The goal of this course is to enable students to recognize, analyze, and solve algorithmic problems. At the end of the course, students should be able to extract the core algorithmic problems that underlie many programming tasks, identify and use appropriate algorithmic techniques to solve those problems, and analyze and compare the performance of algorithmic solutions.

Topics

References

Students are encouraged to refer to the following texts:

Requirements and Grading

Subject to tweaks throughout the semester.

Schedule

Note: the schedule may change throughout the semester.
Date Topic Reading assignment Notes
No class: Rob sick None None
Introduction, binary search, selection sort None None
Merge sort None None
Recurrences, the substitution method None See section 12.2.3 of Mathematics for Computer Science
Quicksort None None
Linear-time median finding, application to quicksort None None
Big-Oh notation and friends None None
Master method None None
Divide and conquer I None None (see notes for later class)
Divide and conquer II None None (see notes for later class)
No class: Rob sick None None
Dynamic programming I None None (see notes for later class)
Class canceled due to steam leak in Frey Hall None None
Divide and conquer I (again) None None
Spring Break None None
Spring Break None None
Divide and conquer II (again) None Notes
Dynamic programming I (again) None None
Dynamic programming II (again) None None
Dynamic programming III (again) None None
Midterm (proposed date) None None
Graph algorithms I None None
Graph algorithms II None None
Graph algorithms III None None
External-memory algorithms I None None
External-memory algorithms II None None
Randomized algorithms I None None
Complexity theory I None None
Complexity theory II None None
Complexity theory III None None
5/16 Final exam (11:15-1:45pm)

Americans with Disabilities Act:

If you have a physical, psychological, medical or learning disability that may impact your course work, please contact Disability Support Services, ECC (Educational Communications Center) Building, room128, (631) 632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.

Academic Integrity:

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Faculty are required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology & Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at http://www.stonybrook.edu/uaa/academicjudiciary/

Critical Incident Management:

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of Judicial Affairs any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures.