Please note
It is your responsibility to make sure you read and understand the contents of this syllabus. If you have any questions, please contact the instructor.
Acknowledgment
Once you have read the syllabus carefully, please sign this form and return it to Atri. As an incentive for you to fill in this form, you will not receive any feedback on your assignments till you fill in the form.
Academic Integrity
Penalty for academic integrity violation
You will get an F in the entire course for your first academic integrity violation. So do not cheat and you will be fine in this course. Unfortunately, I have had to fail students in the last couple of offerings of CSE 331 since they did not follow the class policies. While it gives me no pleasure in failing students, I will do so since I have to be fair to (the vast majority) of students who do not cheat. Please read the homework policies to make sure you follow all the rules and do not violate academic integrity.
For more details, please see the department policy on academic integrity .
Instructor Information
Atri Rudra
- :
atri "at" buffalo "dot" edu
- : 319 Davis
- : 645-2464
- : Mondays, 3:00-3:50pm and Wednesdays, 2:00-2:50pm.
It is preferable to set up an appointment (by email) if you want to talk to me outside of my office hours. However, you can drop by if my office door is open.
TA Information
Here are your wonderful CSE 331 TAs:
Meg Arnold (Head TA)
- :
mharnold "at" buffalo "dot" edu
- : Tuesdays, 1-1:50pm and Wednesdays, 4-4:50pm
- : Davis 302
Adhish Chugh
- :
adhishch "at" buffalo "dot" edu
- : Wednesdays, 11-11:50am and Thursdays, 2-2:50pm
- : Davis 113Y
Emily Hann
- :
emhann "at" buffalo "dot" edu
- : Tuesdays 5-5:50pm, Thursdays, 3-3:50pm
- : Tuesdays - Davis 338A, Thursdays - Davis 302
Jordan Hoeber
- :
jrhoeber "at" buffalo "dot" edu
- : Wednesdays, 3-3:50pm and 6-6:50pm
- : Davis 113Y (3pm) and 310 (6pm)
Elliott King
- :
eking "at" buffalo "dot" edu
- : Tuesdays, 10-10:50am and Thursdays, 4-4:50pm
- : Davis 302
Tri Nguyen
- :
tringuye "at" buffalo "dot" edu
- : Mondays, 5-5:50pm and Tuesdays, 4-4:50pm
- : Davis 338A (Mon) and 302 (Tue)
Ashish Tyagi
- :
ashishty "at" buffalo "dot" edu
- : Wednesdays, 5-5:50pm and Thursdays, 1-1:50pm
- : Davis 310 (Wed) and 113Y (Th)
Contacting course staff
You should first try and post your question on piazza . If you need to send email, please send it to cse-331-staff "at" buffalo.edu
: this will send email to the TAs and me.
Recitations
You should have signed up for one of these five recitation sections:
- Monday, 8:00-8:50am (Cooke 127A)
- Monday, 9:00-9:50am (Hoch 139)
- Mondays, 12:00-12:50pm (Hoch 139)
- Mondays, 4:00-4:50pm (Cooke 127A)
- Tuesdays, 9:00-9:50am (Norton 209)
Attending the recitations is very important, as it will cover material that could not be covered well in the lecture due to time constraints and/or discuss homework problems (and their solutions once the homeworks have been turned in). Also the recitations will provide an opportunity to ask your questions in a smaller gathering.
Course Description
Introduces methods for algorithm design, paradigms such as divide and conquer, greedy, and dynamic programming, and techniques for algorithm analysis, such as asymptotic notations and estimates, as well as time/space tradeoffs. Topics include sorting, searching, scheduling, string matching, graph algorithms, computational geometry, and more.
Pre-requisites
Data Structures (CSE 250 ), Discrete Math (CSE 191 ) and College Calculus II (MTH 142 ). Ideally, you should have a grade of $C^-$ or above in these courses. If you do not satisfy the requirement, please come and see me.
(ABET ) Learning Outcomes
This course is required of all computer science students and has a significant relationship with the following program objectives for computer science:
-
(a)
an ability to apply knowledge of computing and mathematics appropriate to the discipline. -
(g)
an ability to analyze the local and global impact of computing on individuals, organizations, and society.
This course has a strong relationship with the following program objective for computer science:
(j)
an ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computer-based systems in a way that demonstrates comprehension of the tradeoffs involved in design choices.
References
We will be using the following textbook:
Required Textbook
Jon Kleinberg and Eva Tardos, "Algorithm Design ." Addison Wesley, 2005.
The following textbooks could be useful references:
- Thomas S. Cormen, Charles E. Leiserson, Ronald Rivest, and Clifford Stein, "Introduction to Algorithms (2nd Ed) ." MIT Press, 2001.
- Sanjoy Dasgupta, Christos H. Papadimitriou and Umesh Vazirani, "Algorithms ." McGraw Hill, 2007.
- Donald Knuth, "The Art of Computer Programming Volumes 1, 2, 3, 4 ." Addison Wesley.
- Alfred V. Aho John E. Hopcroft and Jeffrey Ullman, "Data Structures and Algorithms ." Addison Wesley, 1983.
- Richard E. Neapolitan, "Foundations of Algorithms (5e) ." Jones and Bartlett, 2015.
- Daniel J. Velleman, "How to Prove It: A Structured Approach (2nd Ed) ." Cambridge University Press, 2006.
Schedule
We will have roughly 13 weeks worth of classes. Here is a tentative list of topics that we will cover (KT refers to the textbook):
- Introduction [KT, Chap 1] (1.5 weeks).
- Asymptotic Analysis [KT, Chap 2] (1 week).
- Graph Basics [KT, Chap 3] (2.5 weeks).
- Greedy Algorithms [KT, Chap 4] (3.5 weeks).
- Divide and Conquer Algorithms [KT, Chap 5] (2.5 weeks).
- Dynamic Programming [KT, Chap 6] (2 weeks).
- NP-completeness and other advanced topics [KT, Chap 8] (1 lecture).
As the semester goes along, a more detailed schedule will appear here.
Piazza
We will be using Piazza for all CSE 331 related announcements. If you are attending the course, you must check Piazza regularly. I would strongly urge you to enable email notifications on piazza (it is on by default). These announcements will include the ones that inform if and when classes/office hours are re-scheduled etc.
There will be an entry for each lecture and homework. Sometimes, the entries may include side comments or stories that I feel are relevant to the course (but are not directly related to the lectures). Also there will be a weekly True/False poll/question to prepare you better for True/False questions on the exams (which you guys will generally not see on the homeworks). Try to work on these problems on your own to prepare better for the exams.
We will also be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates, the TAs, and myself. Rather than emailing questions to the teaching staff, I encourage you to post your questions on Piazza. If you have any problems or feedback for the developers, email team@piazza.com. To familiarize yourself with the system, look at their help page .
You will need to sign up for Piazza. To do so, go to the sign up page .
Few other points:
- You can post anonymously but note that you will be anonymous to students only. Your identity will be known to me and the TAs.
- Please make sure that you use your UB email to sign up-- this is to make sure that I can verify your identity if necessary.
- You can write posts that are private to just the instructors but if we feel that the answer would be relevant to the class then we reserve the right to make the post public. (If you would like not to have your name in the public version of your private post, please post anonymously in the private post too. Note by the first point, we will still know your identity.)
Grading Policy
Here is the split of grades:
Course Component | $\%$ of grade |
Mini project | $6\%$ |
Homeworks | $31\%$ |
Quizzes | $3\%$ |
Exams | $60\%$ |
Letter Grades
To get an A in the course, you will have to obtain a total of $90.00\%$ or more. The rest of the letter grades will be determined based on a curve.
Incompletes
Please see the university rules on an incomplete . I will not consent to an incomplete except in provably extreme circumstances.
Mini Project
Please see the mini project page for more details.
The mini-project will assess student outcome (g)
.
Homeworks
Homeworks will be released on Fridays morning on the CSE 331 web page and will be due via Autolab by 12:30pm next Friday. In addition, there will be a Homework $0$, which will be graded but will not count towards your final grade. Homework $0$ is just to give you feedback on your solutions so that you can avoid your mistakes in the homeworks that will count towards your grade (and also for us to test out Autolab). Homework $0$ will be released on the first day of class and will be due by 12:30pm on Friday, September 2, 2016. Submitting Homework $0$ is optional.
Autolab submissions
All homework submissions will happen on Autolab. The homework will consists of one programming question (which can be submitted in C++, Java or Python and will be autograded by Autolab) and two proof based questions (which will have to be submitted in PDF format on Autolab and will be graded by the TAs).
Late submissions
No late submission will be accepted. (The entire homework schedule is on the schedule page, so please plan accordingly.) However, the three lowest score on your homeworks will be dropped. I strongly encourage you to save these three homeworks till the end of the semester when you will be very busy with projects etc. or for possible sick days.
For more details (including on how not to get an F in the course), please see the homework policy document. The line between collaboration and cheating can be blurry- when in doubt, play safe. Not only is cheating bad in principle, in practice it is highly unlikely that you'll do well in the exams unless you have worked hard on the homeworks on your own. It is highly recommended that you do not try to test my claim out on yourself.
All homeworks assess student learning outcomes (a)
and (j)
.
Quizzes
There will be two quizzes: both in class. The quizzes will be from 1:00-1:10pm on Monday, October 10 and Monday, December 5. The quiz will consist of one or two true/false (with justification) questions. Such questions will be on the exams but are not on homeworks and hence, these quizzes will be an opportunity for you to try and solve such questions before the exams (and under some time pressure). You will also gain experience working on true/false questions with a weekly such question that will be posted on piazza.
Quiz Grade
The quizzes are worth $3\%$ of your grade. However, if it is to your advantage, I will drop the quiz scores and bump up the homeworks to $34\%$ of your grade.
The quizzes will assess student learning outcomes (a)
and (j)
.
Exams
Exam Grade
The mid-term is worth $25\%$ of your grade and the final exam is worth $35\%$ of your grade. However, if it is to your advantage, then the final exam will be worth $60\%$ of your grade.
No makeup exams will be given except in provably extreme circumstances. Please note the following additional policies/suggestions with respect to makeup exams:
- Notify your instructor 24 hours prior to the exam via e-mail or telephone (voice mail) if you are going to miss an exam. If it is medically impossible for you to give prior notice, please obtain a note from a physician detailing the period (and the reason) you were medically incapable of communicating with the instructor.
- If you miss an examination because of sickness or similar reasons, visit a physician and obtain a note detailing the period and the reason you were medically incapable of taking the exam.
- The exam dates are stated below. Please plan your travel and other activities accordingly.
- Exam times are stressful and one could forget about the exam time. Please make sure you arrange for multiple reminders so that you do not forget about the exam(s). This is another reason to religiously follow piazza as there will be numerous reminders about the exam when it gets close to the actual exam date.
The exams will assess student learning outcomes (a)
and (j)
.
Mid-term exam
The mid-term exam will be split across two lectures. The in-class exams will from be 1:00-1:50pm on Monday, October 17 and Wednesday, October 19 in the usual meeting place and time. The exam will be closed book and notes. However, you can bring in a single 8.5x11 inch paper (you can use both sides). (The sheet can be typed as long as the sheet is readable.) The exam is split over two lectures to give your appropriate amount of time to finish the exam.
Final exam
The final exam will be held in the classroom (KNOX 110) on Friday, December 16 from noon-2:30pm. (Note that the exam is for two and a half hours and not for three hours.) Again the exam will be closed book and notes but you can bring in two 8.5x11 inch sheets. (Again, the sheets can be typed as long as they are readable.)
Study time
In this course, as in any course, you are expected to put in additional time beyond the scheduled class times. Professors generally expect that for each credit hour a typical student will put in 2 - 3 hours of time each week outside of class. Since this is a 4 credit course that translates into 8 - 12 hours of time outside of scheduled times, each week. During this time you should review your lecture notes, attend office hours as needed, and work on assignments. As a rough guide, you should expect to spend at least the following time working on this course, each week:
Lectures | 3 hours |
Recitation | 1 hour |
Individual/group study | 3 hours |
Assignments | 5 hours |
Miscellaneous Notes
Here are some other policies/suggestions to keep in mind:
-
Your grade
Your grade will solely depend on your performance in this semester: you will not get any opportunity to do extra work to improve your grade. It is your responsibility to make sure you understand what is expected of you. This course will require a fair bit of work so if you are busy this semester, please plan accordingly.
- If there is a genuine reason for re-grading, please contact the person who graded your homework/exam within a week of when the graded material is handed back.
- See this blog post from Fall 2009 on some tips on how to do well in this course (hint: work hard!)
- If you are not super comfortable with proofs then you will need to put in some extra work to do well in class. The important thing to remember in this case that you are not good at algorithms yet:
- The $6\%$ of the grade for the mini project will be the easiest points in the entire course. Do not miss on those by forgetting about the deadlines.
- Feel free to make up a group of up to three students and stick with it for all your homeworks and the mini project. You can also use the group as your study group for the course. Piazza offers a mechanism to search for group-mates.
Accessibility Resources
If you have a diagnosed disability (physical, learning, or psychological) that will make it difficult for you to carry out the course work as outlined, or that requires accommodations such as recruiting note-takers, readers, or extended time on exams or assignments, you must consult with Accessibility Resources (25 Capen Hall, : 645-2608, TTY: 645-2616, : 645-31160).
You must advise your instructor during the first two weeks of the course so that we may review possible arrangements for reasonable accommodations.
Counseling Center
Your attention is called to the Counseling Center (: 645-2720), 120 Richmond Quad. The Counseling Center staff are trained to help you deal with a wide range of issues, including how to study effectively and how to deal with exam-related stress. Services are free and confidential.
Preferred Name
If you would like to be addressed by a name that is different from the one in UB records, please let us know and we will use your preferred name in our communications with you. Further, you will be able to use your preferred name in all of your exams and quizzes (the homeworks will be submitted online so this issue should not come up there).
Suggestions or Comments?
I would be happy to get feedback from you. You can either talk/send email to me, or use pizza .