General Announcements

Instructor: Evan Golub - egolub at
Note: Please put "[351]" in the subject line.

  • 05/19: The grades for homework #7, the final exam, and semester letter grades are all posted now on the server. 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/06: I've posted some new thought questions and have updated the posted notes area.

  • 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 all familiar.

  • 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 thought questions 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/19: Piotr sent me the URL for a website with an interesting visual/animated comparison of sorting algorithms.

  • 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 HW #5 to remove some ambiguities and fix a typo. Please read the current version if you had already worked on either of those.

  • 04/08: 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 trees.

  • 04/08: 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 aggregate counts.

  • 04/06: I have posted homework #5. I suggest you work on it and try to have it done by Monday April 13th.

  • 04/06: The server 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.

  • 04/01: I've updated the office hours page with the April hours and exceptions and have posted the puzzle questions.

  • 03/31: Reminder - the idea of the programming project 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 description online.

  • 03/26: I have posted a refresher thought question on little-o.

  • 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/11: I have posted the programming project description.

  • 03/05: I have posted a short example partial trace of the Med3 algorithm.

  • 03/05: Piotr will not be able to be at office hours today (1:30-3:30). I will be in my office until 1:50 and back from class at around 3:20.

  • 03/05: Homework #1 and the "curved" Exam 1 grades have been posted to the server.

  • 03/04: Do "algorithms" belong to the mathematicians or the computer scientists and Operational Research gang?

  • 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 the term.

  • 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) this week.

  • 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/23: Homework 1 points were (4,4,5,7,5). I have posted a partial solution to HW2Q6.

  • 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/18: I've posted a variety of thought questions as well as the new questions for the Friday Session. I'll post partial solutions to the Friday Session questions on Friday afternoon. Also, a reminder that I will not have office hours tomorrow from 12:30-1:30, but Adam will be in the TA room at that time.

  • 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/13: I have now posted some asymptotic relationship questions.

  • 02/12: I have posted Homework #2. I will post some new thoughts questions Friday or Saturday as well.

  • 02/12: 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)    and    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: Some extra thought questions about induction. We did one of these at the Friday session but not the other two.

  • 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.

  • 02/04: I have posted an example solution to the Zero-Point Quiz.

  • 02/03: The office hours have been posted.

  • 02/02: Homework #1 has been posted.

  • 02/02: I will have office hours today (Monday) from 11:30-1:30 and tomorrow (Tuesday) from 12:30-1:30. On Wednesday, regular office hours will start (posted Tuesday night).

  • 01/28: Some math fun showing that 7*13=28

  • 01/28: I will be giving out the password to the notes outlines page in class today.

  • 01/26: I'll be in my office (AVW 1115) on Tuesday and Thursday from 12:30-1:30 and Wednesday from 11:00-1:00 this week.

  • 01/26: I've posted some thought questions.

  • 01/25: I have posted the syllabus.

  • 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. 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
      ISBN: 0-07-013151-1
    Available at the University Book Store and Maryland Book Exchange and many other stores such as online at A1Books and and 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.