05/19: The grades for homework #7, the final exam, and semester
letter grades are all posted now on the
Grades will probably appear on Testudo tomorrow.
I hope everyone has a nice and interesting summer.
05/17: Just a reminder that the TAs and I will be grading with the
goal of having grades posted Tuesday night.
05/15: I have posted an
updated formula sheet.
There might be extra things on it that we don't end up using,
but I wanted to post it now so you might have a chance to look
at it in advance.
05/13: For now, the Thursday and Friday Q&A sessions will be in
the regular TA room - if I hear back on getting a different room, I'll
update the webpage and also post a sign at the TA room.
05/11: The first Q&A session will be on Wednesday from 1:30-3:00
in CSIC 2120. I have reserved that room all day though to give you
a place to study and trade questions on campus if you'd like. I am
currently looking into getting rooms for Q&A sessions on Thursday
and Friday from 1:30-3:00 as well and will post when I know more.
05/04: Homework #7 has been posted.
A new set of thought questions will be posted on Tuesday.
04/30: I have posted Notes Sets #18 and #19. We will continue
on in set #19 on Monday, and start set #20 (to be posted on Monday).
04/29: Notes Set #17 is a recap of graph terminology and a simple
proof of a graph property. Please read these and make sure that it is
04/23: HW #5 will be available at 4:00's Thursday office hours
and at either Q&A session on Friday.
This Friday there will be a Q&A session
at both 11:30 (room CSI 1122) and 2:30 (room CSI 2120).
Also, this Monday, Adam will be available for office hours
from 11:00 until noon in the TA room.
04/22: Here's a link directly to the additional
that I'd added to the list.
04/20: A new
formula sheet draft is posted.
Please let me know by 5pm on April 22nd if you spot a possible typo,
or if there was something that you expected would appear but didn't.
04/20: A good input on which to trace the Counting Sort is
[4,2,8,2,15,3,2,5,13,8,20,15,8]. Something to note about Counting
Sort is that it can be easily modified to sort on a "key" and move
the entire record associated with that key.
04/14: "Homework" #6 is mostly posted
(I will fill in the last question after tomorrow's class). You should
do these as if it were a homework assignment to practice and review
the topics. I will discuss answers in class next Wednesday.
04/09: I've reworded questions 2 and 4 a little in
to remove some ambiguities and fix a typo. Please read the current
version if you had already worked on either of those.
When you are working on the quadrary tree questions, if there are any
constants that come into play, keep those in the equation - I want you
to see what the differences are on runtimes between binary and quadrary
An example input sequence on which to trace the Counting Sort
is: [4,2,8,2,15,3,2,5,13,8,20,15,8]. You should trace through this to
see just how the algorithm uses the counting array and how it does the
04/06: I have posted
homework #5. I suggest you work on it and try
to have it done by Monday April 13th.
has been updated with the adjusted Exam 2 scores. NOTE: Exam scores are
"out of 100" when it comes to working out your grade. The grades server
requires me to set the max as the highest score possible in order for it
to accept those. So, if you scored a 95, that's a "95 out of 100".
04/02: ADVISING REQUEST - Unrelated to our course, but related to
being a CS major, I'd like to encourage everyone to sign up for their
advising slot if they are a CS major, soon. There are plenty of spots
in our schedules now, but from past experiences I can say that things
tend to start to fill up VERY fast, so please don't wait until too
close to your registration date to see one of the advising team here.
03/31: Reminder - the idea of the
is to try to think about how you would hard-code an algorithm
to find the median of a list of five numbers and then test it.
It should have no recursion. The best solution has no loops.
03/31: ADVISING NOTE - CMPS is offering a new two-credit course,
CMPS397, in the Fall. It requires a 3.0 or better GPA. Its title
is "Leadership Development for Computer Scientists" and is worth a
look as you start to plan your Fall schedule. There is a
03/24: Since we did not have a little-o or little-omega question
on the first exam, one of the questions that I am considering is a
little-o or little-omega question on the second exam.
03/14: I have posted some partial solutions to the
recurrence thought questions that I posted earlier to show how
changing the work done "inside" the function does and does not impact
different parts of working through the solution. Remember that these
Big-Omega and Big-O results should always be checked via constructive
induction to make sure that the leaves really aren't a factor to be
working out in detail (we could if we needed to).
03/12: Please read the posted notes for "Randomized Algorithms and
Randomized Median" - they recap things that I said in class and fill in
some additional details about randomized algorithms in general.
03/12: I have posted the questions that I was originally
going to have as HW #4 as
thought questions. I will post
one more on March 23rd (about expected runtimes). I will go over
the solutions to these in class on March 25th and I again *strongly*
recommend that you do them as if they were homework questions since
they will be good practice for the upcoming exam.
03/12: I will not be having my office hours at 3:30 today
but I will be on campus tomorrow if you need to see me before
break starts - just send me e-mail to schedule an appointment.
03/12: Tomorrow's "Friday Session" will be from 2:30-3:45pm
in CSIC 2120 as usual and would be a good time to ask about
more recurrence relations (such as the previously-posted one
where the internal work had an n2 term).
03/11: I will be posting the questions that I was originally
going to have as HW #4 as thought questions (some will be posted
tomorrow, another will be posted on March 23rd). I will go over
the solutions to these in class on March 25th and I would *strongly*
suggest you do them as if they were homework questions since they
will be good practice for the upcoming exam.
03/04: I have updated the office hours for March. Monday and
Wednesday office hours will start at noon. I will be updating them
again once advising starts since the times when I normally advise
are currently listed as 351 office hours for this first part of
03/03: I have
UPDATED HOMEWORK 3 to have one more
question but not be due until March 11th.
03/02: I will return the exam in class on Wednesday, and I will
have a Friday Q&A session
at both 11:30 (room CSI 1122) and 2:30 (room CSI 2120)
03/01: I have posted Homework #3 and
also a related set of
thought questions. We will be making
use of recursion trees this week, so you should start on the thought
questions (and the homework too really) now.
02/26: Reminder - there is no Friday session tomorrow - we will
be grading exams tomorrow. There will be Q&A sessions next Friday.
02/21: I have posted the
formula sheet that will be attached
to Exam 1. There are things on the formula sheet that you will
probably not use but, as I mentioned, I wanted to post this in advance
of actually finishing writing the exam so you would know what things
you would not have to memorize.
02/16: I've posted a slightly more generic version of
the heart of today's constructive induction showing that
T(n)=T(n/2 + a) + n is in O(nlogn) for
any constant a. I stopped when I got to the new goal
at the end where the logk term had to be less than the k term
since we'd really need to know what the constant a was to
proceed to a specific value of k from there.
02/12: I have posted
I will post some new thoughts questions Friday or Saturday as well.
The survey was an even split - 27 students for each time slot.
So, for tomorrow we'll do 2:30-3:45 in CSI 2120.
I'll have to think about what the permanent time will be.
02/10: I have posted a
survey about the Friday sessions time. If you are
interested in the Friday Q&A sessions (held by the TAs most weeks
but sometimes by me) please answer the survey by noon on Thursday.
02/09: The thought questions for between today and Wednesday's
class session are:
(1/5)n2-1000n ∈ &Omega(n2)
n2+50n ∈ &Omega(n2)
02/08: In Homework 1, if you haven't started the problem yet,
assume "Bush" means the most recent President Bush. If you have
already done that problem and assumed the first President Bush,
please state that on your homework sheet.
02/06: As we go through the semester, I'll update a
readings page based on the optional text
but I plan to present everything in class and posted notes.
The text is a way to see a different narrative and some different
examples in certain places. They also go into more detail on
occasion than I will.
Our class has two sections on a Monday/Wednesday pattern - one
that meets from 2:00 until 3:15 and another from 3:30 until 4:45.
Last semester we had a regular Friday sessions at times chosen based
on student feedback and TA availability (one session was from 11-12
and the other from 1:30-2:30). We will work on the time slots for
this semester during the first week of classes.
Whatever we do on Friday will not be required, but would likely be
for Q&A sessions with one of the TAs, or occasionally for an extra
topic not in the official requirements for the course but that I
think is interesting and related to the class topics.
As the beginning of the semester approaches, I wanted to inform you that
we would be trying to schedule something for Fridays and I will discuss
this more at the first class.
There are some questions that you should be able to answer
"yes" to coming into this class.
Do you remember your basic logarithm properties and rules?
Do you remember how to manipulate summations?
Do you remember how to perform basic integration?
Do you remember how to formally prove something using induction?
If you can not currently answer all of these questions with a
confident "yes" then you should review your appropriate course notes
(eg: CMSC 250, MATH 141) so that you can say "yes" by the first
day of class. Take a look at
this "YES" sheet for some examples.
The optional book for this course is:
Introduction to Algorithms (Second Edition) by Thomas H. Cormen, Charles E.
Leiserson, Ronald L. Rivest, Clifford Stein
Available at the University Book Store and Maryland Book Exchange
and many other stores such as online at
Barnes & Noble
(these links are not endorsements of any of these stores).
We will not be using the CD that comes with the version the campus
bookstore says is the only available edition to them, so used copies
or copies you find available online without the CD are fine.