MA/CSSE473 – Design and Analysis of Algorithms

Summer, 2012 (201240) Schedule Overview updated Wed Aug 1 at 12:20:06 AM

Link to All non-ANGEL web pages for the course

The schedule and assignments initially posted here are mostly those from a previous term;
   this page will be updated as we proceed through the term.

Bookmark this page in your browser, so you don't have to go through ANGEL every time you want to get to it.


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

Week Session Preparation HW Due Topics Resources
1

1

Mon Jun 4

Details
  • 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
    Suggested readings from Weiss (W:) are optional, except for the brief excerpt on ANGEL that is used in HW02.
  • Weiss reading assignments are always optional.
  • Dasgupta chapters 0 and 1 are on ANGEL. Those are the only sections of those books that you will need to read. They will be assigned over the next few days.
  • Review CSSE 230 background material: W: 5, 7.1-7.3, 8, 16-18, 19.1-19.4, 20, 21.1-21.3
  • All HW will be due at 11:55 PM Eastern Daylight Time unless I specifiy otherwise.
  • Summer: The number in parentheses after an assignment number is the number of grace days allowed (see the syllabus for an explanation). These numbers will get smaller as the course progresses. (I leave more leeway at the beginning of the summer in case something delays your start of the course).
  • Course introduction
  • Introduction to algorithms
  • Algorithm analysis
  • Summer: The topics on this schedule correspond to the PowerPoint Slides from the corresponding day from Fall, 2010-11. In this column, dates don't matter much, but the items here will indicate which PowerPoint documents are likely to be helpful for a given HW assignment

  • Slides
  • Course materials on the web
  • * Summer: Note that not everything in this column will be updated for the summer online course, so there may be a few things (dated announcements in the slides, for example) that are hot relevant.
  • Summer: I will post some of the in-class quizzes and solutions from Fall 2010. I recommend that you read the PowerPoint slides and notes, try to answer the quiz questions, and then look up the answers.
  • Summer: In-class Quiz 01
  • Summer: ICQ 01 solution
1

2

Tue Jun 5

Details
  • L: Chapter 1; Sections 2.1 2.2;
    Most of this should be review.
    For rmore background on Analaysis of Algorithms, W: 5.1-5.7
  • L: Appendix A.
    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 to look at the list.
  • D: Chapter 0, (on ANGEL). A good treatise on the importance of algorithms.
  • W: Continue reviewing 230 material as needed.
  • Slides: If you are not very confidnet about hoe 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 that are linked in this day's Resources column.
  • Background Survey on ANGEL. (0) It is important that you do this one early
  • Master Theorem review
  • What is an Algorithm?
  • Fibonacci Algorithms and their analysis
  • Integer arithmetic
1

3

Thu Jun 7

Details
  • 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 (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 ANGEL)
  • L: 2.4 Review of analysis of recursive algorithms.
  • Dasgupta Chapter 1, under "Reading Materials" on ANGEL, pages 1-15
  • W 7.4-7.4.3 A slightly different approach to some of the matrerial that Dasgupta discusses. (on ANGEL)
  • 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:Number in parentheses is the number of grace days allowed for this assignment.
    Details of how grace days work are in the syllabus.
  • HW 1 (7)
  • In case you don't have the book yet,
    HW01 textbook problems and hints
  • Quick review of big-Oh and its cousins
  • Fibonacci numbers via Matrix multiplication
  • Analyzing Addition
  • Algorithms for multiplication
1

4

Fri Jun 8

Details
  • 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 ANGEL, pages 16-30
  • W: 9.6 has some of the same material as Dasgupta. (On ANGEL)
  
  • Multiplication a la Gauss
  • Induction Examples
  • Trominoes
  • Extended Binary Trees property
2

5

Mon Jun 11

Details
  • L: 3.4. Also introduces some problems that will be considered in detail later
  • L: 3.5 Depth-first and breadth-first search. May or may not be review for you, depending on your 230 class.
  • L: 4.1 Insertion Sort. Should be review. Also see W: 8.3
  • L: 4.4 (Binary search part only). Should be review. Also see W: 5.6.2, 7.3.6
  • NO CLASS TODAY (Fall, 2010)
2

6

Tue Jun 12

Details
  • L: 4.2 Topological Sort. Probably new for you. Se also W: 14.5.1
  • L: 4.3 Permutations and subsets
  
  • Revisit Fibonacci runtimes
  • Integer Division
  • Modular Arithmetic
  • Modular Exponentiation
  • Odd Pie Fight
2

7

Thu Jun 14

Details
  • L: 4.4 Decrease by a constant factor
  • Odd Pie Fight
  • Structural Induction
  • Modular exponentiation
  • Euclid's Algorithm for gcd
2

8

Fri Jun 15

Details
  • L: 4.5 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
 
  • Extended Euclid Algorithm
  • Modular Inverse and Division
  • Primality testing
3

9

Mon Jun 18

Details
  • L: 5.1-5.3   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.
  • Fermat's Little Theorem
  • Primality testing
3

10

Tue Jun 19

Details
  • L: 5.4, L: 5.5 Four very important divide-and-conquer examples:
    integer multiplication, matrix multiplication, closest pair, convex hull.
  • Sections 5.3-5.4
  • Wikipedia article on Miller-Rabin test
  
  • List some review topics from the textbook
  • Fermat's Little Theorem: Proof
  • More Primality testing
3

11

Thu Jun 21

