MA/CSSE473 – Design and Analysis of Algorithms

Summer, 2017 (201740) Schedule Overview updated Wed Aug 16 at 11:23:44 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  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 42

Week Session Preparation HW Due Topics Resources
1

1

Thu Jun 1
  • 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 2017. 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 the textbooks 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 of those 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 Saturday, June 3, 2017).
  • 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
    Put the problems into numerical order
      Try to balance readability with reasonable file size
      I will download some of them from places with poor bandwidth.
    Each assignment has an optional associated survey that you can submit for 5 extra-credit points.
    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 everything is legible and nothing got cut off

     
  • Summer: Important note on timing
    The summer homework schedule is based around the summer course and holiday calendar. You can ignore the specific dates listed here for reading assignments, topics, and slides for given days; they 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 or later 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 needed for the homework questions."
  • Course introduction
  • Graphs and their representations
  • Note about graphs: A loop in a graph is an edge form a vertex to itself. A cycle is a path (a sequence of one or more edges) from a vertex to itself. So every loop is a cycle, but not every cycle is a loop. * Introduction to algorithms
  • Algorithm analysis
  • Summer: The topics on this schedule correspond to the PowerPoint Slides from the corresponding day from Winter, 2016-17, the last time I taught this course in the "face to face" version). In this column, dates don't matter much, but the items here will indicate which PowerPoint (and other) documents are likely to be helpful as you prepare for a given HW assignment

  • 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 for that lecture
     
  • Video: based on Day 1 lecture (7 minutes long)
     
  • Solution to problem posed at the end of Lecture 1. Suggestion: Try to solve the problem yourself before viewing this solution.


     
  • Summer: Note that not everything in this column will be purged for the summer online course, so there may be a few things (dated announcements in the slides, for example) that are not relevant to summer.
1

2

Fri Jun 2
  • 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
    This is critical material from 230. If there is anything from Weiss Chapter 5 that is unfamiliar or that you did not internalize well when you took that course, spend some itme on it now.
     
  • 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 this list.
     
  • D: Chapter 0.
     
    A good treatise on the importance of algorithms.
    Recall that D stands for "the Dasgupta excerpt on Moodle"
  • 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 today's Resources column.
     
  • Course Background Survey (on Moodle). It is important that you do this 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. At least begin thinking about HW2 problems very soon.
  • Master Theorem review
  • What is an Algorithm?
  • Fibonacci Algorithms and their analysis
1

3

Mon Jun 5
  • D: Sections 1.1 and 1.2. (in the Dasgupta excerpt that is on Moodle)
     
  • W 7.4-7.4.3 A slightly different approach to some of the material that Dasgupta discusses. (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. When you get to the sectio0n called "smoothness and the Master Theorem", you may find that the mathematics is a bit overwhelming. At that point, you may want to read Weiss Section 7.5 instead. It has a simpler proof with a more detailed explanantion.
     
  • 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 the analysis of recursive algorithms.
     
  • L: 2.5-2.7 Only 2.7 should be new, and that section is 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

Tue Jun 6
  • 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)
  • Analyzing Addition
  • Algorithms for multiplication
  • Multiplication a la Gauss
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
2

5

Thu Jun 8
  • 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
  • Read CACM interview with Donald Knuth, the most famous (and perhaps most quirky) person in the field of Algorithms.
    (July-August 2008)
     
  • A list of review topics that will not covered in class (but you should know) is in the slides
  • 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 from class that are not in the slides themselves.
     
  • Class notes
2

6

Fri Jun 9
  • 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
  • Summer: Last day to use late days and submit HW 1.
     
  • Odd Pie Fight
  • More Modular Arithmetic
  • Euclid Algorithm, extended Euclid
2

7

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

8

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

Thu Jun 15
  • 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)
  • Miller-Rabin test. Carmichael numbers.
  • Intro to RSA Cryptography (See Dasgupta pages 30-34 or Weiss section 7.4.4)
3

10

Fri Jun 16
  • Summer: Sunday is the last day to use late days and submit HW 3.
     
  
3

11

Mon Jun 19
  • Section 5.5 [4.6]
     
  • W: 7.4.4
     
  • If you have not already read them, Dasgupta Chapters 0 and 1, under "Reading Materials" on Moodle, pages 30-43
     
  • If you have not already read it, 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 Jun 20
  • Catch up on reading
  
  • Decrease-and-Conquer Algorithms
  • DFS
  • BFS
  • TopologicalSort
  • (Permutation generation)
4

13

Thu Jun 22
  • 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.
     
  • Summer: Last day to use late days and submit HW 4.
     
  • HW 5
    This assignment has been updated for Summer, 2017.
     
  • HW05 problems from Levitin
     
  • Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 5 survey.
    Note that in that term (Winter 2016-17), problem 9 was a much easier problem; I moved the current #9 here from a later assignment because otherwise it is a long time between looking at the material and doing the homework.
    So you might expect to spend a couple of hours more for HW5 this term (there will be a couple of hours less for HW 6B) than students spent that term.
     
  • Permutation generation
  • next lexicographic permutation
  • random permutation generation
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
4

14

Fri Jun 23
  • 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: Sunday is the last day to use late days and submit HW 5.
     
  
  • No slides today; this was an exam day in winter term 2017
     
  • Summer: In the summer, there will be only oine exam before the final (during the week after the break). Because of the timing, it will cover more than is covered by Exam 1 in the face-to-face versions of the coiurse. But I think these next two links will be helpful as you prepare for that midterm exam.
     
  • 201720 Exam 1 specification
     
  • Previous Term's Exams
    I do not plan to post solutions. 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 a Piazza "exam" folder that would be appropriate for this.
     
