CIS 615 Design and Analysis of Algorithms Spring 2007
Monday 4:40-7:10pm Tuttleman 302



The Effort Effect: According to a Stanford psychologist, you'll reach new heights if you learn to embrace the occasional tumble.

Textbooks


Teacher and media critic John Maguire wrote:

I think many kids (speaking of freshmen I have taught) today "understand" that the world is an untrustworthy place, that their own minds are untrustworthy, that they must rely on others to explain things to them and the explanations are wormy with self-interest, and that someone else is in charge of everything that matters, and that the truth is not inside them but "out there" and endlessly evasive.
I suspect that many of my students (even graduate students) feel the same way. No authority (including me) has a monopoly on truth. At the same time, a small dose of self-doubt is good for healthy thought. Learn to check your own work and criticize your own thinking. Master logic and apply it carefully; then you will be able to find the truth inside yourself, and you won't need anyone to tell you when you are right.

Professor Richard Beigel

I am usually reachable at ΡrοfessοrΒ@gmail.cοm. I love to answer questions about homework, my lectures, or the textbook. Office hours are MW 12-2pm but I usually stay a bit later. My office is 408 Wachman. Please email me specific questions. If I don't answer right away, please call my cell phone (609)-203-2000, home phone 610-660-5001, or office phone 215-204-6975. I don't always check my voice messages, so keep calling or send email if there is no answer. I'm here to help.


  • We will go over homework at the beginning of each class. If you don't understand a question or don't know how to start on it, ask for help immediately.

  • Homework Policy

  • Approximate grade breakdown (subject to change)

  • Exams will mainly test your mastery of the techniques learned in class, and to a lesser extent your understanding of the algorithms discussed in class. While it may be a good idea to memorize certain algorithms, memorization alone will not get you many points on the exams.

  • Any form of copying or plagiarism will be dealt with harshly.

  • Topics We will teach fundamental techniques for the design and analysis of algorithms. These include: divide and conquer, memoization (dynamic programming), reduction, randomization, recurrences, amortized analysis, and competitive analysis.


    Possibly Useful links

    February 5, 2007

    February 12, 2007

    February 19, 2007

    March 12, 2007

    Slides on blackboard.temple.edu

    March 19, 2007

    Midterm

    March 26, 2007

    Midterm solutions and slides on blackboard.temple.edu

    April 2, 2007

    Class rescheduled

    April 9, 2007

    Makeup Midterm

    April 16, 2007

    April 19, 2007 7:25 - 9:55 in Tuttleman 305B

    April 23, 2007

  • Homework due April 30, 2007 but April 26 would be a good day to ask questions
    1. Modify the Dynamic Tables algorithm from the book or the slides to triple the table size instead of doubling it when the table is full. What is the amortized cost of an insertion?
    2. Modify the dynamic tables algorithm from the book or the slides to use a heap instead of an ordinary table. What is the amortized cost of an insertion in such a dynamic heap?
    3. Modify the Perfect Hashing algorithm from the book or the slides to use a 1st-level table of size m and 2nd-level tables of size ((ni+1) C 2).
      1. Analyze the time to construct the table and the size of the table constructed by the modified algorithm in terms of m and n.
      2. Choose m so as to minimize the space used.
    4. Let p be a prime number, let b denote any number in {0,...,p-1}, and let x denote an n-tuple (x0,...,xn-1) of numbers in {0,...,p-1}.

      Define hb(x) = (Σxibi) mod p. Prove that for every pair of distinct x and y, the probability that hb(x) = hb(y) is less than n/p when b is chosen at random.

    April 26, 2007 7:25 - 9:55 in Tuttleman 305B

    home | research | textbook | address | photos