CSE 340 Design & Analysis of Algorithms (3)

Instructor:  Henry Baird

Current Catalog Description
Algorithms for searching, sorting, counting, graph and tree manipulation, matrix multiplication, scheduling, pattern matching, fast Fourier transform. Minimum time and space requirements are established, leading to the notion of abstract complexity measures and the intrinsic complexity of algorithms and problems, in terms of asymptotic behavior. The question of the correctness of algorithms is also treated. Prerequisites: MATH 22 and CSE 261 (MATH 261).

Textbook

T. Cormen , C. Leiserson, R. Rivest, & C. Stein, "Introduction to Algorithms", 3rd Ed., The MIT Press, Cambridge, Massachusetts, 2009 (ISBN 978-0-262-03384-8 hardcover, or 978-0-262-53305-8 paperback)

References
None

Course Outcomes

On completeing this course, students will be sufficiently familiar with the theory, practice, notation, and vocabulary of algorithm design and analysis to be able to:

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 Program Outcomes

CSE 340 substantially supports the following program outcomes:

A. An ability to apply knowledge of computing and mathematics appropriate to the discipline.

B. An ability to analzye a problem and identify and define the computing requirements appropriate to its solution.

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 trade-offs involved in desidn choices.

CSE 340 provides modest support to the following program outcomes:

C. An ability to design, implement, and evaluate a computer-based system.

H. Recognition of the need for, and an ability to engage in , continuing professional development.

I. An ability to use current techniques, skills, tools necessary for computing practices.

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)

Major Topics Covered in the Course
1. Problems & Algorithms :definitions, properties

2. Algorithm Performance Analysis:

4. Data Structures: Stacks, queues, lists, graphs, trees, heaps
5. Dictionaries; Hashing; Disjoint-Sets Union/Find
6. Graph Algorithms: Bread-first & Depth-first Search; Topological Sort
7. Shortest Paths: Bellman-Ford, Dijkstra
8. Greedy Algorithms: Huffman Trees, Minimum Spanning Trees (Kruskal)
9. Dynamic Programming: Matrix-chain multiplication; All-Pairs Shortest Paths; Floyd-Warshall
10. P,NP,NP-completeness:

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.