CSCI 221: CS Fundamentals II

This is a second course in computer science that serves as an introduction to computer systems fundamentals and provides its students a transition to advanced programming. We introduce students to how programming systems are constructed— from transistors, to logic gates and registers, through an instruction set architecture, to the runtime system of C and C++ programs. This is a dense survey so students gain maturity in how programs actually execute on computer systems. This has value in two ways (1) it gives them a realistic sense of the performance and optimization of programs, and (2) it provides a foundation for thinking about the tools and systems they might someday construct themselves. Furthermore, learning these fundamentals is useful for understanding the various security vulnerabilities that arise in our current hardware and software infrastructure.

The course also serves as an introduction to C programming and to modern object-oriented programming in C++. To master these languages, we cover techniques for structuring code and representing data, including using standard object libraries and widely adopted idioms for careful management of object heap data, and of a program’s references to it.

There will be significant programming projects in C, MIPS assembly, and C++ as well as logic circuit construction in a logic circuit simulator. Program development tools including the Unix command line and editors, compilers, building and debugging tools, and repositories for version control and sharing will also be covered. We meet once a week (Tuesday) for lab exercises, have weekly homeworks (assigned either Wednesday or Thursday, due Wednesday), and have several longer term programming projects usually due every third or fourth week.

Prerequisite: CSCI 121 or the equivalent.

Lecture: MW 3:00-4:20pm in TRL 150/Zoom.
Labs:
• Section FL1 8:50-10:10am in ETC 211 when possible, over Zoom otherwise.
• Section FL2 10:25-11:45am in ETC 211 when possible, over Zoom otherwise.
• Section FL3 3:15-4:35pm over Zoom.

Instructor: Jim Fix jimfix@reed.edu
Zoom hours: M 5-6:30pm, F 2:30-4pm

Teaching assistants (grading and tutoring):
• Ariel Flaster, flastera@reed.edu
• Henry Lindeman, henlindem@reed.edu
• Eli Poppele, poppelee@reed.edu
• Ryan Quisenberry, quisenry@reed.edu

Schedule Overview

Part I: C programming and low-level data structure design. (4 weeks)
Part II: Logic circuits, processor design, and machine-level programming. (4 weeks)
Part III: Object-oriented programming and memory management in C++. (5 weeks)

This schedule is detailed below.

Texts and Resources

The course draws on material from written texts and also on-line, and we will share references to these throughout the semester. Most reading will not be required—your main goal is to work with the lecture and lab materials to complete the assignments— but you will find it useful to consult references on the technical material and also to do some background reading on the topics we cover.

We encourage you to consult the following texts during the semester. The first four C++ books are often required in courses, the first two are references to the language, the third is an attempt by the C++ author to write a programming textbook, and the fourth’s goals seem to be a mash-up of the first three’s, but not written by the language inventor. The two following texts are each a nice overview of the non-C++ components of the course, giving a tour of how computer systems are constructed from the transitor level to the C/C++ language level. The last is an advanced text on digital circuit logic, but some of you might just enjoy delving into the deep details.

I don’t require texts, since many people are good at picking up languages without a text, and there are also lots of reference materials available on C++ on-line.

Recommended Texts

A TOUR OF C++
by Bjarne Stroustrup.
This is a brief reference to many aspects of the C++ language from the language inventor. Get this if you like carrying around a small book rather than searching for info on-line.

THE C++ PROGRAMMING LANGUAGE
by Bjarne Stroustrup.
This is a (the?) comprehensive reference text on the C++ language from the language inventor. It’s a big text, but it has a lot in it. It contains the TOUR (above) within it.

**PROGRAMMING: PRINCIPLES AND PRACTICE USING C++
by Bjarne Stroustrup.
This seems to be available through the O’Reilly Educationportal through Reed’s library catalog. It contains more programming advice and philosophy than the two references above.

C++ PRIMER
by Stanley Lippman and others.
I personally think that Stroustrup’s guides to C++ can be tricky to read, and his writing has its strengths and its weaknesses. This is an alternative written by authors. This is often a primary text for C++ courses, including for a course I helped teach in the 90s (with an older edition).

Optional Additional Texts

