Math 295 — Independent Study on

Course Schedule & Homework Assignments

Here is a link back to the course syllabus/policy page.

In the following, all sections and page numbers refer to the required course
textbook, * Introduction to Algorithms,
(3^{rd} edition)*, by Cormen, Thomas, Charles
Leiserson, Ronald Rivest, and Clifford Stein.

This schedule is only approximate, and will be modified as the semester
proceeds. *E.g.,* homework assignments and quizzes have to be added; both
will be roughly every other week.

*Read:*Chapters 1 & 2*Content:*- Introduction
- Analysis of Algorithms, Insertion Sort, Mergesort
- Correctness of Algorithms
- Horner's rule

*NOTE:*Friday is the last day to add classes

*Read:*Chapters 3 & 4*Content:*- Asymptotic Notation
- Recurrences
- Substitution, Master Method
- Divide-and-Conquer: Strassen, Fibonacci, Polynomial Multiplication

- start
**HW1:***p22:*2.1-3 and 2.1-4,*p29:*2.2-3,*p41:*Chapter 2 Problems: 2-3,*p53:*, 3.1-7,*p75:*, 4.1-5,*p87:*4.2-{1, 2, 6},*p107*Chapter 4 Problems: 4-1{a,b,f,g}, 4-4, 4-5

*Read:*Chapters 5 & 7*Content:*- Recurrences, Sloppiness
- Quicksort, Randomized Algorithms

- more
**HW1:***p117:*5.1-{2, 3},*p122:*5.2-{3, 4} *NOTE:*Monday is the last day to drop classes without a grade being recorded

*Read:*Chapters 6 & 8*Content:*- Heapsort, Dynamic Sets, Priority Queues
- Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort

*Read:*Chapter 9*Content:*- Order Statistics, Median
- Applications of Median
- Bucketsort
**HW2:**please write, in whichever programming language you like, codes for**all**of the algorithms which have been discussed to this point of the course. These include:- quicksort (chap 7)
- heapsort (chap 6)
- counting sort (chap 8,
*p194*) - radix sort (chap 8,
*p197*) - bucket sort (chap 8,
*p200*) - selection, randomized selection, and selection in worst-case linear time (chap 9)

Your program should also measure (and print on the standard output) the time it takes to execute.

*Content:*- More on basic sorting and searching

- Test I

*Read:*Chapters 10 & §§11.1-11.4*Content:*- Stacks, Queues, Linked Lists, Trees
- Hashing, Hash Functions

*Read:*§§ 12.1-12.3*Content:*- Binary Search Trees, Tree Walks
- Relation of BSTs to Quicksort

*NOTE:*Friday is the last day to withdraw (with a**W**) from classes

*Read:*Chapter 13*Content:*- Red-black Trees, Rotations, Insertions, Deletions
- 2-3 Trees, B-trees
**HW3:***p235:*10.1-{2, 6, 7},*p241:*10.2-6,*p248:*any**one**of 10.4-{2-5},*p261:*11.2-2,*p289:*12.1-{2, 3},*p293:*12.2-5,*p299:*12.3-{3, 4}.

Turn in any time this week — before Spring Break! — or as much as you have done, and submit any last ones by e-mail over the break.

**Spring Break!**No classes or office hours.

*Read:*Chapter 14*Content:*- Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
- Skip Lists

*Read:*Chapter 15, 16 (§§1-3), 22 (§1), & 23*Content:*- Dynamic Programming, Longest Common Subsequence
- Greedy Algorithms, Minimum Spanning Trees

*Read:*Chapter 22 (§2) & 24*Content:*- Shortest Paths I: Properties, Dijkstra's Algorithm, Breadth-first Search
- Shortest Paths II: Bellman-Ford, Linear Programming, Difference Constraints

*Read:*Chapter 22 (§§ 3 & 4)) & 25*Content:*- Graph Searching: Depth-first Search, Topological Sort, DAG Shortest Paths
- Shortest Paths III: All-pairs Shortest Paths, Matrix Multiplication, Floyd-Warshall, Johnson

**Exam week**, yippee.- Test II
- Final Projects due