Course Information


Class Description

Flipped learning course for learning techniques for designing efficient algorithms, including choice of data structures, recursion, branch and bound, divide and conquer, and dynamic programming. Complexity analysis of searching, sorting, matrix multiplication, and graph algorithms. Standard NP-complete problems and polynomial transformation techniques.

Instructor

Assistant Professor Sael Lee
Office: Academic Bldg. B422
Email: sael at sunykorea dot ac dot kr
Phone: +82 (32) 626-1215

Meeting Time

[lecture] Mon/Wed 15:30~16:50 Academic Bldg. A117

Office Hours

Office Hours: Tue/Wed 17:00-18:00 (or send emails for appointments) at B422

Prerequisites

N.A.

TextBook

Required:
Introduction to Algorithms, Third Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein

Optional:
Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, and Umesh Vazirani. Textbook digital rental
The Algorithm Design Manual by Steven S Skiena (Nov 5, 2010)
An Introduction to the Analysis of Algorithms (2nd Edition) by Robert Sedgewick and Philippe Flajolet

Grading

Homeworkwill be 15% of your grade and will cover reading and viewing online lectures prior to class checked by a short quiz at the start of class.
Presentationwill be 15% of your grade on an algorithm topic of your choice from Selected Topics chapters of the book. (peer reviewed)
Midterm I & II will be worth 20% of your grade each.
Finals (cumulative) will be worth 30% of your grade.

Assignments

Since this is a flipped class, we solve problems in class.

Presentation

You will do one presentation on an algorithm topic of your choice from Selected Topics chapters of the book. (peer reviewed) .


Notice




10/18 modifications to the notes on list-based 01 knapsack.
+ hashed on w values and sorted on p values
+ drop when p'<= p'' & w'==w''

Class time change:
+10/25 -> 10/25 (W) 8pm
+11/01 -> 10/31 (Tu) 8pm
+11/15 -> 11/15 (W) 8pm

Syllabus in pdf

Note for 2017-09-06 modified (check sol for quiz)



Course Materials




Subject to change.
# DATE('14) CONTENT PRECLASS ASSIGNMENTS MISC
1 8/28 Analysis of Algorithms Read CLRS Ch 3 notes
8/30 Computational models quiz notes
2 9/04 Recurrence Relations: Even Split Read CLRS Ch4 quiz notes
9/06 Cont. Master Theorem Read CLRS Ch4.5 quiz notes
3 9/11 Uneven Split Read CLRS Ch9 quiz notes
9/13 Prune and Search: Selection Problem Read CLRS Ch9 & Ch33.4 quiz notes
4 9/18 Prune and Search: Selection Problem Read CLRS 5.1-5.3, Ch 9, quiz notes
9/20 Randomized Algorithms: Randomized Select Ch 5.1-3, Ch9.1-2 quiz notes
5 9/25 Closest Pair Algorithms Read Ch 15.3-4 notes
9/27 MIDTERM I
6 10/02 NO CLASS
10/04 NO CLASS
7 10/09 NO CLASS
10/11 Dynamic Programming - LCS Read CRLS Ch 15.4, 25.2 notes
8 10/16 DP - All pairs shortest path Read CRLS Ch 13 quiz notes
10/18 DP-01 Knapsack Read pg 425-427 & 01knapsack quiz notes
9 10/23 01 Knapsack quiz notes
10/25 (8pm) Augmenting Data Structures Read CRLS Ch 14
10 10/30 Augmenting Data Structures quiz notes
10/31 (8pm) Augmenting Data Structures quiz notes
11 11/06 Amortized Cost Read CRLS Ch 17 notes
11/08 Disjoint Sets: UNION-FIND Read CRLS Ch 21.1-3 notes
12 11/13 notes
11/15 MIDTERM II
13 11/20 Maximum Flow notes
11/22 Maximum Flow notes
14 11/27 Lower Bounds and Problem Reduction notes
11/29 Adversary Argument notes
15 12/04 In Class Problem Solving
12/06 Presentation Day
16 12/11 Presentation Day
F 12/18 (Mon) FINAL EXAM: 3:30-5:30pm



course policy


Attendance policy

Everyone is strongly urged to attend class regularly and actively participate. You will be responsible for learning all the materials covered in class. Notes and supplementary handouts will cover most of the material; however, in-class participation through engaging in discussions and asking questions should be valued learning activity.

academic misconduct policy

There is no excuse in cheating. Cheating will be considered as an academic misconduct and handled according to the Stony Brook regulations. If cheating has occurred during exam or is evident in submitted assignments, your will get a grade of F. Discussion of assignments is acceptable, however, returned assignments must show originality. This means near duplicate assignments with your peers or duplications of materials found on the web will be considered cheating. All involved personals in cheating will be penalized.




university policy


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, Room 128, (631)632-6748. They will determine with you what accommodations, if any, are necessary and appropriate. All information and documentation is confidential.Disability Support Services .

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 is 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 Academic Judiciary

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 University Community Standards 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. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.