MA/CSSE473 – Design and Analysis of Algorithms

Winter, 2016-17 (201720) Schedule Overview updated Mon Apr 3 at 7:30:41 PM

This page will be updated frequently as the term progresses.

Bookmark this page in your browser; you will go here often!
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

Mon Nov 28
  • This page and all documents linked from it are considered "in progress" throughout the term.
  • Read the Syllabus (has been updated for Winter, 2016-17).
    Pay special attention to the Prerequisites section, including the topics and sample problems from CSSE 230
  • KEY to the textbooks in the reading assignments:
    L: = Levitin
    W: = Weiss
    D: = Dasgupta
    Throughout the course, Readings from Weiss (W:) are optional but highly recommended, except for the brief required excerpts I have placed on Moodle (one is used in HW2).
  • Dasgupta chapters 0 and 1 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)
  • How to succeed (and have more fun) at 473 homework
     
  • Background Survey on Moodle. Lots of questions, but they are all multiple choice. Due before the Day 2 class meeting.
  • Suggestion: Go to the course Piazza page and set your email preferences to "real time'
     
  • Turnins: when and where?
    Due at 11:55 PM on the due date.
    Not accepted late.
    Electronic submissions only.
    Drop box on Moodle.
    Submit each assignment as one or two documents.
    Early submissions are appreciated; they will enable grading to be completed earlier.
    Scanners avalable: F217 and Library.
    Rose ID card gets you into F217 any time Moench is open.
    DO NOT WRITE ON BACK OF PAPERS to be scanned or photographed for submission; bleed-through can be a problem.
    Look over scanned document before submitting to ensure that everythiung is legible and nothing got cut off.

     
  • Course introduction
  • Graphs and their representation
  • Introduction to algorithms
  • Algorithm analysis
1

2

