MA/CSSE473 – Design and Analysis of Algorithms

Summer, 2015 (201540) Schedule Overview updated Thu Aug 13 at 9:18:52 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


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 Jun 8
  • This page and all documents linked from it are considered "in progress" throughout the term.
  • Read the Syllabus.
    Syllabus has been updated for summer 2015. Pay special attention to the Prerequisites section, including the sample problems from CSSE 230
  • Instructor introduction video (on Moodle) You have to be logged in to Moodle before this link will 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)
  • 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.
  • 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 do it for a Rose-Hulman fall term that begins on Thursday and has the Thursday-Friday fall break after session 16.
  • 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 5 MB.
  • Course introduction
  • Introduction to algorithms
  • Algorithm analysis
1

2

Tue Jun 9
  • 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 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

Thu Jun 11
  • 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.
  • 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)
  • Quick review of big-O and its cousins
  • Fibonacci numbers via Matrix multiplication
  • Analyzing Addition
  • Algorithms for multiplication
  • Slides PDF
  • Class notes
  • (on Moodle) VIDEO: Solutions to most of the nine "discover asymptotic relationships by computing limit of a ratio" problems from today's slides
  • In-class code
1

4

Fri Jun 12
  • 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 has some of the same material as Dasgupta. (On Moodle)
  
  • Multiplication a la Gauss
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
2

5

Mon Jun 15
  • 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 Jun 16
  • 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
  • Begin work on the Trominoes implementation problem; due Friday, June 26. 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 Wednesday, June 17.
  • Odd Pie Fight
  • More Modular Arithmetic
  • Euclid Algorithm, extended Euclid
2

7

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

8

Fri Jun 19
  • 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
  • Continue your work on the Trominoes implementation problem; due Friday, June 26.
  • Primality testing
  • Fermat test and its likelihood of effectiveness.
  • Carmichael numbers
3

9

Mon Jun 22
  • 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 and notes from a previous term HW4
  • Miller-Rabin test
  • Intro to RSA Cryptography (See Dasgupta pages 30-34 or Weiss section 7.4.4)
3

10

Tue Jun 23
  • Continue your work on the Trominoes implementation problem; due Friday, June 26.
  • Finish RSA Cryptography
3

11

Thu Jun 25
  • 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

Fri Jun 26
  • Catch up on reading
  • Trominoes implementation problem; due Friday, June 26. Regular late days rules apply.
  • Decrease-and-Conquer Algorithms
  • DFS
  • BFS
  • TopologicalSort
  • (Permutation generation)
4

13

Mon Jun 29
  • 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.
  • Important note for Summer, 2013 HW 6 is a very substantial assignment. It would have been due middle of this week. Because of the July 4 holiday and because I will have limited internet access June 28-July 5, I am postponing the HW6 due date until Monday, July 6.

    But you need to keep going in this course even in my absence. I recommend you do all that you can on this assignment by Tuesday, June 30, then get ahead on reading and do some of HW 7 during the rest of this week. During the weekend, finish all of HW7 that you can, and get going on HW8, which will be due on Friday, July 10.
  • Summer summary: Only three assignments are due during weeks 4 and 5 of this course. To make sure you have time to ask me questions after I return form my trip and before HW6 is due, all three assignments are officiially due during week 5. It is important that you get a lot of the work on these assignments done during week 4, so that week 5 does not become impossibly busy for you. This can also be an opportiunity to earn extra late days.
  • Permutation generation
  • next lexicographic permutation
  • random permutation generation
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
4

14

Tue Jun 30
  • 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, 2015: Begin thinking about the QuickHull implementation problem. Due July 30. Details here. This problem's description has been updated for summer, 2015.
  • Permutation and Subset generation
  • Gray Code
  
4

15

Thu Jul 2
  • 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.
  • Were you expecting an assignment due today?Due to instructor's special circumstances (explained on Piazza), there are three assignments due weeks 4 and 5, and all of them are due during week 5.
  • Student questions on exam topics; may take the entire time.
  • Divide and Conquer
  • Closest Points
4

16

Fri Jul 3

  
  • Summer 2015: only one exam: the Final The final exam on September 2 is the only exam for the summer course. It may be worth looking at the specifications and sample exam here as you prepare for the final.

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

17

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

Tue Jul 7
  • Catch up on reading;
    
5

19

Thu Jul 9
  • 7.2b Boyer-Moore. A really clever algorithm, but not trivial to understand.
  • A reminder that the COnvex Hull implementation problem is due three weeks fomr this date.
  • Leftover decrease-and-conquer problems (false coin, median-finding)
  • Nim
  • (Josephus introduction)
5

20

Fri Jul 10
  • 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
  • HW 8
  • HW08 problems from Levitin
  • Summer 2015:Just in case you prefer to do some "catching up" during the break week, I am giving four "grace days" for this assignment. You can turn it in until Tuesday, July 14 without using any late days. In order to count as an "early" day, you must submit by Thursday, July 9, the day before the actual due date.
  • Josephus problem
  • Gaussian Elimination and LU-decomposition.
  • Quick Review of AVL trees
6

21

Mon Jul 20

  
  • 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. In order to count as an "early" day, you must submit by Sunday, July 19, the day before the actual due date.
    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. If you submit on Wednesday or Thursday, you will use two or three late days.
    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 of the break. If you are in that position, you should go ahead and get a good start on HW10 (a non-trivial assignment) 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 Jul 21
  • Chapter 8 intro and Section 8.1. Binomial coefficients
  • A reminder that the Convex Hull implementation problem is due in nine days.
  • 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 Jul 23
  • 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 Jul 24
  • 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 Jul 27
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  
  • String Search: Boyer-Moore Algorithm
7

26

Tue Jul 28
  • 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 Jul 30
  • Section 10.1 Simplex method
  • String Search: Knuth-Morris-Pratt algorithm
7

28

Fri Jul 31
  • 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 Aug 3
  • Sections 10.3-10.4 Maximum Matching, Stable Marriage
  
  • Optimal linked list
  • Optimal Binary Search Tree
8

30

Tue Aug 4
  • Section 11.1 Lower Bound Arguments
  • Optimal BSTs, continued
  • Greedy Algorithms intro
8

31

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

32

Fri Aug 7

  
  • No class today (instructor medical issue)
9

33

Mon Aug 10
  • Section 11.4 Challenges of Numerical Algorithms
  • Prim, Kruskal
9

34

Tue Aug 11
  • 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

Thu Aug 13
  • Section 12.2 Branch-and-Bound
  • No class due to instructor illness
9

36

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

37

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

38

Tue Aug 18
  • Epilogue (pages 465-468)
  • P and NP
10

39

Thu Aug 20

  
  • Finish Dijkstra
  • Review problems
  
10

40

Fri Aug 21

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

41

Mon Aug 24