CES 202 - Advanced Computer Programming

Syllabus

Winter, 2014

Syllabus Index

• General Information
• What to expect from these courses
• What to expect from this course
• Ground rules [grading]
• Course mechanics

General Information

Catalog description

Extends the students’ skills in computer programming. Provides students with more sophisticated tools, esp. the ability to design and program in an object-oriented manner, debugging, and testing methods. Exposure to medium sized problems in programming is included. Prerequisites: a minimum grade of 2.0 in TCES 201.

What You Need to Know Beforehand

Students entering this course need mastery over the following:

• Ability to write moderate-scale programs in a high-level language used in computer engineering
• Ability to analyze basic problem types encountered in computer engineering contexts
• Ability to specify a program design able to provide solutions to these problem types

What To Expect From the Computer Programming Sequence of Courses (201, 202, & 203)

The overall objective of this sequence of courses is to get you ready for the many problem solving situations in computer engineering that involve general purpose programming in a high-level language. In the third course you will learn oneor more object-oriented languages as well as the basic language (C) that will prepare you for most of the courses ahead in CES.

By the end of the sequence you should be able to write fairly large programs (> 1,000 lines of code) starting from a functional description (or requirements, telling what the program should do). You will learn how to generate functional specifications (specifying HOW the program will meet its functional requirements), external and internal documentation, and program design and implementation.

What To Expect From 202

In this course we shift focus from learning basic syntax and semantics of the language to the larger issues of engineering and design of programs. This shift will begin with a review and extension of our understanding of pointers and abstract data types (ADTs), started in 201.

The fundamental issues in advanced programming revolve around data structures and algorithms design and implementation. A data structure is the organization of a body of data in memory (main memory and external - disk). In an ADT we focus on the algorithms for accessing and manipulating the data in a structure according to an abstract model of what that data is. In both data structures and algorithms our concerns will turn to efficiency and effectiveness. There is a constant tradeoff between time and space efficiency when designing ADTs. Time efficient algorithms and space efficient data structures are the goals, but many times it is necessary to trade time and space off for an optimal overall solution. We will see numerous examples of this.

We will start with traditional, and well understood examples of ADTs and their implementations so that you achieve two objectives. First you will learn an armamentarium of techniques that you will be able to use in most design situations. You will need only recognize the nature of the problem you are trying to solve and then recognize which of these techniques applies most appropriately. The second objective is that you will learn how to think about these design issues so that when you encounter a problem that doesn't quite fit the models you know, you will be able to analyze the problem and devise an ADT approach that will provide an optimal solution.

One of the most commonly used ADTs for computer systems engineering is the TABLE, or lookup table. A table is defined as a list of data elements (usually but not always a set) that is extensible (i.e. can be added to) and searchable (i.e. data can be found using a key). Typical examples include the phone book, IP addresses in a DNS server, and databases. There are many ways to implement a table ADT. There are naive ways to do it that are relatively quick to do but do not have good performance if scaled up to large sizes. And there are sophisticated ways that involve more work to develop but are highly scalable. We will be investigating not only how these various implementations are accomplished, but what the time and space complexity issues are that guide their proper uses. [NOTE: These approaches are also covered in TCSS321/322 to some degree.]

Another very useful ADT is called a MAP. A map is a tool for translation from a domain to a range. It turns out that very often a map can be implemented with a table ADT! But we will explore the uses of maps as they relate to translation, not just lookup.

Both of these ADTs can be implemented using non-abstract data structures such as arrays, linked-lists, trees, hash tables, and graphs. We will focus on the first three of these and show how they are useful in producing table and map based applications. In 203 we will look at the latter two and see some interesting applications involving them.

This course will prepare you to understand true Object-Oriented Programming (OOP) to which you will be introduced in 203 in the form of C++ and Java. By the end of 203 you will be prepared to tackle any and all of the engineering programming problems you will encounter in multiple languages.

Student Learning Goals

In addition to the knowledge aspects of programming discussed above, the overall learning goals for students include being able to:

• Demonstrate an understanding of multiple programming styles (paradigms) and when each is appropriate for engineering designs
• Demonstrate an understanding to the architecture and development tool chain of a procedural language used in engineering design and implementation
• Describe and design complex data structures as abstract data types with basic operations defined on those structures
• Describe the basis of OOP in the ADT concept
• Demonstrate an ability to implement ADTs as object modules
• Demonstrate an ability to use object modules in multi-module applications
• Demonstrate mastery of an integrated development environment (IDE) tool for developing complex programs
• Demonstrate skills in debugging programs involving memory management
• Demonstrate knowledge and skills in implementing various levels of testing

Learning Outcomes

