Overview

Catalog Description

The design, implementation and use of data structures. Principles of abstraction, encapsulation and modularity to guide in the creation of robust, adaptable, reusable and efficient structures. Specific data types to include stacks, queues, lists, priority queues, dictionaries, trees and graphs.

Class Meeting Time/Location

Time: Mon, Tue, Wed, Fri (Lab) 9:00 am - 9:50 am
Where: Ritter Hall 115 (Linux Classroom)

Instructor

Tae-Hyuk (Ted) Ahn, PhD
Assistant Professor
Department of Computer Science
Program of Bioinformatics and Computational Biology
Email: ted.ahn@slu.edu
Office: 305 Ritter Hall (Lab: 302 Ritter Hall)
Phone: (314) 977-3633
Office Hour: Mon 10 am - 11:30 am, Tue 12:30 pm - 2 pm or by appointment

Credits/Pre-requisites

Credits: 4 Credits Pre-requisites: The official prerequisite is a C- or better in CSCI 1300 and a passing grade or concurrent enrollment in MATH 1660 or equivalent.

Topical Outline

This is an undergraduate follow-up course to introductory programming, where the focus is primarily on learning how to solve a problem using an object-oriented framework. However, in this course, we focus on the fact that there are often multiple ways to solve a problem, with tradeoffs in the approaches that are possible. The goal of this course is to learn the various types of data structures which are commonly used throughout computer science, as these are the building blocks of most larger projects.

  • Why Data Structures?
  • C++ Crash Course for Python programmers
  • Introduction to analysis of algorithms, big-O
  • Linear data structures: lists, stacks, queues, vectors, heaps
  • Binary trees, binary search, heaps, AVL trees, Huffman trees
  • Dictionaries and hashing
  • Graph implementations and algorithms

Student Learning Outcomes

After successfully complete this course, students are expected:

  • Understand underlying fundamental concepts of data structures
  • Demonstrate the inner workings of fundamental data structures such as stacks, queues, vectors, linked lists, heaps, trees, and graphs
  • Implement generic versions of any of these data structures, using low-level programming concepts such as pointers and dynamic memory management
  • Select an appropriate data structure and use it to solve a given programming problem, understanding any tradeoffs involved
  • Analyze the asymptotic time and space efficiency of data structure operations using standard notations

Course Materials and Resources

Textbook

This semester, we will be using a zyBooks text, combined with ZyLabs for some of the early programming assignments. Do sign up, please do the following:

  1. Sign in or create an account at learn.zybooks.com
  2. Enter zyBook code: SLUCSCI2100AhnFall2019
  3. Subscribe Please note that you can download a pdf of the book, and I STRONGLY recommend that you do so! Data structures questions are quite fundamental in CS, and are a huge part of most technical interviews for jobs, so it is likely you will want this reference later in yoru career.

Until last year, I used Data Structures and Algorithms in C++ (Second Edition) (Michael T. Goodrich, Roberto Tamassia and David M. Mount, John Wiley & Sons, 2011, ISBN-13 978-0-470-38327-8). If you like to have a traditional textbook for Data Structures, please get it.

Course website

https://biohpc.github.io/CSCI2100F19/ will be used to announce schedules, slides, assignments, and news.

Git

Our SLU CS GitLab or GitHub Classroom could be used to submit some assignments. The instructor will provide further info if we use the Git system.

Blackboard:

Blackboard could be used to post grades.

Email

Face-to-face contact in class and in office hours is most desirable. Yet email is a convenient form of communication as well. I try to respond to email promptly, including at least once each evening when possible. Email contact over the weekend will likely be more sporadic, although I will be sure to check at least once.

If your question involves your progress on a current programming assignment, my response will be more informative if you can point out the specific problem you have encountered, and if I am able to see all of your source code. Therefore I strongly suggest that you either attach all relevant files to the email or submit preliminary versions of such files through git system.

Computer and Cell Phone Policy

Computers (laptops) 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 laptops or 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 do not send text messages of any kind.

Grading

