Data and Algorithm Analysis

About the course

This course emphasizes the understanding of data structures and algorithms from an analytical perspective rather than from an implementation standpoint. The concepts developed allow discussion of the efficiency of an algorithm and the comparison of two or more algorithms with respect to space and run-time requirements. Analytical methods are used to describe theoretical bounds as well as practical ones. In general, this course discusses paradigms for algorithm design, addresses the constraints that affect problem solvability, and defines the theory of NP-completeness as a means to understand intractable problems.

Course Outline

Below is the schedule for the course, which may be adjusted as needed during the semester. Students are expected to supplement lectures with a careful study of the relevant sections of the textbook.

Textbook

• Algorithm Design by Jon Kleinberg and Eva Tardos. Addison-Wesley, 2006, ISBN: 0321295358.

Additional Reference

• Introduction to Algorithms (Fourth Edition). Cormen, Leiserson, Rivest, and Stein. MIT Press, 2022. ISBN: 9780262046305.

Reading

There will be reading assignments consisting of sections from the textbook. Reading assignments will be announced on the class web page and you are strongly encouraged to complete them by class time.

Grading

Homework will be assigned every two to three weeks. There will be a midterm exam and a comprehensive final exam. Both homework and exams are due midnight of the deadline day. The grade will be based on:

Key points

• Each homework will consist of multiple problems; you will have about one week between when the homework is posted and the deadline for submitting the solutions. The Midterm and Final exams will consist of multiple problems and will have their own deadlines.
• The homework and exams will be posted on the class canvas page. Students will submit their solutions through Canvas. The solutions need to be typeset (LATE Xis suggested); handwritten solutions will not be graded.
• Solutions submitted after the corresponding deadline will not be graded, except in those situations where you have obtained prior approval from the instructor. Expect some homework problems to be difficult and to require creative solutions; please start working on the homework early, and take advantage of the office hours that the TA hold.

• If you feel that your solutions have been graded incorrectly you may request a re-evaluation within one week of the date you received the graded assignment back.

• 20% Midterm Exam (take home)
• 30% Final Exam (take home)
• 50% Homework

Grading Scheme