ABOUT THIS COURSE

The goal of this course is to teach you solid knowledge and techniques in design and analysis of algorithms. You will learn algorithm design techniques such as

• Greedy Algorithms
• Divide-and-Conquer
• Dynamic Programming
• Approximation Algorithms

This course may be taken as CSE450 for undergraduate students or as CSE598 for graduate students. The requirement for graduate students will be higher than that for undergraduate students.

This course requires a lot of work. Depending on different knowledge levels the students may have, all students may not be required to spend the same amount of time on this course. However, every student is encouraged to preview before the class and review immediately after the class.

Students are encouraged to ask questions in class, and to fully use the office hours of the instructor and the TA. Students may also ask questions via email to the instructor and/or the TA. However, the instructor and the TA may choose to ignore questions on topics well covered in class and from students not attending the lecture(s).

There will be closed book exams and many heavyweight homeworks. Homeworks may involve theoretical contents as well as programming contents. The instructor will also assign suggested readings/exercises after each lecture. Students should work on these before the next lecture day but will not hand in the solutions to the exercises. Very often, solutions to these exercises can be found on the Internet. It is not cheating to get the solutions on the Internet. Discussion on these exercises are encouraged. However, you will gain only after you can understand the materials.

Web Material

You are required to make sure that you are enrolled at my.asu.edu by the end of first week of class. Also, it is your responsibility to make sure that your email address at my.asu.edu is the one you read everyday. Students are required to check the Bulletin Board which can be reached from my.asu.edu by following the link to Discussion Board on the left-hand side of the screen everyday. All course announcements will be posted on the bulletin board (some course announcements may actually be posted on the bulletin board only).

Tentative Schedule of Topics

• Introduction and Basic Algorithm Analysis (3 lectures)
• Graphs (3 lectures)
• Greedy Algorithms (3 lectures)
  • Minimum spanning trees
  • Huffman codes
  • Metroid theory
• Divide-and-Conquer (3 lectures)
  • Mergesort
  • Counting Inversions
  • Finding the closest pair of points
• Dynamic Programming (3 lectures)
  • Subset sums and knapsacks
  • Shortest paths
  • Distance vector protocols
• Network Flow (3 lectures)
  • The Ford-Fulkerson maximum flow method
  • Karp's maximum flow method
  • Computing a pair of node-disjoint paths
• NP-completeness and reductions (3 lectures)
  • NP, NP-hard and NP-complete
  • Reduction examples
• Approximation Algorithms (5 lectures)
  • The vertex-cover problem
  • Steiner minimum trees
  • The subset-sum problem
  • Multi-constrained QoS routing
• Optional Topics (if time permits)
  • Local search techniques
  • Randomized algorithms

Text book

Prerequisites:

Grading:

• Midterm-1 15%
• Midterm-2 15%
• Final Exam 20%
• Homeworks 50%

Special Cases:

• Medical Problems: Within two days, you need to submit a statement with the signature of the doctor and the seal of the hospital saying that you can not come to class during a particular time.
• Travel Accident: Within two days, you need to submit a police report stating that you are involved in an accident or your car broke down while you are traveling to school. Your car does not start at home is not a valid reason.
• Death of Immediate Family Members: If you need to attend the funeral of an immediate family member (defined as grant parents, parents, spouse, sibling or child), you need the instructor's prior approval. Proof may be required.

Policy on Homework Assignments:

Grade Appealing:

Policy on Midterms and Final Exams:

Brief Summary of the University Policies on Cheating: