CS420dl Introduction to the Analysis of Algorithms

CS420dl Introduction to the Analysis of Algorithms. Syllabus

· Home · Syllabus · Resources · Assignments · Discussions

Outline

Problems, programs, decidability
Mathematical Fundamentals
Lower Bounds
Recurrence Relations
Sorting and Priority Queues
Depth First and Breadth First Graph Traversals
Greedy Algorithms
Dynamic Programming
Backtrack
Shortest Paths

Topics

Problems, programs, (in)tractability
- Problem, algorithm definitions
- Decidability, Halting Problem
- Tractability, Towers of Hanoi
- Algorithm Complexity, lower and upper bounds
- NP completeness, Coping with Intractability
Fundamentals
- Orders of Magnitude
- Growth rates, some common bounds (constant, logarithmic, linear, polynomial, exponential)
- Polynomial Evaluation
- Arithmetic and geometric series, harmonic numbers, sets, relations, functions, combinations
Lower bounds
- Example problems and their lower bounds
- Comparison problems
- Tournaments
Recurrence Relations
- Substitution, repeated substitution
- Master Method, examples of use
- Linear homogeneous Recurrence relations, Fibonacci
- Linear Inhomogeneous Recurrence relations
Sorting and Priority Queues
- Heapsort, analysis
- Priority Queues, insert, extract, increase key
- Quicksort, worst and average case complexity
Graph Traversals
- Graph representations
- Breadth first traversal, discovery times, breadth first tree
- Depth First Search, time stamps, nesting, depth first tree, white path theorem
- Topological Sort, Strongly Connected Components
Greedy Algorithms
- Recursive Approach and Proof Technique
- Activity Selection
- Minimal Spanning Trees
- Huffman Codes
Dynamic Programming
- Optimization Problems, Scheduling example
- Optimal Substructure
- Longest Common Subsequence
BackTrack
- Search Problems, examples n-Queens and Subset sum
- Iterative and Recursive Back Track Schemata
- Application to example problems
Shortest Paths Problems
- Problem Categories, negative weights and Cycles, Convergence and Bound Properties
- Single Source Shortest Paths, Bellman-Ford, SSSP in DAGs, Dijkstra
- All pairs Shortest Paths, Floyd-Warshall, Predecessors in Floyd-Warshall
- Transitive Closure

Textbooks

Required, edition does not matter that much.
Introduction to Algorithms
Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein,
MIT Press
optional, but very useful
Discrete Mathmatetics and its Applications
Ken Rosen
McGraw Hill

Assignments, Quizzes, Exams, and Discussions

The distance learning course consists of study, quizzes, discussions, assignments, a mid-term and a final exam. The distance learning class uses RamCT for discussions, quizzes and tests.

Quizzes are to be done after study to check whether the material is comprehended. They are to be done before work on discussions and assignments is started (when available). Quizzes are available on RamCT in the indicated period - each has a time policy associated with it that will be announced. The worst quiz result is dropped. The quizzes are there to help you study.
Discussions are done in discussion groups, so that students can extend their understanding by learning from each other. Students are assigned to discussion groups by the TA. If you have requests to be grouped with specific students, please email these requests to cs420dl@cs.colostate.edu.

The (pdf) lecture notes highlight and extend book material and indicate which parts of the book are most important. As pointed out on the front page, the notes are brief and indicate what you need to study in more detail.

Assignments and Exams are done individually. Assignments will be due by the indicated date and time. Midterm and final exams are taken in the form of online quizzes, and can be taken only once.

The late period is 48 hours for assignments, with a 10% reduction in score.

Quiz Instructions

You will take your quizzes online through RamCT. Check that your pop-up blocker does not block the quiz attempt window.

Discussion Instructions

Each student submits an initial solution to his/her discussion group. This is the starting point for the discussions. All students of that discussion group participate in discussing the pros and cons of each solution. They must then arrive at a solution agreed upon by the whole group.

Each group selects a representative to write and submit a consensus report. The consensus report can be a text, doc or PDF file. It must contain the following information:

Dicusssion number/topic
Discussion group name
Names of people who participated in the discussion.
Name of the representative
Actual report: This must contain the solution agreed upon by the whole discussion group. If you submit only the final solution (and it is incorrect), you will not get any partial credit. If you submit the steps followed to arrive at the solution, you will get partial credit depending on where the actual mistake occured.

The consensus report is submitted by the representative by attaching the document to a message in the appropriate discussion before the due date for that discussion. Each discussion must have a different representative.

Grading

Students are evaluated on the basis of assignments, proctored examinations, online quizzes, and discussions:

assignments (30%)
discussion assignments (on campus: audience participation) (10%)
quizzes (10%)
a mid-term exam (25%)
a final exam (25%)

Your grades will be posted on RamCT. Letter grades follow the standard 10 point cutt offs.

Policy

Midterm and Finals: Make-up exams are only given for extraordinary circumstances (e.g., illness, death of family member).
Quizzes: No make-ups will be given for missed quizzes.
Programming Assignments: Assignments will be submitted electronically through Ram CT.

Professional Conduct

All students are expected to conduct themselves professionally. We (the instructor and the GTA) assume you are familiar with the policies in the student information sheet for the department. The guidelines outlined in these documents will be followed in this course.