This course is the first of a two-course sequence that introduces students to realm of computing and teaches them how to use computers effectively in problem solving. Student will learn how to formulate data and procedural abstractions, and apply basic problem solving strategies and techniques to problems from different domains. Students are automatically enrolled in the accompanying lab section, in which students will get practical hands-on experience with the material covered in the lecture.
Harold Abelson and Gerald J. Sussman with Julie Sussman, Structure and Interpretation of Computer Programs, McGraw-Hill, 1996, 2nd Edition.
Available online at http://mitpress.mit.edu/sicp/
E-mail: mscheutz@cse.nd.edu
Office: 351 Fitzpatrick Hall, Phone: 1- 3053
Office hours: M, 3 p.m. - 6 p.m. and by appointment
| Paul Schermerhorn | Scott Christley |
|
| Email: | pscherm1@nd.edu | schristl@nd.edu |
| Office: | 355 S Fitzpatrick Hall | 206 Cushing Hall |
| Phone: | 1-8380 | 1-7596 |
| Office hours: | M, T before/after the lab and by appointment | By appointment only |
|
Monday
|
Tuesday
|
Wednesday
|
Thursday
|
Friday |
Lab
|
|
7 - 11 p.m.
|
7 - 11 p.m.
|
7 - 11 p.m. |
7 - 11 p.m.
|
3 - 6 p.m. |
Fitzpatrick
|
131 DeBartolo Hall
MWF 9:35 a.m.- 10:25 a.m.
177 Fitzpatrick Cluster
CSE 211L 01: M 3:00 p.m.- 3:50 p.m. (13 students max.)
CSE 211L 02: M 4:05 p.m.- 4:55 p.m. (13 students max.)
CSE 211L 03: T 2:30 p.m.- 3:20 p.m. (13 students max.)
CSE 211L 04: W 3:20 p.m.- 4:20 p.m. (13 students max.)
This course introduces fundamental techniques of programming as a foundation for more advanced study of computer science. Considerable attention is devoted to developing effective software engineering practice, emphasizing such principles as design, decomposition, encapsulation, procedural abstraction, testing, and software reuse. Topics include standard programming constructs problem-solving strategies that emphasizes algorithmic strategies over syntactic detail. The primary aim of this course is to develop the student's problem solving abilities, while introducing various aspects of programming languages (object-oriented programming, parallel programming, language design, etc.). By using a simple and elegant language (such as SCHEME) the student will be able to concentrate on the methodologies and modes of thinking about the development of complex systems.
EG 111/112
Procedural abstraction: simple functions; parameters and results; composition; conditional expressions
Recursion: the concept of recursion; recursive specification of mathematical functions (including inductive definitions); simple recursive procedures, mathematical functions (such as factorial and Fibonacci); simple recursive procedures (Towers of Hanoi, permutations, fractal patterns); implementation of recursions
Data abstraction: list structures; hierarchical data; symbolic data; the importance of data abstraction
Algorithms and problem-solving: problem-solving strategies; the role of algorithms in the problem-solving process; implementation strategies for algorithms; debugging strategies; the concept and properties of algorithms (brute-force algorithms; greedy algorithms; divide-and-conquer; backtracking; numerical approximation algorithms
Object-oriented paradigm: object-oriented design;encapsulation and information-hiding; separation of behavior and implementation; classes, subclasses, and inheritance; polymorphism; class hierarchies; collection classes and iteration protocols; fundamental design patterns
Basic computability theory: tractable and intractable problems; the existence of noncomputable functions
Basic computational complexity: asymptotic analysis of upper and average complexity bounds; big-O notation; standard complexity classes; empirical measurements of performance
Overview of programming languages: history of programming languages; brief survey of programming paradigms; the role of language translation in the programming process
Fundamental programming constructs: syntax and semantics of a higher-level language; variables, types, expressions, and assignment; simple I/O; conditional and iterative control structures; functions and parameter passing; structured decomposition
Evaluation strategies: representing computation state; streams; lazy evaluation; nondeterminism; the construction of an interpreter
Software development methodology: Fundamental design concepts and principles; structured design; testing and debugging strategies; test-case design; programming environments; testing and debugging tools
Machine level representation of data: bits, bytes, and words; numeric data representation and number bases; signed and twos-complement representations; representation of nonnumeric data
Breakdown according to chapters (according to the Abelson and Sussman book):
Chapter 1: Building Abstractions with Procedures (9 lect.)
Chapter 2: Building Abstractions with Data (9 lect.)
Chapter 3: Modularity, Objects, and State (13 lect.)
Chapter 4: Metalinguistic Abstraction (10 lect.)
Breakdown according to topics:
|
Graphs and trees |
3 |
|
Fundamental programming constructs |
3 |
|
Algorithms and problem-solving |
2 |
|
Fundamental data structures |
6 |
|
Recursion |
5 |
|
Basic algorithmic analysis |
2 |
|
Algorithmic strategies |
2 |
|
Fundamental computing algorithms |
4 |
|
Basic computability |
1 |
|
Overview of programming languages |
1 |
|
Declarations and types |
1 |
|
Abstraction mechanisms |
2 |
|
Functional programming |
4 |
|
Concurrency |
2 |
|
Software design |
1 |
|
Software tools and environments |
1 |
|
History of computing |
1 |
The homework will involve programming assignments using the language SCHEME. All students need to have an account on the engineering computer cluster. All programming tools needed for the programming problems in this course will be made available on the cluster machines. The engineering cluster (i.e., the Sun SPARC architecture) is the only computing environment guaranteed to be supported for this course. Students who desire to work in other environments/architectures (i.e., PC under WINDOWS9x) may do so, but must also assume full responsibility for porting any necessary software, data, etc. to the other environment/architecture.
This course is conducted using the integrated online teaching support system WebCT (please, follow the link http://webct.nd.edu/ to obtain a student user guide for WebCT). This system serves as a general storage for all class related material and as a forum for all class related discussions. In particular, this syllabus, the table of contents, all lecture notes, the individual and group homework assignments, a course calendar (also available here), the class bulletin board, and much more is available online in WebCT. Every student in this class has a personal account in WebCT, which can be accessed immediately at http://webct.nd.edu/. In addition to the WebCT space, there is a course directory in AFS space at /afs/nd.edu/courses/cse/cse211.01/dropbox/ (also available at /usr/local/courses/cse/cse211.01/dropbox/) which will be used to turn in group assignments.
Laboratory Usage:
There will be a one hour laboratory meeting once a week, where students will get the chance to implement algorithms presented in the lecture and to do programming assignments that will be checked by the TA teaching the lab section then and there.
In addition to the lab section, where you can your TA questions about the course material, there will be scheduled cluster hours, where undergraduate teaching assistants are avaible to answer questions.
Grading:
The course will be graded on the basis of homework assignments from chapter problems and other sources, three short examinations after each of the first three chapters, and a comprehensive final exam. The following weights will be used to compute the final grade:
|
30%
|
Individual assignments |
|
25%
|
Group assignments |
|
5%
|
Participation and attendance |
|
15%
|
Short examinations |
|
25%
|
Final exam |
The following grade breakdown will be
used:
|
92 - 100 |
A |
|
89 - 91 |
A- |
|
86 - 88 |
B+ |
|
82 - 85 |
B |
|
79 - 81 |
B- |
|
76 - 78 |
C+ |
|
72 - 75 |
C |
|
69 - 71 |
C- |
|
62 - 68 |
D |
|
0 - 61 |
F |
This grading formula implies that there is no curve; your grade will depend only on how well you (and, to a small extent, your partners) do, and not on how well everyone else does. (If everyone does exceptionally badly on some exam, I may decide the exam was at fault rather than the students, in which case I will adjust the grade cutoffs as I deem appropriate. But I will never adjust grades in the other direction; if everyone gets an A, the better!).
There will be weekly individual assignments as well as 5 group assignments, which will be done in groups of five.
Individual assignments are intended to give you a chance to to practice the concepts presented in class in an effort to keep up with the class material (that's why they are assigned "weekly"). These assignments are available in WEBCT and must be turned in before the given due date/time (typcially F 6:00 p.m.), otherwise they will be considered "late". Note that "individual" here means that you are not allowed to discuss these assignments with anybody except your CSE 211 staff (see the section on academic honesty below).
Group projects are intended to cover a major course topic and enforce cooperative learning (see the next section). They are designed to let you "get your hands dirty" with computer problems, to introduce new topics, to fully develop concepts from lecture, and to test your mastery of the course material. They will also allow you to develop communicative skills necessary for future collaborative work (e.g., in industry or academia) and give you the opportunity to discuss and develop ideas together with other people (which often results in a "synergy effect"). Group assignments have to be turned before the indicated due date/time (typically F 6:00 pm.). Specifically, the SCHEME file with all the documented code for the project and a detailed list of the responsibilities of each group member has to be copied into the dropbox directory of the respective group in AFS space (you will get detailed instructions about how to turn in group assignments with your first group assignment). Occasionally, you will be asked to demonstrate your solution for a group project to one of the CSE 211 staff, in which case part of the grade for the assignment will be based on the demonstration. Be prepared to be asked questions about your solution (even about code of fellow group members, so make sure you understand the program in its entirety). Group projects will involve a significant amount of programming. Hence, do not wait until the night before a group assignment is due to start working on it, you won't be able to finish the assginment!
There will be three in-class quizzes (after chapters 1, 2, and 3 respectively) to ensure that you are able master the respective material.
Attendance is required for both the lecture and the lab section (and will be checked regularly). Missing classes without prior notification and documented reasons--vacation is not a reason--will lower your attendence and class participation grade (which is 5% of your overall grade!).
Make-up exams will be given only in extraordinary and documented circumstances!
Individual and group assignments may be turned in late, but a penalty of 20% per calendar day late (and fractions thereof) will be assessed without any exception (for group assignments, the whole group will be penalized)! Note that in order to turn in assignments late you will have to contact your TA (as in WEBCT the submission time will have expired, and in AFS the insert permissions will have been removed).
A quarter of the work for this course will be carried out in groups of five. This may be the first time in your college career that you have to work cooperatively in a group throughout the semester and it will be a change from the traditional approach in which students work competitively and in isolation. However, current educational research has shown that cooperative learning is an extremely effective means of learning.
One advantage of cooperative learning is that it allows the instructor to give very comprehensive (and very intense) assignments, from which you will learn a great deal. At the same time, the amount of individual work per student is kept at a reasonable level. Another advantage is that the students can understand new ideas by discussing them with other students. Even the "smartest" person in a group will learn a lot by discussing the material with other students. Most professors will tell you (and I certainly will) that they did not really understand their course material until they had to teach it. And, hopefully, all of you are here to learn as much as you can - not just to get by.
Also, working as a member of a project team is (in all likelihood) how you will work in real life. Learning how to do that well -- and how to work out the little inconveniences (scheduling, personalities, etc.) that come along with it -- is a valuable skill that you will be able to take with you into the world of work.
In this course there are no "drill and practice" exercises; every problem teaches a new idea. For example, a good question to ask about each exercise in is, "Why did they include this exercise in the book?" It is best if your group also discusses the problems together before you split up to work on individual exercises to make sure that everyone in the group understands the broad ideas of the assignment. Always keep in mind that the exams will be done individually.
If you split up the work, then be sure that your group meets to collect the results in time! If one group member fails to do the work, the entire group is responsible for ensuring that it gets finished. The ideal working arrangement is for the whole group to meet shortly after the assignment is available to plan the necessary subtasks, divide the work, set up a work schedule, and then get together again after everybody has finished their part to integrate the code fragments. You may need to resolve various problems in between. Email is usually a good first option, but sometimes it will be better and more efficent to meet and talk in person. Finally, before you turn in your solution, make sure that every group member knows how the solutions works and that everybody is in agreement with the summary of their contribution to the overall solution.
If some medical or personal emergency takes you away from your group for an extended period of time, or if you decide to drop the course altogether, do not just silently disappear. Inform the instructor and the other members of your group as soon as possible.
If there are discrepancies within a group as to the division of labor, etc., first attempt to solve them internally. However, if no solution can be found, see your instructor either individually or as a group. It is important that any issue that might disturb the productivity and general climate of a group be resolved as soon as possible as your grade will to some extent depend on the proper functioning of your group.
Learning cooperatively might seem to cloud the issue of academic honesty, but really it does not! The honesty issues relate to the group corporately. For instance, if a particular problem set includes a large number of written exercises, you may be tempted to simply divide them among the group members so that each of you does only two or three exercises. This is perfectly fine, as long as you get together after doing the individual work to discuss the results and to ensure that each member of the group understands every exercise (and could work it individually if necessary). (Recall that some problem sets may require a demonstration. Any member of your group may be asked any question at all about the problem set during that demonstration. Therefore, it will be to your advantage to teach each other about the material.)
Directly copying homework answers or computer code from another group or from any other external source (e.g., the web, solutions from previous courses, etc.) is not cooperative learning, rather it is cheating. When in doubt, ask the instructor.
Nobody begins the semester with the intention of cheating. Students who cheat do so because they fall behind gradually, and then panic at the last minute. Some students get into this situation because they are afraid of an unpleasant conversation with an instructor if they admit to not understanding something. I would much rather deal with your misunderstanding early than deal with its consequences later. Please, feel free to ask for help as soon as you need it.