Spring 2017 CPSC 223b Data Structures and Programming Techniques Instructor ~~~~~~~~~~ Stephen Slade, 014 Watson (432-1246) Office hours: Wednesday 3m - 5pm and by appointment Teaching Fellows / Senior ULA ~~~~~~~~~~~~~~~~-------------- Luciano Dyballa Michael Gao Sachith Gullapalli ULA's ~~~~~~~~~~~ Bilal Abu-Ghazaleh Adriana Elwood Roland Huang Nisant Jain Sreejan Kumar Hannah Lawrence (Minh Tri Pham) Bonnie Rhee Shanelle Roman Ngan Vu You may contact ALL the staff by email: cs223help@cs.yale.edu Textbooks ~~~~~~~~~ Brian W. Kernighan and Dennis M. Ritchie, The C Programming Language, 2nd edition, Prentice-Hall, 1988 ($55.02 online) Brian W. Kernighan and Rob Pike, The Practice of Programming, Addison-Wesley, 1999 ($36.67 online) Neil Matthew and Richard Stones, "Beginning Linux Programming", 4th edition, Wrox, 2007 ($28.56 @ Amazon / on-line @ Orbis) Coursework ~~~~~~~~~~ The class will not meet during reading period. There will be 7 programming assignments requiring a median over all students of between 6 and 9 hours per week. There will be in-class examinations on Wednesday, February 22nd, and Monday, April 24th. Homework will constitute ~70% of the final grade; the examinations will constitute the remaining ~30%. 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 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ What Assigned Due Topic ~~~~ ~~~~~~~~ ~~~ ~~~~~ Program #1 01/18 01/27 (F) standard i/o Program #2 01/25 02/03 (F) arrays, command line arguments Program #3 02/01 02/17 (F) hash tables, file i/o Midterm 02/22 (W) Program #4 02/22 03/31 (F) stacks/queues [extension] Program #5 03/08 03/31 (F) trees, binary search Program #6 03/29 04/14 (F) graphs, heaps In-class final 04/24 (M) Program #7 04/12 04/28 (F) dynamic programming On-Line Course Resources ~~~~~~~~~~~~~~~~~~~~~~~~ Directory: /home/classes/cs223/* (handouts; test scripts; other files) Web Page: http://zoo.cs.yale.edu/classes/cs223 (handouts; links; some available only within yale.edu domain) Piazza: https://piazza.com/yale/spring2017/cpsc223/home (announcements; Q and A) Computing Facility ~~~~~~~~~~~~~~~~~~ Zoo: 40 Intel Pentium IV workstations and a server running Fedora Linux Apply for a class account at http://zoo.cs.yale.edu/accounts.html. Late Homework Policy ~~~~~~~~~~~~~~~~~~~~ Programs should be submitted electronically by 2:00 am on the day specified in the assignment. Late work without a Dean's excuse will be assessed a penalty of 5 points per day, based on the day and time recorded by the Zoo electronic submit program. At the end of term, up to 25 points will be deducted from the total lateness penalties your homework has accrued. However, according to Yale College regulations, *no* homework can be accepted after the end of Reading Week without a Temporary Incomplete (TI) authorized by your dean. If you have a Dean's excuse or a TI, making up missed work may involve alternative assignments, at the discretion of the instructor; please check with the instructor in this case. 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). DO NOT UNDER ANY CIRCUMSTANCES COPY ANOTHER PERSON'S CODE OR GIVE A COPY OF YOUR CODE TO ANOTHER PERSON---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. Note: Reusing published code (e.g., from the Net or from books other than texts used in this class) is an important part of programming. However, it is inappropriate in a course at this level. Thus, while you may study such sources, you may not make any written or electronic record and the Gilligan's Island rule applies (see below). The Gilligan's Island Rule ~~~~~~~~~~~~~~~~~~~~~~~~~~ When discussing an assignment 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 resume work on the assignment. 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) storage management and garbage collection graph algorithms (including path-finding, minimal spanning trees) 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/18/17