CSE 340 Design & Analysis of Algorithms (3)

Instructor:

Hank Korth, Hector Munoz-Avila  (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, 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 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 978-0262033848 hardcover, or 978-0262533058 paperback)

References

None

COURSE OUTCOMES

Student will have

  1. Design new algorithms, prove them correct, and analzye their asymptotic and absolute runtime and memory demands.
  2. Locate in the literature provably correct and - to the extent possible-efficient algorithms to solve a wide range of computational problems.
  3. Understand how to judge whether or not a problem is likely to possess an efficient algorithm.
  4. 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 computer-based 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; 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 semeser, 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.

© 2014-2016 Computer Science and Engineering, P.C. Rossin College of Engineering & Applied Science, Lehigh University, Bethlehem PA 18015.