CSC241 - Abstract Data Types & Programming Methodology

Instructor:          M.  Mohammadi           Office Hours:  MW (5:00-5:30 PM)
Office:              112 Snygg                              MW (8:40-9:30 PM)
Phone:               341-2689 (office)                      and by appointment
                     564-5911 (home)                        

Objectives:          Create an environment where students have ample 
		     opportunities to improve their problem solving skills,

		     teach about program validation and verification, and 
		     analysis of algorithms as a significant part of 
                     software design,  

		     provide an in depth exposure to well known non-persistent
		     data structures in the context of C++ classes and objects.


Room:                104 Snygg              Time:      M W (5:30 - 8:40)


Texts:               'Data Abstraction and Problem Solving with C++:
                     Walls and Mirrors' by F. Carrano, Benjamin/Cummings 1995.

Computer
Facilities:          SUN work-stations and servers (rocky,gidney).
                     Terminals are in Snygg, rooms 6, 8, and 103 also in 
                     room 210 Mahar. The programming labs will meet in room 
                     103 Snygg.
Grading:
                     Exams 1,2............................. 30%
                     Final Exam............................ 15%
                     Participation in class exercises......  9%
                     Structured Labs ......................  6%
                     Programs 1-4.......................... 40%

Notes:
    . The exams and the final are expected to each take 1.5 hours.  
      Exam #1 is scheduled for July 12th, Exam 2 July 26th, and Final on 
      August 9th.
    
    . Programs are due by mid-night on the date due. Late programs
      will be penalized five percent if turned in by the following class,
      after that, you will lose ten percent. No programs are accepted two
      weeks after the due date regardless of holidays. Programs dated two days
      early (dated by the computer on the burst page) will be given a five 
      percent extra credit.  August 11th is the last day where the last
      program can be turned in.  You must work on your programs individually.
      Using another person's program in writing your own is illegal.  Giving 
      your program to another person is also illegal.  You will receive 
      an E in either case.

    . This course will not be taught in a typical way, for the most part, I'll
      lecture for half of the class and the other half you will either
      break up into small groups and work on problems or we will go to the lab
      and work on structured lab assignments.  I intend to design 6 or so of 
      such labs for this Summer.  As you can see above, you will be graded for 
      your participation in group work and the structured labs that you 
      complete.

    . READ THE COMPUTER SCIENCE POLICY ON CHEATING.























                            Course Outline
                            --------------

                            C S C   2 4 1
              
	    Abstract Data Types & Programming Methodology
   
                            Summer 1995
   
                            M Mohammadi


                                                       Classes		Reading
                                                       -------		-------

I.      Revisit classes and objects.	  		#1		CH#1
	discuss Separating class signatures from
        their implementation.  

II. 	Programming Methodology.			#2		CH#2
	1. Software life cycle.
	2. OOD and TDD

III.	Recursion.					#3		CH#3,
	Tower of honoi, parsing, etc.					Part of CH#5

IV.	Abstract Data Types.		
        1. List ADT					#4,#5,#6	CH#4
	   a. Basic concepts.						Part of CH#5
	   b. Dynamic and static representaion.
	   c. Definition and implementation of operations.
	   d. Efficiency of algorithms.
           e. Ordered list, Rings, etc.   
	   f. Using lists in applications.
	2. Stacks and Queues.                           #7,#8		CH#6,CH#7
	   a. Basic concepts.
	   b. Dynamic and static representaion.
	   c. Definition and implementation of operations.
	   d. Efficiency of algorithms.
	   
V.	O(n log n) and O(n) sorting techniques and   	#9,#10		CH#9
        their comparison analytically or empirically.  
        Merge Sort, Quick Sort, and Radix sort.

VI.     Binary tree. 					#11,#12		CH#10
           a. Basic concept.
	   b. Dynamic and static representaion.
	   c. Definition and implementation of operations.
	   d. Use as an ADT.
	   e. Efficiency of algorithms.