ECS30-A: Introduction to Programming and Problem Solving, Fall 2008

Lecture:

6 Wellman, MWF 10:00am - 10:50am

Discussion:

Sec.30-A01, M 4:10-5:00pm, 115 Hutchinson

Sec.30-A02, F 1:10-2:00pm, 176 Chemistry

Sec.30-A03, R 8:00-8:50am, 1006 Giedt

Professor:

Zhaojun Bai, 3005 Kemper Hall, 752-4874, bai@cs.ucdavis.edu

Office Hours: MWF 11:30-12:30 or by appointment

Teaching Assistant:

Stanley Tzeng, stzeng@ucdavis.edu

Office hours: M 1:00-3:00pm and W 4:10-5:10pm, 53 Kemper

Matthew Lietzke, mjlietzke@ucdavis.edu

Office hours: T 3:30-5:00pm and R 4:10-5:40pm, 53 Kemper

Webpage

Textbook :

Hanly, Jeri R., and Koffman, Elliot B, Problem Solving and Program Design in C, 5th ed., Addison Wesley, 2007, ISBN-10: 0321409914, ISBN-13: 9780321409911

Course objectives:

learn how to use Unix operating system tools to develop and debug programs, develop expertise in using C programming language, understand the process of writing efficient and robust programs to solve problems.

Course Outline

• Unix tools, including vi, make, and gdb, to develop and debug programs
• Algorithms: general concept, development of efficient algorithms.
• Programming in C
  • Scalar data types, concept of data type, standard and user-defined scalar types.
  • Simple Statements, arithmetic and boolean expressions, assignment statements, simple input and output statements.
  • Flow of control, repetitive statements, conditional statements, unconditional branching
  • Data structures: single and multidimensional arrays; character strings; structs.
  • Functions: general concept; declaration and calls; & and * operators; parameters; introduction to recursion.
• Software engineering: running, debugging, testing programs, building quality programs.

Prerequisite

Math 16A or 21A (may be taken concurrently); prior experience with basic programming concepts recommended.

Homeworks and Exams:

• There will be about 8 program projects/homework assignments.
• Written homework must be submitted in Room 2131 by 4pm on the date due.
• Programs will be submitted using the handin facility of Unix. Programs will be due at 11:50pm on the date due.
• No late homework will be accepted!
• All exams are closed-book, no notes allowed.

Grading:

Grading breakdown:

• Programming projects (homework): 35%
• Two midterm exams: 40%
• Final exam: 25%

Regrading is only considered within one week (7 days) from the date return. The request must be submitted in writing.

On-line Info/Discussion:

• Class webpage: http://www.cs.ucdavis.edu/~bai/ECS30
  class annoucements, assignments and notes will be posted on this site.
• Course questions and discussions should be posted to the ucd.class.ecs30.sec-a.d newsgroup at the URL http://news.ucdavis.edu (web-based news reader)
• E-mail to Instructor/TAs should only be regarding personal matters.

Distribution list