THE ELEMENTS OF COMPUTING SYSTEMS:
BUILDING A MODERN COMPUTER FROM FIRST PRINCIPLES
by Noam Nisan and Shimon Shocken.
Useful side-reading to give you more perspective and context on the work we do this semester.

INTRODUCTION TO COMPUTING SYSTEMS:
FROM BITS & GATES TO C & BEYOND
by Yale Patt and Sanjay Patel.
Siimilar to the above but with additional depth.

Fundamentals of Digital Logic
by Stephen Brown and Zvonko Vranesic.
This is a rich supplement, a text for digital design junior-level computer engineering courses. We only look at circuits and processors briefly, for three weeks. Probably half of this book would be used for a semester-long course.

In addition, here are some links for the tools we will use this semester: • Unix command-line: how we compile and run C/C++ programs.
• Git repository for saving and submitting work.
• Editors for program development, listed below. Cheat sheets for using these abound.
… VIM
… Emacs or nano
… Atom
… Sublime Text
* repl.it: an on-line (collaborative) IDE for C++
• LogiSim a (now outdated) Java program for simulating circuits.
• Logisim Evolution: updated version of the above.
• SPIM simulator for MIPS32 assembly.
• PDX C++ meetup: the local C++ community.
• C++ podcast: C++ podcast for both the new andseasoned.

Detailed Schedule and Daily Materials

This section will update as lectures happen and as materials are posted.

Part I: The C programming language and runtime system.

Week 01: Introduction to C programming.
. Lecture 01-1: course overview slides video
. Lab 01: Unix/C/git logistics attempt by 9/9 at 3pm
. Lecture 01-2: C programming slides examples video
… A grammar for C++.
… Guide to installing Unix tools and ssh
… Git-It tutorial you can download here
. Homework 01: some Pythonic C++ due 9/10 at 10am

Week 02: Functions and procedures. The call stack.
. Lecture 02-1: controlling the flow slides videos
. Homework 02: procs funcs rec due 9/15 9am

Week 03: Arrays and structs. Pointers and addresses. Stack vs heap.
. Lecture 03-1: arrays and structs slides materials
. Lab 03: stack-allocated arrays and structs
. Lecture 03-2: heap allocation slides materials
. Homework 03: structs and arrays due 9/24 4pm

Week 04: Heap-allocated structs. Linked data structures.
. Lecture 04-1: all things pointer-related
… slides notes videos
. Lab 04: struct pointers
… solution using “star dot” notation
… solution using “arrow” notation
. Lecture 04-2: intro to linked lists
… slides notes videos
… sample linked list code
. Homework 04: a few pointers due 10/1 4pm

Week 05: Finish linked lists. Start digital circuits.
. Lecture 05-1: a linked list library
… slides notes videos code
. Lab 05 linked lists
. Lecture 05-2A: wrap-up linked lists
… videos
. Homework 05: linked lists due 10/8 4pm

Part II: Circuits and processor design.
. Lecture 05-2B: logic circuits.
… videos

Week 06: number encodings and arithmetic circuits
. Lecture 06-1: gates; XOR circuit; 2:1 MUX circuit.
… slides videos
. Lab 06 circuits
. Lecture 06-2: boolean algebra; adders; subtraction.
… slides videos
. Homework 06: circuits due 10/15 11:59pm

Week 07: Flip-flops. Sequential circuits. The MINICS2 4-bit processor.
. Lecture 07-1: flip flops and registers
… circuits videos notes
. Lab 07 sequential circuits
. Lecture 07-2: Project 1; MINICS2 processor; MIPS preview
… videos
. Project 1: stats and chats due 10/30

Week 08: Intro to MIPS assembly.
. Lecture 08-1: MIPS assembly programming
… samples videos slides notes
. Lecture 08-2: 1st Midterm Exam on C++ Programming
… practice midterm A and its solution
… practice midterm B and its solution
. Midterm #1

Week 09: MIPS assembly programming. Function calls in assembly.
. Lecture 09-1: More sample programs. Load/store instructions.
… slides videos code
. Lab 09: SPIM intro
. Lecture 09-2: Function call mechanisms. Calling conventions.
… slides videos
. Homework 09: MIPS assembly
. Project 1 due.

