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: Mon, Wed, Fri 12:00PM - 12:50PM
Lecture Location: NSC 225
Credits: 3
Instructor: Kelin Luo
Office Location: 306 Davis Hall
Office Hour: Mon and Wed 03:00PM - 03:50PM
Except for the office hours provided, you can also set up an appointment (by email) for additional office hours.
Email: [first name][last name][at][buffalo][dot][edu]
|
Teaching Assistants: Xiaoyu Zhang Ibrahim Bahadir Altun Wen Zhang Pratik Pokharel Jason Niu Mohammad Jakir Hossain Sumaiya Islam Mouno |
Email: [zhang376][at][buffalo][dot][edu][ialtun][at][buffalo][dot][edu] [wzhang59][at][buffalo][dot][edu] [pratikpo][at][buffalo][dot][edu] [jasonniu][at][buffalo][dot][edu] [mh267][at][buffalo][dot][edu] [smouno][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, Exam |
| 2. Have a good overall picture of algorithm analysis and design techniques | Quiz, Homeworks, Projects, Exam |
| 3. Solve simple to moderately difficult algorithmic problems arising in applications | Quiz, Homeworks, Projects, Exam |
| 4. Understand the notions of NP-completeness and approximation algorithms | Quiz, Homeworks, Exam |
| 5. Be able to demonstrate the hardness of simple NP-complete problems | Homeworks, Exam |
There is no textbook for the course. All needed materials will be provided via the course's website and Piazza.
You will be using various free on-line tools for this course -- links will be posted on the course website.
Your final grade will be computed as follows:
| HWs/Projects | Releasing Date | Deadline |
|---|---|---|
| HW1 | Sep 02 | Sep 16 |
| HW2 | Sep 23 | Oct 07 |
| HW3 | Oct 28 | Nov 11 |
| HW4 | Nov 18 | Dec 02 |
| Project 1 | Oct 07 | Oct 21 |
| Project 2 | Nov 04 | Nov 18 |
Late assignments will be accepted up to 2 days late (only by Email submission) for a penalty of 50% of the total points (lower your earned points by 50% of the possible points for the entire assignment). Please keep track of the time if you are working up until the deadline. Submissions become late after the set deadline, even by 1 minute.
Keep in mind that submissions will close 48 hours after the original deadline and you will no longer be able to submit your assignment
after that time.
If your latest submission was submitted:
Attendance in lecture is not mandatory, but highly encouraged. Lectures
will typically be recorded, but recordings have been known to get corrupted; do not count on lecture recordings. No makeup in-class quiz will be given except in provably extreme circumstances.
There will be two in-class 45-minute midterm exams and one 3-hour final exam. The midterms are worth 10% of your grade each.
The final exam is worth 30% of your grade. We reserve the right to change the scaling of the exams.
No makeup exams will be given except in provably extreme circumstances.
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, please consult on Piazza. Any questions about the grading of a piece of work must be raised within one week (and the regrade deadline posted on Piazza) of the date that the work was returned by the teaching assistant or the instructor.
Please see the University rules on an Incomplete. Assignment of an ''I'' grade is at the discretion of the instructor.
The last day to resign the course is Wednesday, Nov 13, 2024.
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 the Undergraduate Academic Integrity policy and Graduate Academic Integrity policy.
Failure to follow to the university academic integrity policy will be treated as cheating and a violation of academic integrity. For more information, please refer to theUndergraduate Academic Integrity Procedures and Graduate Academic Integrity Procedures.
* Homework and project assignments must be completed individually. Using reference materials from lecture notes, libraries, or books is allowed, provided that you explicitly cite these sources in your submission. However, copying or aggregating solutions from online sources (e.g., Stack Overflow, Google, YouTube, or other platforms) or from previous semesters is still considered cheating, even if you cite the sources.
* 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.
* Excuses such as "I was not sure" or "I did not know" will not be accepted. If you are not sure, ask the TAs and/or the instructor.
In accordance with the current university and departmental policy on academic integrity violations, we will follow this sanctions:
* If the violation is the first ever academic violation, then it will result in a minimum of a letter grade reduction in the course and zero in the relevant assignment/exam. If the violation is serious enough, then it can result in an F in the course.
* If the violation is the student's second academic violation, then it will result in an automatic F letter grade in the course.
* All the violation (whether it's the first or second instance) will be reported to the Office of Academic Integrity (OAI), the Department, and the School, as required by the University policy Academic Integrity.
For more details, please see The Computer Science and Engineering department's
policy on academic integrity can be found here:Department's undergraduate Graduate Academic Integrity Policy andDepartment's Graduate Academic Integrity Policy.
We understand that students are under a lot of pressure and people make mistakes. If you have concerns that you may have violated academic integrity on a particular assignment, and would like to withdraw the assignment, you may do so by sending me an email BEFORE we discover it. The email should take the following format:
Dear Dr. Luo,
I wish to inform you that on assignment X, the work I submitted was not entirely my own. I would like to withdraw my
submission from consideration to preserve academic integrity.
J.Q. Student
Person #12345678
UBIT: jqstuden
When we receive this email, student J would receive a 0 on assignment X, but would not receive an F for the course, and would
not be reported to the office of academic integrity.
All materials prepared and/or assigned by me for this course are for the students' educational benefit. Other than for permitted collaborative work, students may not photograph, record, reproduce, transmit, distribute, upload, sell or exchange course materials, without my prior written permission. "Course materials" include, but are not limited to, all instructor-prepared and assigned materials, such as lectures; lecture notes; discussion prompts; study aids; tests and assignments; and presentation materials such as PowerPoint slides, Prezi slides, or transparencies; and course packets or handouts. Public distribution of such materials may also constitute copyright infringement in violation of federal or state law. Violation of this policy may additionally subject a student to a finding of "academic dishonesty" under the Academic Integrity policy and/or disciplinary charges under the Student Code of Conduct.
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.
UB is committed to providing a safe learning environment free of all forms of discrimination and sexual harassment, including
sexual assault, domestic and dating violence and stalking. If you have experienced gender-based violence (intimate partner
violence, attempted or completed sexual assault, harassment, coercion, stalking, etc.), UB has resources to help. This includes
academic accommodations, health and counseling services, housing accommodations, helping with legal protective orders, and
assistance with reporting the incident to police or other UB officials if you so choose. Please contact UB’s Title IX Coordinator at
716-645-2266 for more information. For confidential assistance, you may also contact a Crisis Services Campus Advocate at
716-796-4399
As a student you may experience a range of issues that can cause barriers to learning or reduce your ability to participate in daily
activities. These might include strained relationships, anxiety, high levels of stress, alcohol/drug problems, feeling down, health
concerns, or unwanted sexual experiences. Counseling, Health Services, and Health Promotion are here to help with these or other
issues you may experience. You can learn more about these programs and services by contacting:
Counseling Services:
● 120 Richmond Quad (North Campus), 716-645-2720
● 202 Michael Hall (South Campus), 716-829-5800
Health Services:
● 4350 Maple Rd, Amherst, NY 14226, 716-829-3316
Health Promotion:
● 114 Student Union (North Campus), 716-645-2837
The UB School of Engineering and Applied Sciences considers the diversity of its students, faculty, and staff to be a strength,
critical to our success. We are committed to providing a safe space and a culture of mutual respect and inclusiveness for all. We
believe a community of faculty, students, and staff who bring diverse life experiences and perspectives leads to a superior working
environment, and we welcome differences in race, ethnicity, gender, age, religion, language, intellectual and physical ability,
sexual orientation, gender identity, socioeconomic status, and veteran status.
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