[ General Information
| Lecture Schedule
| Resources
| Requirements
]
Course description: This course is for students interested in design and analysis of computer algorithms. The study of algorithms is at the very heart of computer science. Topics covered will include: various searching and sorting algorithms as well as a number of graph algorithms; time and space complexity; upper-bound, lower-bound, and average-case analysis; introduction to NP completeness. Some machine computation is required for the implementation and comparison of algorithms. This course is offered as CSE 373 and MAT 373. | Prerequisites: AMS 210 or Mat 211; CSE 214 or CSE 260. | Credits: 3. | Official description.
Instructor: Annie Liu | Email: liu@cs.stonybrook.edu | Office: Computer Science 1433 | Phone: 631-632-8463. | Office hours: Tue 9:30-10:00AM, 11-11:30AM, 12:30-12:55PM, Wed 9:30-9:55AM, 12:35-1PM, Thu 9:30-10AM, email for an appointment, or stop by any time I'm around.
TAs: Koosha Mir | Email: koosha.mirhosseini@gmail.com |
Office hours: Mon 3:30-4:50PM, Fri 4-5:20PM, CS 2110.
Haolong Ning | Email: Haolong.Ning@stonybrook.edu |
Office hours: Thu 3-4PM, CS 2110.
Grader: Jasison George | Email: jaisong87@gmail.com.
Lectures: Tue Thu 1:00-2:20PM, in Computer Science 2120.
Textbook: The Algorithm Design Manual by Steve Skiena. Second Edition, Springer, 2008. | Steve Skiena's textbook page.
Grading: In-class exercises, weekly or biweekly assignments, quiz 1, quiz 2, and a final, worth 10%, 20%, 20%, 20%, and 30%, respectively, of the grade. Extra credit work will be given as appropriate. Partial credit will be given for partial work. Reduced credit for late assignments, 20% off per day. | Letter grades will be assigned by subjectively identifying brackets in the numeric scores. Borderline grades will be determined by my opinion of students on the boundary. There is no pre-determined curve. In particular, I have no objection to giving all high grades (or all low grades) if it looks appropriate.
Course homepage: http://www.cs.stonybrook.edu/~liu/cse373/
Date Subject Lecture topic Ch Reading Asgn Slides 8/28 Preliminaries Introduction to algorithms 1 1-27 1 8/30 Asymptotic notation 2 31-40 A1 2 9/4 No class, labor day break 9/6 Analysis and Logarithms 2 41-56 3 9/11 Data Structures Elementary data structures 3 65-83 4 9/13 Dictionary data structures 3 83-89 A2 5 9/18 Hashing 3 89-98 6 9/20 Sorting Heapsort/Priority queues 4 103-119 7 9/25 Mergesort/Quicksort 4 120-128 A3 8 9/27 Linear sort 4 129-138 9 10/2 Quiz 1 10/4 Graph Algorithms Data structures for graphs 5 145-160 10 10/9 Breadth-first search 5 161-168 A4 11 10/11 Topological sort/Connectivity 5 169-183 12 10/16 Minimum spanning trees 6 191-204 13 10/18 Shortest paths 6 205-216 A5 14 10/23 Exploiting graph algorithms 6 217-224 10/25 Search Combinatorial search 7 230-238 15 10/30 Program optimization 7 239-247 A6 16 11/1 Decomposition Elements of dynamic programming 8 273-290 16 11/6 Examples of dynamic programming 8 291-300 17 11/8 Limitations of dynamic prog 8 301-310 18 11/13 Quiz 2 11/15 Intractability Reductions 9 316-322 A7 19 11/20 Easy reductions 9 323-329 20 11/21-25 Thanksgiving break 11/27 Harder reductions 9 330-333 21 11/29 The NP-completeness challenge 9 334-340 22 12/4 Advanced topic Concurrent and distributed paradigms A8 12/6 Non-blocking queues/Leader election 12/17 Final exam, Monday, 5:30-8PM. You can prepare one hand-written personal "crib sheet", single-sided.Unless specified otherwise, assignments are always due at the beginning of the class on the day that the next assignment is given.
Interactive Site of This Course, for students in the class
Computer Science Department Windows Computing Facilities
Learn all information on the course homepage. Check the interactive site periodically for dynamic contents.
Attend all lectures and take good notes. This is the most efficient way to learn the course materials, because we will both distill and elaborate textbook materials and discuss other important materials. We will start promptly on time, with quick reviews as well as exercises. We will have every student participate in solving problems and presenting solutions in class.
Do all course work. The readings are to help you preview and review the materials discussed in the lectures. The assignments are to provide concrete experiences with the basic concepts and methods covered in the lectures. The exercises are to help you keep up with the lectures and the assignments. The exams will be comprehensive.
Ask questions and get help. Ask questions in class, visit the TA during office hours, and visit the professor with any remaining questions. Talk with your classmates, and share ideas (but nothing written or electronic).
Academic Integrity: All course work must be done individually, unless specified otherwise; you may discuss ideas with others and look up references, but you must write up your solutions independently and credit all sources that you used. Any plagiarism or other forms of cheating discovered will have a permanent consequence in your university record.
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. 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/
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.
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. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.