## Colorado State University, Pueblo; Spring 2014 Math 295 — Independent Study on Algorithms and Data Structures 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, (3rd 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:
1. Introduction
2. Analysis of Algorithms, Insertion Sort, Mergesort
3. Correctness of Algorithms
4. Horner's rule
• NOTE: Friday is the last day to add classes

• Read: Chapters 3 & 4
• Content:
1. Asymptotic Notation
2. Recurrences
3. Substitution, Master Method
4. 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:
1. Recurrences, Sloppiness
2. 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:
1. Heapsort, Dynamic Sets, Priority Queues
2. Linear-time Sorting: Lower Bounds, Counting Sort, Radix Sort

• Content:
1. Order Statistics, Median
2. Applications of Median
3. Bucketsort
4. 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:
1. quicksort (chap 7)
2. heapsort (chap 6)
3. counting sort (chap 8, p194)
4. radix sort (chap 8, p197)
5. bucket sort (chap 8, p200)
6. selection, randomized selection, and selection in worst-case linear time (chap 9)
In each case, your program should read its input from a file which has the values each on a separate line with no other fields, and should write its output on another file in the same (when there are multiple outputs, such as in sorting; not in algorithms with a single output, such as the selection problem).
Your program should also measure (and print on the standard output) the time it takes to execute.

• Content:
1. More on basic sorting and searching

• Test I

• Read: Chapters 10 & §§11.1-11.4
• Content:
1. Stacks, Queues, Linked Lists, Trees
2. Hashing, Hash Functions

• Content:
1. Binary Search Trees, Tree Walks
2. Relation of BSTs to Quicksort
• NOTE: Friday is the last day to withdraw (with a W) from classes

• Content:
1. Red-black Trees, Rotations, Insertions, Deletions
2. 2-3 Trees, B-trees
3. 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.

• Content:
1. Augmenting Data Structures, Dynamic Order Statistics, Interval Trees
2. Skip Lists

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

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

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

• Exam week, yippee.
• Test II
• Final Projects due