Details
  • Sections 5.5 and 5.6
  • W: 7.4.4
  • Dasgupta Chapters 0 and 1, under "Reading Materials" on ANGEL, pages 30-43
  • RSA Cryptosystem
3

12

Fri Jun 22

Details
  • Catch up on reading
  
  • Donald Knuth Interview
  • Brute Force Algorithms
  • Amortizatiion and Arraylists
4

13

Mon Jun 25

Details
  • 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 probebly new.
  
  • Brute Force Algorithms (continued)
  • Divide and Conquer
  • Closest Points
  • QuickHull
4

14

Tue Jun 26

Details
  • Section 6.3. AVL trees are review form 230. See also Weiss section 19.4, and 230 day 13 and 14 slides.
  • 2-3 trees are probably new to most students. For additional examples, see here or here
  • Strassen's Matrix Multiplication algorithm
  • Decrease-and-Conquer Algorithms
  • DFS
4

15

Thu Jun 28

Details
  • Section 6.4. 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.
  • DFS summary
  • BFS
  • Topological Sort
  • Permutation generation
4

16

Fri Jun 29

Details
  • Section 6.5. All of this is probably new to most students.
  • Permutation generation
  • Trotter-Johnson generation
  • lexicographic generation
5

17

Mon Jul 2

Details
  • Section 6.6. Most of this is new.
  
  • More permutations
  • next lexicographic permutation
  • random permutation generation
5

18

Tue Jul 3

Details
  • 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.
  • Find (lexicographic) sequence number of a permutation.
  • Find permutation from sequence number
  • Subsets of a set.
5

19

Mon Jul 9

Details
  • 7.2b Boyer-Moore. A really cleaver algorithm, but not trivial to understand/
    
5

20

Tue Jul 10

Details
  • 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
  • Lexicographic Permutation Generation
  • Subset Generation
  • Gray Codes
  • Textbook and a page of notes
6

21

Thu Jul 12

Details 		   
  • Generating All subsets of a set.
6

22

Fri Jul 13

Details
  • Chapter 8 intro and Section 8.1. Binomial coefficients
  • HW 10 (4)
    Summer, 2012 grace days extend until Thursday, July 19. This will put a little bit of a crunch on later assignments, but allow more time for exam prep.
  • HW10 problem statements
  • Gray Codes
  • Interpolation Search
  • Quick Select
  • Fake Coin problem
6

23

Mon Jul 16

Details
  • Section 8.2. Warshall's and FLoyd's Algorithms
  • Section 8.3 Optimal Binary Search Tree
  
  • Transform and conquer:
  • Pre-sorting (3 qpplications)
  • Gaussian Elimination (3 applications)
  • Balanced trees
6

24

Tue Jul 17

Details
  • Section 8.4. Knapsack problem
  • Also carefully re-read the two paragraphs at the bottom of page 260 and all of p261. At the beginning of this day's class, you will be asked to construct a good-suffix table for a pattern.
  
  • Finish AVL trees
  • 2-3 trees
  • Heap definition and representation
  • insert and removeMax operations
  • HeapSort
  • BuildHeap
7

25

Thu Jul 19

Details
  • Sections 9.1-9.2 Prim's and Kruskal's Algorithms, Disjoint Subsets and Union-Find
  
  • Heap C0nstruction Comparisons
  • Horner's Rule
  • Linear Programming at a GlLance
  • Problem reductions
  • Space-Time tradeoff examples
  • Efficient String Search Intro
7

26

Fri Jul 20

Details
  • Section 9.3-9.4 Dijkstra's Algorithm and Huffman Trees
  • Weiss also has a good discussion of Huffman Trees oin Chapter 12
  • Horspool's Algorithm
  • Boyer-Moore
7

27

Mon Jul 23

Details
  • Section 10.1
  
  • Boyer-Moore wrapup
  • Review of Hashing algorithms and analysis
7

28

Tue Jul 24

Details
  • Section 10.2
  • Summer Exam
    Wednesday, 8:30-10:30 PM EDT
    Will include material covered by HW01-HW10, not HW 11.
  • Hashing
  • B-trees
  • Dynamic Programming
8

29

Thu Jul 26

Details
  • Sections 10.3-10.4
8

30

Fri Jul 27

Details
  • Section 11.1
  
  • Optimal Lists
  • Optimal BSTs intro
8

31

Mon Jul 30

Details
  • Section 11.2
  • Optimal BSTs
8

32

Tue Jul 31

Details 		 
  • No Class (work on take-home exam) not in summer
  • Take-home exam available by 10 AM. not in summer
  • None
9

33

Thu Aug 2

Details
  • Section 11.4
  • Optimal BSTs
9

34

Fri Aug 3

Details
  • Sections 12.1
  
  • No class due to death in Claude's family
  • More on Prim, Kruskal
9

35

Mon Aug 6

Details
  • Section 12.2
  
  • Greedy Algorithms
  • Huffman trees (text compression)
9

36

Tue Aug 7

Details
  • Section 12.3
  • Prim, Kruskal intro
  • Lemma needed for Krukal proof
10

37

Thu Aug 9

Details
  • Section 12.4
  
  • Kruskal proof
  • Prim data structures and detailed algorithm
10

38

Fri Aug 10

Details
  • Epilogue (pages 465-468)
  • MinHeap implementation
  • Kruskal Data Structures, detailed algorithm
10

39

Mon Aug 13

Details 		 
  • Complete the Course evaluation on Banner
  • Disjoint set alternate implementations
  • Dijkstra's algorithm
10

40

Tue Aug 14

Details 		 
  • P and NP