4

15

Mon Jun 26
  • 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
  • Towers of Hanoi
  • Permutation and Subset generation
  • Gray Code
4

16

Tue Jun 27
  • 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 2017: there will be only two exams: the midterm (Week 6) and Final (August 30). It may be worth looking at the specifications and sample exam here as you prepare for those exams; 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
  • Solutions: Permutations and Order
  • Divide and Conquer
  • Closest Pair of points
  • Slides     PDF
     
  • Class notes
  • Levitin 3rd Edition description and pseudocode for Closest Pair (it's on Moodle, in the Reading Materials section).
5

17

Thu Jun 29
  • 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.
  • Summer: Last day to use late days and submit HW 6A.
     
  • Summer: Because of the holiday weekend, I delayed the due date for HW 6B until Saturday, so you have the option of catching up during the weekend if you prefer. If you want to have an easier weekend, pretend that it is due on the normal day, which would be today.
     
  • QuickHull
  • QuickHull algorithm for convex Hull
  • Strassen's Matrix Multiplication algorithm
5

18

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

19

Mon Jul 3
  • 7.2b Boyer-Moore. A really clever algorithm, but not trivial to understand.
  • Summer 2017: Independence Day holiday
     
  • Summer 2017: HW 7 is due on Thursday, since Monday and Tuesday are holidays
     
  • At some point you should do the reading and look at the slides for days 19 and 20.
  • Josephus problem
  • Gaussian Elimination and LU-decomposition.
  • Quick Review of AVL trees
5

20

Tue Jul 4
  • 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 2017: Independence day holiday
  • Summer: Last day to use late days and submit HW 6B.
     
  • Finish Josephus problem
  • Transform and Conquer algorithms
6

21

Thu Jul 6

  
  • HW 7
    This assignment has been updated for Summer, 2017.
     
  • HW07 problems from Levitin
     
  • Summer 2017:Just in case you prefer to have an easier week this week and do some "catching up" during the break week, I am giving five "grace days" for this assignment. You can turn it in until 11:55 PM Tuesday, July 11 without using any late days. After that you must use late days.
     
  • In order to count as an "early" day, you must submit by Monday, July 10.
     
  • Drop Box    Survey    Solution
     
  • The numbers from a previous term's HW 7 survey.
     
  • Review: AVL Tree logarithmic maximum height proof
  • 2-3 trees
6

22

Fri Jul 7
  • Chapter 8 intro and Section 8.1. Binomial coefficients
  • Recommendation: If you are not going anywhere for the break, why not go ahead and get HW 8 and part of HW 9 out of the way so you can focus more on exam preparation the following week?
  • This was an exam day in the Winter of 2017, so there is no new material here.
  
6

23

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

Tue Jul 18
  • Section 8.2 [8.4] Knapsack problem
  • Summer 2017: Last day to use late days and submit HW 8. Only one late day may be used due to midterm exam.
     
  • Space/time trade-offs
  • Hashing Review
  • Examples of linear, quadratic probing, rehashing
  • Quadratic probing: proof of success if conditions are right.
7

25

Thu Jul 20
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  • String search: Horspool and Boyer-Moore
7

26

Fri Jul 21
  • 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
  • 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

Mon Jul 24
  • Section 10.1 Simplex method
  • 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

Tue Jul 25
  • Section 10.2 Maximum Flow
  
  • Optimal Static Binary Search Trees
8

29

Thu Jul 27
  • Sections 10.3-10.4 Maximum Matching, Stable Marriage
  • Optimal Static Binary Search Trees (continued)
8

30

Fri Jul 28
  • Section 11.1 Lower Bound Arguments
  • Summer: Sunday is the last day to use late days and submit HW 10.
     
  • Nothing new. This was an exam day in the winter term.
  
8

31

Mon Jul 31
  • Section 11.2 Decision Trees
  • Huffman trees (text compression)
  • Prim, Kruskal intro
8

32

Tue Aug 1

  
  • No class today (instructor medical issue)
  
9

33

Thu Aug 3
  • Section 11.4 Challenges of Numerical Algorithms
  • Summer 2017: Last day to use late days and submit HW 11.
     
  • Summer 2017: Due date for HW 12 postponed until Monday.
     
  • Prim, Kruskal
9

34

Fri Aug 4
  • Sections 12.1 Backtracking
  • Summer: The midterm and final final exam are the only exams. 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

Mon Aug 7
  • Section 12.2 Branch-and-Bound
  
9

36

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

37

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

38

Fri Aug 11
  • Epilogue (pages 465-468)
  
  • P and NP
10

39

Mon Aug 14

  
  • Finish Dijkstra
  • Review problems
  
10

40

Tue Aug 15

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

41

Thu Aug 17

  
  • Summer 2017: You should do these problems and check the solutions sometime before the final exam, but you are not required to submit them.
     
  • HW 15
    This assignment has been updated for Summer, 2017.
     
  • HW 15 problem statements
     
  • Student survey results from a previous term's HW15
     
    
11

42

Fri Aug 18

  
  • Summer 2017: You should do these problems and check the solutions sometime before the final exam, but you are not required to submit them.
     
  • HW 16
    This assignment has been updated for Summer, 2017.
     
  • HW 16 problem statements
  • Summer 2017:Final exam Wednesday, August 30, 9:00-11:00 AM, room G310
  • Final exam specification for Fall, 2017
  • Final exam from Fall, 2014. I do not plan to publish solutions; perhaps students will want to collectively work out solutions to some problems on Piazza. This was 4-hour exam, so it is much longer than yours will be, but you can see severaal probllems that I have given in the past.