Introduces basic elements of the design and analysis of algorithms. Topics include asymptotic notations and analysis, divide and conquer, greedy algorithms, dynamic programming, fundamental graph algorithms, NP-completeness, and approximation algorithms. For each topic, beside in-depth coverage, we discuss one or more representative problems and their algorithms. In addition to the design and analysis of algorithms, students are expected to gain substantial discrete mathematics problem solving skills essential for computer scientists and engineers.
Lecture Time: Tue, Thu 11:00PM - 12:20PM
Lecture Location: Nsc 215
Credits: 3
Please sign up for the course on Piazza. You can post all questions related to lectures, quiz, and assignments on Piazza. Instructor posts announcement on piazza.
Instructor: Kelin Luo
Office Location: 306 Davis Hall
Office Hour: Tue 09:30 - 10:30 and 12:30-13:30, Thu 12:30 - 13:30
Except for the office hours provided, you can also schedule an appointment with me via email for additional office hours at least two days in advance.
Email: [first name][last name][at][buffalo][dot][edu]
|
Teaching Assistants: Ibrahim Bahadir Altun Yuxin Liu Chen Xu Wen Zhang |
Office Hour: Fri 9:00 - 11:00Thu 9:00 - 11:00 Mon 9:00 - 11:00 Wed 9:00 - 11:00 |
Email: [ialtun][at][buffalo][dot][edu][yuxinliu][at][buffalo][dot][edu] [chenxu][at][buffalo][dot][edu] [wzhang59][at][buffalo][dot][edu] |
You should have taken CSE250 (data structure) or similar courses before. We expect you to have certain levels of mathematical maturity: You should have basic understanding of calculus (e.g., limit, differentiation, integration) and linear algebra (e.g., matrix, vector space, linear transformation); You should be comfortable to read and write mathematical proofs, understanding common proof strategies (e.g., proof by induction, contradiction). We also expect you to have some programming experience: know what is a computer program, and be able to read and write code.
Master the fundamental concepts in algorithm analysis and design.
| Learning Outcomes | Method of Assessment |
|---|---|
| 1. Proficiently understand and apply asymptotic notations and analysis | Quiz, Homeworks, Final Exam |
| 2. Have a good overall picture of algorithm analysis and design techniques | Quiz, Homeworks, Projects, Final Exam |
| 3. Solve simple to moderately difficult algorithmic problems arising in applications | Quiz, Homeworks, Projects, Final Exam |
| 4. Understand the notions of NP-completeness and approximation algorithms | Quiz, Homeworks, Final Exam |
| 5. Be able to demonstrate the hardness of simple NP-complete problems | Homeworks, Final Exam |
Your final grade will be computed as follows:
* Class Participation: 10% = 1% × (10 quizzes). Quizzes will be given randomly during the lectures.
* Homeworks: 40% = 8% × (5 homeworks). We choose the best 5 scores out of 6 homeworks.
* Programming Projects: 20% = 10% × (2 programming projects).
* Final Exam: 30%.
Note: (1) Each component will receive a numerical score. The course grade will be based on the weighted total of all components. (2) Class participation includes attendance, participation in class discussions, or quizzes. We will choose the best 10 scores out of a total of 12-15 quizzes for grading. (3) Although the weight of quiz is relatively low, it is a very
important and essential part for learning concepts and algorithms. Problems similar
to quiz and homework problems may appear in final exams. (4) The final exams will be closed-book, and closed-notes.
The following outlines the grade breakdown that will be utilized for assigning grades in the course. Please note that these ranges may be subject to adjustment at the end of the semester to address any inconsistencies or hardships that may arise. It is important to emphasize that grades will not be curved/adjusted during the semester.
| Grade | Percentage |
|---|---|
| A | 90% - 100% |
| A- | 85% - 89.99% |
| B+ | 80% - 84.99% |
| B | 75% - 79.99% |
| B- | 70% - 74.99% |
| C+ | 65% - 69.99% |
| C | 60% - 64.99% |
| C- | 55% - 59.99% |
| D | 50% - 54.99% |
| F | Below 50% |
If you have a question about the grading of any piece of work, first consult with
the teaching assistant who graded your work on Piazza. If you cannot resolve your
questions with the teaching assistant, you should consult with the instructor.
Any questions about the grading of a piece of work must be raised within
one week of the date that the work was returned by the teaching assistant or
the instructor.
Academic integrity is a fundamental university value. Through the honest completion of academic work, students sustain the integrity of the university and of themselves while facilitating the university's imperative for the transmission of knowledge and culture based upon the generation of new and innovative ideas. For more information, please refer to theGraduate Academic Integrity policy.
* Collaboration and Discussions: You are permitted to engage in discussions with your classmates regarding homework problems. Prior to discussing, please take the time to thoroughly consider each problem independently.
All solutions must be written in your own words and produced by you individually. If you collaborate with fellow students, you must provide their names when submitting your work.
* Use of Artificial Intelligence Technologies: The use of generative artificial intelligence, large language models (LLMs), and other artificial intelligence-related technologies is prohibited. This encompasses tools like OpenAI's ChatGPT, Google Bard, and AI models within search interfaces like Google or Bing. Utilizing these tools for course content creation, debugging assistance, idea generation, or similar purposes constitutes a breach of academic integrity. All work submitted for evaluation in this course must be exclusively your own.
* Consequences for Violations: Failure to follow to the aforementioned rules will be treated as cheating and a violation of academic integrity. In addition to receiving an immediate grade of F for the course, further actions in alignment with theDepartment's Academic Integrity Policy and theUniversity's Academic Integrity Policy will be taken.
Here are some of the University's available free resources:
* If you need help with writing, check UB Center for Excellence in Writing theWriting Support Services
* If you have issues with your device, the UB University Libraries provides access to computers, as well as equipment loans, see theEquipment Loans
* Your well-being is highly important, if you have any concerns, please check theCounseling Service
If you have any disability which requires reasonable accommodations to enable you to participate in this course, please contact the Office of Accessibility Resources in 60 Capen Hall, 716-645-2608 and also the instructor of this course during the first week of class. The office will provide you with information and review appropriate arrangements for reasonable accommodations, which can be found on the web at theAccessibility Resources.
There are no required textbooks, but most of the contents we will discuss are covered in the following books:
Similar courses taught in other universities:
| HWs/Projects | Releasing Date | Deadline |
|---|---|---|
| HW1 | Feb 06 | Feb 20 |
| HW2 | Feb 20 | Mar 05 |
| HW3 | Mar 05 | Mar 19 |
| HW4 | Mar 26 | Apr 09 |
| HW5 | Apr 09 | Apr 23 |
| HW6 | Apr 23 | May 07 |
| Project 1 | Feb 13 | Mar 12 |
| Project 2 | Mar 19 | Apr 30 |
| Week | Date | Topic | Contents | Other Notes |
|---|---|---|---|---|
| 1 | Jan 25 | Introduction | course syllabus | |
| 2 | Jan 30 | asymptotic notations (KT 2.2) | ||
| Feb 01 | common running times (KT 2.4) | |||
| 3 | Feb 06 | Graph Basics | graph basics, connectivity and traversal (KT 3.1, 3.2, 3.4) | HW 1 released |
| Feb 08 | topological order (KT 3.6) | |||
| 4 | Feb 13 | Greedy Algorithm | basics, interval scheduling (KT 4.1, 4.2) | Project 1 released |
| Feb 15 | optimum caching (KT 4.3) | |||
| 5 | Feb 20 | huffman code (KT 4.8) | HW 1 deadline HW 2 released |
|
| Feb 22 | More Greedy Algorithm Exercise Problems | |||
| 6 | Feb 27 | Divide and Conquer | merge sort and counting inversions (KT 5.1, 5.3) | |
| Feb 29 | quicksort, median-finder, selection (KT 13.5) | |||
| 7 | Mar 05 | polynomial and matrix multiplications (KT 5.5) | HW 2 deadline HW 3 released |
|
| Mar 07 | solving recurrences and fibonacci number (KT 5.2) | |||
| 8 | Mar 12 | More Divide and Conquer Algorithm Exercise Problems | Project 1 deadline | |
| Mar 14 | Dynamic Programming | weighted interval scheduling (KT 6.1) | ||
| 9 | Mar 19 | Spring Break, no class | HW 3 deadline Project 2 released |
|
| Mar 21 | Spring Break, no class | |||
| 10 | Mar 26 | subset sums and knapsack (KT 6.4) | HW 4 released | |
| Mar 28 | shortest paths and Matrix-Chain-Multiplication | |||
| 11 | Apr 02 | Optimum Binary Search Tree | ||
| Apr 04 | More Dynamic Programming Algorithm Exercise Problems | |||
| 12 | Apr 09 | Graph Algorithms | Kruskal's algorithm for MST (KT 4.5) | HW 4 deadline HW 5 released |
| Apr 11 | Prim's algorithm for MST (KT 4.6) | |||
| 13 | Apr 16 | Dijkstra's algorithm for shortest path (KT 4.4) | ||
| Apr 18 | Bellman-Ford, Floyd-Warshall (KT 6.8) | |||
| 14 | Apr 23 | NP-Completeness | P, NP, Co-NP (KT 8.1-8.3) | HW 5 deadline HW 6 released |
| Apr 25 | polynomial time reductions and NP (KT 8.4) | |||
| 15 | Apr 30 | circuit-SAT, 3-SAT (KT 8.5) | Project 2 deadline | |
| May 02 | independent set problem and more exercise problems (KT 8.5) | |||
| 16 | May 07 | Last Day of Classes, Q & A | HW 6 deadline | |
| May 09, Thursday, 15:30-18:30: Final Exam, at Nsc 225 | ||||