CSE 340 Design & Analysis of Algorithms (3)
Instructor:
Hank Korth, Hector MunozAvila (Fall 2017)
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, divideandconquer, greediness, dynamic programming. Limits on algorithm efficiency using elementary NPcompleteness theory. Credit will not be given for both CSE 340 (MATH 340) and CSE 441 (MATH 441). Prerequisites: (MATH 022 or MATH 096 or MATH 032) and (CSE 261 or MATH 261).
Textbook
T. Cormen , C. Leiserson, R. Rivest, & C. Stein, "Introduction to Algorithms", 3rd Ed., The MIT Press, Cambridge, Massachusetts, 2009 (ISBN 9780262033848 hardcover, or 9780262533058 paperback)
References
None
COURSE OUTCOMES
Student will have
 Design new algorithms, prove them correct, and analzye their asymptotic and absolute runtime and memory demands.
 Locate in the literature provably correct and  to the extent possibleefficient 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
CSE 340 substantially supports the following student enabled characteristics:
A. An ability to appy knowledge of computing and mathematics appropriate to the discipline
B. An ability to analyze a problem and identify and define the computing requirements appropriate to its solution
I. An ability to use current techniques, skills, and tools necessary for computing practices
J. An ability to apply mathematical foundations, algorithmic principles, and computer science theory in the modeling and design of computerbased systems in a way that demonstrates comprehension of the tradeoffs involved in design choices
K. An ability to apply design and development principles in the construction of software systems of varying complexity
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, intregral, 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 Theroem
 Sorting: Heapsort, Priority Queues; Quicksort
 Lower Bounds, Sorting in Linear Time
 Data Structures: Stacks, queues, lists, graphs, trees, heaps
 Dictionaries; Hashing; DisjointSets Union/Find
 Graph Algorithms: Breadfirst & Depthfirst Search; Topological Sort
 Shortest Paths: BellmanFord, Dijkstra
 Greedy Algorithms: Huffman Trees, Minimum Spanning Trees (Kruskal)
 Dynamic Programming: Matrixchain multiplication; AllPairs Shortest Paths; FloydWarshall
 P,NP,NPcompleteness:

 The Complexity Classes P & NP
 Polynomialtime Reductions among Problems
 NPcomplete Problems, P=NP?
 Approximation Algorithms for NPcomplete problems
 Miscellaneous (as time permits):

 String Matching: KnuthMorrisPratt, RabinKarp
 Computational Geometry: Convex Hull, Voronoi diagrams
 Parallel Algorithms (threads) and Parallel Complexity (NC and NCcompleteness)
 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 maximumand so can make up for the points lost.
Exams: There are two hour exams and final 3hour exam: all are closedbook, 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 semeser, I ask students to rate the novelty, clarity, difficulty, etc of each topic covered and invite them to suggest improvement; this motivates my selfassessment and improvement plan. Each semester I include this and the above data from the assessment plan for the course in my selfassessment of the course. This report is reviewed, in turn, by the Curriculum Committee.