Course Syllabus
Computer Science 12

Programming Methods in C

Fall 2008

Course Description

CS 12 is a second course in C programming within a Unix environment. Instruction and programming assignments focus on a selection of fundamental data structures and algorithms. Practice implementing and applying these data structures and algorithms is required for the course.

Pre-requisites

• Required: Computer Science 5 or 10 or Engineering 3.
• Assumption: most students have taken Engineering 3, and therefore begin the course with a working knowledge of both C and Unix.
• Restrictions: not open for credit by Computer Science majors or pre-majors, and not open for credit to students who have completed Computer Science 11C, 22 or 60.

Course Goals

1. Students expand their knowledge of the C programming language and Unix tools, and gain confidence in using them.
   
2. Students learn to implement and apply abstract data types, including linked lists, stacks, queues, binary trees and tables.
   
3. Students learn basic complexity analysis, and how to distinguish algorithms and data structures on the basis of efficiency.

Dr. C. Michael Costanzo, mikec@cs.ucsb.edu
Office hours: Monday 12-12:50 and Wednesday 9-9:50, Phelps 1409B (enter through 1413)

Teaching Assistant

David Johnson, davidj@cs.ucsb.edu
Office hours: Thursday 11am-1pm, Phelps 1413

Instruction Schedule

• Lectures - 3 per week - MWF 11-11:50, Bldg. 387 room 103
• Discussion - 1 per week - F 10-10:50, Phelps 1440

Required Texts

• Thomas A. Standish, Data Structures, Algorithms & Software Principles in C, Addison-Wesley, 1995.
• Brian W. Kernighan, and Dennis M. Ritchie, The C Programming Language: Second Edition, Prentice Hall, 1988.

Grading Policy

• 24 percent - homework (mostly programming) assignments
• 20 percent - first midterm exam - Monday, October 20 (unless announced otherwise)
• 20 percent - second midterm exam - Monday, November 10 (unless announced otherwise)
• 36 percent - final exam - Friday, December 12, 12:00-1:30pm (just 1.5 hours, not 3)

Course Outline and Required Reading (Standish text unless noted; KR is Kernighan-Ritchie text)

• Review of key C constructs - KR chapters 1-4
• Focus on C pointers and structures - chapter 1, and KR chapters 5-7
• Introduction to linked data structures - chapter 2
• Abstract data types, and C modules - chapter 4 - note ch. 4 before 3
• Recursion - chapter 3
• Software life-cycle issues - sections 5.1-3, 5.5, 5.7-8
• Introduction to algorithm analysis - chapter 6, exc. section 6.5
• Stacks and queues - chapter 7
• Lists - sections 8.1-3 and 8.5, and pp. 319-21
• Trees - sections 9.1-7
• Tables - chapter 11, exc. pp. 476-88
• Searching and sorting - pp. 180-4 and 241-6, and sections 13.1-5

Notes

• The course's web pages (http://www.cs.ucsb.edu/~mikec/cs12) are mandatory reading. Students are responsible for monitoring them throughout the quarter.
• Make-up exams can only be arranged at least 48 hours prior to the exam, and only in extraordinary circumstances (which do not include having other exams that day).
• Assignments must be completed, and correctly turned in on time for full credit - no exceptions, no extensions, no excuses.
• IMPORTANT: All of the work you turn in for CS 12 must be your own, personal work. The university's honor code will be strictly enforced, and we will use an automated system to detect plagiarism and collusion.