CS 3114: Data Structures and Algorithms
Welcome to our class! This course will cover many data structures that are widely used in software development, as well as the associated algorithm analysis to determine the appropriate usage for the situation. These data structures and algorithms are used continuously and everywhere in computing, and far beyond too. I’m very excited to share with you these powerful ideas, and to hear your perspective on learning about them.
We will be “learning-by-doing” to both strengthen our understanding of these concepts and to create compelling software. This software is designed to solve computational problems that are quite common, but would overwhelm any naive approach. Data structures and algorithms were (and still are) largely responsible for why Computer Science exists as a distinct discipline. So let’s learn about and create some cool ones.
When / Where / Who:
Alex Hicks is your instructor. See the Home Page to view more semester-specific information.
Course Objectives
By the end of this course, students should be able to:
Choose the data structures (DS) that effectively model the information in a problem; Judge efficiency trade-offs among alternative DS implementations or combinations; Apply algorithm analysis techniques to evaluate the performance of an algorithm and to compare DS; Understand and apply standard algorithms for searching and sorting; Recognize when a design pattern is being used and make judgments about when using a particular pattern will improve a design; Design, implement, test, and debug programs using a variety of DS such as buffer pools, hash tables, binary and general tree structures, search trees, heaps, graphs, and B-trees; Select appropriate methods for organizing data files and implement file-based DS; Apply design guidelines to evaluate alternative designs; Course Topics
During this course we will cover the following:
Time Complexity Analysis Binary Search Trees, Heaps, and Hashing Tables Sorting, Searching, and Indexing Graphs And much, much, more! Course Prerequisites
(If you are a VT CS undergrad student, you are likely familiar with this content)
Required Java Background. All students taking this course are expected to have successfully passed a traditional second semester programming course, taken for a grade from an accredited college or university. At Virginia Tech, this course is CS 2114. For an example of the expected prerequisite experience, see this page that describes CS 2114. If you don’t have a course with a similar background, please contact me immediately! Doing it “on your own” is almost never satisfactory; you need to have completed an actual course. In addition, you are advised to have either taken a course or else made an effort to brush up on the material typically taught in a standard Discrete Math class.
Finally, all programming for this course is done in Java. You should be proficient in understanding the structure of an object-oriented Java program, and also understanding how to use an integrated development environment (IDE) to develop Java programs, preferably Eclipse. If you want to use another IDE, that’s okay, but our course materials assume Eclipse, so you may have to do some adjusting. If you want to brush up on your Java knowledge, all VT students have access to LinkedInLearning (Lynda), and we have a curated list of tutorials that I think will help you get a handle on the language (“Java 8 essential training”, “Java 8+ essential training: Objects and APIs”, and “Java 8+ essential training: Syntax and Structure” all by David Gassner, as well as “Advanced Java Programming” by Bethan Palmer).
Time Commitment
It is incredibly important to me that your expectations for this class are realistic and accurate. This course covers lots of important content, and is therefore time-consuming. Students who have a working background of Java should expect to spend about 10-12 focused hours per week on this course’s activities on average. If you don’t have a strong background in Java, or understand effective design solutions, this amount of time increases substantially. Keep in mind that some weeks will require more time and effort than others as well.
If you have other commitments that demand a substantial amounts of time from you, please consider your options. Perhaps you would be better prepared in this course at a different time. Or you could take a different course that would help prepare you for this course. Success in this course might mean taking in during a different semester.
This is not meant to push you away from the class. I am actually very passionate about teaching these ideas and supporting your perspective while you learn them. You have a choice on going to college, you have a choice on your Computer Science degree, and you have a choice to take this class this semester.
Assessment and Grading
In this class, you will complete numerous homework problems and quiz questions over the course of the semester. There will also be three project assignments, where you will design and implement different data structures and algorithms. Tentative dates for the topics, assignments, and their deadlines will be shown on the course schedule. A final exam will be given at the end of the semester.
Individual assignments are not curved. There is no plan to curve grades for the entire course, and the letter grades given at the end of the semester are structured around the standard VT grading scale:
B+ is >= 87% C+ is >= 77% D+ is >= 67% A is >= 93% B is >= 83% C is >= 73% D is >= 63% F is < 60% A- is >= 90% B- is >= 80% C- is >= 70% D- is >= 60%
See the “Honesty and Academic Integrity” section to see the impacts an honor code violation can have on your final course grade.
Final grades in the course are broken down as such:
Programming Projects: 50% of final grade. The largest portion of work and credit in the course is dedicated to projects. There are 3 programming projects, spaced throughout our semester. Small milestones will be used to help promote an incremental approach to completing the projects. Each project requires a significant amount of time investment. Typically, students spend 20-30 hours per project, but some might need half that time or twice that time to finish. We spend time in class discussing project design and implementation. See the “More on Programming Projects” and “Time Commitment” sections.
Homework: 20% of final grade. These are made up of micro-sized, auto-graded exercises created by OpenDSA and accessed within Canvas. Roughly 100-150 exercises are covered in the semester. They work on a “mastery” basis, meaning that you can keep attempting any given exercise until you get full credit. If you made some mistake in your homework, feel free to work on it again until you are 100% correct. Normally, nearly all students earn 100% of the homework credit in this course. For homework assignments, discussion is encouraged but each individual should submit their OWN work. If no due date is posted on the assignment in Canvas, then it is due on August 6.
Exams: 20% of final grade. Exams are larger, scheduled assessments to fully evaluate your understanding of the covered course material. They are taken online, during the class lecture time, and cover the material that has been already presented in lectures. The Final Exam will be held during the lass class period. The final exam is cumulative, covering material from the entirety of the course. The Final Exam will be worth roughly twice the number of points compared to the Midterm Exam.
Participation: 10% of final grade. This is participation with the class, measured through several ways: attendance checks, positive contributions on our class forum (Piazza), and other miscellaneous activities. You are given a choice at the beginning of the semester whether you want your attendance to impact your grade (positively or negatively). If you choose attendance, then the attendance will consist of attending at least 75% of each class (by time) and participation for in-class quizzes (participation only - no correctness) will counts as points here. If you choose non-attendance, then it will use an exam-as-attendance assignment, which will copy your exam category grade as your attendance grade. It is generally more difficult to get a 100% consistently on the exams than on attendance checks. But for students that feel very prepared and want the most schedule flexibility, then this is a option.
More on Programming Projects
General Grading Criteria: If our task is to learn data structures and algorithms that are effective, then the programs we create should be (1) readable, (2) well-designed, (3) correct, and (4) efficient. Meeting less than all 4 criteria is not satisfactory. A program with excellent documentation style and correct output does not completely offset the consequences of a poor design. The same can be said for any combination of the 4 criteria.
Note that while design and efficiency may have been optional objectives in previous classes, that is not the case here. A primary objective of a data structures course is to teach efficient algorithms and use of appropriate data structures. Another objective of this course is to exercise your design abilities when solving different problems. Projects are graded in part on design and organization quality, and in part on efficiency. Some of our class discussions will focus on “good” and “poor” design choices for the projects, so it is important to pay attention to these discussions. Typical project specifications for the course often will not explicitly state requirements for efficiency or design generality, because you are now the designer.
You already have a fair amount of experience in programming and making smaller design decisions prior to this course. This course will help you to extend those abilities further and give you the reasoning behind the larger aspects of project design and efficiency, including:
Time and space efficiency. If an operation needs significantly more time or memory than necessary to run, it is not efficient. Our programs should be able to handle inputs that scale to a large size, or be usable within a limited memory capacity. Versatile data structures. The data structures in this class can have a very practical use in situations beyond the class projects. There is no reason to limit them to only use the data types described in the project. For example, a search tree implementation should support storing just about any kind of data, rather than only supporting strings. Purposeful classes. Object-oriented design suggests that each class should have a singular, precise responsibility. For projects in this course, this is most often a concern when deciding how to separate the main class, reading any command files, executing those commands, and communicating between the various data structures classes.
Programming Language: The projects must be implemented in Java.
Submissions Grading : Webcat is our semi-automated grading system of projects. If you have not already, please register with the Web-CAT system, and install the latest Web-CAT plug-in for Eclipse (see the Web-CAT portion of the OpenDSA Modules list). Program correctness will be assessed by Web-CAT upon submission. It is the responsibility of the student to submit a program that will successfully compile and execute under Web-CAT.
Note: The most recent Web-CAT submission is the one used for final grading. NOT the highest score out of all attempts. This is because your final submission design is manually graded by TAs, and it could be greater than the auto-graded penalties.
Note: Both the Eclipse plugin and Web-CAT testing process will have significant changes to include the feature of “Mutation Testing” instead of the basic “Code Coverage” used in CS2114.
Allowed / Forbidden Code and Classes: You are generally NOT allowed to use built-in Java data structures such as ArrayList, HashMap, Stack, Vector, etc., unless the project spec explicitly permits their use. Do not use Java’s import statement carelessly, because it could import one of those classes! You may use code given from the textbook or the instructor. Note that the OpenDSA code is likely not suitable for use without modifications. If in doubt, ask the instructor or TA.
Lateness: Projects will have a deadline (date and time) specified within Canvas and Web-CAT. Web-CAT will provide the official timestamp used to determine whether a project is on time. Note that the default timezone is Eastern Time if none is specified. Projects that arrive “a few minutes late” are still late, and are graded appropriately. Late submissions are penalized by 5% project points every 12 hours late, up to a maximum of 72 hours late. Project submissions that are 72+ hours past the deadline are not accepted unless explicit permission is given by your instructor.
Early Submission Points: You will be rewarded for using good time management during projects. You will earn 10 bonus points on your submission for being 24 hours early you are to a project deadline (max of 10 points). Note that only your final submission to a project will be graded. For submissions that are missing a significant amount of the project specifications, instructors and TAs have the ability to remove the early submission points.
Project Partner and Group Work: While the homeworks, quizzes, and final exams are all individual, you may work with either zero or one other classmate (currently in our class) on the projects. The project specification is the same for solo work and group work. If you form a partnership, you must work as respectful colleagues and to have clear, consistent communication throughout the project. Between projects, you are free to switch to another partner, or work solo. You must contact and get permission from the instructor to change partners during a project, and this is only given in dire circumstances.
Be aware of the added overhead of working with a project partner. If using code collaboration tools (such as GitHub or code.VT) make sure you do so privately and only with your project partner to avoid honor code violations.
Honor Code Violations / Plagiarism / Cheating: Don’t do this. There are serious consequences, and I absolutely will enforce the policies of the Virginia Tech Honor Code. See the “Honesty and Academic Integrity” section below.
Getting Help
The material in this course is complex and very new to many students. It is both understandable and expected that you will need some direct support in learning it and completing the assignments at times. The role of the Instructor and the TAs in the course is not to do the work for you. Our role is to assist you in making the connections so you fully understand the concepts. We can only do this if you ask us your questions, so PLEASE ASK! This could be during class, office hours, on piazza, or in email. Asking is step one, but it is incredibly helpful to us (and to you) if you also:
List your questions in an explicit way. Include any supporting information. Make an attempt at the task. Tangible things are easier to understand than speculations. For projects, submit to Web-CAT first. Then we can see your code, how it runs, and a report of Web-CAT’s findings. It is often the case that your unit tests will pass, but the reference tests will fail. A recent submission is more helpful than an out-of-date one.
Generally, we don’t review your code. If you have a particularly gnarly bug, we will ask if you have created a test case for that condition. If the answer is “no”, we will ask you to write the test, examine how the fault could be happening, and then come back with your findings.
This is not to be mean, because following this process actually reveals bugs and helps you to find and fix bugs in the future. It also narrows down where/when the bug is occurring, and where our assumptions could be misleading us. This is similar to the difference between giving someone a fish and teaching someone to fish (feeding them for a day or a lifetime).
Policies Health and Safety
Virginia Tech is committed to protecting the health and safety of all members of its community. By participating in this class, all students agree to abide by the Virginia Tech Public Health Guidelines. The Ready.VT site is the main source of these information, and clarifies policies that apply to all classes and students. It also contains reasonable instructions for responding to symptoms, test results, and self-isolation. There are also a wide range of health resources at HokieWellness.vt.edu to support students.
If a student will miss significant class activities because of an extended illness or isolation, then the Dean of Students Office should be contacted for an official absence verification. Prolonged absences may be difficult to make-up. Students should consult with their advisor about possible options if too much course work is missed to feasibly make-up.
Communication Expectations
The teaching team of our course will work to respond to emails and Piazza posts in a timely and reasonable manner. However, this does not cover every hour of every day. We put in extra effort to respond quickly during time-sensitive periods (e.g. closer to project deadlines), but there is no guarantee you will get an instant answer.
Accommodations and SSD
You are welcome here! I’m happy to include accommodations that remove or reduce the unfair barriers within our educational systems. These academic barriers can be due to ADHD, chronic or temporary medical conditions, deaf or hard of hearing, learning disability, mental health, vision impairment, or another disability. If you anticipate or experience these barriers, you can contact the Services for Students with Disabilities (SSD) office (540-231-3788, email ssd@vt.edu, or visit www.ssd.vt.edu). If you have an SSD accommodation letter, please it to me as early as you can using this SSD system (as of 2024). You can also meet with me privately during office hours to deliver your letter and to discuss accommodations. I will then implement your accommodations within a reasonable time frame. You can also meet directly with me to discuss ideas alternative to this.
Academic Support
I encourage any student requiring academic support to come to talk to me at any time. Also, there are many resources from Undergraduate Academic Affairs and the Graduate School.
Basic Needs Accommodations
For any student who has difficulty affording groceries, accessing sufficient food to eat every day, or who lacks a safe and stable place to live, and if you believe this may affect your performance in this course, you are urged to contact the Dean of Students office for support at 540-231-3787 or complete an interest form to participate in The Market at Virginia Tech. There is also a Student Emergency Fund program. If you are comfortable in doing so, please notify your professor or departmental advisor of your situation. This will enable them to provide any resources they hav
Land and Labor Acknowledgement
Virginia Tech acknowledges that we live and work on the Tutelo / Monacan People’s homeland and we recognize their continued relationships with their lands and waterways. We further acknowledge that legislation and practices like the Morrill Act (1862) enabled the commonwealth of Virginia to finance and found Virginia Tech through the forced removal of Native Nations from their lands, both locally and in western territories.
We understand that honoring Native Peoples without explicit material commitments falls short of our institutional responsibilities. Through sustained, transparent, and meaningful engagement with the Tutelo / Monacan Peoples, and other Native Nations, we commit to changing the trajectory of Virginia Tech’s history by increasing Indigenous student, staff, and faculty recruitment and retention, diversifying course offerings, and meeting the growing needs of all Virginia tribes and supporting their sovereignty.
We must also recognize that enslaved Black people generated revenue and resources used to establish Virginia Tech and were prohibited from attending until 1953. Through InclusiveVT, the institutional and individual commitment to Ut Prosim (that I may serve) in the spirit of community, diversity, and excellence, we commit to advancing a more diverse, equitable, and inclusive co
Attendance/Participation
Participation in the class benefits you, and allows me to tailor the class to be more engaging to you and relate to your interests. Attendance and participation may be given a minor role in the course’s grading during the semester. Try to come to class and ask questions about the material. Participate on the classroom forums. Unexpected barriers that are long-term are a great reason to email me, and discuss how we can make adjustments that support you academically.
Hardware/Software Usage
You must have access to a reliable computer and reliable internet for this course. If this is a challenge, please reach out to me. Remember to back up your work early and often. “My hard drive crashed” is not an acceptable excuse for not turning your work in on time. Your programs are valuable and take significant effort, so protect them.
Neatness, Legibility, and Professionalism
The ability to express ideas in a clear, cogent, compelling, legible, and concise manner is of paramount importance in the CS profession. Marks will be deducted if your work is not properly identified (name, course, assignment name, date); professionalism is lacking, e.g., inconsistent page formats; unlabeled diagrams, missing page numbers, etc.
Assignment Submissions
Homework/project assignments must be submitted electronically by the due date and time as indicated in Canvas or Web-CAT. Remember that your clock and the server’s clock may be different, so plan accordingly. Also, if the assignment is due at 5:00 PM, that means 5:00:00 PM. For example, Canvas treats 5:00:01 as late, so again, plan accordingly. Unless otherwise noted, written assignments should be submitted in PDF format.
For late project submissions, review the project section in the syllabus. If a different assignment is acceptably late (as determined by the instructor), it will be penalized accordingly: first occurrence: -25% penalty, second occurrence: -50% penalty, more occurrences: -100% penalty (a score of zero).
If you are unable to complete/submit an individual assignment due to extenuating circumstances (i.e. Illness), please contact me as soon as possible to discuss alternatives. Note that for projects where you are working with a partner, either of you can submit. It is unlikely that both of you are prevented from doing so by circumstance. There will be no extensions for projects without a prior discussion with me.
Make-Up Exams and Assignment Deadline Changes need to be discussed with me. These actions would need a justifiable reason (personal sickness, family emergency, university scheduling). This discussion should also happen at the earliest possible opportunity. Final exam date changes will only be entertained if 3 exams are scheduled within 24 hours, and you must use the approved University process to formally request to have an exam changed. Note the deadline for having an exam rescheduled is typically three to four WEEKS before final exams start. Requests made afterward will not be entertained.
Return of Graded Items
Every effort will be made to return graded items within 7 days of the due date.
Regrades
Course assessments are graded thoroughly and with great care. However, if you feel a grading error has been made, you can submit the item for regrading by:
Meeting with the TA who completed the grading during office hours. The person who graded a project is listed in the comments in Web-CAT. Meeting with the instructor and clearly discussing the conflict. Emailing the instructor a written regrade request, including a clear explanation of the exact item being graded, why you believe it is incorrect, and what you believe should be done to correct it. If the assignment is within Gradescope (testing/grading software), regrade requests should be made there instead of through email.
In either case, the request must be made within three days of the grade’s publication. Adjusted scores shall be considered final. Note that the instructor reserves the right to regrade the entire assignment.
Honesty and Academic Integrity
The Virginia Tech Honor System applies to this course, and will be vigorously enforced, just as it has done so in the past. Students enrolled in this course are responsible for abiding by the Honor Code. These standards are the same for in-person or online classes. A student who has doubts about how the Honor Code applies to any assignment is responsible for obtaining specific guidance from the course instructor before submitting the assignment for evaluation. Ignorance of the rules does not exclude any member of the University community from the requirements and expectations of the Honor Code. For additional information about the Honor Code, please see the Undergraduate Honor System and the Graduate Honor System .
For purposes of this course, all assignments are considered ‘graded work’, and are subject to the Honor System. Homework assignments, quizzes, and exams must be done strictly on an individual basis. For each programming assignments you are permitted to work with a single partner. Aside from your programming partner, it is acceptable to discuss with classmates a programming assignment in a general way. In other words, you may discuss with your classmates what your program is required to accomplish but not in detail how to achieve that goal using Java. All source code can only be shared or discussed with 3 groups of people: instructors, teaching assistants, and your current project partner. Always give credit for work that is not entirely your own (e.g., parts of programs or homework answers borrowed from a book).
If you have questions or are unclear about what constitutes academic misconduct on an assignment, please speak with me. I take the honor code very seriously in the course. The normal sanction I will recommend for a violation of the Honor Code is an “F” (F star) sanction as your final course grade. The “F” represents failure in the course. The “” (star) is intended to identify a student who has failed to uphold the values of academic integrity at Virginia Tech. A student who receives a sanction of F* (F star) as their final course grade shall have it documented on their transcript with the notation “failure due to academic honor code violation.” You would be required to complete an education program administered by the Honor System in order to have the “*” and notation removed from your transcript. However, the “F” would be permanently on your transcript.
To be concise: Don’t do this. If you have concerns, you can always speak to the instructor or a TA.