Graded Work

  • Exam (40%)
    • Midterm 1(10%): Tentative schedule: Friday, Oct. 4th, 2019 at 9:00-9:50 am (classroom)
    • Midterm 2 (10%): Tentative schedule: Friday, Nov. 8st, 2019 at 9:00-9:50 am (classroom)
    • Final Exam (20%): Tentative schedule: Monday, Dec. 9th, 2019 at 9:00-9:50 am (classroom)
  • Homework (Programming Assignments and Written Homework) (40%) We expect about 10 assignments through the course of the semester. Some will be due via zyBooks submission (usually due by 11:59pm in these cases), while others may be done on paper and due at the start of class. I can also use either Email or GitHub Classroom for few assignments. I will provide detailed info in the course. Please read the academic integrity section of this document carefully, since I expect students to work on their own material and hold to high standards of behavior on all assignments.

On certain assignments, you will be required to work individually; on others you will be allowed to work in pairs. Early in the course you will have approximately one week for each assignment; later in the course you will often have two weeks.

Students will also be able to drop their lowest programming or homework assignment score at the end of the semester.

  • Lab Assignments (10%) Most Friday will be devoted to a hands-on problem. Although we hope to have students complete it in class, we will allow each to be submitted anytime by 11:59pm on the following Monday. Each lab will also have a pre-lab associated with it which will be due before class begins on the day of the lab.

These problems will be graded automatically through ZyLabs. Each will have a simple pre-lab, which is worth 1 point. The remaining points are awarded for a successful completion of the lab work, based on how many test cases your program passes. Note that completion of the prelab and an honest attempt at the lab will give at least some partial credit!

At the end of the semester, we will ignore your lowest of the lab grades, with the remaining scores contributing equally to this portion of the grade.

  • zyBooks Reading (10%) This semester, the course text will be an online text through zyBooks. You will be required to do reading BEFORE class regularly; in addition, the book contains some simple exercises to reinforce the concepts. Your solutions will not be graded for correctness, but the zyBooks framework records participation credit for attempting - if you get the solution correct, you move on, and otherwise it requires a certain number of attempts on each question before showing you the correct solution.

I will only score participation, but it is my hope that you will choose to engage with both the read and the reinforcement questions, as I think they are very helpful! At the least, I can guarantee understanding them will improve your exam and homework scores, since I plan to build on them as much as possible. I will also assume students have completed the reading, so that my lecture will continue from there; students who have not completed the reading are likely to be quite lost in class.

Percentages

Letter grades will be based on each students overall percentage of awarded points according to the following formula.

Student percentage above 93% will result in a grade of A or better.
Student percentage above 90% will result in a grade of A- or better.
Student percentage above 87% will result in a grade of B+ or better.
Student percentage above 83% will result in a grade of B or better.
Student percentage above 80% will result in a grade of B- or better.
Student percentage above 77% will result in a grade of C+ or better.
Student percentage above 73% will result in a grade of C or better.
Student percentage above 70% will result in a grade of C- or better.
Student percentage above 60% will result in a grade of D or better.
Student percentage below 60% will result in a grade of F.

Any curving of this scale at the end of the year will be in favor of the students. In other words, I reserve the right to decide to award an A to a student who is slightly below the above cutoff, but I will never deny an A to someone who is above the cutoff.

Extra Credit

The programming and homework assignments provided will be challenging enough for most students, so please focus as much as possible on the assignments provided.

Upon occasion (and solely at the instructor’s discretion), there may be small extra credit activities, 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.

Late Homework

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.

Regrade Requests

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.

Policies and Resources

Academic Integrity

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 grader has 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, if you blindly copy an incorrect solution, don’t expect to get very many points for 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.

A statement of minimum standards for student academic integrity at Saint Louis University is described here; I expect full compliance with the policies described.

Attendance

Our course follows university level attendance policy.

Title IX

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 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 Office of the General Counsel.

Please see the College of Arts and Sciences Syllabi statements. I am more than happy to accomodate any requested accommodations; come see me or get in touch via email if you have any questions.

Disability Services

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 Disability Services.

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 the 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 the Student Success Center or call the Student Success Center at 314-977-3484.

Basic Needs Security

Students in personal or academic distress and/or who may be specifically experiencing challenges such as securing food or difficulty navigating campus resources, and who believe this may affect their performance in the course, are encouraged to contact the Dean of Students Office (deanofstudents@slu.edu or 314-977-9378) for support. Furthermore, please notify the instructor if you are comfortable in doing so, as this will enable them to assist you with finding the resources you may need.