CPSC 223b Data Structures and Programming Techniques (Spring 2020)

In Spring 2020 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.

Class Web Page

http://zoo.cs.yale.edu/classes/cs223

Instructor

Stanley C. Eisenstat, 208 Watson   (432-1246)   <sce@cs.yale.edu>
Office hours: TBA and by appointment (see http://sce.cs.yale.edu)

Teaching Fellow

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

James Aspnes,   Notes on Data Structures and Programming Techniques   (PDF)
Brian W. Kernighan and Dennis M. Ritchie,   The C Programming Language,   2nd edition
(within the yale.edu domain only; netID and password required)
Neil Matthew and Richard Stones,   Beginning Linux Programming,   4th edition (Second Source) (Third Source)

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 (tentative)
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/06
Program #5 04/17 (F) 04/01 04/10
In-class final 04/22 (W)
Program #6 05/01 (F) 04/15 04/24

Other Resources

Directory:   /home/classes/cs223/*   (handouts; test scripts; other files)
Web Page:   http://zoo.cs.yale.edu/classes/cs223   (handouts; links; within yale.edu domain only)
Newsgroup:   http://sce.cs.yale.edu/News/cs323/index.html   (announcements; responses to e-mail)
Mailing List:   http://mailman.cs.yale.edu/mailman/listinfo/cs323   (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, 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

CPSC-223b-03/26/20