CS 515 - Algorithms
Credits: 3
Course Description
The design and analysis of efficient algorithms and data structures for problems in sorting, searching, graph theory, combinatorial optimization, computational geometry, and algebraic computation. Emphasis on paradigms for design and on rigorous analysis. Practical issues pertaining to efficient implementation and performance measurements.
Prereqs: CS315 or instructor's consent.
Needed Skills
Students need to be familiar with basic data structures and algorithms. Students should be adept in programming in a modern object-oriented language.
Learning Outcomes
A successful student will develop knowledge of various mathematical tools and algorithmic methods that are applicable in computer science. Specifically, students will be able to:
1. Prove algorithms correct
2. Analyze the computational complexity of algorithms
3. Design algorithms for complex problems
4. Select and apply the best algorithmic approach for practical problems algorithms
Measures
These four specific outcomes will be evaluated on the basis of student work (homeworks, programming assignments, and exams) that will contain problems specifically addressing these outcomes. They will also be evaluated on the basis of student self-assessment of their mastery of the four outcomes performed at the end of the semester.
CAC Categories
Topic
|
Core
|
Advanced
|
Math
Fundamentals
|
0
|
0
|
Data
Structures
|
3
|
10
|
Algorithms
& Software Design
|
0
|
9
|
Computer
Organization and Architecture
|
0
|
3
|
Concepts
of Programming Languages
|
4
|
10
|
Social
and ethical issues
|
0
|
1
|
Total
|
6
|
33
|
Math Fundamentals (12):
Core (4): Basic recurrences (2); Basic asymptotic estimation (2);
Advanced: Advanced recurrences (2); Proof techniques (3); Intractibility (3).
Data structures (9):
Core (3): Fundamental data structures (graphs, trees, heaps)
Advanced (6): Advanced data structures (sets, balanced search trees, directed graphs, strings).
Algorithms and Software (24):
Core (8): Searching and sorting (4); Graph algorithms (4)
Advanced (16): Graph algorithms (6); Advanced algorithms (algebraic algorithms, string algorithms, geometric algorithms) (8) implementation of algorithms and data structures (2).
Written Communication
10-12 homeworks and projects, 3 pages/assignment
Coverage
Theoretical Content: 50%
· Recurrences
· Asymptotic estimates
· Proof by invariant
· Lower boundsintractability and NP completeness
· Search algorithms
· Sorting algorithms
· Order statistics
· Dictionaries and heaps
· Union find algorithms
· Graph algorithms (traversal, shortest paths, spanning trees, network flows)
· Algebraic algorithms (Euclidean algorithm, modular arithmetic, primality testing, and cryptography)
· String algorithms
· Computational geometry [JWJ - structures, algorithms and designing methods for geometric problems]
· Greedy methods
· Dynamic programming
· Reductions between problems
· Types of problems.
Problem Analysis: 25%
Formulate and study properties of algorithms, data structures, and computational problems
Solution Design: 25%
· Design algorithms and data structures, construct proofs of properties of algorithms
· Construct proofs of properties of computational problems
· Find solutions recurrence and asymptotic estimation problems
Student Evaluation and Feedback
Students are evaluated on their work (homeworks, exams). Students receive back their homework and exams. These papers are marked to indicate problems, point out correct or better solutions, and improve the quality of presentation. Problems that turn out to be especially difficult are discussed in class during lectures.
NOTE: 100% lecture - 0% recitations
Course Evaluation Questions
The course has helped me to:
37. Prove algorithms are correct
38. Analyze the complexity of algorithms
39. Design new algorithms
40. Use existing algorithms for complex problems
41. Understand the relevance of algorithm design and analysis in CS
Possible Textbooks
Introduction to Algorithms, Second Edition
T.H. Cormen, C.E. Leiserson, R.L. Rivest, Clifford Stein
MIT Press, 2001.
Introduction to Algorithms: A Creative Approach
U. Manber
Addison-Wesley, 1989.