CS 2341 - Data Structures

Fall 2020 - SMUFlex Version

Overview

Welcome to Data Structures! During this semester, we will delve into the world of object oriented C++, data organization and access, and associated software development topics. A major aspect of computer science is finding an efficient solution to a given problem that can be implemented on a computer. We will explore some of the more intermediate and advanced parts of the C++ language and how they can be leveraged in construction and implementing various data structures and algorithms to operate on those data structures. We will also begin to explore how data organization and access can enhance or inhibit the efficiency of a solution to a problem.

As a similar saying goes, programming languages are to computer science what hammers are to carpentry. Programming is a tool that we use to communicate with a computer and express our solutions to problems. It is important to know how to use this tool efficiently to solve complex problems. To get the most out of this class and ultimately to be successful, you must be willing to work hard.

Instructor Info

• Mark Fontenot, PhD.
• Caruth 433
• mfonten@lyle.smu.edu
• markfontenot.net

Course Info

Lectures:

• Section 801 MWF 9:00 - 9:50
• Section 802 MWF 11:00 - 11:50

Where to Find Info

Catalog Description

Emphasizes the object-oriented implementation of data structures, including linked lists, stacks, queues, sets, and binary trees. The course covers object-oriented software engineering strategies and approaches to programming in interdisciplinary teams.

Prerequisite

C- or better in CS 1342 or equivalent or permission of Dr. Fontenot

Textbooks

• Shaffer, Cliff. Data Structures and Algorithm Analysis, C++ version, Edition 3.2, Dover publications. Available in PDF at Dr. Shaffer’s Website
• Morin, Pat, Open Data Structures in C++, Book PDF.

Notes about Books - I’m not a huge fan of textbooks. I think they are overpriced and provide a false sense of security of the scope of a subject. However, they are quite useful as an organized treatment of a topic. It is important that you learn how to figure things out on your own. For this reason, I typically don’t follow any textbook very closely.

HOWEVER - this is an interesting semester with the Pandemic and all. So, I think there will be some added value in following a textbook closer than I usually would. To some degree, the students in the class are distributed all over the world.

Learning Outcomes

1. Ability to properly handle dynamic memory management tasks in C++
2. Ability to compare data structures and their algorithms analytically and experimentally
3. Ability to implement a range of data structures including but not limited to linked lists, stacks, queues, binary search trees, hash tables, and heaps
4. Ability to compare and contrast various comparison-based sorting algorithms
5. Ability to decompose and solve large problems
6. Ability to choose appropriate data structures to solve a problem
7. Ability to design, implement, test, and debug classes in C++

Method of Evaluation

The final course grade in CSE 2341 will be based on the performance of various deliverables such as implementation projects and homework assignments. Additionally, your attendance and active participation in lecture and lab will be reflected in your final grade. The percentage breakdown is as follows:

The Final Exam may be administered as an oral comprehensive exam that takes the form of a mock technical interview related to the course content.

The due dates for all assignments will be explicitly stated on each assignment and will be available on the course website. Final grades in this course are determined as follows:

Additional Grading Stipulations

In order to get a grade above D+ in this course, you must maintain a passing average (>= 60%) independently in the categories 1) Homeworks and Quizzes, 2) Programming Projects, and 3) Final Project.

Homework Assignments and Quizzes

Homework assignments are assigned throughout the semester. Quizzes may be announced or unannounced. Homework assignments will be available via Canvas and/or will be handed out in class. Each will clearly state the due date and method of submission.

Programming Projects

Nearly every week, you’ll be working on some aspect of a programming assignment in and out of your lab period. You will not be able to finish an entire assignment during lab time; if you do, you should question whether or not you actually fulfilled the requirements. Further, your lab period is not the time to start your work for the week. You should work on your assignments before lab and use lab as time to get clarifications and explanations as needed from the TAs. Each lab packet will clearly state the due dates for each of the deliverables.

Rather than penalize late submissions, you will be rewarded for early submissions. Programming projects (except for the final semester project) will be eligible for 10% extra credit for submitting the project at least 48 hours early. Recognizing that sometimes things happen at the last minute that are beyond our control, each student will get one (1) two-day (2-day) “free” extension - no questions asked. This means you can submit this one project (except for the final semester project) up to 48 hours late.

If/when you want to use your one extension, send an email to Dr. Fontenot and TA Eli Laird. The email should include your:

