MA/CSSE473 – Design and Analysis of Algorithms

Fall, 2014 (201510) Schedule Overview updated Tue Nov 11 at 9:45:14 AM

This page will be updated frequently as the term progresses.

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


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
0

1

Thu Sep 4
  • This page and all documents linked from it are considered "in progress" throughout the term.
  • Read the Syllabus.
    Pay special attention to the Prerequisites section, including the sample problems from CSSE 230
  • 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)
  • How to succeed (and have more fun) at 473 homework
     
  • All HW will be due at 11:55 PM Terre Haute time unless I specify otherwise.
  • Diagnostic Survey on Moodle. Lots of questions, but they are all multiple choice.
  • 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 2 MB.
  • Course introduction
  • Introduction to algorithms
  • Algorithm analysis
0

2

Fri Sep 5
  • 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, (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. It is important that you do this one early in the first week.
  • 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.
  • Master Theorem review
  • What is an Algorithm?
  • Fibonacci Algorithms and their analysis
  • Integer arithmetic
1

3

Mon Sep 8
  • 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.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.
  • Dasgupta Chapter 1, under "Reading Materials" on Moodle, pages 1-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 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)
  • Summer:The number in parentheses after each HW number is the number of grace days allowed for that.
    Fall term: You can ignore those parenthesized numbers for all assignments in the fall course.
  • HW 1 (7) Due at 11:55 PM
  • HW01 textbook problems and hints
  • Quick review of big-O and its cousins
  • Fibonacci numbers via Matrix multiplication
  • Analyzing Addition
  • Algorithms for multiplication
1

4

Tue Sep 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.
  • Dasgupta Chapters 0 and 1, under "Reading Materials" on Moodle, pages 16-30
  • W: 9.6 has some of the same material as Dasgupta. (On Moodle)
  
  • Multiplication a la Gauss
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
1

5

Thu Sep 11
  • 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
1

6

Fri Sep 12
  • 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

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

8

Tue Sep 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
 
  • Primality testing
  • Fermat test and its likelihood of effectiveness.
  • Carmichael numbers
2

9

Thu Sep 18
  • 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 (6)
  • None of these problems are from the Levitin textbook; all are on the assignment page.
  • Student survey results and notes from a previous term HW4
  • Miller-Rabin test
  • Intro to RSA Cryptography
2

10

Fri Sep 19

  
  • Finish RSA Cryptography
3

11

Mon Sep 22
  • 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.
  • Donald Knuth Interview discussion
  • Amortizatiion and Arraylists
  • Brute Force Algorithms
  • (If time) Decrease and Conquer Intro
3

12

Tue Sep 23
  • Catch up on reading
  
  • Decrease-and-Conquer Algorithms
  • DFS
  • BFS
  • TopologicalSort
  • (Permutation generation)
3

13

Thu Sep 25
  • 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.
  • HW6 is now due Monday (and it has 3 new problems). See the extensive explanation on Day 15 in this sachedule.
  • Permutation generation
  • next lexicographic permutation
  • random permutation generation
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
3

14

Fri Sep 26
  • 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
  
  • Permutation and Subset generation
  • Gray Code
4

15

Mon Sep 29
  • 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.
  • HW 6 (7) A substantial assignment!
  • HW06 problems from Levitin
  • Student survey results and notes from a previous term HW6
  • Note that the due date was postponed until Monday and the previuosly-removed problems 9-11 were added back in.
  • No late days may be used for this assignment, since the exam is the next day.
  • History of this assignment: When I modified HW6 for Fall, 2014, I removed the last three problems because I didn't think we would get to the material in class soon enough. (I forgot to remove the "It's a substantial assignment" note). Now I see the same problem with a couple of the problems that I left in the assignment. To make sure that you have some "sink-in" time, I postponed the assignment by four days. Now we should have plenty of time to cover the material for the problems that I originally cut out, so I added them back in. The assignment is again substantial, but you have several additional days to get it done.
  • Student questions on exam topics; may take the entire time.
  • Divide and Conquer
  • Closest Points