Week 10: MIPS redux
. Lecture 10-1: List code. Bit shifting.
… slides videos
. Lecture 10-2: MIPS function call redux.
… slides videos

Part III: Object-orientation with C++; the C++ Standard Template Library

Week 11: C++ classes, objects, methods; heap vs. stack objects; public vs. private.
. Lecture 11-1: object-oriented C++
… slides videos
. Lab 11: a Rational C++ class
. Lecture 11-2: operators, destructors
… slides videos
. Homework 11: due 11/20.

Week 12: inheritance; templates; reference type
. Lecture 12-1: references and immutability; inheritance intro
… slides videos
… Account code; Shape code
. Lecture 12-2: inheritance; templates
… slides videos
… Stck_T code

Week 13: the C++ STL
. Lecture 13-1: vector, unordered_map, lambdas
… slides
. Lab 13: templates, pair, and vector
. Lecture 13-2: memory management; smart pointers
… slides code

Week 14: last bits
. Lecture 14-1: copying and moving
… slides dc code

Final Exam: Thursday, December 10th, 1-5pm.
… about the length of two midterms
. Topics:
.. truth tables, logic, sum of products
.. logic gates, digital circuits
.. binary number representation, arithmetic
.. registers, sequential circuits
.. MIPS assembly programming
.. load/store instructions
.. bit shifting
.. pointers, addresses
.. arrays, linked data structures
.. passing by value, by pointer, by reference
.. C++ classes and their methods
.. constructors and destructors
.. heap objects versus stack objects
. practice exam with solutions and test code
• Exam repo. Upload your work by 5pm.

Final Homework: Due Tuesday, December 15th 11:59pm.
… It is the length of two labs, with extras/BONUS
. Topics:
.. lambdas
.. templates, std::vector, etc.
.. inheritance
. Homework 12 and 13 the last homework

this week

The course has ended. Scroll up to see prior weeks.

Responsibilities

You are responsible for all material discussed in class and assigned as reading, and you are required to read course-related email and slack posts, and also the course web pages linked here. There will be two in-class exams during the semester, a final comprehensive exam at the end of the semester, and an occasional in-class quiz question to foster questions and discussion. There will also be a mix of lab exercises, homework assignments, and programming projects detailed below.

Lab Exercises
We will assign several short programming exercises every Tuesday for the lab meeting. The goal of these exercises is to have you “dive into” the content being taught that week. The work should hopefully foster questions and discussion in lecture and will prepare you for the next homework assignments. For these labs, we will sometimes pair you with programming partners and you’ll collaborate on completing the work. Unless requested, we will not grade or evaluate the lab work thoroughly; we’ll only check whether an earnest attempt was made and to see how much work was completed. You should work to complete them to the best of your ability by the following day’s lecture.

Homework
Each week, usually on Wednesday, we will give a programming assignment for you to complete for the next week. These will be more substantial assignmemnts than the labs andwill also exercise and apply the concepts being taught that week in lecture. Some of the problems will have you work to develop a larger program. Others will be small puzzles worth solving to help and demonstrate your understanding. These are to be completed on you’re own, and you’ll normally have a week to complete them. They are designed to require the week to be solved, and so you should start working on them immediately. That way you’ll have time to seek help from us if you get stuck completing the work.

Programming projects
A larger-scale programming project will be assigned every three or four weeks. These are intended to comprehensively cover the recent unit of course content, or to tie several different units’ concepts together, giving you a chance to build a code a significant program component. Past projects have included text analysis, circuit simulation, program language parsing and compilation, and a server for games with network play.

Evaluation

We evaluate your understanding of the material through the assigned work you submit, a mix of exams, labs and quizzes, homework, and programming projects. Below is a rough breakdown of how each kind of assignment will be weighted to determine your final grade for the course:

You will write a number of computer programs throughout the semester. Your code is expected to compile and execute correctly in the course’s virtual machine, independent of any IDE, to receive any credit.

Students are normally expected to take the midterm exams, quizzes, and the final exam at their designated times. These will not be given at alternate times unless there are truly extenuating circumstances. If a student anticpates an absence, say due to some special extra-curricular opportunity or some major health problem, they should contact an instructor as soon as possible, preferably at least one week in advance of that day.