• Name,
• ID Number, and
• on which project you’re asking for an extension.

All projects will be reviewed, evaluated, and graded using the programming environment detailed by the course staff. Your submission must conform to the specifications in each project handout. Each submission is required to use the specified build system to compile and run your projects. The specifics for this will be covered in a separate handout.

Project submissions that do not build/compile using the above stated build system and that stated in associated course handouts including any modifications to the build system as stated in each individual project handout will receive no credit. No matter how much time you spend writing code, if it doesn’t build/compile, you will receive NO credit.

We will use GitHub throughout the semester as a code versioning and backup tool as well as the platform for final submissions. If used as instructed (and as GitHub is intended), you will always have a safe and secure backup of your source code. Therefore, I will entertain no excuses related to computer hardware failure for not submitting projects or assignments on time.

Communication, Attendance, and Grading

Because of the nature of this class, attendance and participation in lecture and lab are very important. I expect you to attend all classes and lab sessions. If you are absent from class, it is your responsibility to make arrangements with me to make up any work missed or to ensure that assignments are submitted on time or early. Except as stated above in Programming Projects section, no late work will be accepted. Any assignments that will be missed (including those due to university-sanctioned events) must be completed before the due date. This includes projects, exams, and homework assignments.

Note that a portion of the semester grade is based upon class attendance and active participation. This attendance score will be determined based on attendance and active participation in both lecture and lab. Attendance in lecture will be randomly taken. Lab attendance will be taken weekly. After three missed lab or lecture classes, one percentage point will be deducted from your final course average for each missed class or lab missed up to the max listed in the table above.

Any issues with grades assigned on projects, homework, quizzes, exams or any other graded materials must be brought to Dr. Fontenot’s attention within 48 hours of the grades being posted on Canvas, or they will not be entertained. This should be done via email.

A college course is taught by a professor and attended by a student. So, the educational engagement is between the two of us, and informed by the course staff of graduate and undergraduate teaching assistants. This educational engagement does not include your parents, guardians, or others in any way. Therefore, I will only be communicating with you. I will not be communicating with your parents or guardians in any way, regardless of the presence of a FERPA release that you have issued.

Outside Work

This course will require a substantial amount of work outside of class. The best way to learn this material is to sit down, get comfortable, and just do it. There will be several programming assignments and projects that will require a great deal of time. Some of these projects may be collaborative in nature. It is reasonable to expect that you may spend 10 or more hours per week outside of lecture/lab working on programming projects for this class.

Here are some soft-skills that we hope to help you hone over the course of the semester:

• Time Management (i.e. not waiting until the last minute to begin work on projects and assignments)
• Work smart by using your time wisely and using tools related to the course material effectively
• Large-scale problem solving (i.e. planning and designing before coding)

Academic Ethics and Collaboration

I take academic ethics very seriously. Each of you should have read the SMU Honor Code by this point in your academic career at SMU. What you submit for any course deliverable must be your own intellectual work product, except where collaboration with other students is explicitly allowed, and you must be able to defend any of the work submitted (ie. explain it in sufficient detail). The metadata associated with your work product (file timestamps, commit logs from GitHub, etc.) are also part of your work and will be treated as such. Any modification of these metadata done to intentionally mislead one of the course staff members will be treated as a cheating offense.

You are expected to create, edit and print your own assignments and take tests without outside assistance. All work is expected to be your own. In particular:

• You should never look at or review another person’s work for any given assignment. This includes looking at papers, solutions, or computer screens where another student’s work is displayed. This also includes solutions from previous semesters.
• You should never give or receive solutions/answers to any questions or projects or any parts or questions or projects. This includes but is not limited to source code, design documents, homework, etc.
• In the header comments of your source code, you must reference online sources you consulted to complete the project. This is especially important if you’ve “quoted” source code.

If you collaborate on any assignment for any reason unless specifically permitted by the instructor, you will receive an F in the course and may be brought in front of the SMU Honor Council. The presumption should be that collaboration is not permitted and collaboration should only take place subsequent to explicit instructions by the course instructor. It is your responsibility to know and understand the University’s Honor Code and the expectations for collaboration in this course. Dr. Fontenot reserves the right to impose less severe penalties at his sole discretion.

Words of wisdom: The penalty for academic dishonesty will always be more severe than simply not submitting the assignment. Not turning in an assignment will result in a zero on that assignment. Engaging in academic dishonesty related to that assignment will likely result in an F in the entire course and/or referral to the honor council.

