Spring 2009 CPSC 223b Data Structures and Programming Techniques Instructor ~~~~~~~~~~ Stanley C. Eisenstat, 208 Watson (432-1246) Office hours: TBA and by appointment (see http://sce.cs.yale.edu for a list of available slots) Teaching Fellows ~~~~~~~~~~~~~~~~ Eric Cheng Office hours: TBA Ronny Dakdouk Office hours: TBA Textbooks ~~~~~~~~~ Noel Kalicharan, Data Structures in C, CreateSpace, 2008 Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, 2nd edition, Prentice-Hall, 1988 Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999 OPTIONAL: Graham Glass and King Ables, Linux for Programmers and Users, Pearson, 2006 Coursework ~~~~~~~~~~ The class WILL meet during reading period. There will be 6 programming assignments and 3 non-programming assignments, requiring a median over all students of between 6 and 9 hours per week. There will be an in-class examination on Thursday, February 26th, and a 75-minute final on Friday, May 8th. Homework will constitute ~66% of the final grade; the examinations will constitute the remaining ~33%. Grading of Programs ~~~~~~~~~~~~~~~~~~~ Programs will be checked using test scripts: a public script, which will generally be available at least one week before the assignment is due; and a more comprehensive private script, which will be used to assign a grade. Programs will also be evaluated for "style". Homework/Examination Schedule ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Spec Script What When Due Ready Ready ~~~~ ~~~~~~~~ ~~~~~ ~~~~~~ Program #1 01/23 (F) 01/13 01/16 Program #2 02/06 (F) 01/20 01/27 Homework #N1 02/12 (Th) 01/29 Program #3 02/20 (F) 02/03 02/10 Midterm 02/26 (Th) Program #4 03/27 (F) 02/19 03/05 Homework #N2 04/02 (Th) Break Program #5 04/10 (F) 03/24 03/31 Homework #N3 04/23 (Th) 04/09 Program #6 05/01 (F) 04/09 04/16 Final 05/08 (F) On-Line Course Resources ~~~~~~~~~~~~~~~~~~~~~~~~ /home/classes/cs223/* (handouts; test scripts; other files) yale.cs.cs223 newsgroup (announcments; responses to e-mail) http://zoo.cs.yale.edu/classes/cs223 (handouts; links; copy of yale.cs.cs223) Computing Facility ~~~~~~~~~~~~~~~~~~ Zoo: 31 Intel Pentium IV workstations and a server running Redhat Linux Apply for a class account at http://zoo.cs.yale.edu/accounts.html. See Donna in AKW 007 to validate your Yale ID for after-hours access to Watson. Late Homework Policy ~~~~~~~~~~~~~~~~~~~~ Programs should be submitted electronically by 2:00 am on the day specified in the assignment. Late work not authorized by a Dean's excuse will be assessed a penalty of 5% per calendar day or part thereof and MAY not be graded at all if more than ten days late. The submit-times of the source files will determine when the program was completed. Non-programming homework should be submitted IN CLASS (on Tuesday/Thursday) or at my office (by 2:30 pm on Friday, which is treated as a class period for this purpose). Work submitted at other times will be treated as if submitted during the next class period. Work handed in after the day specified in the assignment and not authorized by a Dean's excuse will be assessed a penalty of 10% per class period and MAY not be graded at all if handed in more than ten days late or after solutions are released. Note: If a Dean's excuse would authorize work to be submitted more than ten days late or after solutions are released, then the student MAY be asked to complete an equivalent assignment instead. General Statement on Collaboration ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Programming, like composition, is an individual creative process in which you must reach your own understanding of the problem and discover a path to its solution. During this time, discussions with others (including the instruc- tional staff) are encouraged. (But see the Gilligan's Island Rule below.) However, when the time comes to write code, such discussions are no longer appropriate---the program must be your own personal inspiration (although you may ask the instructional staff for help in writing and debugging). Since code reuse is an important part of programming, you may incorporate published code (e.g., from text books or the net) in your programs, provided you give proper attribution AND THE BULK OF THE CODE SUBMITTED IS YOUR OWN. DO NOT UNDER ANY CIRCUMSTANCES COPY ANOTHER PERSON'S CODE---to do so is a clear violation of ethical/academic standards that, when discovered, will be referred to the Executive Committee of Yale College for disciplinary action. Modifying code to conceal copying only compounds the offense. The Gilligan's Island Rule ~~~~~~~~~~~~~~~~~~~~~~~~~~ When discussing an assignment (either programming or nonprogramming) with other students, you may write on a board or a piece of paper, but you may not take any written or electronic record away from the discussion. Moreover, you must engage in a full hour of mind-numbing activity (such as watching back-to-back episodes of Gilligan's Island) before you work on the assignment again. This will ensure that you can reconstruct what you learned from the discussion, by yourself, using your own brain. Topics Covered/Emphasized ~~~~~~~~~~~~~~~~~~~~~~~~~ Programming in C Data structures arrays, strings, linked lists, stacks, queues, binary trees priority queues, graphs, multiway trees Algorithms sorting and searching (including hashing) graph algorithms (including path-finding, minimal spanning trees) storage management and garbage collection string matching Elementary analysis of algorithms and data structures Programming techniques structured programming and modularity abstract data types debugging, testing, and verification of program correctness Efficient programming not algorithms, but code rewriting (a la Bentley's books) writing code in different ways and seeing how fast the code runs CS-223-01/09/09