Introduction to analysis and complexity of algorithms. Big-O notation. Running time analysis of algorithms for traversing graphs and trees, searching and sorting. Recursive versus iterative algorithms. Complexity, completeness, computability. (3 credit hours)
CSCI 180: Data structures and Math 143: Calculus 2. While not officially required, you are also strongly encouraged to have completed either MATH 135: Discrete Mathematics or MATH 266: Principles of Mathematics before taking this course.
At the conclusion of this course, students should be able to:
Class: MWF, Room 120 in Ritter Hall
Office Hours: Monday 2-3pm, Tuesday 9-10am, Friday 1-2pm, or by appointment, in 301 Ritter Hall
Your primary reference will be lecture notes written by Jeff Erickson for the algorithms course at University of Illinois. His complete notes are available on his webpage here; I'll also try to post the relevant notes in the course schedule as we go. He also has a list of old homework and exam problems on his webpage, which are a good additional source for practice problems.
Outside of office hours and lectures, email is usually the easiest way to get ahold of me with questions. I will check email several times throughout the work day, and will also check email once per evening to answer questions and resolve issues. Email contact over the weekend will likely be more sporadic, although I will be sure to check at least once.
Note that the first is available freely online; the others are in the library or can be purchased used. (Definitely don't buy a new copy for this class!)
Laptops and other electronic devices are unnecessary for most of this course, and are frequently a distraction to other students in lecture. Since you are unlikely to need a computer during lecture, please do not bring laptops or other electronics for use in class.
Also, please ensure that your cell phone is set to vibrate or silent during lecture, and do not send text messages of any kind.
There will be homework due every week, for a total of about 12 homework assignments over the course of the semester. Some homeworks will be written assignments turned in during class, while others will be presented orally to the instructor.
For all homeworks, you are allowed to submit in groups of 2-3. In fact, given the difficult nature of the assignments, I encourage all of you to work with another student, as the best way to learn this material is to discuss and problem solve in a small group.
As discussed below, students are expected to complete assignments using only approved course materials.
It is important in this course to write clearly and concisely. Don't babble, regurgitate, or otherwise try to fake out the instructor if you don't know the answer! Include relevant details or citations, and make sure to write the entire solutions clearly and in your own words.
For any question, either on the homework or on an exam, if you do not know the answer, you may write "I don't know" and nothing else to receive 25% of the total points for that problem. So if you don't know the solutions, don't waste the grader's time by writing steaming piles of crap for a solution; it'll only make her grumpy.
Letter grades will be based on each students overall percentage of awarded points according to the following formula.
Any modification to this scale at the end of the year will be in favor of the students. That is we may later decide to award an A to a student who is slightly below the cutoff, but we certainly will not deny an A from someone who is above the cutoff.
No matter what curve I impose, I maintain that the minimum passing grade for this class is a 50% - so if your average is lower than that, you will fail this class.
In general, extra credit will not be assigned in this class. The homework assignments provided will be challenging enough for everyone, so I would like for students to focus on the assignments provided.
Upon occasion (and solely at the instructor's discretion), some small extra credit activities may be included, either by announcement in class or as part of an assignment. Please keep in mind that the extra credit is unlikely to significantly affect your grade; if you are concerned about your final grade, it is much better to focus your energy on the regular assignment. Extra credit is solely designed to provide an opportunity to students who wish to explore the topics further.
And no, you can't say "I don't know" on an extra credit problem to get 25% of the points!
Late homework will suffer a penalty of 10% for every hour they are late. For example, homework which is submitted one hour late is worth at most 90% of the total credit.
In unusual circumstances, such as extreme illness or injury (documented by a doctor's note), family emergencies, etc., please contact the instructor as early as possible to arrange accomidations.
I am happy to regrade any assignmentss or exam problems which you think were unfair or incorrect. Please bring me the original assignment, plus a written explanation of your question or complaint, within two weeks of the time the paper in question is graded and returned to you.
In the context of this course, I encourage students to discuss general course material, which includes studying for exams, sharing notes if a student must miss class, and working on any practice problems which are assigned. You are also allowed to turn in homework assignments in pairs. I also encourage you to discuss problems with other students, but please be careful to write up all solutions separately and do not copy any material from another student. As a good rule of thumb, make sure to write your solutions without using any notes or papers written while talking to anyone other than your partner. Remember, you will be on your own in the exam, so it is in your own best interest to make sure that you really understand the material and can solve each problem on your own!
You are allowed to use outside sources of information in this class, including textbooks and webpages. If the complete and correct answer is on page 263 of the lecture notes, the best solution you can submit is "See page 263 of the lecture notes." Period. However, if you find a solution from any other source, such as a web page, a journal paper, a different algorithms textbook, or your mom, you must rewrite the solution in your own words, and you must properly cite your sources. Assume the graders have access to all the official course material, but nothing else. While we strongly encourge you to use any outside source at your disposal, please remember that the homework is supposed to demonstrate that you understand of the material, not just how to use Google.
Students who violate academic integrity policies will be reported to the department, particularly in cases where relevant sources are not cited or in cases of direct copying of another student's work. First time offenses on homework will result in a minimum of a failing grade on the assignment in question, with egregious or repeated offenses resulting in failure in the course. In addition, students may be referred to the College of Arts and Sciences for further disciplinary action.
The following is a statement of minimum standards for student academic integrity at Saint Louis University; I expect full compliance with the policies described.
Academic integrity is honest, truthful and responsible conduct in all academic endeavors. The mission of Saint Louis University is "the pursuit of truth for the greater glory of God and for the service of humanity." Accordingly, all acts of falsehood demean and compromise the corporate endeavors of teaching, research, health care, and community service through which SLU embodies its mission. The University strives to prepare students for lives of personal and professional integrity and therefore regards all breaches of academic integrity as matters of serious concern. The governing University-level Academic Integrity Policy was adopted in Spring 2015, and can be accessed on the Provost's Office website: https://www.slu.edu/the-office-of-the-provost/academic-affairs-policies Additionally, each SLU college, school and center has adopted its own academic integrity policies, available on their respective websites. All SLU students are expected to know and abide by these policies, which detail definitions of violations, processes for reporting violations, sanctions, and appeals. Please direct questions about any facet of academic integrity to your faculty, the chair of the department of your academic program, or the dean/director of the college, school or center in which your program is housed. Specific College of Arts and Sciences Academic Honesty Policies and Procedures may be found here.Saint Louis University and its faculty are committed to supporting our students and seeking an environment that is free of bias, discrimination and harassment. If you have encountered any form of sexual misconduct (e.g. sexual assault, sexual harassment, stalking, domestic or dating violence), we encourage you to report this to the University.
If you speak with a faculty member about an incident of misconduct, that faculty member must notify SLU's Title IX coordinator, Anna R. Kratky (DuBourg Hall, room 36; anna.kratky@slu.edu; 314-977-3886) and share the basic fact of your experience with her. The Title IX coordinator will then be available to assist you in understanding all of your options and in connecting you with all possible resources on and off campus.
If you wish to speak with a confidential source, you may contact the counselors at the University Counseling Center at 314-977-TALK.
Student Success Center Syllabi Statement:In recognition that people learn in a variety of ways and that learning is influenced by multiple factors (e.g., prior experience, study skills, learning disability), resources to support student success are available on campus. The Student Success Center assists students with academic related services, and is located in the Busch Student Center (Suite, 331) and the School of Nursing (Suite, 114). Students who think they might benefit from these resources can find out more about:
Students with a documented disability who wish to request academic accommodations are encouraged to contact Disability Services to discuss accommodation requests and eligibility requirements.
Please contact Disability Services, located within the Student Success Center, at disability_services@slu.edu or 314-977-3484 to schedule an appointment. Confidentiality will be observed in all inquiries. Once approved, information about academic accommodations will be shared with course instructors via email from Disability Services and viewed within Banner via the instructor's course roster.
Our department employees many junior/senior computer science majors to help out in our department labs. Those students are also available to provide assistance with course materials at such times; check the department webpages for availability. (However, it is worth noting that these tutors are often students in these upper level courses, and hence may not be quite as useful as for earlier courses!)
As stated in the Academic Integrity policy, these workers are an acceptable resource for help, yet you should still document both the source of the help as well as the extent, if significant.