MA/CSSE473 – Design and Analysis of Algorithms

Summer, 2016 (201640) Schedule Overview updated Tue Aug 16 at 2:21:25 PM

This page will be updated frequently as the term progresses.

Bookmark this page in your browser; you will go here often!
Late Day Balances  Who grades what?


Session quick links:  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

Week Session Preparation HW Due Topics Resources
1

1

Fri Jun 3
  • Summer: In this column, dates do not matter, since there are no synchronous lectures. The items in this column do provide the order in which you should read things. And of course you should read the material before the corresponding homework is due.
  • This page and all documents linked from it are considered "in progress" throughout the term.
  • Read the Syllabus.
    Syllabus has been updated for summer 2016. Pay special attention to the Prerequisites section, including the sample review problems from CSSE 230
  • Instructor introduction video (on Moodle) You have to be logged in to Moodle for this link to work
  • KEY to reading assignments:
    L: = Levitin
    W: = Weiss
    D: = Dasgupta
    Throughout the course, Suggested readings from Weiss (W:) are optional, except for the brief excerpts I have placed on Moodle (one is used in HW02).
  • Dasgupta chapters 0 and 1 are on Moodle. Those are the only chapters of this book that you will need to read. They will be assigned over the next few days.
  • (Ideally do this before the course begins) Review CSSE 230 background material: W: 5 (algorithm analysis), 7.1-7.3 (basics of recursion), 8(sorting algorithms), 16-18 (stacks, queues, linked lists and trees -- including traversals, iterators and height vs. size properties), 19.1-19.4 (BSTs and AVL trees), 20 (hash tables, including collision resolution), 21.1-21.3 (priority queues, binary heaps, and heapsort)
  • Read my document: How to succeed (and have more fun) at 473 homework
     
  • Background Diagnostic Survey on Moodle. Lots of questions to answer, but they are all multiple choice. Summer: Please complete this by the end of the day Sunday, June 5, 2016).
  • Summer: not to be turned in Write the algorithm that is described on the last of the slides from Session 1. Once you get that one, try to write the formula for a Rose-Hulman fall term that begins on a Thursday and has the Thursday-Friday fall break after session 16.
  • Turnins: when and where?
    Homework problems:
    Due at 11:55 PM Indiana time on the due date.
    Electronic submissions only.
    Drop box on Moodle.
    Submit each assignment as a single document,
    preferably less than 5 MB.
    Each assignment has an optional associated survey that you can submit for 5 extra-credit points.

     
  • Summer: Important note on timing
    The summer homework schedule is based around the summer course and holiday calendar. The dates for reading assignments, topics, and slides for given days are based on the last time the course was taught on-campus. You should read the textbook sections and the PowerPoint slides in the order given here, but not necessarily on the days indicated. Sometimes a summer HW due date may be earlier than the "session day" when its material is covered in the slides. So the rule for you is "when working on a homework assignment, read far enough in the textbook and slides to cover the material for the homework questions."
  • Course introduction
  • Introduction to algorithms
  • Algorithm analysis
  • Slides    PDF
    Summer:PDFs are easier to browse to;
    Slides (you must download them) include instructor notes and hidden slides)
     
  • Class notes (Summer:For this and all later Class Notes documents, ignore the announcements; the "Main ideas from today" section will help you to focus some of the things that I considered important
     
  • Video: based on lecture 1 (7 minutes long)
     
  • Solution to problem posed at the end of Lecture 1. Suggestion: Try to solve the problem yourself before viewing this solution.
     
  • All 473 Course materials on the web
1

2

Mon Jun 6
  • L: Chapter 1 (Intro); Sections 2.1 (analysis Framework) 2.2 (Asymptotic notations) ;
    Most of this should be review.
    For more background on Analysis of Algorithms, W: 5.1-5.7
  • L: Appendix A (useful formulas).
    You do not need to memorize these formulas, but you should be aware of the kinds of formulas in this list, so that you will know when you should look at the list.
  • D: Chapter 0. A good treatise on the importance of algorithms. Recall that D stands for "the Dasgupta excerpt on Moodle"
  • D: Sections 1.1 and 1.2. Introduction to Numeric Algorithms.
  • W: Continue reviewing 230 material as needed.
  • Slides and video: If you are not very confident about how to prove that (ordinary and strong) mathematical induction is a valid proof technique and how to use it to do proofs about numbers and about binary trees, be sure to see the slides and video that are the last two items in today's Resources column.
  • HW 1 Due at 11:55 PM. See late days policy in the syllabus
  • HW01 textbook problems and hints

     
  • Note: HW2 is a long assignment. I recommend that you do some of the problems on Monday; if you do this you will spread out your week 1 workload more evenly.
  • Master Theorem review
  • What is an Algorithm?
  • Fibonacci Algorithms and their analysis
  • Integer arithmetic
1

3

Tue Jun 7
  • D: Chapter 1. (in the Dasgupta excerpt that is on Moodle)
  • L: 2.3 This is a review of using summations in algorithm analysis. If you are not confident about this after 230, read this section very carefully.
  • L: Appendix B (solution techniques for recurrence relations). Most should be review of 230/375.
  • W 7.5.3 (unlike other Weiss readings, this one is not optional) This proof of the Master Theorem is a little bit simpler than Levitin's; knowing Weiss's level of detail of the proof is sufficient for this course (this excerpt is under "Reading Materials" on Moodle)
  • L: 2.4 Review of analysis of recursive algorithms.
  • W 7.4-7.4.3 A slightly different approach to some of the material that Dasgupta discusses. (on Moodle)
  • L: 2.5-2.7 Only 2.7 should be new, and it is not technical. W: 7.3.4, 5.7, 5.8 have similar material.
  • CACM interview with Donald Knuth, the most famous (and perhaps most quirky) person in the field of Algorithms.
    (July-August 2008)
  
  • Quick review of big-O and its cousins
  • Fibonacci numbers via Matrix multiplication
  • Analyzing Addition
  • Algorithms for multiplication
1

4

Thu Jun 9
  • L: 3.1-3.3. Most of 3.1 and 3.2 should be review (of Weiss 5.6, and 8.3). Pay special attention to three new problems that are introduced here for the purpose of discussing efficient solutions later: String match, closest pair, convex hull.
  • W: 9.6 Randomized Primality Testing has some of the same material as Dasgupta. (On Moodle)
  • trominoes descussion from Johnsonbaugh algorithms book (on Moodle)
  • HW 2 due date moved to Friday.
     
  • Summer: Last day to use late days and submit HW 1.
  • Multiplication a la Gauss
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
  • Summer: Virtual Office Hours (VOH) Optional 9:00 PM. I'll post the link on Piazza.
     
  • Slides    PDF
  • Class notes
     
  • Video: Induction examples (trominoes, EBT) 11 minutes
2

5

Fri Jun 10
  • L: 3.4. Exhaustive Search. Also introduces some problems for which we will see efficient algorithms later.
     
  • L: 3.5 [5.2 in 2nd ed] Depth-first and breadth-first search. May or may not be review for you, depending on your CSSE 230 class.
     
  • L: 4.1 [5.1] Insertion Sort. Should be review. Also see W: 8.3
     
  • L: 4.4 [4.3] (Binary search part only). Should be review. Also see W: 5.6.2, 7.3.6
  • Review topics not covered in class
  • Factoring and primality (where we are headed)
  • Integer Division algorithm exercise
  • Modular arithmetic intro
  • Slides    PDF
    This is one where you'll probably want to look at the PowerPoint version, because the instructor notes have many details that are not on the slides.
     
  • Class notes
2

6

Mon Jun 13
  • L: 4.2 [5.3] Topological Sort. Probably new for you. Se also W: 14.5.1
  • L: 4.3 [5.4] Permutations and subsets
  • HW 3
  • HW03 textbook problem details
  • Student survey results from a previous term's HW3
     
  • Begin work on the Trominoes implementation problem; due Friday, June 24. You may work alone or with a partner. If you want help in finding a partner, see instructions in the problem specification, and contact me by Friday, June 17.
     
  • Summer: Last day to use late days and submit HW 2.
     
  • Summer: VOH (optional) 9:00 AM.
     
  • Odd Pie Fight
  • More Modular Arithmetic
  • Euclid Algorithm, extended Euclid
2

7

Tue Jun 14
  • L: 4.4 [5.5] Decrease by a constant factor
  • Continue your work on the Trominoes implementation problem; due Friday, June 24.
  • Modular Inverse and Division
  • Primality testing overview
  • Fermat's little theorem
2

8

Thu Jun 16
  • L: 4.5 [5.6] Variable-size decrease algorithms
  • W: Some of the same material form a different perspective:
    • 5.6.3 interpolation search
    • 19.1 BST search and insert
      • <13.1>Josephus problem
  • Summer: Last day to use late days and submit HW 3.
  • Primality testing
  • Fermat test and its likelihood of effectiveness.
  • Carmichael numbers
3

9

Fri Jun 17
  • L: 5.1-5.3 [4.1, 4.2, 4.4] Read this quickly; everything in the chapter introduction and in sections 1-3 should be review of the following sections from Weiss:
  • W: 7.5 (divide-and-conquer, including Master Theorem)
    5.6.2 and 7.3 (binary search, iterative and recursive)
    8.6 (quicksort)
    8.5 (mergesort)
    18.4 (tree traversals)
  • HW 4
  • None of these problems are from the Levitin textbook; all are on the assignment page.
  • Student survey results from a previous term's HW4
  • Summer: VOH (optional) 9:00 PM.
     
  • Miller-Rabin test. Carmichael numbers.
  • Intro to RSA Cryptography (See Dasgupta pages 30-34 or Weiss section 7.4.4)
3

10

Mon Jun 20
  • Summer: VOH (optional) 9:00 AM.
      * Finish RSA Cryptography
3

11

Tue Jun 21
  • Section 5.5 [4.6]
  • W: 7.4.4
  • Dasgupta Chapters 0 and 1, under "Reading Materials" on Moodle, pages 30-43
  • CACM interview with Donald Knuth, the most famous (and perhaps most quirky) person in the field of Algorithms.
    (July-August 2008) Was also assigned for Day 3. If you read it before, refresh your memory.
  • Continue your work on the Trominoes implementation problem; due Friday, June 24.
  • Donald Knuth Interview discussion
  • Amortizatiion and Arraylists
  • Brute Force Algorithms
  • (If time) Decrease and Conquer Intro
3

12

Thu Jun 23
  • Catch up on reading
  • Summer: Last day to use late days and submit HW 5.
     
  • Summer: VOH (optional) 9:00 PM.
     
  • Decrease-and-Conquer Algorithms
  • DFS
  • BFS
  • TopologicalSort
  • (Permutation generation)
4

13

Fri Jun 24
  • Section 6.1. to presort or not to presort, that is the question.
  • Section 6.2. You have probably seen the straightforward approach to Gaussian Elimination before; the LU decomposition approach is probably new.
  • Permutation generation
  • next lexicographic permutation
  • random permutation generation
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
4

14

Mon Jun 27
  • Section 6.3. AVL trees should be review from 230. See also Weiss section 19.4, and 230 AVL tree slides.
  • 2-3 trees are probably new to most students. For additional examples, see here or here
  • Summer: VOH (optional) 9:00 AM.
     
  • Permutation and Subset generation
  • Gray Code
4

15

Tue Jun 28
  • Section 6.4. Heaps and HeapSort. Everything in this section should be review from 230; if not, you should pay special attention to it, because heaps will play a central role in later algorithms. For many more details and examples, see Weiss sections 21.1-21.5.
  • Section 6.5. Horner's Rule and Binary Exponentiation.
  • Section 6.6. Problem reduction. Most of this is new.
  • Summer: Begin thinking about the QuickHull implementation problem.
  • QuickHull is due Friday, July 8 (last day before the break)
  • For background, see the slides from Session 17 and Levitin section 5.5 [4.6]
  • This is an individual assignment.
  • Divide and Conquer
  • Closest Points
4

16

Thu Jun 30
  • Summer 2016: only one exam: the Final. The final exam on August 31 is the only exam for the summer course. It may be worth looking at the specifications and sample exam here as you prepare for that final; that is why I left them in the schedule page.

  • Exam 1 in class. Will cover HW 1-6, readings through Session 11, lectures through Session 14.

  • Exam 1 specification
  • Summer: Last day to use late days and submit HW 6A.
     
  • Summer: VOH (optional) 9:00 PM.
     
  • Not Summer: Exam 1 in class.
  • You may bring one 8.5" x 11" sheet of paper with hand-written notes on one side.
  • A calculator is allowed for doing normal arithmetic calculations.
  • No other electronic devices (laptops, phones, tablets, MP3 players, etc.)
  • Previous Exam 1
    I do not plan to post a solution. I suggest that if you think you have a solution to one of the problems, you should post it on Piazza and let other students give you feedback. There is an "exam" folder that would be appropriate for this.
5

17

Fri Jul 1
  • Section 7.1. Sorting by Counting. The concept should be review, the applications are new.
  • Section 7.2a Horspool's algorithm for string matching. It's one of the trickier parts of the course, and a good warmup for Boyer-Moore.
  • QuickHull
  • Strassen's Matrix Multiplication algorithm
5

18

Mon Jul 4
  • Catch up on reading;
  • Summer: HW 7 is due on Tuesday, since Monday is a holiday.
     
  • Note: Convex Hull implementation is due Day 21. Get started soon if you have not already done so!
     
  • Summer 2016 : Independence day holiday
  
5

19

Tue Jul 5
  • 7.2b Boyer-Moore. A really clever algorithm, but not trivial to understand.
  • Leftover decrease-and-conquer problems (false coin, median-finding)
  • Nim
  • (Josephus introduction)
5

20

Thu Jul 7
  • 7.3 hashing. All of this should be review of 230. Weiss chapter 20 has a much more detailed explanation if this quick explanation is not enough.
  • 7.4 B-trees. Probably new. Weiss also has B-tree explanation and examples in Section 19.8
  
  • Summer: VOH (optional) 9:00 PM.
     
  • Josephus problem
  • Gaussian Elimination and LU-decomposition.
  • Quick Review of AVL trees
6

21

Fri Jul 8

  
  • Summer: Last day to use late days and submit HW 7.
     
  • QuickHull implementation problem. This is an individual assignment.
     
  • Summer 2016:Just in case you prefer to do some "catching up" during the break week, I am giving five "grace days" for this assignment. You can turn it in until Wednesday, July 13 without using any late days. After that you must use late days.
     
  • In order to count as an "early" day, you must submit by Thursday, July 7, the day before the actual due date.
     
  • Note: During the weekdays during the break, I may only be able to respond to email and Piazza posts in the early mornings and early evenings.
  • Review: AVL Tree logarithmic maximum height proof
  • 2-3 trees
6

22

Mon Jul 18
  • Chapter 8 intro and Section 8.1. Binomial coefficients
  • review of binary heaps
  • Heap definition and representation
  • insert and removeMax operations
  • HeapSort
  • BuildHeap
  • Heap Construction Comparisons
  • Miscellaneous transform and conquer algorithms
  • Linear Programming at a Glance
  • Recap: Horner's rule and binary exponentiation
  • Problem Reduction
  • Least Common Multiple
  • Counting Paths in a Graph
6

23

Tue Jul 19
  • Section 8.4 [8.2] Warshall's and Floyd's Algorithms
  • Section 8.3 Optimal Binary Search Tree
  
  • Space/time trade-offs
  • Hashing Review
  • Examples of linear, quadratic probing, rehashing
6

24

Thu Jul 21
  • Section 8.2 [8.4] Knapsack problem
  • Summer: Last day to use late days and submit HW 8.
     
  • Quadratic probing: proof of success if conditions are right.
  • String search: Horspool's Algorithm intro
7

25

Fri Jul 22
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  • String Search: Boyer-Moore Algorithm
7

26

Mon Jul 25
  • Section 9.3-9.4 Dijkstra's Algorithm and Huffman Trees
  • Weiss also has a good discussion of Huffman Trees in Chapter 12
  • No class meeting (Fall, 2014) Instructor is using one of his late days!
  • I have designated B Trees as a "read it on your own and ask questions" topic. Today may be a good day to work on this.
7

27

Tue Jul 26
  • Section 10.1 Simplex method
    
7

28

Thu Jul 28
  • Section 10.2 Maximum Flow
  • Summer: Last day to use late days and submit HW 10.
     
  • B-Trees overview (you are to read and get details on your own)
  • Dynamic Programming
  • (Read the simple examples from 8.1 on your own)
  • Binomial Coefficients
  • Warshall's algorithm
8

29

Fri Jul 29
  • Sections 10.3-10.4 Maximum Matching, Stable Marriage
  • Optimal linked list
  • Optimal Binary Search Tree
8

30

Mon Aug 1
  • Section 11.1 Lower Bound Arguments
  • Optimal BSTs, continued
  • Greedy Algorithms intro
8

31

Tue Aug 2
  • Section 11.2 Decision Trees
  
  • Huffman trees (text compression)
  • Prim, Kruskal intro
8

32

Thu Aug 4
  • Summer: Last day to use late days and submit HW 11B.
     
  • No class today (instructor medical issue)
9

33

Fri Aug 5
  • Section 11.4 Challenges of Numerical Algorithms
  • Prim, Kruskal
9

34

Mon Aug 8
  • Sections 12.1 Backtracking
  • Summer: The final exam is the only exam. It may be worth looking at the specifications and sample exam here as you prepare for the final.

  • Exam 2 in class. Will cover HW 1-13, readings through Session TBA, lectures through Session TBA.

 
9

35

Tue Aug 9
  • Section 12.2 Branch-and-Bound
    
9

36

Thu Aug 11
  • Section 12.3 Approximation Algorithms
  
  • Recap of Kruskal proof
  • Prim detailed algorithms and data structures.
  • Indirect MinHeap implementation
10

37

Fri Aug 12
  • Section 12.4 Nonlinear Equations
  • Kruskal Data Structures, detailed algorithm
  • Disjoint set alternate implementations
10

38

Mon Aug 15
  • Epilogue (pages 465-468)
  • P and NP
10

39

Tue Aug 16

    
  • Finish Dijkstra
  • Review problems
  
10

40

Thu Aug 18

  
  • Complete the Course evaluation on Banner (not required, but I will greatly appreciate it if you do this).
  
11

41

Fri Aug 19