Syllabus for
Evan Golub's CMSC 351 Sections (0301 and 0401)
Spring 2018
Catalog Description
A systematic study of the complexity of some elementary algorithms related
to sorting, graphs and trees, and combinatorics. Algorithms are analyzed
using mathematical techniques to solve recurrences and summations.
Some Course Goals
Learn and demonstrate the proper use of formal proof techniques
to ascertain and/or verify algorithm asymptotic run-times
(eg: best, worst, expected) as well as using these techniques
to make practical determinations, such as when an input size
might influence the choice of algorithm.
Obtain a thorough grounding in basic algorithms and related data
structures, asymptotic bounds (eg: upper and lower), recurrences,
core graph algorithms (eg: DFS, BFS, MST), core algorithm strategies
(eg: divide & conquer, greedy, dynamic), randomization, reductions, and
an introduction to NP-completeness.
Pre-requisites
Prerequisites: Grades of C- or higher in CMSC216 and CMSC250.
Contact Information
Evan Golub :
1115 AV Williams Building :
egolub (at) glue (dot) umd (dot) edu :
Voicemail 301-405-0180
Telephone is the worst way to try to contact me.
The above e-mail is probably the best
(e-mail sent to addresses other than this one are likely not to be seen).
Office hours will be posted after the semester begins
and should start during the second week of classes.
During the first week of classes, I will be available after lecture
for questions.
Course Website
http://www.cs.umd.edu/class/spring2018/cmsc351-03XX04XX
This website will be divided into sections for posting homework,
projects, examples, etc.
Any official announcements will be posted there.
You may receive e-mail informing you of emergency announcements, but you are
responsible for checking the main class site regularly.
Parts of the site may be password-protected. The password will be given
out in lecture.
We will be making use of the university ELMS system for some things,
but the above CS website is the official home for this course and where
you should regularly check for assignments, etc. in addition to things
announced in lecture.
In-class Technology
Due to the nature of the material, "pen and paper" is seen as the best
technology for taking notes.
Due to this, and the distraction that the use of laptops, tablets, and
phones tend to cause in the classroom, they are not allowed in this class
without specific permission based on accommodations or other requests
in advance.
Recommended Text
There is no required textbook for this course and no assignments will
refer to a textbook.
However, there is a recommended textbook for students who like to
have one; any edition of
Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest (and later with Clifford Stein).
Expected Major Topics (not listed in order of presentation)
Review of induction and introduction to constructive induction,
topics in Calculus such as integration, topics in Probability
such as expected values.
Simple dynamic programming and approximations examples (eg: via
Fibonacci recursive, recursive w/table, approximation formula).
Algorithms and analyses for basic graph algorithms such as DFS, BFS.
Review and extension of asymptotics (eg: Big-O, Omega, Theta).
Recurrences and ways to solve some basic recurrences.
Analysis of algorithms for searching and sorting.
Basic data structures and some related algorithms and analysis of
those algorithms. Examples may come from Lists, BSTs, balanced trees
(eg: AVL, heaps), heaps, and Union-Find problems.
Algorithms for processing b-bit values (such as primality and
linear-approach sorting).
Algorithms and analyses for more advanced graph algorithms such as MST.
Algorithm-design paradigms: examples and patterns such as greedy
algorithms, Divide and Conquer algorithms, and randomized algorithms.
NP-Completeness.
Homework, Practice Problems, Quizzes, Aporés
There will be some form of "at-home" work assigned most weeks
and doing these are an important part of practicing the material.
Some of these will be homework assignments
and have a due date and be graded.
Some of these will be practice/thought problems
and will sometimes have a suggested date for completion but will not be
collected or graded.
Some of these might be ELMS quizzes, potentially
on readings you are asked to do before class time,
and have a due date and be graded.
Homework assignments should be handwritten and
legible. The exams will be handwritten, which
is why we encourage handwritten homework as well.
We will start by trying having these submitted on ELMS, where you
scan or take very clear photos of your answer pages and upload them,
but if there are issues with that, we will return to the traditional
form of handing them in at the start of class time.
Homework assignments are individual work.
You may ask questions of us during office hours but
may not work with other students, past or present
or search online for answers on the homework assignments.
It is suggested that you attempt practice/thought problems
as if they were homework assignments (on your own) but for these
practice/thought problems you are allowed to also ask fellow
students for help and encouraged to discuss solutions in small groups
after everyone in the group has tried the problem.
It is very important that if you do work with others on these that
you also revisit them a few days later on your own to try to make sure you
truly understood them.
We might have an occasional in-class aporé
that will be shuffled and peer-annotated in class as I review the answer.
The aporés should be treated as individual work
and closed-notes/book.
Grading
Exams: 85% (Three Semester Exams - 50%, Final Exam - 35%)
Homework/Quizzes/Programming assignments: 15%
The three semester exams will be held during the regular class period.
The planned date for the first exam will be
Friday, February 16th
(during your lecture period).
The planned date for the second exam will be
Wednesday, March 14th
(during your lecture period).
The planned date for the third exam will be
Friday, April 20th
(during your lecture period).
The cumulative Final Exam will be held on Tuesday, May 15th at 4pm.
(please see me during the first two weeks of class if this
exam date/time presents a conflict).
Grades will be assigned based on the following anticipated ranges.
It should be noted that these ranges may be expanded based on
results obtained during the semester, but they will not be made smaller.
A narrow range in the lower and upper parts of each range will be reserved
for any +/- grades.
Range Grade
90 - 100 A
80 - 89 B
70 - 79 C
60 - 69 D
0 - 59 F
Academic Honesty
All graded assignments and exams must be done individually.
Please visit the webpage of the Student
Honor Council for a detailed explanation of what
constitutes academic dishonesty. Note that it includes not only
cheating, fabrication, and plagiarism, but also includes helping
other students commit acts of academic dishonesty by allowing
them to obtain copies of your work. You are allowed to use the Web
for reference purposes, but you may not copy code from any website
or any other source. In short, all submitted work must be your own.
Cases of academic dishonesty are typically dealt with harshly.
Each such case will be referred to the
University's Office of
Judicial Programs.
If the student is found to be responsible of academic dishonesty,
the typical sanction results in a special grade "XF", indicating
that the course was failed due to academic dishonesty. More serious
instances can result in expulsion from the university. If you have
any doubt as to whether an act of yours might constitute academic
dishonesty, please contact your TA or the course instructor in
advance.
Excused Absence and Academic Accommodations
Any student who needs to be excused for an absence from a single
homework exercise is due as a
result of a medically necessitated absence shall,
within 24 hours of the missed deadline, inform the
instructor of the missed assessment(s) by using email and by using
the "Report Absence" button on the grades server.
The note must contain an
acknowledgment by the student that the information provided is true and
correct. Providing false information to University staff is prohibited
under Part 10(j) of the Code of Student Conduct (V-1.00(B) University of
Maryland Code of Student Conduct) and may result in disciplinary action.
This self-documentation
may not be used for any Major Scheduled Grading Events, defined below,
and it may only be used once during the entire semester.
Any student who needs to be
excused for a prolonged absence
for additional homework assignments, or for a Major
Scheduled Grading Event,
must inform the instructor at the start of this period and then
provide written documentation regarding the illness
from the Health Center or
from an outside health care provider.
This documentation must
verify dates of treatment
and indicate the timeframe that the student was unable to meet academic responsibilities.
In addition, it must contain the
name and phone number of the medical service provider to be used if
verification is needed.
The student should contact the instructor via e-mail at the beginning of the
prolonged period and this documentation must be given to the instructor on
the student's return to classes.
The Major Scheduled Grading Events for this course
are the three semester exams and the final exam.
At the time the instructor is informed about the missed exam,
arrangements can be discussed regarding that Major Scheduled Grading Event.
Due to the nature of the exams, the default arrangement will be to have
the weighted scores on the remaining exams be used in place of the missed exam.
It is also the student's responsibility to inform the
instructor of any intended absences from exams for religious observances
or official University events
by the end of the drop/add period
so that arrangements can be made.
Disability Support Services
Any student eligible for and requesting reasonable academic accommodations
due to a disability is requested to provide, to the instructor in office
hours, a letter of accommodation from the Office of Accessibility and
Disability Services (ADS)
within the first two weeks of the semester and the
arrangements for individual exams must be made with the instructor
at least one week in advance.
University-Wide Items
University-wide
course policy information of course applies
as well.
The Department of Computer
Science takes the student course evaluations very seriously.
Evaluations will usually be open during the last two weeks of the semester.
Students will be able to complete their evaluations at:
www.CourseEvalUM.umd.edu
Copyright Notice
Class materials are copyrighted and may not be reproduced for anything other than for your personal use
without written permission from instructor.
Web Accessibility