Last day to withdraw: Monday, April 26.

Last Lecture: Monday, April 26.

Instructor:  Dr. James F. Korsh Office: SERC 322  Phone: 204-8199   Email: korsh@temple.edu
Office Hours: To be decided after class starts.

Prerequisite: CIS 3223
Text (optional) and References:
Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3^rd Edition, MIT Press, 2009.

Aho, Hopcroft, and Ullman. Data Structures and Algorithms. Addison-Wesley, 1983 (reprinted 1987))

Dijkstra. A Discipline of Programming. Prentice-Hall, 1976.

Korsh and Garrett. Data Structures, Algorithms, and Program Style Using C. PWS-Kent, 1988.

Standish. Data Structure Techniques. Addison-Wesley, 1980.

Weiss. Data Structures and Algorithm Analysis in C++, 3^rd Edition. Adison-Wesley, 2007.

Dr. Dobbs Essential Books on Algorithms and Data Structures. Miller Freeman, Inc. (This CD contains the complete text of Cormen et al (1^st edition), Aho et al, and Korsh & Garrett.)

Knuth. The Art of Computer Programming, 2d -- Vol 1 / Fundamental Algorithms. Addison-Wesley, 1973.

Knuth. The Art of Computer Programming, 2d -- Vol 2 / Seminumerical Algorithms. Addison-Wesley, 1981.

Knuth. The Art of Computer Programming, Vol 3 / Sorting and Searching. Addison-Wesley, 1973.

The links below are to drafts of Knuth:

·  Pre-Fascicle 2a: Generating all $n$-tuples (version of 10 December 2004)

·  Pre-Fascicle 2b: Generating all permutations (version of 10 December 2004)

·  Pre-Fascicle 3a: Generating all combinations (version of 10 December 2004)

·  Pre-Fascicle 3b: Generating all partitions (version of 10 December 2004)

·  Pre-Fascicle 4a: Generating All Trees (version of 28 October 2005)

·  Pre-Fascicle 4b: History of Combinatorial Generation (version of 28 October 2005)

Horowitz and Sahni. Fundamentals of Computer Algorithms. Computer Science Press, 1984.

Gries. The Science of Programming. Springer-Verlag, 1981.

Bentley. Programming Pearls. Addison-Wesley, 1986.

Bentley. More Programming Pearls -- Confessions of a Coder. Addison-Wesley, 1988.

Goodrich and Tamassia , Date Structures and Algorithms in JAVA, 4th Edition. Wiley,  2005

Sedgewick, Bundle of Algorithms in Java, Third Edition, Parts 1-5: Fundamentals, Data Structures, Sorting, Searching, and Graph Algorithms, 3rd Edition, Addison-Wesley, 2004

Grades: Determined by a combination of performance on assignments, on the midterm, and on the final examination.
Assignments There will be a series of programming assignments (5-7). To pass the course all assignments must be completed in a satisfactory manner. They are to be completed on time or credit may be lost.
Late-to-class or missed class: It is the student’s responsibility to find out what material or announcements were missed. After reviewing this material, if more help is needed, then the student can see the instructor..

Notes:
1. You will be enrolled in this course on Canvas where much of the material and other information needed for this course is located. Canvas can be accessed through the TUPortal
2. Access to the Temple Technology USAGE policy can be obtained through http://policies.temple.edu/list_docs.asp#T.
3. Any student who has a need for accommodation based on the impact of a disability should contact me privately to discuss the specific situation as soon as possible. Contact Disability Resources and Serrvices at 215-204-1280.
4. Freedom to teach and to learn are inseparable facets of academic freedom. The University hasd a policy on Student and Faculty and Academic Rights and Responsibilities which can be accessed through http://policies.temple.edu/getdoc.asp?policy_no=03.70.02.

Description The purpose of this course is to gain a basic knowledge of fundamental data structures and an understanding of their relationship to the performance of algorithms and programs. This includes an introduction to execution time analysis and to the proof of program correctness.

OUTLINE  This is intended to give a general idea of the course but is subject to change.

Week:

1             Detailed development of a prototype solution to the Topological Sorting problem to illustrate 
               programming methodology and the impact of data structure selection on program characteristics.

2             Solutions to the maximum subsequence problem.     
              Asymptotic analysis and proof of correctness of programs.

3             Garwick's multiple stack management algorithm and a modified version.

4             Binary tree traversals using stacks, linked inversion and constant storage (Robson and modified Robson).

5             Parentheses and Binary trees.

6             Trees and Stack permutations.

7             Mid Term Examination

8             Heaps, priority queues, Heapsort, Huffman Codes.

9           Optimal Binary Search Trees.

10           Binary search trees, balanced binary trees, AVL trees and splay trees.

11           Strahler and pruning numbers, Disjoint Sets.

12           Amortized Analysis and Examples.

13           Minimum spanning trees.

14           Graph Traversals, Shortest Paths, strongly connected components, biconnected graphs.