CMSI 2120 - Data Structures & Applications
Professor Andrew Forney • Andrew.Forney[at]lmu.edu • Fall 2021
CMSI 2120 is a 4-Unit intermediate-level programming class that teaches students how to craft efficient and space-conscientious applications by analyzing and then choosing the "right" data organization for a task. Although Java is the course's language of focus, students will learn core concepts that permeate all programming languages, as well as language-agnostic tools to analyze and think deeply about implemented algorithms.
Learning Outcomes
By the course's end, students will:
gain experience with an enterprise programming language (Java), advanced topics in object-oriented programming, and software development best practices, logistics, and test-driven development.
understand analytic programming concepts such as asymptotics, time-complexity, and space-complexity -- that not all programs are created equal; two programs that perform the same task may not do so with the same efficiency or cleanliness.
be introduced to a wide range of Data Structures and Abstract Data Types (ADTs), learning which are best suited for which tasks, including: lists, stacks, queues, heaps, priority queues, hash tables, sets, maps, trees, search trees, tries, and graphs.
gain a deeper understanding of class hierarchies and inheritance, object-oriented programming, and both implementing and applying data structures programmatically.
learn the interfaces for popular Java collections, and how to use them in a variety of non-trivial programming tasks.
identify beneficial and detrimental interactions between ADTs and algorithms that operate with them.
Prerequisites
Warning: before taking this course, you must have strong foundations in the fundamentals of programming (CMSI 185).
This class uses Java for its concrete examples, homework, and exams. We will spend the first few weeks of the course covering the Java necessary to succeed in the course and beyond, though we will not dwell on basics like how or when to use iteration or conditionals.
If you require additional practice, you may learn through our textbook (see next section) and any number of online tutorials -- a list of which can be found on this LMU CMSI resources page.
Note: this section of CMSI 2120 is transitional between old and new LMU CMSI curricula! This means that some students may already have Java experience from CMSI 186, and others may not -- please be patient during the first weeks' calibration of skillsets!
Additionally, you should be comfortable with the fundamentals of Git, and managing GitHub repositories.
We will be using GitHub Classroom for assignment distribution and collection, so advance comfort with these tools will make your life easy.
Need a refresher? Take a look at the GitHub Tutorials here.
Texts
We will be "using" two optional textbooks for the course, which will primarily cover or dive deeper into the theoretical material than we have the time to during lecture:
Although these specific texts are not mandatory for the course, they contain all concepts that we will be covering in great detail, and your exams will expect that you deeply understand these concepts.
These are also popular textbooks with many editions; any edition will likely match what we cover in the course, so you may purchase whichever you like (if any).
Additionally, I will provide abbreviated course notes for our lectures on my course page (see Notes tab)
Resources will be provided throughout the course detailing any additional topics that are not sufficiently contained in the above text. These resources will be free and publicly available.
Lecture Attendance
As university policy surrounding the COVID-19 pandemic evolves, we will follow health guidelines in the classroom to the best of our ability. Stay posted to university communications regarding this as they are distributed.
At the time of this writing, *ALL MEMBERS* of the class (including me) are required to wear a mask during lecture attendance!
Additionally, all students are requested to choose a seat to stick with for the semester in the event that contact tracing is required.
Although not mandatory, lecture attendance is strongly advised since you'll otherwise miss out on all of our inside-jokes. Less importantly, you'll be missing out on lecture content that will not be posted online, classwork (see below), and hints for homework and exams. If you miss a lecture, the important points will be sketched in our course notes posted on this site's Notes tab.
Lectures are participatory in nature, often with exercises and group-work to facilitate learning. Laptops are *discouraged* for note-taking, but *encouraged* for working on in-class problems.
Workload Expectations
As this is a 4-Unit class, it is expected that you will be allocating an average of 9 hours outside of lectures per week working on course assignments, reading, and studying. Some weeks will have less material to keep you busy, and others more, but be aware that this is a work-intensive course that may require you to spend a lot of time programming!
Slack Messaging
Alongside email exchanges, you may reach me via the Slack messaging service (Slack is a chat client that can be downloaded here) in the LMUCS channel (lmucs.slack.com).
Office Hours
TR 10:30am - 12:00pm, DOO 201A or 217
W 12:00pm - 3:00pm, DOO 201A, 217, or on Zoom (will be announced if moved here, ping me on Slack otherwise)
By appointment for other times (contact me via email or Slack)
In addition to my office hours, this course has the following stellar TAs who are versed in its topics to assist (see LMU Slack / Discord for contact info):
Tentative Schedule of Topics
The following constitutes the tentative schedule for topics to be covered in the course. This is largely an approximation for what we will cover each lecture, and is subject to change.
For textbook chapter references, IA = Introduction to Algorithms and JN = Java in a Nutshell.
Note: Exam Topics may differ from this schedule; see the Materials tab of our course site for each exam's stated topics.
Note: Assignment deadlines are not listed on this page as they are sensitive to the pace of the lectures -- see the associated Homework tabs on the main course page for these.
| Item | Date | Topic | Text Pages |
|---|---|---|---|
| Lecture 1-1 | |||
| Lecture 1-2 | |||
| Lecture 2-1 | |||
| Lecture 2-2 | |||
| Lecture 3-1 | |||
| Lecture 3-2 | |||
| Lecture 4-1 | |||
| Lecture 4-2 | |||
| Lecture 5-1 | |||
| Lecture 5-2 | |||
| Lecture 6-1 | |||
| Lecture 6-2 | |||
| Lecture 7-1 | |||
| Lecture 7-2 | |||
| Lecture 8-1 | |||
| Lecture 8-2 | |||
| Lecture 9-1 | |||
| Lecture 9-2 | |||
| Lecture 10-1 | |||
| Lecture 10-2 | |||
| Lecture 11-1 | |||
| Lecture 11-2 | |||
| Lecture 12-1 | |||
| Lecture 12-2 | |||
| Lecture 13-1 | |||
| Lecture 13-2 | |||
| Lecture 14-1 | |||
| Lecture 14-2 | |||
| Lecture 15-1 | |||
| Lecture 15-2 | |||
| Final | 12 / 11 11:00 am |
Assignments & Grading
Grade Decomposition
Grades will be assigned based on the following weighted coursework:
[25%] Classwork: Small classwork assignments will be given throughout each week, with in-class time allocated for their completion. Though you will have the opportunity to finish these in groups and with my assistance during class, you are not required to attend lectures, and so may submit these electronically by their listed due dates. Your lowest classwork grade will be dropped (even if you skipped it entirely).
[45%] Homework: Larger assignments with heavy coding required. Programming style and comments are graded as well. All homework assignments are weighted equally. Expect roughly 5-6 assignments in total, apportioned once every ~2.5 weeks.
[30%] Exams: There will be 2 exams (a midterm and final). Your best exam score will constitute 2/3 of the exam grade, with your worse score constituting the remaining 1/3. For example, if your 2 exam scores were 60 and 90, then your weighted exam score for the course will be 80.0 (= 60*(1/3) + 90*(2/3))
Final Grades
Final letter grades are given based on the university scale of grade percentages:
A: 93 - 100
A-: 90 - 92
B+: 86 - 89
B: 83 - 85
B-: 80 - 82
C+: 76 - 79
C: 73 - 75
C-: 70 - 72
D: 65 - 69
F: 64 and below
Fractional grade percentages at 0.5 or over will be rounded up, so an 89.5% will be considered a 90% (A-), but an 89.4% will be considered an 89% (B+) on the above scale.
That said, these are only the guaranteed grade assignments: if your "final" grade is an 82%, you are guaranteed a B- or better, but you might still get an A if 82% is the top score.
Extra Credit
Extra credit opportunities will be sporadically available during lectures / exams; if you are present and can hand in an attempt at the extra credit opportunities, you will receive bonus points!
If you receive all extra credit opportunities, you can gain a maximum +2% on your final grade. These bonuses are applied post-curve, so no student will be punished for not attending lectures relative to their peers.
Submission Standards
Each of your submitted homeworks and projects are subject to the following constraints:
Assignment posting: all assignments (classwork, homework, or otherwise) will be announced in class and posted on this site with due dates. You are responsible for checking this site / your email for any updates to assignments and their associated deadlines.
Late Policy: assignments are due at exactly the time indicated by the method specified. Assignments that are late by anywhere from 0 - 24 hours will only receive 80% of the points that they would have otherwise earned. Assignments that are late by 24+ hours receive a 0. There are no exceptions to this rule.
Individual Work: students are encouraged to talk and think about problems in groups, but each submission should be their own, containing no code that has been copy-pasted from another student. We take plagiarism very seriously, and each submission will be run through a similarity-checking mechanism to ensure fairness. Code or homework which we believe to be shared innapropriately between students or copied from the internet is subject to severe disciplinary action (not that you would, just sayin'). The following are examples of unacceptable behavior in this course:
Copying non-trivial amounts of code from the internet into an assignment (excluding small things from StackOverflow like how to use Java Streams to simplify some code).
Copying another group's solutions on a classwork exercise (sharing between group members is encouraged... that's what it means to... you know... group up).
If you plan to copy anything from the internet, ask first!
Style: assignments which are sloppily submitted without proper formatting, style, and comments are subject to penalties. We will discuss what constitutes such offenses in class, though you should be familiar with clean coding standards from your introductory courses.
Development Environment: I will be using the Eclipse IDE for in-class demonstration; for your work, you are free to use whatever development environment you wish, and the class will not force you to choose one or another, though at minimum you are expected to be able to develop iteratively using JUnit tests and GitHub Classroom for your version control.
Resources
Student Rights and Responsibilities
Just as I have certain expectations of you in this course, you may have certain expectations of me. Here is a high-level list of each:
My Responsibilities
Provide you with an educational experience superior to that which could be gleaned from a textbook or online source alone.
Answer your questions and curiosities in office hours, over Slack, and via email with a turnaround of at most 36 hours.
Give you feedback on your submissions and individualized instruction on how to maximize your gain from this class.
Your Responsibilities
Be responsible with use of your time, class time, office hours, email, and the Keck Lab TAs. Last minute pleas for help on assignments or exams are the opposite of this.
Be respectful of classmates.
Don't cheat or plagiarize on exams or assignments.
Tips for Success in this Class
Here are a few tips for succeeding in this class (and college, in general); they're not meant to sound patronizing, but rather, are simply pearls of wisdom to hand down from someone who has recently trodden your path!
Ask questions: if there is one piece of advice I can impart unto you, it's to ask questions when you have them. Chances are good that if you have a question, someone else has the same one, you won't be left behind wondering about something that was covered minutes ago (and which future material might employ), and I promise not to judge you for whatever you ask (well, not too hard at least). At the very least, if you have a question, write it down and then ask it on Slack after class (which can be done anonymously if you so please). The heart of academic inquiry is just that: inquiry!
Fear not the specter of error: in college classes, there tends to be a crippling aversion to being wrong, especially publicly! I'm here to tell you that there is no better time to be wrong than in class, particularly in one as interactive as ours. There are a variety of silver-linings to being wrong: you won't forget what you were wrong about (one fewer thing to cram for later), it's better to learn from being wrong when it doesn't matter (i.e., in discussion) than when it does (i.e., on a test or during an interview), and I will respect you for your courage. There is only one circumstance in which you should fear error: when you fail to learn from it (at which point, see tip above for remedy).
Indulge your curiosity: and no, that's not some tagline stolen from a Vegas day-spa (actually, it might be, don't quote me on that), but the wisdom is sound... in class, we will cover a variety of topics with accompanying exercises that highlight the main take-away messages of the lesson, but that does not mean that your learning should stop there. Indeed, computer science is one of those beautiful disciplines wherein experimentation and exploration are so trivially entertained. Curious about what would happen if you changed the value of a variable? Do it! Curious about what other methods exist for certain data types? Google them! There is no reason why your learning should be constrained to what I (strategically) offer you; we have only limited time in class, and I'll prioritize the most important topics, but your interests can spread their own wings. Go forth and explore!
University Resources
Here are some LMU links for University Resources that might be of interest:
Academic Degree Requirements and Policies: Pay particular attention to honor code and process.
Disclaimer: Note that due to the potentially volatile nature of the COVID-19 climate, all items on this syllabus are tentative and may potentially change as university and federal guidelines dictate.