Syllabus

Description and Objectives

Welcome to CS 312! This course will provide an introduction to the analysis and design of algorithms. The course adopts both a theoretical (mathematical) and a practical perspective. Algorithms solve problems, and we will explore a wide variety of problems, some relatively abstract and some down-to-earth. Practical application domains include cryptography, geometry, image processing, bioinformatics, logistical planning, route planning, and artificial intelligence. More abstract applications include combinatoric optimization and graph theory. As such, CS 312 provides an excellent mathematical foundation and will serve as a gateway to problem solving in other domains. The domain of CS 312 is one of the key areas of focus for technical interviews, because of the centrality of the topic to computer science. Doing well in this class will help you excel as a computer scientist and software engineer.

We will explore several families of algorithms, with the ability to solve problems of increasing complexity:

• Divide and Conquer
• Graph Algorithms
• Greedy Algorithms
• Dynamic Programming
• Real-valued Linear Programming
• Heuristic Search (Branch & Bound and A*)

The theoretical analysis of algorithms can answer questions that are difficult or impossible to answer by other means. However, one’s trust in theoretical results should be tempered by a firm understanding of their limits. The most important strength and limitation of theoretical analysis is the generality one can achieve. This generality is not always useful when attempting to solve a small set of problems with a well-defined performance goal.

After completing CS 312, the student will have learned to successfully apply the following theoretical analysis techniques:

• Asymptotic analysis
• Probability theory in service of average case analysis
• Recurrence relations for the analysis of recursive algorithms

The practice and theory of algorithms covered in this class will serve you well as you move on to more ambitious subjects in Computer Science, and it will serve you well in your careers. This course is also required by many of the department’s 400-level courses.

As a practical objective of the course, CS 312 students will use Visual Studio, the C# programming language, and the .NET framework.

Instructor

• Email: ringger AT cs DOT byu DOT edu
• All questions about Homework and Project assignments should be directed to the Google discussion group for the benefit and participation of others
• Any message sent to the professor should have a subject that begins with “312:”
• Phone: 801-422-7615
• Office: 3328 TMCB
• Office Hours: See Office hour chart and by appointment

TAs

Thomas Hansen, Sean Lane, & Michael Walker

