CIS 8511 Syllabus
Fall  2011
Programming Techniques

First class: Wednesday September 31.
Last day to drop: Monday September 5.
Last day to withdraw: Tuesday, October 25.
Last Class: Wednesday, December 7.

Instructor:  Dr. James F. Korsh Office: Wachman Hall 317    Phone: 204-8199
Office Hours: By appointment.

Prerequisite: CIS 3223
Text (optional) and References:
Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms, 3nd 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++, 3rd 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 (1st 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 new 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). 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. 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.
2.Freedom to teach and freedom to learn are inseparable facets of academic freedom. The University has adopted a policy on Student and Faculty Academic Rights and Responsibilities (Policy # 03.70.02) which can be accessed through the following link: 

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 program 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             Three solutions to the maximum subsequence problem. 
3             Garwick's multiple stack management algorithm and a modified version.
4,5          Asymptotic analysis of programs. Proof of correctness of programs.
6             Binary tree traversals using stacks, linked inversion and constant storage (Robson and modified Robson).
7             Counting binary and other trees. Stack permutations.
8             Mid Term Examination
9             Heaps, sorting and priority queues.
10           Binary search trees, balanced binary trees, AVL trees and splay trees.
11           Disjoint Sets, min spanning trees
12           Huffman coding, Optimal binary search trees.
13           Graph Traversals, biconnected graphs, strongly connected components.
14            Review and selected topics.