Analysis of Algorithms (Summer 2016) 1 Introduction 2 Meetings 3 Projects 4 Turn-In and Grading 4.1 Turn-in 4.1.1 Exercises 4.1.2 Projects 4.2 Exercise Scores 4.3 Project Scores 4.4 Numeric Grade 4.5 Letter Grade 5 Help 6 Readings 7 Software 8 Fine Print

Analysis of Algorithms (Summer 2016)

This class is taught by Jay McCarthy. Call him Jay. Email him at first-name DOT last-name AT gmail DOT com.

We meet in Olsen 109 at 1030-1225 on MWR.

Jay McCarthy’s office hours are MWR 0700-1300 in Olsen 221.

There is a mailing list hosted at Google Groups. Use it to ask non-revealing questions and receive answers, as well as general course announcements. You are responsible for reading the content of this mailing list.

1Introduction

Development of more sophisticated ideas in data type and structure, with an introduction to the connection between data structures and the algorithms they support. Data abstraction. Controlled access structures. Trees, lists, stacks, queues, graphs, arrays, hash tables. Algorithm design strategies such as divide and conquer. Elementary techniques for analysis; asymptotic analysis, recursion equations, estimation methods, elementary combinatorial arguments. Examination of problem areas such as searching and sorting, and the indicated representations and algorithms. The student will use the techniques learned in this course and in previous courses to solve a number of logically complex programming problems using pseudocode, with an emphasis on establishing algorithmic correctness and estimating time and space complexity.

2Meetings

 Day Date Topic Links Exercises 1 05/16 Ch 1: Introduction 2 05/18 Ch 2: Getting Started 2.1-3 (p22), 2.1-4 (p22), 2.2-2 (p29), 2.2-3 (p29), 2.2-4 (p29), 2.3-3 (p39), 2.3-4 (p39), 2-2 (p40) 3 05/19 Ch 3: Growth of Functions code 3.1-1 (pg73), 3.1-2 (pg73), 3.1-3 (pg74), 3.1-7 (pg74), 3.2-1 (pg81), 3.2-8 (pg81), 3-4 (pg83) 4 05/23 Ch 4: Divide-and-Conquer code 4.1-4 (pg95), 4.1-5 (pg96), 4.2-1 (pg103), 4.2-6 (pg104), 4.3-1 (pg108), 4.3-5 (pg108), 4.3-6 (pg108), 4.4-1 (pg113), 4.4-6 (pg114), 4.4-8 (pg114), 4.5-1 (pg117), 4.5-2 (pg118), 4.5-4 (pg118), 4-5 (pg130) 5 05/25 Ch 5: Probabilistic Analysis and Randomized Algorithms 5.1-1 (pg138), 5.2-1 (pg143), 5.2-2 (pg143), 5.2-5 (pg143), 5.3-2 (pg149), 5.3-3 (pg149), 5.3-4 (pg150), 5.4-1 (pg163), 5.4-2 (pg163) 6 05/26 Ch 6: Heapsort code 6.1-1 (pg174), 6.1-3 (pg174), 6.1-5 (pg175), 6.2-1 (pg177), 6.2-3 (pg177), 6.2-6 (pg177), 6.3-2 (pg180), 6.4-2 (pg181), 6.4-3 (pg181), 6.5-4 (pg186), 6.5-5 (pg187), 6.5-9 (pg187), 6-1 (pg187) 7 06/01 Ch 7: Quicksort 7.1-2 (pg195), 7.1-3 (pg195), 7.2-1 (pg199), 7.2-2 (pg199), 7.2-3 (pg199), 7.2-4 (pg199), 7.3-1 (pg201), 7.3-2 (pg201), 7.4-2 (pg205), 7.4-3 (pg205), 7.4-5 (pg206) 8 06/02 (cont) code (cont) 9 06/06 Ch 8: Sorting in Linear Time 8.1-1 (pg214), 8.1-4 (pg215), 8.2-2 (pg217), 8.2-4 (pg218), 8.3-2 (pg221), 8.3-4 (pg221), 8.4-2 (pg225), 8.5-abc (pg228) 10 06/08 Ch 9: Medians and Order Statistics 9.1-1 (pg236), 9.2-1 (pg240), 9.2-4 (pg241), 9.3-1 (pg244), 9.3-5 (pg244), 9.3-8 (pg244), 9-1 (pg245) 11 06/09 Midterm 12 06/13 Ch 11: Hash Tables 11.1-1 (pg276), 11.1-2 (pg276), 11.2-1 (pg282), 11.2-3 (pg282), 11.2-4 (pg282), 11.2-6 (pg282), 11.3-1 (pg289), 11.3-2 (pg290), 11.4-1 (pg298), 11.4-3 (pg298) 13 06/15 Ch 12: Binary Search Trees code 12.1-2 (pg310), 12.1-4 (pg310), 12.2-4 (pg314), 12.2-5 (pg314), 12.3-2 (pg320), 12.3-4 (pg320) 14 06/16 Ch 13.1: Balanced Binary Tree 13.1-1 (pg332), 13.1-3 (pg332), 13.1-4 (pg332), 13.1-5 (pg333), 13.1-6 (pg333), 13.1-7 (pg333) 15 06/20 Ch 15: Dynamic Programming code 15.1-1 (pg390), 15.1-5 (pg391), 15.2-1 (pg399), 15.2-3 (pg399), 15.3-2 (pg410), 15.3-4 (pg411), 15.4-4 (pg417), 15.5-2 (pg425) 16 06/22 (cont) code (cont) 17 06/23 Ch 22: Elementary Graph Algorithms 22.1-1 (pg613), 22.1-6 (pg614), 22.1-8 (pg614), 22.2-1 (pg622), 22.2-4 (pg623), 22.2-7 (pg623), 22.3-1 (pg631), 22.3-8 (pg632), 22.3-11 (pg633), 22.4-4 (pg636), 22.5-1 (pg641) 18 06/27 Ch 23: Minimum Spanning Trees 23.1-1 (pg650), 23.1-3 (pg650), 23.1-10 (pg651), 23.2-1 (pg658), 23.2-2 (pg658), 23.2-4 (pg658) 19 06/29 Ch 24: Single-Source Shortest Paths 24.1-1 (pg675), 24.1-3 (pg675), 24.1-4 (pg675), 24.3-1 (pg683), 24.3-2 (pg684), 24.3-4 (pg684) 20 06/30 Ch 34: NP-Completeness 34.1-1 (pg1081), 34.1-5 (pg1082), 34.2-1 (pg1086), 34.3-1 (pg1098), 34.4-1 (pg1106), 34.5-2 (pg1121) 21 07/06 Final Prep 22 07/07 Final