Learning outcomes are the capabilities that you will acquire here and take with you into the workplace. They are program-specific learning outcomes reinforced in most of the other courses. These and many more are developed in all of your courses in the CES program. The ones that we will focus on in this class are:

• an ability to apply knowledge of computing and mathematics appropriate to the discipline;
• an ability to analyze a problem, identify and define the computing requirements appropriate to its solution;
• an ability to design, implement and evaluate a computer-based system, process, component, or program to meet desired needs.

Ground Rules

Grades

Grades will be based on a percentage of total points acquired through a variety of exams, in-class assignments, programming assignments and possibly quizzes.

Assessment of Learning Objectives

• Weekly programming assignments (6 to 8 weeks of course) – 25%
  • In-class exercises, many of which will require completion at home
• A multi-staged programming project to integrate their previously learned skills (six weeks) – 30%
  • Two week stages (3 stages) with each stage graded. Each subsequent stage will offer the student an opportunity to improve and receive retroactive points.
• Two midterm exams covering concepts – 25%

  These exams will be given in two parts. The first hour will be comprised of a written part. The second will be a programming test in which you will be asked to write code that compiles and works properly.

  • Basic understanding of ADTs and their implementation with advanced programming constructs
  • Analysis of time and space efficiencies
• Final exam (two parts: 1) written knowledge and 2) problem solving ability through programming (not necessarily on the computer) – 20%
  • Advanced problem solving concepts (how to apply programming constructs and data structures to specific problem descriptions)
  • Demonstrate an ability to devise a suitable solution to a problem with a short program

Topics Covered

• Complex data structures implemented in a procedural language
• Abstract data types (ADTs), operations and composition
• Modular programming, object modules and libraries
• Object oriented design (from ADTs) – encapsulation, inheritance, and polymorphism
• IDE programming and project management
• Advanced debugging and unit testing

Target Schedule

This schedule will be refined and posted on the Moodle site. Please refer to that site often as subjects may change based on class progress.

• Introduction — Design and coding discipline (importance of)
• Review — Modular programming, code reuse, libraries
• Basic debugging using gdb, examples
• Pointers and dynamic allocation, memory models, the ‘this’ pointer - project overview
• TABLE ADT and implementation approaches (double linked list examples)
• Advanced pointer uses and constructing TABLEs. Pointers to functions
• MAP ADT and implementation approaches
• Sorting and searching tables and maps - binary search on arrays
• Trees and efficient ADTs
• Integrated Development Environment - programming and debugging tools and uses
• Testing methodologies
• Methods of inheritance and polymorphism using void pointers; generic container classes

Test make-ups

Academic Honesty

You should feel comfortable discussing topics, including general approaches to assignments, in a collaborative atmosphere. Discussing concepts and methods to be applied to problems is often a tremendous aid to studying. But when it is time to sit down and write down answers or program code, you should work on your own.

Course Mechanics

Lectures

In this class lectures are short talks to cover principles regarding language constructs and programming practices. They will be followed by exercises (some graded, some not) so total lecture time is kept short compared with practice time. However, based on the subject matter times can vary.

Attendance is not mandatory. However, there will be graded exercises on occassion during classes and if you miss these and do not have a medical or other legitimate excuse you will not be able to make them up.

Office Hours

I maintain regular office hours (see above), but have a general open door policy. If my door is open (even if only cracked open) I am in and willing to take walk-in visits. If my door is closed, even if you know I am in my office, I am not available at that time, so please do not knock.

I sincerely encourage all students to drop by several times during the quarter even if you don't have a specific problem or question. It is good to get to know one another. But if you are having problems you need to come see me for certain. Don't be shy. I really don't bite.

Moodle Web Site

Currently we use Moodle for course management (https://moodle.insttech.washington.edu/). Please be sure to check in frequently as most information on the course and all assignments will be made through that site.

There will also be a collaborative forum set up for students to participate with questions and answers as well as sharing interesting programming information and web site links. You are encouraged to use this forum for communications outside of class time.

Grader

The homeworks, programs and exams will be graded by a qualified grader under my supervision. Generally the grading is fair and complete, but occasionally a student will have a question or problem with how their answer(s) was handled. In such cases you should first try to get an explanation from the grader (office hours will be announced). If you are not satisfied with that answer, by all means bring it to me for clarification or adjudication as needed.

Textbook Resources

The C Programming Language, Brian W. Kernighan, Dennis M. Ritchie

Support for students with disabilities

Institute Resources

• Lab Facilities
• Mentors web site for information about when the mentors are in the labs and other information. A word of caution however. Most of the mentors are Java proficient but not many know C so you would be advised to not seek mentor help unless you know for sure that the mentor is a C programmer. In truth, I would prefer you try to get ahold of me for problems.

---