4

16

Tue Sep 30

  

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

  • Exam 1 specification
  • 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.
4

17

Thu Oct 2
  • 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
4

18

Fri Oct 3
  • Catch up on reading;
      
5

19

Mon Oct 6
  • 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

Tue Oct 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
  • Josephus problem
  • Gaussian Elimination and LU-decomposition.
  • Quick Review of AVL trees
6

21

Mon Oct 13

  
  • HW 9 (5)
    Due to the break, there is a "grace day" for this assignment. You can turn it in up through Tuesday at 11:55 without using a late day.
    The official due date is still Monday, so if you want to earn an extra late day, you must submit by 11:55 on Sunday.
    At the risk of begin pedantic, I want to say that the grace day takes the place of the traditional late day. It is is not a "postponed due date", it is simply a :"free late day". It is meant to be a buffer for those who could not quite finish by Monday because they need to get questions answered. If you are in that position, you should go ahead and get a good start on HW10 on Tuesday, so that you have plenty of time to complete it by its Thursday due date
  • HW09 problem statements
  • Review: AVL Tree logarithmic maximum height proof
  • 2-3 trees
6

22

Tue Oct 14
  • 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

Thu Oct 16
  • 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

Fri Oct 17
  • Section 8.2 [8.4] Knapsack problem
  
  • Quadratic probing: proof of success if conditions are right.
  • String search: Horspool's Algorithm intro
7

25

Mon Oct 20
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  
  • String Search: Boyer-Moore Algorithm
7

26

Tue Oct 21
  • 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 will be in my office during class time (hours 3 and 4) to assist you with HW 11. I also expect to be in my office hours 6, 8, 10.
  • 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

Thu Oct 23
  • Section 10.1 Simplex method
  • HW 11 (5)
  • This is probably the longest assignment of the course, and it has some difficult problems. Start early. Due date postponed until Friday
  • HW11 problem statements
  • String Search: Knuth-Morris-Pratt algorithm
7

28

Fri Oct 24
  • Section 10.2 Maximum Flow
  
  • Dynamic Programming
  • (Read the simple examples from 8.1 on your own)
  • Binomial Coefficients
  • Warshall's algorithm
8

29

Mon Oct 27
  • Sections 10.3-10.4 Maximum Matching, Stable Marriage
  
  • Optimal linked list
  • Optimal Binary Search Tree
8

30

Tue Oct 28
  • Section 11.1 Lower Bound Arguments
  
  • Optimal BSTs, continued
  • Greedy Algorithms intro
8

31

Thu Oct 30
  • Section 11.2 Decision Trees
  
  • Huffman trees (text compression)
  • Prim, Kruskal intro
8

32

Fri Oct 31
  • No class today (instructor medical issue)
  
9

33

Mon Nov 3
  • Section 11.4 Challenges of Numerical Algorithms
  
  • Prim, Kruskal
9

34

Tue Nov 4
  • Sections 12.1 Backtracking

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

 
9

35

Thu Nov 6
  • Section 12.2 Branch-and-Bound
  
  • No class due to instructor illness
9

36

Fri Nov 7
  • Section 12.3 Approximation Algorithms
  • Recap of Kruskal proof
  • Prim detailed algorithms and data structures.
  • Indirect MinHeap implementation
10

37

Mon Nov 10
  • Section 12.4 Nonlinear Equations
  
  • Kruskal Data Structures, detailed algorithm
  • Disjoint set alternate implementations
10

38

Tue Nov 11
  • Epilogue (pages 465-468)
  • HW 14 (4)
    You may not use a late day for this assignment.
    This is the last assignment that has been updated for Fall, 2014
    On November 7, I removed the problems from Chapter 10.
  • HW 14 problem statements
  • P and NP
10

39

Thu Nov 13

  
  • Finish Dijkstra
  • Review problems
  
10

40

Fri Nov 14

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

41

Mon Nov 17