• Email: byu312ta AT gmail DOT com
• All HW and Project questions should be directed to the Google discussion group for the benefit and participation of others.
• Location: CS 312 Cubicle in 1058 TMCB (Cubicle #20)
• Office Hours: See Office hour chart and by appointment

Lecture

• Section 001: M, W, F 9:00-9:50am, 1103 JKB
• Section 002: M, W, F 10:00-10:50am, 1103 JKB

Resources

Textbook: ''Algorithms'' by Dasgupta, Papadimitriou, and Vazirani.

• We also use supplemental handouts, which are available via links from the course schedule.

Schedule: On BYU Learning Suite.

Lecture slides: Lectures here on this wiki.

Announcements: Google Group - BYU CS 312 Announcements : The announcements Google group is used for announcements only. Please give messages on this mailing list high priority.

Discussion Forum: Google Group - BYU CS 312 Discussion : The discussion Google Group will be used by all class members to discuss questions concerning the homework assignments and projects. TAs and instructor will participate on the group when available.

Project Submission: On BYU Learning Suite

• If you submit after the due date, please send email to the TA email address to inform the TAs of your late submission, so that the responsible TA will know to look for your assignment.

Homework Submission: In class, at the beginning of class.

Homework Keys: On BYU Learning Suite (in the Documents tab)

• To view feedback on a graded assignment, use the 'Grades' page on Learning Suite, and click on the assignment's 'Feedback' button.

Preparation

Essential

• Competence as a programmer
• CS 240
• CS 252
• Familiarity with basic probability and statistics (as in Statistics 121 or 321)
• Math 290 (Proofs)

Development Tools

CS 312 assumes that you are a competent programmer and relies on CS 240 to help you achieve and demonstrate that status.

CS 312 uses Visual Studio, the C# programming language, and the .NET framework. This gives CS 312 students some exposure to a widely used development environment. We find that many CS graduates working in industry use Microsoft tools in their professions and that their experiences in CS 312 serve them well. Although the course uses C#, you are expected to come up to speed on C# on your own without any guidance in class and to be productive in the language. We spend zero time on C# in class.

That said, for several of the projects, we provide pre-constructed scaffolding to save you time and to allow you to focus on implementing the core algorithms and data structures for the project while benefiting from a non-trivial GUI. Consequently, you will be insulated from some of the .NET framework. If you would prefer to implement from scratch (including the GUI), you may do so, but you must recognize that this will require more time on your part. For some of the projects, in addition to the GUI version, we may offer a version of the project that does not require any scaffolding and which has alternative requirements that do not depend on a GUI.

You must use Visual Studio to program in C# on the Windows platform to complete the projects. Visual Studio 2010 is recommended, although newer versions should work well also.

Because Visual Studio requires Microsoft Windows, you will need access to a Windows machine. If you are using a virtual machine but don't already have a Windows license, then you can get one for free through BYU's DreamSpark Premium subscription (see below).

Visual Studio 2010 is installed on a Windows virtual machine on each Linux machine in the department labs.

Visual Studio 2012 is also available, and you can get a free copy for your own machines if you are a BYU CS student through the MSDN Academic Alliance / Dreamspark here:

Furthermore, if you do not wish to go through MSDNAA / DreamSpark, you can download Visual C# Express for free from Microsoft without any DreamSpark credentials. Students have used it successfully for all that we do in this class.

Note, however, that the Express edition tries to make the interface a little simpler to begin with. Take the following steps to prepare Visual C# Express for use in CS 312 (note that these directions were written for version 2010):

• Click the “Tools” menu option
• Choose “Settings”
• Choose “Expert settings”
• The “Build” menu will now be available, as will the very useful "Refactoring" menu.

Then:

• Choose “Configuration Manager”
• Click the drop-down menu under “Platform”
• Select “New”
• In the drop-down menu under “New platform” choose x86
• Press “OK”

Getting Started

To help you get started, here are some useful articles at MSDN:

Great Windows Tools

Consider installing and getting to know all of the great "SysInternals" tools. In particular the Process Explorer is particularly useful when watching process memory usage.

Out-of-class Learning Experiences

Interviews with students suggest that what and how students do outside of class is the strongest predictor for engagement and learning in a given class (Light, Richard J., Making the Most of College: Students Speak their Minds, Harvard University Press, 2001). The same study suggests that working in groups was also well-correlated with successful engagement and learning in class. So you are welcome to work in groups outside of class and to help one another. However, you must each write and turn in your own work, unless the assignment explicitly states otherwise. Furthermore, if you work with others, you must acknowledge that you did so by listing your collaborators on your work. See the complete Cooperation Policy below for more details.

There will be several types of out-of-class learning experiences: reading, screencasts, quizzes, homework, projects, and exams.

Most lectures on the schedule have associated readings. You are expected to do the reading prior to the indicated lecture and to come to class prepared with any questions you have, so that they can be discussed in class, as time permits. The assigned reading is an important part of understanding the key concepts of the course. While you are not graded directly on your reading, it will be reflected in your mastery of the subject and your ability to perform well on the exams.

Screencasts and Quizzes

Some lectures will be presented using screencasts outside of class. You are expected to view the screencast and complete its associated quiz by the specified date on the course schedule. Such online lectures will prepare you for the corresponding in-class problem solving session to follow the screencast lecture. Without the screencast (and the associated reading), it will be difficult to participate well in the in-class problem solving.

Scheduled screencasts and the accompanying quizzes will generally be published a day before the date on the schedule. It is advisable to watch them after having read the assigned reading up to that point on the schedule and/or after having participated in all previous lectures. Screencasts may not make sense if watched prematurely.

Homework

Regular homework assignments are posted on the schedule and announced in class. We will have homework due every day; in a Spring or Summer term, potentially more than one assignment will be due each day due to the double pace. One purpose of the homework is to solidify concepts learned during the lecture and from the required reading. Another purpose of the homework is occasionally to explore new concepts not covered in class. Often the homework will help you prepare to succeed on your projects as well.

I reserve the right to fine-tune the homework assignment up until the beginning of the lecture at the end of which the assignment is formally announced. Thus, if you are working ahead on the daily homework assignments, be sure to verify that you are in sync with the correct assignment right after each lecture.

Show Work

In order to make your work especially readable and easy to follow, you should consider using a mathematical typesetting system such as LaTeX or the latest version of Microsoft Word to prepare your homework. Another alternative is MathType Lite.

Time Limit

The (non-project) homework assignments have been planned to require no more than two hours of concentrated effort per assignment unless the assignment specifies otherwise. Also note that it is in your best interest to finish every assignment to learn the methods and prepare for the exams. Ideally, you will need only two hours of concentrated effort to finish. However, if you run out of time, you may indicate “2 HOUR TIME LIMIT EXPIRED” at the end of the assignment. If you do so, then your assignment score will be computed by scoring the completed problems and adding half credit for each of the untouched problems. Please do not abuse this privilege. In particular, finishing no exercises during the two hours will nullify the two hour privilege on that assignment.

Homework Submission

Homework assignments are due on paper at the beginning of class on the due date specified on the schedule. Late homework is not accepted, not even later during class.

If you would prefer to submit online through Learning Suite, then you must type the assignment and submit your homework as a .pdf before the first section starts (9 a.m.). Doing so may be necessary if you are unable to attend class because of exceptional circumstances known in advance. For homework submitted online, feedback will also be given online via Learning Suite (and not returned on paper).

If an illness or emergency causes you to be unable to complete and submit your homework on time, then correspond with the instructor about other special arrangements.

Sometimes I teach multiple sections of 312 back-to-back, and students decide to attend a different section than the one for which they are registered. Attending another section is fine, as long as you submit your homework at the beginning of whatever section you attend. The goal is to come to class well prepared by doing what it takes to complete the homework before class, whatever section that may be.

Homework problems will be graded using a simple 3/2/1/0 standard:

• 3 points are awarded for a correct answer and complete and clear work.
• 2 points are awarded for either:
• a correct answer and some (but incomplete) work or
• a nearly correct answer and complete work.
• 1 point is awarded for either:
• an answer without work (even if it is correct) or
• a decent try or start.
• 0 points are awarded for no effort or clearly last-ditch effort.

Keys

After an assignment has been submitted, solutions / keys for the homework will be made available online, usually a day or two after the due date for the given assignment. The keys are for your eyes only during this semester and are never to be shared or re-used in a future taking of the class.

Projects

There will be several projects throughout the semester, some of them more challenging than others. In every project, you will have the opportunity to design the conceptual solution to a concrete problem before you write any code; the final project of the semester will require the most effort in terms of design. Only once you have understood the problem and designed the solution should you begin to implement your solution and actually write code.

Whiteboard Problem-solving

You are developing as a problem solver. In this class, you are also learning the importance of solving a problem and analyzing the solution before you start writing code. For each project, you are required to step up to a whiteboard after reading the project instructions but before writing any code. In medical school, they use the learning pattern “learn one, do one, teach one”. Class lectures and reading help with the learning; the homework provides opportunities to actually solve similar problems; and the whiteboard experience is your opportunity to teach / explain the idea.

Use the whiteboard to walk through the solution with a one-person technical audience. The best person for your audience would be a CS 312 classmate. Other pssibilities could be another CS major or another technical person with an eye for detail. Make sure you sketch out and understand how to represent a problem instance (both inputs and outputs) and how to map from inputs to outputs (your algorithm). Simulate simple examples and a non-trivial example or two with your marker. Think out loud. Listen to your audience as he or she poses questions or identifies potential complications. In short, make sure you understand what you are going to do before you write a stitch of code. If two students reciprocate for one another, then each person should take a turn as presenter and as audience member / question asker.

There are whiteboards all over campus. In particular, many of the study rooms in the Lee Library have whiteboards, and there are whiteboard markers that can be checked out at the reference desks in each section of the library.

To recap: the purpose is to get the concept of a working solution out in front of yourself and one other thoughtful person. If you don’t have a solution that appears to work and hold up to scrutiny, then your whiteboard experience is not complete. Don’t code without clear thinking upfront.

Whiteboard Experience Submission

For each whiteboard experience, prepare a simple one-page PDF format report including your name, your net-ID, and the project number. Also include a photo of your “whiteboard experience” with you standing next to your whiteboard designs. The photo is a required element of your whiteboard experience report. Include a caption on the photo listing the elements to be found in the picture on the board. The instructions for each project give additional guidance. Each project's whiteboard experience has a submission deadline on the course schedule in advance of the project report submission due date. Submit via Learning Suite. The reports are due by midnight on the specified due date (see the schedule). Late whiteboard experiences are not accepted, but if you are late you should go through the process anyhow before writing code.

Performance

For some of the projects, your implementation will be required to meet a conservative performance requirement. A reasonable implementation will sail through the performance requirement. You will prepare a typed report according to the instructions for each project. You will explain your design and answer questions posed in the project instructions and sometimes report the results of an empirical analysis of your algorithm. No partial credit will be given for non-working code.

In each project, be sure to always document your algorithm with legible comments in important places in your code that make it obvious to the reader what your solution is doing. This documentation also provides evidence of your comprehension. With the aid of adequate documentation, the correctness of your approach should be easy for the reader (e.g., TA) to verify.

Report Submission

All project reports should be prepared in PDF format and submitted via LearningSuite. The project reports are due by midnight on the specified due date (see the schedule).

There are several ways to produce PDF documents, including the following:

• Microsoft Office 2007 allows you to save a document in PDF format
• OpenOffice can export to PDF
• Recommended: Install a PDF printer (software) in Windows. PDFCreator is one free option. You produce the document in whatever program you would like and then just print it to a PDF file by selecting the appropriate PDFCreator “printer”.
• OIT-managed machines around campus have PDF printers installed already.
• LaTeX is always an option for those willing to take the time to learn it. For Windows, the MiKTeX distribution is recommended.

Help Sessions

It is intended that the project instructions should be self-contained and sufficient. Even so, a help session will accompany each project. Help sessions are available primarily to demonstrate a working implementation of the projects and to answer student questions about the instructions. If you cannot go to a help session and the project instructions document is not meeting your needs, you are certainly welcome to post questions on the Google Group, to meet in office hours with the TAs, or to meet with the instructor to get your questions answered.

Exams

There will be one mid-term exam and a final exam. The mid-term exam will take place in the testing center with a three hour time limit. The mid-term exam will be scheduled to allow for flexibility. The final exam will be held in the classroom on the date specified on the University’s calendar (see the course schedule). As per University policy, no exceptions will be granted to final exam time or location. Plan your travel accordingly.

The only aid you may bring to an exam is one page of notes hand-written or typed by you only for the mid-term or two pages (same restrictions) to the final exam. Since the final exam is comprehensive, one of your pages of notes can be the page you used for the mid-term exam. If the notes are not hand-written or typed by you, you may forfeit the exam or incur a significant point penalty. Copying and pasting other notes, including from the course slides or textbook is an example of “not by you”. You may use both sides of the page. Your notes must be submitted with the exam. You are encouraged to study together in preparation for the exams.

Course Policies

The final grade consists of the following components:

Project #1 3%
Project #2 10%
Project #4 10%
Project #5 10%
Project #6 4%
Project #7 10%
Whiteboard Experiences 3%
Homework 15%
Quizzes 10%
Mid-Term Exam 10%
Final Exam 15%

Note that the Learning Suite gradebook includes a category called “Project Raw Scores”. That category has 0 weight and is there only for internal TA and instructor purposes. Please disregard that section.

The following table shows the guaranteed lowest final grade for any given percentage (i.e., if you earn 93.0% of the possible points above, you will get a final grade no lower than an A). I use three significant digits in course grades. I reserve the right to adjust final grades upward at the end of the semester in order to account for your diligence in the class.

A 93.0
A- 90.0
B+ 87.0
B 83.0
B- 80.0
C+ 77.0
C 73.0
C- 70.0
D+ 67.0
D 63.0
D- 60.0
E 0.0

The University policies on I (Incomplete) grades will be strictly followed.

Early Policy

I encourage early submissions and reward students for staying fully engaged and working ahead in the course. For the project assignments, turning in a project report early (at least by midnight on the date of the lecture prior to the regular deadline) will result in an automatic bonus of up to 1% (absolute) toward the final course grade. See the schedule for early submission deadlines (in blue). The per-project early bonus is recorded in its own column as a binary indicator (a 0 or a 1) in the Learning Suite gradebook. The actual early bonus will consist of the actual score earned on the project divided by 100 and weighted by the project's category weight. All early bonuses will be added to the final grade at the end of the semester.

If part of a project is considered extra credit, then the required part of the project can be handed in early and separately from the extra credit part, thereby making it possible to get the early bonus on the required part. The extra credit part of the project would still be due by the normal due date & time, with late policies applying. There may be no extra credit available in a particular semester.

There is no special early policy for homework assignments (an early homework assignment counts as much as an on-time one).

Late Policy

Homework assignments are not accepted late, as they are meant to help students prepare for the lectures.

Whiteboard experience reports are due by midnight on the specified due date. Whiteboard experience reports are not accepted late, since they are intended to help students get an early start on the projects. If a whiteboard experience due date is missed, students are nonetheless strongly encouraged to complete the whiteboard experience for a project, since problem solving before coding will aid in quicker project completion.

The project reports are due by midnight on the specified due date (see the schedule). Each weekday that is not a University holiday or scheduled mid-term exam day thereafter is considered a late day. To be clear, weekends are not counted as late days.

For project reports, each student has a budget of five penalty-free late days in Fall or Winter semesters. In Spring or Summer terms, the budget is three penalty-free late days. These penalty-free late days can be spent on any project, no questions asked, with the constraint that no more than two days (one in Spring or Summer) from the budget may be used on any single project. Penalty-free late days are consumed greedily. This budget should allow for some flexibility in the schedule, given a student’s other class constraints and unexpected life events. Once the penalty-free late days for an assignment have been spent, each additional late day results in a penalty of 10% (of the total possible) per day, up to 10 days (at which point the penalty is 100%). Each late day ends at midnight. The grading of late work takes lower priority on our grading queue and may not be returned as promptly as work submitted on time.

All late project reports must be submitted by the withdrawal day for the semester. No projects due before the withdrawal day will be accepted after the withdrawal day. Furthermore, any late project reports from the time period after the withdrawal day must be submitted by the last day of instruction for the semester. The University does not permit me to accept any work after the last day of instruction.

Cooperation Policy

Students are welcome (and encouraged!) to discuss the general topics of the class, including details of specific algorithms or methods appearing in the lectures or readings. Use of the Google Group for this purpose is strongly encouraged. Please feel free to post your questions there. The instructor, the TAs, and your classmates are all ready to help. If you want a quicker average response time, the group is the way to go! Furthermore, others benefit from the discussion.

Unless the assignment explicitly states otherwise, all students are expected to do their own work (both homework and projects), write their solutions, write their own code, and submit their own reports. However, collaboration is encouraged in terms of sharing ideas and working out solutions at a conceptual level. You are encouraged to work together in this way and to help one another. If you work with someone else, simply acknowledge that you did so by indicating the person(s) by name on the front page of your work. You are also welcome to post a non-assigned problem to the class's Google group and ask for others to show you how to work it out, but do not ask for outright solutions to assigned problems. For the Google group, there is no need to give acknowledgment. I understand that it is a common resource and is useful to many students. Just acknowledge those with whom you collaborated on an individual basis, including for the whiteboard experience.

Code Reviews

Code reviews are permissible and encouraged. Both the reviewer and the reviewee should have given the project serious effort individually prior to meeting for a review. For example, someone who has not started the project should not code review for someone who is almost done. As always, be sure that before you rely on someone else's idea that you have taken the time to think things through yourself. The experience of working through a solution on your own is an important learning experience and an important part of this class.

Ideally a code-review is a face-to-face experience. To identify problems, it is often more productive for the coder to step up to the whiteboard (or electronic whiteboard) and explain his/her solution before diving into the code. Doing so enables conceptual debugging. Generally, source code files should not be sent to the mailing list / Google group. First-round code reviews should be conducted by a classmate. As noted above, all collaboration with other students must be attributed, so give credit to your reviewer. If you have a stubborn bug that you cannot find with a classmate in the first round, then you may ask a TA to help you with a second-round code review, but only after having attempted with a classmate. Note that TAs are instructed not to put their hands on your keyboard – you are the driver! The instructor is available for third-round code reviews as a last resort.

Third-Party Code Policy

You are required personally to solve the problems in the homework and the assigned projects (e.g., write the pseudo-code yourself). Beyond the conceptual solution, the implementation thereof must also be yours. However, you may use a third-party class for a useful data-type if it and you satisfy the following conditions:

• it supports your solution and does not constitute the solution to the assigned problem
• it is accessible to all
• you explicitly acknowledge the third-party code and explain how to acquire it in your report
• you know and report the worst-case efficiency (as a Big-O or Big-$\Theta$ bound) of each method on the class that you actually use

Appropriate Use of Course Materials

Some course materials are designated as sharable via a Creative Commons license as directly noted on the relevant materials (e.g., course lectures and PowerPoint presentations). All course materials not so designated (e.g., exams and homework keys) are proprietary. Students are prohibited from posting or selling proprietary course materials without the express written permission of the professor teaching this course. To do so is a violation of the Brigham Young University Honor Code.

Preventing Sexual Harassment

Harassment of any kind is inappropriate at BYU.

Title IX of the Education Amendments of 1972 prohibits sex discrimination against any participant in an educational program or activity that receives federal funds. The act is intended to eliminate sex discrimination in education and pertains to admissions, academic and athletic programs, and university-sponsored activities. Title IX also prohibits sexual harassment of students by university employees, other students, and visitors to campus. If you encounter sexual harassment or gender-based discrimination, please talk to your professor; contact the Equal Employment Office at 801-422-5895 or 1-888-238-1062 (24-hours), or http://www.ethicspoint.com; or contact the Honor Code Office at 801-422-2847.

Disabilities

BYU is committed to providing reasonable accommodation to qualified persons with disabilities. If you have any disability that may adversely affect your success in this course, please contact the University Accessibility Center at 801-422-2767. Services deemed appropriate will be coordinated with the student and instructor by that office.

Acknowledgments

Many thanks to Mike Jones, Eric Mercer, and Sean Warnick of BYU CS for many of the materials used in this course. Thanks also to Paul Felt, George Busby, David Wilcox, Aaron Stewart, Everett Morse, Michael Goulding, Cindy Goulding, Earl Greathouse, Kevin Cook, Ty Lewis, Seth Stewart, Dean LeBaron, Thomas Ellsworth, and other past TAs for their significant contributions to the course. Thanks also to Kevin Black for improvements to the homework keys.