CSE373 (Fall 2012)
Analysis of Algorithms

[ General Information | Lecture Schedule | Resources | Requirements ]


General Information

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/


Lecture Schedule

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.


Resources

Interactive Site of This Course, for students in the class

Computer Science Department Windows Computing Facilities


Requirements

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.

Your handins, whether on paper or in electronic form, should include the following information at the top: your name, student id, course number, assignment number, and due date, and should be submitted in a neat and organized fashion.

Your programming solutions should always be submitted with a README.txt file explaining where things are, what you did and found for the assignment (that is not described in the assignment handout), and how to run and test your code.

Your approach to solving problems is as important as your final solutions; you need to show how you arrived at your solutions and include appropriate explanations. Always include good explanations in your submissions and good comments in your code.

If you feel your grade was assigned incorrectly, please bring it up no later than two weeks after the assignment was returned to the class.

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.


Annie Liu (Thanks to Prof. Steve Skiena: I am using much of his course material.)