CMSI 282 - Algorithms
Professor Andrew Forney • Andrew.Forney[at]lmu.edu • Spring 2019 • PER 140 • 12:40 pm - 1:55 pm
In CMSI 281 (Data Structures) we learned about the tools that best suited particular computing tasks, and in CMSI 282 (Algorithms) we extend this experience by learning new programming techniques that best suit particular tasks. By analogy, an architect may know what materials and tools should be used to construct a house, but experienced ones will have an appreciation for paradigms of architecture (e.g., modern, craftsman, etc.) to best suit their clients' needs.
Learning Outcomes
By the course's end, students will:
Gain intimate understanding with a number of programming paradigms, including: search, heuristic design, memoization, dynamic programming, greedy algorithms, and backtracking.
Integrate knowledge of appropriate data structures in pursuit of the above (e.g., search and minimax trees, tabular caching, hash tables) as well as some modern applications of each (e.g., game playing agents, spell checkers).
Understand the fundamentals of some modern topics computational mathematics, compression, cryptography, optimization, and linear algebra.
Prerequisites
Warning: before taking this course, it is assumed that you have a matured grasp on the Java programming language, as well as the conceptual topics from Data Structures (CMSI 281).
This class uses Java for its concrete examples, homework, and exams. We will not spend much class time reviewing Java fundamentals, though you are welcome to ask for clarification at any point.
If you require additional practice, you may learn through any number of online tutorials, and test your skills on codingbat.com (for instance).
Texts
There is an optional, companion textbook for the course: Introduction to Algorithms, by Cormen, Leiserson, and Rivest.. Although this specific text is not mandatory for the course, it contains many concepts that we will be covering in great detail, and your exams will expect that you understand these concepts.
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
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, though may be missing lecture-exclusive information (see Note tab on course page).
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 3-Unit class, it is expected that you will be allocating an average of 6 hours 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
Although you're always free to email me, I'll host some in-person office hours at the following times:
MW 2:30 - 4:30pm, DOO 201A
T 2:30 - 4:30pm, DOO 201A
On other days, you'll find me in the Keck Lab, ACT Lab (DOO 217), or my office (DOO 201A). If my door's open, stop by for any homework questions, lecture clarifications, or chat!
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 each topic, the relevant chapter of the textbook is also given, however, you are only required to understand the sections of each chapter that correlate with the material in the course notes -- the rest are for your curiosity and edification!
* CN = Course Notes, indicating topics that will be covered and listed on our course website but are not found in the textbook, even though *all* topics will have an accompanying page in our course notes.
| Item | Date | Topic | Text Chapters |
|---|---|---|---|
| Lecture 1M | 1 / 14 | ||
| Lecture 1W | 1 / 16 | ||
| Lecture 2M | 1 / 21 | ||
| Lecture 2W | 1 / 23 | ||
| Lecture 3M | 1 / 28 | ||
| Lecture 3W | 1 / 30 | ||
| Lecture 4M | 2 / 4 | ||
| Lecture 4W | 2 / 6 | ||
| Lecture 5M | 2 / 11 | ||
| Lecture 5W | 2 / 13 | ||
| Lecture 6M | 2 / 18 | ||
| Lecture 6W | 2 / 20 | ||
| Lecture 7M | 2 / 25 | ||
| Lecture 7W | 2 / 27 | ||
| Lecture 8M | 3 / 4 | ||
| Lecture 8W | 3 / 6 | ||
| Holiday | 3 / 11 | ||
| Holiday | 3 / 13 | ||
| Lecture 9M | 3 / 18 | ||
| Lecture 9W | 3 / 20 | ||
| Lecture 10M | 3 / 25 | ||
| Lecture 10W | 3 / 27 | ||
| Lecture 11M | 4 / 1 | ||
| Lecture 11W | 4 / 3 | ||
| Lecture 12M | 4 / 8 | ||
| Lecture 12W | 4 / 10 | ||
| Lecture 13M | 4 / 15 | ||
| Lecture 13W | 4 / 17 | ||
| Lecture 14M | 4 / 22 | ||
| Lecture 14W | 4 / 24 | ||
| Lecture 15M | 4 / 29 | ||
| Lecture 15W | 5 / 1 | ||
| Final | 5 / 8 11:00 am |
Assignments & Grading
Grade Decomposition
Grades will be assigned based on the following weighted coursework:
[20%] 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).
[40%] Homework: Larger assignments with heavy coding required. Programming style and comments are graded as well. All homework assignments are weighted equally. Expect assignments once every ~2.5 weeks.
[40%] Exams: There will be 3 exams every ~5 weeks throughout the semester (including the final). Your best 2 exam scores will constitute 80% of the exam grade, with your worst score constituting the remaining 20%. For example, if your 3 exam scores were 70, 80, and 90, then your weighted exam score for the course will be 82 (= 70*0.2 + 80*0.4 + 90*0.4)
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's Announcements and Brightspace 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 inappropriately between students is subject to severe disciplinary action. (not that you would, just sayin')
Style: assignments which are sloppily submitted without proper formatting, style, and comments are subject to penalties. As this is an upper-division computer science class, you should be intimately familiar with these stylistic requirements.
Development Environment: for in-class examples, I will be using the Eclipse IDE, but you are free to use whatever development environment you'd like for your own work.
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 after class. 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.