Jay will not be present on days marked with a * in the Exercises column. Page numbers are for the PDF, subtract 21 to get the page number for the text.

3Projects

 Project Code Out Due Midterm midterm 06/09 Algorithm Experiment the First alg1 05/16 06/09 Final final 07/07 Algorithm Experiment the Second alg2 06/09 07/07

Out dates are suggestions—you may need to start earlier.

This schedule may change.

4.1Turn-in

4.1.1Exercises

You turn in your exercises by putting them on the lectern at the start of class on the day listed. Exercises are typically due the day we will talk about a subject, so it will not be requisite that the work be fully complete and correct, instead you are simply required to have made a diligent effort on each exercise. The idea is that by doing the exercise before class we can more effectively use our time together and discuss the chapter.

No assignments will be accepted after class starts. Each exercise set should clearly have your name on it and the date of the exercises (listed in the lecture table) formatted as mm/dd. I recommend preparing them electronically with LaTeX.

Typically in class, we will be going over the material that the exercises cover, so you should probably keep a copy for yourself. If you prepare them electronically, then you can just give me a print-out. If you prepare them any other way, you’ll have to make yourself a copy.

In any case, you are responsible for my ability to read and understand the paper.

For a (cont) exercise, nothing changes, i.e. turn in the same set of problems a second time.

4.1.2Projects

You should email your projects to me before 6PM Lowell time on the due date listed.

If you send an assignment late (even by a single second), it will not be graded. This is a real due date and due time. Please use this early due time to get a good night’s sleep and enjoy your evenings.

Your email should have [CS404] code as the subject, where code is the code listed on the assignment table. Do not send multiple emails, if you do, I’ll count the oldest one.

Your email should contain one Zip file with your files inside it, such that they extract to a directory with the same name as the code of the assignment. Any non-code documents should be submitted as a PDF. I recommend producing PDFs with LaTeX.

4.2Exercise Scores

As mentioned above, exercise sets will be graded based on diligent effort. I will give you a score of (/ n (* 0.75 m)) where n is the number of diligently attempted exercises and m is the number of assigned exercises. This means you don’t need to do all of them, but you’ll get extra-credit for doing them all. In the end, I will average all these together with no weighting.

4.3Project Scores

Each project’s page describes how it will be graded. All projects will receive a grade from the closed interval between 0 and 1.

I will take your various points and combine them with this function to get a numeric grade:

 > (define (combine exercises alg1 midterm alg2 final) (+ (* 0.2 exercises) (* 0.1 alg1) (* 0.3 midterm) (* 0.1 alg2) (* 0.3 final)))

Examples:
 > (combine 0.0 0.0 0.0 0.0 0.0) 0.0 > (combine 1.0 0.0 0.5 1.0 1.0) 0.75 > (combine 1.0 1.0 1.0 1.0 1.0) 1.0

I will then run the following function to convert it to a letter:
 > (define (convert-to-letter ng) (cond [(> ng 0.93) "A"] [(> ng 0.9) "A-"] [(> ng 0.86) "B+"] [(> ng 0.83) "B"] [(> ng 0.8) "B-"] [(> ng 0.76) "C+"] [(> ng 0.73) "C"] [(> ng 0.7) "C-"] [(> ng 0.66) "D+"] [(> ng 0.6) "D"] [else "F"]))

Examples:
 > (convert-to-letter 1) "A" > (convert-to-letter 0.94) "A" > (convert-to-letter 0.899999) "B+" > (convert-to-letter 0.81) "B-" > (convert-to-letter 0.74) "C" > (convert-to-letter 0.6999999) "D+" > (convert-to-letter 0.62) "D" > (convert-to-letter 0.57) "F"

5Help

If you need a "shallow" amount of help, then look at the Google Group. First, see if I have already answered your question. Then, send your own email.

Only send me personal email if you need to talk about something private, such as your grades. Anything else is best discussed in public, so others can benefit. If you do send personal email, put [CS404] as a prefix in the subject.

If you need a "deep" amount of help, please come to my office or call me (801-361-0732) and we’ll talk and try to resolve whatever ails you.