So, what is explicitly permissible? I will be the first to agree that sometimes we learn better when we are talking through things. When a project is assigned, you are certainly allowed to ‘whiteboard’ design ideas, high level plans, etc. But they should never get to the level of code. If you have questions about what is allowed or not allowed, please just ask Dr. Fontenot

SMU Policies

Disability Accommodations

Students needing academic accommodations for a disability must first register with Disability Accommodations & Success Strategies (DASS). Students can call 214-768-1470 or visit the DASS Website to begin the process. Once approved and registered, students will submit a DASS Accommodation Letter to faculty through the electronic portal DASS Link and then communicate directly with each instructor to make appropriate arrangements. Please note that accommodations are not retroactive and require advance notice to implement.

Religious Observance

Religiously observant students wishing to be absent on holidays that require missing class should notify their professors in writing at the beginning of the semester, and should discuss with them, in advance, acceptable ways of making up any work missed because of the absence. (https://www.smu.edu/StudentAffairs/Chaplain/ReligiousHolidays).

Excused Absences for University Extracurricular Activities

Students participating in an officially sanctioned, scheduled University extracurricular activity should be given the opportunity to make up class assignments or other graded assignments missed as a result of their participation. It is the responsibility of the student to make arrangements with the instructor prior to any missed scheduled examination or other missed assignment for making up the work. (See 2020-2021 SMU Undergraduate Catalog under “Enrollment and Academic Records/Excused Absences.”)

Pregnant and Parenting Students

Accommodations for pregnant and parenting students: Under Title IX students who are pregnant or parenting may request academic adjustments by contacting Elsie Johnson (elsiej@smu.edu) in the Office of the Dean of Students, or by calling 214-768-4564. Students seeking assistance must schedule an appointment with their professors as early as possible, present a letter from the Office of the Dean of Students, and make appropriate arrangements. Please note that academic adjustments are not retroactive and, when feasible, require advance notice to implement.

Covid-19 Attendance Policy

Students who are experiencing COVID-19 symptoms or who have been notified through contact tracing of potential exposure and need to self-quarantine or isolate must follow the protocols laid out in SMU’s Contact Tracing Protocol. To ensure academic continuity, students in these situations will not be penalized and will be provided appropriate modifications to assignments, deadlines, and testing. Please also note that SMUFlex classes might, in rare circumstances, go remote for two-week periods to accommodate COVID-related issues. To ensure these necessary accommodations, affected students must:

• Provide as much advance notification as possible to the instructor about a change in circumstances. Students must notify their instructor about a potential absence as well as plans for a return to class. For cases in which students test positive for COVID-19, they should fill out a CCC form at this link.
• Communicate promptly with the instructor to establish, as necessary, alternative assignments and/or changes to deadlines and exams. Students are then responsible for meeting the expectations laid out in these alternative arrangements.
• Continue participation in class via Zoom, as health circumstances permit. Attend class regularly, when not in a situation outlined above, in accordance with safety measures laid out by SMU CAN in the Pledge to Protect (including wearing masks, maintaining social distancing, and cleaning personal space after class). In-person participation in SMUFlex classes is required on students’ assigned red/blue rotation days except in cases when students are experiencing illness, are in self-quarantine or in isolation.
• Students facing multiple or extended COVID-19-related absences or illness can work with the Office of the Dean of Students to consider options such as fully remote learning or medical withdrawal.

Conduct Expectations

Students shall observe the following:

• If attending class Virtually (over Zoom), it is expected that you will have your camera on. Please observe general best practices when attending virtually as well such as reasonable dress, etc.
• Using a laptop in class is a privilege; it is not a right. When laptops distract your or other students in the class you will no longer be allowed to use them. I reserve the right to ask to see your screen and class notes taken during class to determine if you are using your laptop appropriately.
• Cell phones should be in vibrate/silent mode at all times during lecture. If your cell phone does not have this feature, then it should be turned off. DO NOT answer your cell phone during class.
• Sending text messages, surfing the Internet, playing games, reading the newspaper, etc. is considered disrespectful and will be dealt with accordingly. You are not only disrespecting the instructor, you’re also distracting students around you whether you think so or not.
• Students should remain quiet during lecture so as to avoid disturbing other students.
• Yawning out loud is disrespectful!

---

Table of contents

• Schedule

---