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:
- 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)
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:
- More on basic sorting and searching
- 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