Students eligible for disability accommodation should contact the instructor in advance also. They should of course be able to provide college documentation for the accommodations requested.

Participation in laboratory sections is optional, but we require that you make an earnest attempt to complete every weekly lab exercise. Labs are an opportunity to ask us or your fellow students questions, to collaborate in programming teams, and to learn the material hands-on. Working on them will help you keep up with the material of the couurse.

Homework and project work should be handed in on time, otherwise you risk getting no credit. We do give some partial credit for homework exercise solutions that are handed in shortly after the due date. The scoring is roughly thus:
• Up to two days late: maximum possible score is 80%.
• Up to four days late: maximum possible score is 60%.
• Up to a week late: maximum possible score is 40%.
If you have extenuating circumstances preventing your completion of an assignment, contact us to arrange for an extension.

Support

This class can be challenging, but the instructors are excited (and geared up) to help you learn the material. You are not alone! We encourage you to talk with us, seek help often if you need it, either at class meetings or in office hours. Though we do have to evaluate your work and give you a grade for the course, our goal is to help you master the material so that your work will be good. Start early. That way, should you struggle to complete an assignment, you’ll have plenty of time to seek our help. We are more than happy to offer it.

Not understanding the material when you first approach it is to be expected, otherwise you are not learning it! There is no shame in asking questions. We assign problems to challenge you, to make you puzzle things out, to provoke questions, to have you refigure or refine your knowledge, and to help reveal the less obvious aspects of what you are learning. Think of this as a collaboration between us and you. Leran to work with us when you’re figuring things out, be brave in that way. It’s what we get paid to do! We can help better as we get to know you better.

We’ve appointed several student experts with past experience in CS2 as teaching assistants and tutors for the class. We encourage you to attend the evening tutoring sessions (in Library 387, see the schedule) and maybe also seek one-on-one tutoring provided by Student Life. See the DoJo pages for details, including the drop-in tutoring schedule.

As a student you may experience all sorts of things that may be barriers to learning and to accomplishing your studiers. Strained relationships, anxiety, alcohol/drug problems, feeling down, difficulty concentrating, lack of motivation— these are a common enough part of some students’ college experience. These can be stressors and can certainly diminish your academic performance, as well as get in the way of a having healthy and rich intellectual and social life here. Reed College is committed to advancing the mental health and well-being of its students. If you or someone you know is feeling overwhelmed, depressed, or in need of support, services are available with the Office for Student Life, including a broad range of confidential mental health services available on campus.

Honor System and Collaboration Policy

We assume that each of you is honorable and will abide by the Honor Principle. Unless provided to you by the instructor, you may not look at assignments, exams, or solutions from previous instances of this class. Nor can you look at similar assignments, exams, or solutions that you can find on the Internet or elsewhere. You may use the Internet to look up compiler errors and how to use different programming language libraries and functions, but you may not use the Internet to look up how to solve specific problems you have been assigned. If you have questions about this, please ask the course staff. You may not receive assistance on assignments from any students who are not serving as staff (e.g. tutors) associated with this course, and you must follow the corresponding collaboration policy for working with students enrolled in this course.

For lab assignments, you may be assigned a programming partner (or partners). Pair or team programming involves two or several programmers working together on a single piece of source code, interacting to arrive at a single solution. One person might be put in charge of editing, while another is reviewing that work, looking for errors or suggesting refinements, and everyone in the collective is brainstorming about what coding needs to be done next. Roles should switch (say, who is typing) from exercise to exercise, or even within an exercise. When completed, it’s important that everyone understand the completed solution. Should one person have a better sense of what was just done, it is their responsibility (and usually a fun challenge) for them to explain it to their partner(s).

For other assignments, the collaboration policy will be stated on each assignment. For many assignments, you will be allowed to work with other students in the class on the problems according to the “empty hands” policy. This policy states that you must each tear up all notes, delete code, or discard recorded material created while discussing the problem with those students PRIOR to beginning to write up the solution you intend to turn in. You may not discuss the problem again once any of you has started writing up your solution. Other assignments will limit the level of collaboration permitted. Failure to comply with each assignment’s collaboration policy will be treated as an honor principle violation.