1. 9/26
   • Introduction and logistics

   • Norman Matloff's toturial page: Read, at least,
     1. `if you have no Unix background at all'
     2. `The Unix file system'
     3. `Extremely quick and simple introduction to the Vi Text editor'

   • Work your way through Sean Davis' ECS30 Unix tutorial and vi tutorial

   • Everyone who is enrolled should have a computer account set up for using computers in the CS Instructional facility (CSIF) in the basement of Kemper Hall. Go to the CSIF lab to look up your user name. Your initial password is the last 8 digits of your student ID. If you want to change your password, and you should want to, read the man file for the Unix command yppasswd (type man yppasswd), to learn more about the command. Help is available in room 47 for using the labs. Note that this help is for using the labs, not help with CS 30.

   • You may also log into the CSIF machines remotely (see UCDAVIS Computer Science at Home). Or you can work on any other machine that has Unix, and a C compiler for writing C programs, and internet access.

   • Note: Different systems (operating systems, computer type, configurations, libraries etc.) can behave differently, so a C program written on one machine and system might not behave exactly the same on a different machine or system (an ugly reality!). You may find it more convenient to do most of your work at home, or in another lab, BUT before handing in your program, you must make sure it works correctly on the machines in the CSIF. Those are the machines we will use when we compile, run and grade your programs. If your programs don't run correctly there, it will not matter to the grader that they ran correctly elsewhere. It is your responsibility to port your programs in time to the CSIF and test them there. It will not be a legitimate excuse that the connection to the CSIF was down just before the assignment was due. Also, we (Instructors and the TAs) can only give very limited help on problems you encounter on machines and systems outside of the CSIF, and how to set up the software to work at home, or connect to the CSIF remotely. Campus IT staff and the CSIF staff can also help somewhat on those issues if you run into problems.

   • Unless stated otherwise, all assignments are meant to be done individually. Of course you can discuss some aspects of the assignment with others, but each student is expected to individually work out assignments. If you have any questions about the degree of individuality that is expected, please ask. We may routinely run all the submitted homework programs through a utility that finds pairs of programs that are ``too similar". We really don't like dealing with such a situation, so please design and write your programs yourself. Also, you will learn much more that way, and be better prepared for exams.

   • Discussion sections in the first week of 9/29-10/3 will be held in the CSIF Computer Lab (room 67). After the first week, all the discussion sections will be held in their scheduled classrooms.

   • Learning C requires learning a great number of exacting details and you will not get your C programs working unless you learn those details. However, in the long run, what is of value is learning how to think like a programmer, how to organize your thoughts in a way that can be translated into a computer program, and how to debug and verify the correctness of your program. Those skills will be emphasized in this class - to large extent, you will teach yourselves the details of C, and I will teach you how to think like a programmer.

   • Software development method (section 1.4)
     1. Understanding and specifying the problem requirements (problem)
     2. Analyze the problem (analysis)
     3. Design the algorithm to solve the problem (design)
     4. Implement the algorithm (implementation)
     5. Test and verify the completed program (testing)
     6. Maintain and update the program (Maintenance)
     7. Caution: Failure is Part of Process

2. 9/29
   • Lecture; C language elements, section 2.1
   • The following programs were discussed in the class:
     hello.c,
     miles2kilos_v1.c
   • Homework #1, due October 6, 4:00pm, Room 2131 Kemper Hall

3. 10/1
   • Lecture notes by Professor Felix Wu
   • Sorry, Professor Bai will be out of office today, so will not have office hour today

4. 10/3
   • Lecture/reading: Overview of C, data types, executable statements, arithmetic expressions, interactive/batch/data-file mode (sections 2.2 - 2.7)
   • The following programs were discussed in the class:
     coins_v1.c (interactive mode),
     miles2kilos_v2.c (batch mode)
     coins_v2.c (batch mode)
     miles2kilos_v3.c (data-file mode),
     
   • Self-check exercise: rewrite the program coins_v2.c in a data-file mode (similar to miles2kilos_v3.c)
   • Homework #2,
     due October 13, 4:00pm (Written), 2131 Kemper, and 11:59pm (programming), handin cs30a p1

5. 10/6
   • Lecture/reading: Functions, Chapter 3
   • The following programs were discussed in the class
     quadroots.c (use C math lib. functions),
     trisidelength.c (use C math lib. functions),
     stickfigure.c (void function without arguments),
     scale.c (function with input arguments and a single output)
     
   • Homework 1 due today, homework box is located at Room 2131 Kemper Hall
   • Starting the week of Oct. 6, the discussion sections will be held in their originally scheduled classrooms, not in the CSIF computer labs.
   • The first midterm is on October 20, Monday

6. 10/8
   • Lecture/reading: Selection, the if statement (sections 4.3,4.4 and 4.6)
   • The following programs were discussed in the class
     quadroots2.c (if statement),
     waterbill.c (if statement),
     tax.c (multi-alternatives),
     

7. 10/10
   • Lecture/reading: more on conditions and if statement (section 4.2)
   • The following programs were discussed in the class
     danglingelse.c (the ``dangling else'' problem),
     conditioneg.c (conditions)
     logicalassign.c (logical assignment)
     
   • homework 2 due next Monday, Oct. 13
   • Homework #3 (pdf file)
     Due October 20, 4:00pm (Written), 2131 Kemper, and 11:59pm (programming), handin cs30a p2

8. 10/13
   • Lecture/reading: the switch statement (section 4.8)
     Repetition and loop statements (Chapter 5)
     The while statement (section 5.2)
   • The following programs were discussed in the class
     grade.c (nest-if ==> switch),
     shipclass.c (switch),
     date.c (switch),
     squareroots.c (while loop),
     sum.c (while loop),
     payroll.c (while loop),
     
   • homework 2 due, handin cs30a p1

9. 10/15
   • Lecture/reading: the for loop (section 5.4)
   • The following programs were discussed in the class
     squareroots2.c (a variation of ``squareroots.c'', use for-loop),
     factorial.c (for-loop),
     incdecops.c (illustrate the side-effect of increment and decrement operators),
     cel2fah.c (for-loop)
   • Practice midterm #1 html file or pdf file.
   • Question: where to find the keys for homeworks/programs?

10. 10/17
    • Lecture/reading: the do-while loop (section 5.8)
    • The following programs were discussed in the class
      squareroots3.c
      numdigits.c
      getint.c
      
    • Brief review for the midterm #1
    • My office is from 11--12, instead of 11:30--12:30 (today only).
    • I am offerning an extra office hour to discuss the practice midterm today starting from 5:30pm to about 6:30pm.

11. 10/20
    • Midterm 1 (50 min.)
    • Homework 3 due
    • Homework grades and TA's homepage can be found

12. 10/22
    • Lecture/reading: (1) recap of loop statements (chapter 5 review)
      (2) functions with multiple results (section 6.1)
    • Chap.5 Review and sample programs: forloop.c, fornegloop.c, senvalloop.c, eofloop.c, dowhileloop.c,
    • The following program were discussed in the class
      separate.c(functions with multiple outputs), (vs. scale.c in Lecture #5, 10/6)
    • Homework #4
      Due October 29, 11:59pm, handin cs30a p3

13. 10/24
    • Lecture/reading: more on functions with multiple results (sections 6.1 and 6.2)
    • The following program were discussed in the class
      separate.c,
      sum_n_avg.c,
      sort.c,
      
    • Note: use Ctrl-N as sential value, sample test.c (helpful for Homework #4)

14. 10/27
    • Lecture/reading: modular programming (sections 6.4 and 6.5)
      use makefile to managing modularity
    • The following program were discussed in the class
      main.c and its subprograms
      scan_fraction.c,
      get_operator.c,
      add_fractions.c,
      multiply_fractions.c,
      find_gcd..c,
      reduce_fraction.c
    • Makefile (update version)
    • Homework #5 , due Nov. 5
      

15. 10/29
    • Lecture/reading: discussion on makefile, Makefile
      Types (chapter 7)
    • Notes
    • The following program were discussed in the class
      sizeof.c
      posnumrange.c
      inaccuracy.c
      

16. 10/31
    • Lecture/reading: More on Types (chapter 7)
    • Notes on Types(updated)
    • The following program were discussed in the class
      col_seq.c
      length.c (getchar())
      length2.c
      expenses.c (enumerated type)

17. 11/3
    • Lecture/reading: (1) More on types, (2) Function parameters (section 7.4), (3) Arrays (Chapter 8)
    • Notes on Arrays
    • The following program were discussed in the class
      week_hours.c (enumerated type)
      eval_fun.c (function parameter)
      bisection.c (application of function parameter)
      array1.c (arrays, basics)
      mean.c (arrays, basics)
    • Extra office hour: 5:30 - 6:30, Room 3005 Kemper Hall

18. 11/5
    • Lecture/reading: Arrays (Chapter 8)
    • Notes on Arrays (updated)
    • The following program were discussed in the class
      fill_array.c
      fill_array2.c
      maxmin.c
      get_max.c
      add_arrays.c
      
    • The array search and sort will be discussed more on Friday's lecture
      search.c
      select_sort.c
      
    • homework #5 due
    • Homework #6 , due Nov. 12
      

19. 11/7
    • Lecture/reading: Arrays (Chapter 8)
    • Notes on Arrays (updated)
    • The following program were discussed in the class
      search.c (problem solving)
      select_sort.c(problem solving)
      add_matrices.c(multidimensional arrays)
      

20. 11/10
    • Lecture/reading: Strings (Chapter 9)
    • Notes on Strings
    • The following program were discussed in the class
      strings.c (string declaration and initialization)
      courses.c (string reading and writing)
      names_ages.c (2-d string)
      strings2.c (Using string lib functions: strcpy, strlen)
    • More examples: strings3.c components.c, strings5.c
    • Practice midterm #2
    • Today: extra office hour starts at 5:00, Room 3005 Kemper Hall
    • Message from Cindy Kwok, peer advisor in College of Engineering: for tuturing service go to the 1050 Kemper Hall or email engrapa@ucdavis.edu for further information.

21. 11/12
    • Lecture/reading: Strings (Chapter 9) -- scanf vs. gets
    • Notes on Strings (updated)
    • The following program were discussed in the class
      lineinput_scanf.c (line scanning, ``whitespace'' issue)
      lineinput_gets.c (full line scanning)
    • Short review for midterm 2
    • Homework #6 due today

22. 11/13, Thursday
    Extra office hour (review session for midterm #2) starts at 5:00pm, 3005 Kemper Hall

23. 11/14
    • Midterm 2 (homeworks 4, 5, 6)
    • Homework #7 (see pdf file for better format), due Nov. 21
      

24. 11/17
    • Lecture/reading: Strings
    • Notes on Strings (updated)
    • The following program were discussed in the class
      components.c (substring copy)
      strings6.c (string comparison, and ordering)
      alphaorder0.c (string comparison and ordering using array of pointers)
      alphaorder.c
      

25. 11/19
    • Lecture/reading: Strings. Recursion (Chapter 10)
    • Notes on Strings (updated)
    • The following program were briefly discussed in the class
      scanline1.c (getchar, putchar)
      scanline2.c (same function as scanline1.c, but uses char *)
      
    • Notes on Recursion
    • The following program were discussed in the class
      multiply.c (multiply_trace.c)
      factorial_rec.c (factorial_rec_trace.c)
      fibonacci.c

26. 11/20
    Extra office hour starts at 5:30pm, 3005 Kemper Hall

27. 11/21
    • lecture/reading: Recursion (Chapter 10)
    • Notes on Recursion (updated)
    • The following program were discussed in the class
      gcd_rec.c
      select_sort_rec.c
      rev_input_words.c
      towerhanoi.c (classical example)
    • More examples: char_count.c, find_caps.c
    • Homework #7 due,
    • Homework #8 (Part A) (pdf file) (on recursion)
      due December 3, handin cs30a p7

28. 11/24
    • lecture/reading: Structure Types (Chapter 11)
    • Notes on Structure Types
    • The following program were discussed in the class
      struct1.c
      struct2.c
      struct3.c
      struct4.c
      
    • Homework #8 (Part B) (pdf file) (on structure types and dynamic memory allocation)
      due December 3, handin cs30a p7
    • Note: This is the last homework assignment. we have not discussed the concept of dynamic memory allocation in the class yet. I posted it just for those students who like to work on it over the upcoming holiday break.

29. 11/26
    • Lecture/reading: Structure Types (cont'd), and dynamic memory allocation (sections 14.1 and 14.2)
    • Notes on Structure Types (update)
    • The following program were discussed in the class
      struct4.c
      timeupdate.c
      complexarithm.c (only partially done, one of your homework assignments is to complete it).
      array_dyn.c (intro. to dynamic memory allocation, more on Monday, Dec. 1)
      
    • Practice final problems on strings, recursion, structure types and dynamic memory allocation.

30. 12/1
    • Lecture/reading: dynamic memory allocation (sections 14.1 and 14.2)
    • Notes on Dynamic memory allocation
    • The following program were discussed in the class
      array_dyn.c (use malloc) (vs. array.c)
      array_dyn2.c (use calloc)
      select_sort_dyn.c
      string_dyn.c (use malloc)
      string_dyn2.c (use calloc)
    • Practice final problems on strings, recursion, structure types and dynamic memory allocation.

31. 12/2 TA Office hours 3:30 - 5:30

32. 12/3
    • Lecture/reading: dynamic memory allocation and Final Review
    • Notes on Dynamic memory allocation
    • examples: alphaorder_dyn.c, struct_dyn.c, array2d_dyn.c
    • Office hours: 11:30-12:30 (Prof) and 4-5 (TA)
    • Homework #8 (Parts A and B) due

33. 12/4 Discussion 8-9, TA Office hour 4 - 5:30

34. 12/5
    
    • Final review, notes
    • Review of Midterms 1 and 2
    • Practice final problems on strings, recursion, structure types and dynamic memory allocation.
    • office hour 11:10 -12:30,
      
    • Discussion 1-2

35. 12/6 (Saturday)
    Extra Office Hour and Review, 1:00 - 3:00, 1131 Kemper Hall

36. Final: December 8, 8:00-10:00am, 6 Wellman

1. Homework #1
2. Homework #2
3. Homework #3
4. Homework #4
5. Homework #5
6. Homework #6 pdf file.
7. Homework #7 pdf file.
8. Homework #8 (Part A) (pdf file)
   Homework #8 (Part B) (pdf file)
   

9. Tutorial on gdb. Learn the basics of the gdb debugger and debugging. At a minimum learn how to list, execute one line at a time, set and unset breakpoints, print variable values. The use of a debugger is often essential. gdb is available on most unix based systems. ddd is a GUI based on gdb. Use it if you have it.