Course Information


Class Description

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 apply 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. - Rob Johnson

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] Mo We 17:00~18:20 Academic Bldg. B206

Office Hours

Office Hours: Tu 15:30~17:30 (or send emails for appointments) at B422

Prerequisites

C or higher in AMS 210 or Mat 211; CSE 214 or CSE 260

TextBook

Required:
Steven Skiena, The Algorithm Design Manual, 2nd edition, Springer-Verlag

Optional:
MIT Open Courseware Introduction to Algorithms (Fall 2005).
Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Introduction to Algorithms.
Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirani. Algorithms.
Jon Kleinberg and Eva Tardos. Algorithm Design

Grading

Participation will be worth 5% of your grade
Homework will be worth 20% of your grade.
Midterm I will be worth 20% of your grade.
Midterm II will be worth 20% of your grade.
Final will be worth 35% of your grade and will cover all materials (cumulative).

Assignments

There will be total of 4~5 assignments one every two or so weeks. I will drop the lowest grade from among your homework scores. No late assignments will be accepted.

Course Learning Outcomes

The ABET objectives for the course are the following:
- Ability to perform worst-case asymptotic algorithm analysis
- Ability to define and use classical combinatorial algorithms for problems such as sorting, shortest paths and minimum spanning trees
- Knowledge of computational intractability and NP completeness.

The course will also satisfy the following program objectives:
(b) An ability to analyze a problem, and identify and define the computing requirements appropriate to its solution;
(j) An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices;

Major Topics Covered in Course

- Preliminaries: Algorithm correctness and efficiency, asymptotic notations, problem modeling, (1.5 weeks)
- Data Structures: Review of elementary data structures, dictionary data structures, including binary search trees, and priority queues (heaps). (1.5 weeks)
- Sorting: Algorithmic applications of sorting, analysis of quicksort, mergesort, and heapsort, distribution/radix sorting, lower bounds, (1.5 weeks)
- Problem Decomposition Algorithms: Dynamic programming (edit distance, chain matrix multiplication), divide-and-conquer algorithms (binary search and variants), (1.5 weeks)
- Combinatorial Search: Backtracking, exhaustive search, permutations/subsets, (1 week)
- Graph Algorithms: graph data structures (adjacency lists/arrays), BFS/DFS, topological sorting, connectivity testing, minimum spanning trees, shortest paths (Dijkstra's and Floyd's algorithms), (3 weeks)
- Intractability: problem reductions, NP-completeness, approximation algorithms, (2 weeks)




Notice




Dec. 21: Final Exam : 12:30-15:00
Dec. 7: Please finish the Course Evaluation
Dec. 1: HW5 out; due Dec. 14th on noon; bring them to my office (B422).
Dec. 1: Solutions to HW4 is available in Blackboard.
Nov. 8: Solutions to HW2&3 will be available in Blackboard.
Nov. 3: HW4 out; due Nov. 14th.
Oct.24: Midsemester Survey scheduled In class.
Oct.20: HW3 out; due 31st.



Course Materials



* Content details are subjected to changes.
** Please be prepared to take notes.

.
# DATE('15) CONTENT (READING) SLIDES Assignments & Daily Problems
1 8/29 Analyzing Algorithms (3-22) Lec0
8/31 Asymptotic Notations (31-40) Lec1 potd1
2 9/5 Program Analysis (40-51) Lec2 potd2
9/7 Elementary Data Structure (65-77) Lec3 potd3 HW1 out ( HW1) due on 21st.
3 9/12 Dictionaries (77-94) Lec4 potd4
9/14 NO CLASS Harvest Moon
4 9/19 Heapsort / Priority Queues (103-120) Lec5 potd5
9/21 Heapsort / Priority Queues cont. Lec6 potd6; HW2 out due on 5th.
5 9/26 Merge Sort / Divide-and-Conquer (120-123,135-139) Lec7 potd7
9/28 Quick Sort (123-130) Lec8 potd8
6 10/3 NO CLASS National Foundation Day
10/5 MIDTERM I HW2 DUE
7 10/10 Graph Data Structures (145-160) Lec9 potd9
10/12 Breadth-First Search (161-169) Lec10 potd9
8 10/17 Breadth-First Search cont. (161-169) potd10
10/19 Depth-First Search (169-184) Lec11 potd11; HW3 out due on 31st
9 9/24 Min. Spanning Tree (191-205) Lec12 No POTD; We will do Midsemester Survey
9/26 Min. Spanning Tree (191-205) cont potd13
10 10/31 Shortest Path (205-217) Lec13 potd14 HW3 due
11/2 Exhaustive Search - Backtracking (230-246) td> Lec14 potd15 HW4 out due Nov. 14th
11 11/7 Heuristic Search (247-269) Lec15
11/9 Dynamic Programming (273-280) Lec16 potd16
12 11/14 MIDTERM II HW4 due
11/16 Edit Distance (280-289) Lec17
13 11/21 DP Examples (289-310) Lec18 potd18
11/23 DP Examples cont.
14 11/28 NP-Completeness (317-350) Lec19
11/30 NP-Completeness Proofs Lec20 HW5 out; due Dec. 14th.
15 12/5 Reductions Lec21
12/7 REVIEW Review
F 12/21 FINALS (Cumulative; 12:30 - 15:00 )


Usesful Links:
Visualized Algorithms
Solutions for selected exercises/problems


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. Lecture slides 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.

Assignments grading policy

Assignment will be handed out in class and are due at the start of class of the due date. Legible handwritten copies of the assignments should be turned in. Programing components should be turned in through Blackboard before 23:55 of the due date. The Blackboard facility will mark your time of submission. It is your responsibility to check if the uploads are done properly and to check if you received a proper grade. Grades will be e-mailed to you individually in a timely fashion.

Total points of each assignment will be different depending on the difficulty of the problems. However, the maximum total point of an assignment will be less than or equal to two times the minimum total point of an assignment. Expect to see difficult problems towards the end of semester.

I will drop the lowest grade from among your homework scores. No late assignments will be accepted.

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.