CSE/MAT 373 Fall 2015. Algorithms
||Alisa Yorovski and Zhixin Shu
||137 Harriman Hall
|Rob's Office Hours:
||Tu 11:30am-2:00pm, 368 Computer Science Building
|Alisa's Office Hours:
||We 11-1pm 2203 OLD Computer Science Building
|Zhixin's Office Hours:
||TuTh 10-11:00am 2203 OLD Computer Science Building
||Mo 4-6pm, We 11:30am-1pm, 4-5pm, Th 1:30-3:30pm, 236B Engineering Building
- (Dec. 12) The final exam will be in .
- (Dec. 12) Update: the review session will be Monday at 6pm in CS 115.
- (Dec. 12) Zhixin has graciously agreed to hold a review session
Tuesday Dec. 15th at 5pm in room CS 120.
- (Dec. 12) Here's an article on B^e-trees,
the DAM model, etc. Please don't distribute this PDF outside this
- (Dec. 12) Solutions for the midterm are
now available. Also, I uploaded a corrected/completed solutions for
HW5 (at the link below).
- (Dec. 10) Solutions for HW4 and HW5 are now available.
- (Nov. 30) Rob's OH this week are moved to Thursday 11:30-2,
since that will probably be more useful for everyone.
- (Nov. 30) HW5 is now available. Due Dec. 7.
- (Nov. 20) HW4 is now available. Due Nov. 30.
- (Nov. 16) Rob's OH this week are Friday, Nov. 20, 2:30-5.
- (Nov. 5) Solutions and grading guide to HW3 are now available.
- (Nov. 3) The midterm will be on Nov. 9.
- (Oct. 26) Solutions and grading guide to HW2 are now available.
- (Oct. 16) HW3 is now available. Due Oct. 26.
- (Oct. 12) Rob's OH this week are Thursday (Oct. 15 11:30-2).
- (Oct. 12) Note Alisa's OH have changed permanently to 11-1.
- (Oct. 12) Solutions to HW1 are now available.
- (Oct. 6) In the last part of problem 8, assume the weights are positive.
- (Oct. 6) Alisa's office hours this week are Friday 3-4pm.
- (Oct. 6) Since we haven't yet covered counting sort, the
counting sort question in HW2 is canceled.
- (Sep. 25) HW2 is now available. Due in
class 10/9. There is a bonus for typing your homework, and other
grading policy changes described in the write-up.
- (Sep. 12) Tutoring for CSE 373 is available from the College of
Engineering and Sciences. You are encouraged to use this service
in addition to Rob, Alisa, and Zhixin's office hours. Time and
location information is listed at the top of this page.
- (Sep. 4) HW1 is now available. Due in class 9/18.
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.
- Math basics: Asymptotic notation, logarithms, commonly-occuring sums
- Sorting and searching: Insertion sort, merge sort, quicksort, integer sorting, search trees
- Greedy algorithms: Matchings, spanning trees
- Divide-and-conquer algorithms: Matrix multiply
- Dynamic programming: Edit distance, parenthesis problem
- Graph algorithms: Depth-first search, breadth-first search, Djikstra's algorithm, all-pairs shortest path, min-cut
- Amortized analysis: Union-find
- Randomized algorithms: Hash tables, , skip lists, Bloom filters
- Numerical algorithms: Newton-Raphson method
- External-memory algorithms:B-trees, LSM-trees, B^epsilon-trees
- Offline vs online algorithms and competitive analysis: Paging
- Complexity theory:P vs. NP, approximation algorithms
Students are encouraged to refer to the following texts:
- MIT Open Courseware
to Algorithms (Fall 2005). This course will follow roughly
the same outline.
- Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms.
- Steven Skiena. The Algorithm Design Manual.
- Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms.
- Jon Kleinberg and Eva Tardos. Algorithm Design
Requirements and Grading
Subject to tweaks throughout the semester.
- Homeworks (40%). I will assign 4-8 homeworks throughout
the semester. I will drop the lowest grade from among your homework
scores. No late assignments will be accepted.
- Class participation (10%). I strongly encourage
discussion and debate in class. Please don't hesitate to ask
questions if you don't understand or disagree with anything
covered in this course.
- Midterm exam (25%).
- Final exam (25%). The final is cumulative, so it will
have questions covering topics from the entire semester.
Note: the schedule may change throughout the semester.
||Introduction, binary search
||Sorting, recurrence relations
||More sorting, more recurrence relations
||Even more sorting, even more recurrence relations
||Final exam (2:15-5:00pm) Javits 100
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
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
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.