Current Catalog Description
Algorithms for searching, sorting, manipulating graphs and trees, finding shortest paths and minimum spanning trees, scheduling tasks, etc.: proofs of their correctness and analysis of their asymptotic runtime and memory demands. Designing algorithms: recursion, divide-and-conquer, greediness, dynamic programming. Limits on algorithm efficiency using elementary NP-completeness theory. Credit will not be given for both CSE 340 (MATH 340) and CSE 441 (MATH 441). Prerequisites: (MATH 021 or MATH 031 or MATH 076) and CSE 140 and CSE 017
Instructor: Arielle Carr, David Saldaña (Fall 2022)
Textbook
T. Cormen , C. Leiserson, R. Rivest, & C. Stein, "Introduction to Algorithms", 3rd Ed., The MIT Press, Cambridge, Massachusetts, 2009, ISBN 978-0262033848
References
None
COURSE OUTCOMES
Student will have
- Design new algorithms, prove them correct, and analyze their asymptotic and absolute runtime and memory demands.
- Locate in the literature provably correct and - to the extent possible-efficient algorithms to solve a wide range of computational problems.
- Understand how to judge whether or not a problem is likely to possess an efficient algorithm.
- Have a grasp of basic engineering issues arising in the implementation, adaptation, and application of algorithms.
RELATIONSHIP BETWEEN COURSE OUTCOMES AND STUDENT ENABLED CHARACTERISTICS
SO 6: Apply computer science theory and software development fundamentials to produce computing-based solutions. [CS]
Prerequisites by Topic
- Math 21(Calculus I), Math 22 (Calculus II) and CSE 261/Math 261 (Discrete Math)
- Sets: basic operations, Cartesian products, relations, functions, graphs, trees
- Summations: formulas & properties, bounds
- Counting: strings, permutations, combinations, Binomial coefficients
- Matrices: basic operations, inverse, rank, determinant
- Derivative, integral, differentiation, integration
- Proof techniques: direct, by contradiction, by contrapositive, by induction
Major Topics Covered in the Course
- Problems & Algorithms :definitions, properties
- Algorithm Performance Analysis:
- Asymptotic Growth of Functions, O(.), etc.
- Iterative vs Recursive algorithms; Divide and Conquer, Insertion Sort & MergeSort
- Recurrences & their solution: by Substitution; the Master Theorem
- Sorting: Heapsort, Priority Queues; Quicksort
- Lower Bounds, Sorting in Linear Time
- Data Structures: Stacks, queues, lists, graphs, trees, heaps
- Dictionaries; Hashing; Disjoint-Sets Union/Find
- Graph Algorithms: Bread-first & Depth-first Search; Topological Sort
- Shortest Paths: Bellman-Ford, Dijkstra
- Greedy Algorithms: Huffman Trees, Minimum Spanning Trees (Kruskal)
- Dynamic Programming: Matrix-chain multiplication; All-Pairs Shortest Paths; Floyd-Warshall
- P,NP,NP-completeness:
-
- The Complexity Classes P & NP
- Polynomial-time Reductions among Problems
- NP-complete Problems, P=NP?
- Approximation Algorithms for NP-complete problems
- Miscellaneous (as time permits):
-
- String Matching: Knuth-Morris-Pratt, Rabin-Karp
- Computational Geometry: Convex Hull, Voronoi diagrams
- Parallel Algorithms (threads) and Parallel Complexity (NC and NC-completeness)
- Polynomials & the Fast Fourier Transform
Assessment Plan for the Course
There are weekly written homework assignments, due normally on Friday morning, to be handed in as hardcopy at the start of the class. For part of each Friday's class, students are invited to present their solutions on the blackboard, for which they will receive 5 points credit (whether or not their solution is correct); this "presentation" credit is added to the HW+Quiz score, up to a fixed maximum-and so can make up for the points lost.
Exams: There are two hour exams and final 3-hour exam: all are closed-book, written exams.
Grading: 80% Exams (20% 1st hour exam, 20% 2nd exam, 40% final exam); 20% Homeworks + Quizzes + Presentations.
How Data in the Course are Used to Assess Program Outcomes:
At the end of the semester, I ask students to rate the novelty, clarity, difficulty, etc of each topic covered and invite them to suggest improvement; this motivates my self-assessment and improvement plan. Each semester I include this and the above data from the assessment plan for the course in my self-assessment of the course. This report is reviewed, in turn, by the Curriculum Committee.