Tue Nov 29
  • L: Chapter 1 (Intro); Sections 2.1 (analysis Framework) 2.2 (Asymptotoic 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, pages 1-10 (on Moodle). A good treatise on the importance of 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 linked in this day's Resources column.
  • Background Survey on Moodle.
    Due before today's class meeting.
     
  • Note that HW2 is a long assignment.
    I recommend that you do some of the problems before HW1 is due; if you do this you will spread out your workload more evenly. At least begin thinking about HW2 problems very soon.
  • Questions on the syllabus and course policies.
  • Master Theorem review and examples
  • Fibonacci Algorithms and their analysis
1

3

Thu Dec 1
  • D: Sections 1.1 and 1.2, basic numerical algorithms.
  • 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.2 and 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 (under "Reading Materials" on Moodle)
  • L: 2.4 Review of analysis of recursive algorithms.
  • D: Chapter 1 on Moodle, pages 11-15
  • 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 that section s not technical. W: 7.3.4, 5.7, 5.8 have similar material.
  • Quick review of big-O and its cousins
  • Fibonacci numbers via Matrix multiplication
1

4

Fri Dec 2
  • 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.
  • D: Chapter 1 on Moodle, pages 16-30
  • W: 9.6 has some of the same material as Dasgupta. (On Moodle)
  • Trominoes discussion by Jonsonbaugh (on Moodle).
  
  • Analyzing addition
  • Algorithms for multiplication
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
2

5

Mon Dec 5
  • 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 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
2

6

Tue Dec 6
  • 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
  
  • Odd Pie Fight
  • More Modular Arithmetic
  • Euclid Algorithm, extended Euclid
2

7

Thu Dec 8
  • L: 4.4 [5.5] Decrease by a constant factor
  • Modular Inverse and Division
  • Primality testing
  • Fermat's little theorem
2

8

Fri Dec 9
  • 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
 
  • Primality testing
  • Fermat test and its likelihood of effectiveness.
  • Carmichael numbers
3

9

Mon Dec 12
  • 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.
  • Quiz
  • Miller-Rabin test
3

10

Tue Dec 13

  
  • RSA Cryptography
3

11

Thu Dec 15
  • Section 5.5 [4.6]
  • W: 7.4.4
  • CACM interview with Donald Knuth, the most famous (and perhaps most quirky) person in the field of Algorithms.
    (CACM July-August 2008)
  • Donald Knuth Interview discussion
  • Amortizatiion and Arraylists
  • Brute Force Algorithms
  • (If time) Decrease and Conquer Intro
3

12

Fri Dec 16
  • Catch up on reading
  
  • Decrease-and-Conquer Algorithms
  • Interpolation Search
  • DFS
  • BFS
  • Topological Sort
  • (Permutation generation)
4

13

Mon Dec 19
  • 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.
  • HW 6A
  • HW6A problems from Levitin
     
  • Because of the exam and the break, I am giving "grace days" for this sassignment, you may submit HW6a for credit until 11:55 PM on Monday, Dec 26.
    I recommend that you do as much of it as you can before you leave for break.
  • Permutation generation
  • next lexicographic permutation
  • random permutation generation
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
4

14

Tue Dec 20
  • 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

  • Exam 1 in class.

  • A calculator is allowed for doing normal arithmetic calculations (but probably will not be necessary).
  • No other electronic devices (laptops, phones, tablets, MP3 players, etc.)
4

15

Thu Jan 5
  • Review binary-reflected Gray code and its relationship to subset generation, for example in
    • Levitin pages 146-148 [180 - 181]
    • Grimaldi example 3 (pages 121-123)
    • Wikipedia Gray Code article
    • First page of this article
    You will need this for HW 7
  • Permutation and Subset generation
  • Gray Code
4

16

Fri Jan 6
  • 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.
  
  • Solutions: Permutations and Order
  • Divide and Conquer
  • Closest Pair of points
5

17

Mon Jan 9
  • 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 algorithm for convex Hull
  • Strassen's Matrix Multiplication algorithm
5

18

Tue Jan 10
  • Catch up on reading;
  
  • Finish Shell's Sort discussion
  • Leftover decrease-and-conquer problems (false coin, median-finding)
  • Nim
  • (Josephus introduction)
5

19

Thu Jan 12
  • 7.2b Boyer-Moore. A really clever algorithm, but not trivial to understand.
  • Josephus problem
  • Gaussian Elimination and LU-decomposition.
  • Quick Review of AVL trees
5

20

Fri Jan 13
  • 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
  
  • Finish Josephus problem
  • Transform and COnquer algorithms
6

21

Mon Jan 16

  
  • Review: AVL Tree logarithmic maximum height proof
  • 2-3 trees
6

22

Tue Jan 17
  • Chapter 8 intro and Section 8.1. Binomial coefficients

  • Exam 2 in class.

  • Change to Exam resource allowed: Details in Day19 announcements
  • Download and try this page before Monday's class, so that if it does not work for you, there is time to do something about it.
6

23

Thu Jan 19
  • Section 8.4 [8.2] Warshall's and Floyd's Algorithms
  • Section 8.3 Optimal Binary Search Tree
  • review of binary heaps
  • Heap definition and representation
  • insert and removeMax operations
  • HeapSort
  • BuildHeap
  • Heap Construction Comparisons
  • Recap: Horner's rule and binary exponentiation
  • Problem Reduction
  • Least Common Multiple
  • Counting Paths in a Graph
6

24

Fri Jan 20
  • Section 8.2 [8.4] Knapsack problem
  
  • Space/time trade-offs
  • Hashing Review
  • Examples of linear, quadratic probing, rehashing
  • Quadratic probing: proof of success if conditions are right.
7

25

Mon Jan 23
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  • String search: Horspool and Boyer-Moore
7

26

Tue Jan 24
  • Section 9.3-9.4 Dijkstra's Algorithm and Huffman Trees
  • Weiss also has a good discussion of Huffman Trees in Chapter 12
  
  • Finish string search
  • B-trees
7

27

Thu Jan 26
  • Section 10.1 Simplex method
  • Since there is no assignment due Monday (Day 29), I moved the due date for HW 11 from Thursday to Friday
  • Dynamic Programming intro (Read the simple examples from 8.1 on your own)
  • Binomial Coefficients
  • Warshall's algorithm
  • Optimal linked list
  • Optimal Static Binary Search Tree intro
7

28

Fri Jan 27
  • Section 10.2 Maximum Flow
  • Optimal Static Binary Search Trees
8

29

Mon Jan 30

    
  • Optimal Static Binary Search Trees
8

30

Tue Jan 31
  • Section 11.1 Lower Bound Arguments

  • Exam 3 in class.

  • Note that there are no old Exam #3's online because this course has never before had a third exam. Some of the problems from the old Exam #2's will be relevant to this exam.
8

31

Thu Feb 2
  • Section 11.2 Decision Trees
  
  • No class due to instructor's illness.
8

32

Fri Feb 3

  
  • Once again, no class due to instructor illness.
  • I have made preliminary sdjustments to the schedule as a result;
  • Further adjustments may be necessary.
  • Adjustments include delaying assignments and removing A16 from assignments that are required to be turned in.
  
9

33

Mon Feb 6
  • Section 11.4 Challenges of Numerical Algorithms
  • HW 12 On 1/31/2017, I removed problems 1, 2, and 10. The remaining problems have been renumberd to be 1-7.
  • HW 12 problem statements
     
  • Previous 473 students have said that #4 is quite difficult.
  
9

34

Tue Feb 7
  • Sections 12.1 Backtracking
    
9

35

Thu Feb 9
  • Section 12.2 Branch-and-Bound
  
  • We are going to move on to Greedy algorithms today. We may come back and do some more Dynamic Programming algorithms later if there is time.
  • Greedy Algorithms intro
  • Huffman trees (text compression)
  • (Prim, Kruskal intro)
9

36

Fri Feb 10
  • Section 12.3 Approximation Algorithms
  
  • Prim, Kruskal continued
  • Kruskal data structures
  • Disjoint sets
  • Union/find
10

37

Mon Feb 13
  • Section 12.4 Nonlinear Equations
  • Kruskal data structures (union/find)
10

38

Tue Feb 14
  • Epilogue (pages 465-468)
  
  • Intro to computational complexity
  • P and NP
10

39

Thu Feb 16

  
  • Randomized algorithms, Skip Lists
  • Backtracking
10

40

Fri Feb 17

  
  • Complete the Course evaluation on Banner (not required, but I will greatly appreciate it if you do this). At a class meeting week 10 , I will describe the benefit if 90% of the members of a section complete it.
  • These assignments will not be turned in, because there is not enough time to get them graded before the final exam. You should be sure that you can do them before the final exam, but you do not have to write them up carefully. As we get close to the end of the course, I will talk about which ones will actually be relevant to the exam.
  • HW 15
  • HW 15 problem statements
  • HW 16
  • HW 16 problem statements
  • HW 17
    Not to be turned in. These will be practice problems for the final exam.
11

41

Mon Feb 20

    
  • Final exam Tuesday Feb 21, 6:00-10:00 PM E-104. Assigned seats.