The "CPSC 201 or equivalent" prerequisite for CPSC 223 will be enforced. For details, see http://zoo.cs.yale.edu/classes/cs223/current/equiv.html. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Spring 2020 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 ~~~~~~~~~~~~~~~~ Chris Lim Undergraduate Learning Assistants ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Alex Briasco-Stewart, Gabriel Buchdahl, Nishitha Burman, Celia Gazepi, Clayton Hebert, Yunji Jong, Hao Li, Sally Ma, Jun Park, Emma Pierce-Hoffman, Kaitlynn Pineda, Adin Ring, Vincent Schaffer, Manuel Schneider, Andrew Sheinberg, Xiuya Yao Textbooks (available online) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~ James Aspnes, "Notes on Data Structures and Programming Techniques", 2018; HTML: http://cs.yale.edu/homes/aspnes/classes/223/notes.html PDF: http://www.cs.yale.edu/homes/aspnes/classes/223/notes.pdf Brian W. Kernighan and Dennis M. Ritchie, "The C Programming Language", 2nd edition (available via Orbis or the link on the class web page) Neil Matthew and Richard Stones, "Beginning Linux Programming", 4th edition (available via Orbis or the link on the class web page) Coursework ~~~~~~~~~~ The class will NOT meet during reading period. There will be 6 programming assignments requiring a median over all students of between 6 and 9 hours per week. There will be in-class examinations on Wednesday, March 4th, and Wednesday, April 22nd. Homework will constitute ~70% of the final grade; the examinations will constitute the remaining ~30%. Grading of Programs ~~~~~~~~~~~~~~~~~~~ Programs will be submitted electronically and 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 may also be evaluated for "style". 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 or after solutions are released. The submit-times of the sources determine when a program was completed. Note: If a Dean's excuse would authorize an assignment 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. Homework/Examination Schedule ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ What When Due Spec Script ~~~~ ~~~~~~~~ ~~~~ ~~~~~~ Program #1 01/31 (F) 01/13 01/17 Program #2 02/14 (F) 01/29 02/07 Program #3 02/28 (F) 02/12 02/21 Midterm 03/04 (W) Program #4 04/03 (F) 02/26 03/13 Program #5 04/17 (F) 04/01 04/10 In-class final 04/22 (W) Program #6 05/01 (F) 04/15 04/24 On-Line Course Resources ~~~~~~~~~~~~~~~~~~~~~~~~ Directory: /home/classes/cs223/* (handouts; test scripts; other files) Web Page: http://zoo.cs.yale.edu/classes/cs223 (handouts; links; reachable only within yale.edu domain) Newsgroup: https://sce.cs.yale.edu/News/cs223/index.html (announcements; responses to e-mail) Mailing List: http://mailman.cs.yale.edu/mailman/listinfo/cs223 (optional; home delivery of newsgroup) 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 members of the teaching staff) are encouraged. But see the Gilligan's Island Rule below. However, when the time comes to design the program and write the code, such discussions are no longer appropriate---your solution must be your own personal inspiration (although you may ask members of the teaching staff for help in understanding, designing, writing, and debugging). Since code reuse is an important part of programming, you may study and/or incorporate published code (e.g., from text books or the Net) in your programs, provided that you give proper attribution in your source code and in your log file and that THE BULK OF THE CODE SUBMITTED IS YOUR OWN. Note: Removing/rewriting comments, renaming functions/variables, or reformatting statements does not convey ownership. But when you incorporate more than 25 lines of code from a single source, this code (prefaced by a comment identifying the source) must be isolated in a separate file that the rest of your code #include-s or links with. The initial submission of this file should contain only the identifying comment and the original code; revisions may only change types or function/variable names, turn blocks of code into functions, or add comments. DO NOT UNDER ANY CIRCUMSTANCES COPY SOMEONE ELSE'S CODE OR GIVE A COPY OF YOUR CODE TO SOMEONE ELSE OR OTHERWISE MAKE IT PUBLICLY AVAILABLE---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 with anyone other than a member of the teaching staff, you may write on a board or a piece of paper, but you may not keep any written or electronic record of the discussion. Moreover, you must engage in some mind-numbing activity (e.g., watching an episode of Gilligan's Island) before you work on the assignment again. This will ensure that you can reconstruct what you learned, by yourself, using your own brain. The same rule applies to reading books or studying on-line sources. Topics Covered/Emphasized (tentative) ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Programming in C Data structures: arrays, strings, linked lists, stacks, queues, hash tables, 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-03/26/20