This course is concerned with the design, analysis, and implementation of advanced data structures. A key element of the course will be the role of data structures in algorithm design, as well as the use of amortized complexity analysis to determine how data structures affect performance. The precise topics will depend on the interests and background of the course participants; see the current schedule for details. Potential topics include self-adjusting binary search trees, dynamic trees and graphs, persistent data structures, geometric data structures, kinetic data structures, I/O-efficient and cache-oblivious data structures, hash tables and Bloom filters, data structures that beat information-theoretic lower bounds, and applications of these data structures in computational geometry, combinatorial optimization, systems and networking, databases, and other areas of computer science.
CSCI 3100: Algorithms (or equivalent)
At the conclusion of this course, students should be able to:
Lecture notes will be posted on the course schedule page. These are provided as a resource, but are NOT a substitute for attending lecture. In particular, something will break at least once this semester! Please make arrangements with a fellow student if you do have to miss class.
Additional articles or online references will be provided throughout the semeseter; please reference the schedule throughout the semester for such additions.
Email contact with the course instructor is a necessity in this class.. 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 may be more sporadic, although I will be sure to check at least once.
We will use a git system this year to submit any coding assignments or final projects. Details on how to sign up and use the system will be posted on the announcement page and discussed in class.
Computers will be an integral part of this course, both inside and outside of class. However, out of courtesy to both the instructor and other students, please do not use the lab computers for non-class related activity. In particular, you do not need to be using a computer unless an exercise or in class activity requiring them is in progress.
You are unlikely to need cell phones during the course of lecture. Please ensure that your cell phone is set to vibrate or silent during lecture, and excuse yourself from class if you need to answer it.
There will be a series of written/or and programming assignments which (in total) will compromise half of your final grade.
The remaining half of your grade is tied up in your final project; see the homework page for discussion.
Homeworks will generally be due at 11:59pm via email. Late submissions will generally not be accepted unless arrangements have been made ahead of time. Please contact me as early as possible with any potential issues, since I am much more likely to grant an extension if you come to be ahead of time! In general, I try to be flexible if students have good reason, but I do reserve the right to not accept late submissions if solutions have already been released or if a student is abusing this flexibility.
I am happy to regrade any assignments, programs, quizzes 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 in your own group, 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 10 of the lecture notes from class, the best solution you can submit is "See page 10 of lecture notes on this date." 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. In particular, verbatim copying is worth NOTHING, and will be considered a violation of the academic integrity policy. (Note that I'm also pretty good with google, so I wouldn't recommend trying it!)
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 via 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 at: https://www.slu.edu/provost/policies/academic-and-course/policy_academic-integrity_6-26-2015.pdf. 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.For any student raising children, I understand that minor illnesses and unforeseen disruptions in childcare often put parents in the position of having to chose between missing class to stay home with a child and leaving him or her with someone you or the child does not feel comfortable with. While this is not meant to be a long-term childcare solution, occasionally bringing a child to class in order to cover gaps in care is perfectly acceptable.
All exclusively breastfeeding babies are welcome in class as often as is necessary to support the breastfeeding relationship. Because not all women can pump sufficient milk, and not all babies will take a bottle reliably, I never want students to feel like they have to choose between feeding their baby and continuing their education. You and your nursing baby are welcome in class anytime.
I ask that all students work with me to create a welcoming environment that is respectful of all forms of diversity, including diversity in parenting status. In all cases where babies and children come to class, I ask that you sit close to the door so that if your little one needs special attention and is disrupting learning for other students, you may step outside until their need has been met. Non-parents in the class, please reserve seats near the door for your parenting classmates. (Policy adapted from Dr. Melissa Cheyney)
Student Success Center: 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). Students can visit https://www.slu.edu/life-at-slu/student-success-center/ to learn more about tutoring services, university writing services, disability services, and academic coaching.
University Writing Services: Students are encouraged to take advantage of University Writing Services in the Student Success Center; getting feedback benefits writers at all skill levels. Trained writing consultants can help with writing projects, multimedia projects, and oral presentations. University Writing Services offers one-on-one consultations that address everything from brainstorming and developing ideas to crafting strong sentences and documenting sources. For more information, visit https://www.slu.edu/life-at-slu/student-success-center/ or call the Student Success Center at 314-977-3484.
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;akratky@slu.edu; 314-977-3886) and share the basic facts 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. To view SLU’s sexual misconduct policy and for resources, please visit the following web addresses: www.slu.edu/here4you and https://www.slu.edu/general-counsel.
Students with a documented disability who wish to request academic accommodations must contact Disability Services to discuss accommodation requests and eligibility requirements. Once successfully registered, the student also must notify the course instructor that they wish to access accommodations in the course.
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 the student’s eligibility for academic accommodations will be shared with course instructors via email from Disability Services and viewed within Banner via the instructor’s course roster.
Note: Students who do not have a documented disability but who think they may have one are encouraged to contact to Disability Services.