ECS30-B: Introduction to Programming and Problem Solving, Winter 2009

Lecture:

  234Wellman, MWF 1000-1050

Discussion:

Sec.30-B01, T  0800-0850 147 Olsson

Sec.30-B02, W 1510-1600 1130 Hart

Professor:

Prem Devanbu, 3039 Kemper Hall, 752-7324,  devanbu@cs.ucdavis.edu

       

          (First name rhymes with "frame", last name with "Day Sun Blue").

Office Hours: M 1400-1600 

Teaching Assistant:

Michael Ogawa msogawa@ucdavis.edu

Office hours:  F 1340-1440,  Kemper 53

Kartik Pandit kdpandit@ucdavis.edu 

Office hours:  M  1230-1400, Kemper 53

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

Email & Newsgroup:

• Newsgroup: ucd.class.ecs30b newsgroup at the URL http://news.ucdavis.edu (web-based news reader). Students should post questions, responses and comments to ucd.class.ecs30b.d newsgroup. TAs and instructor will post to ucd.class.ecs30b
  
  
• Posting Policy:  All general questions related to curriculmum must be posted to the newsgroup. Only topics of a personal nature can be emailed to TAs or the instructor. Such emails should have "ECS30b" in the subject line. Emails not following these rules will probably end up in my SPAM folder, and may not be read.
  
  
• Class website: All announcements, assignments, etc will be posted here. READ THIS PAGE REGULARLY! Book mark http://www.cs.ucdavis.edu/~devanbu/teaching/30
  

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.

Midterm/Exam Schedule:

• First Midterm: January 28th, Wednesday
• Second Midterm: Feb 25th, Wednesday.
  
• Finals: W March 18 1030-1230
  

NO EARLY OR LATE OR MAKEUP MIDTERMS or FINALS. If this schedule doesn't work for you, please drop the class.

Distribution list

1. 1/5
   • 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

   • All enrolled students will now (or very shortly) 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.

   • 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.
     
     
   • Homework #1, due January 12th, written part, 4pm in 2131 Kemper, on line part, submitted using handin by 1155pm January 12th.
     
     
   • 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. 1/7
   • Lecture; C language elements, section 2.1
   • The following programs will be useful:
     trajectory.c (Discussed 1/7) hello.c,
     miles2kilos_v1.c

3. 1/9
   • Lecture notes
     
   • Example program used in class (prompt and read a value, and print it out).
     
   • To compile this program, put the text in a file, say, this1.c, and type in "gcc this.c -o this1". To run the resulting binary output, which will be in "this1", type in "./this1"
   • Concerning Assignment 1, a Student posted a question on the newsgroup asking about "relative and absolute paths" and also about "permissions" (making a file readable or writeable to all). Wikipedia has information on paths, and also has information about the chmod command, which can be used to change permissions.
   • 
     
4. 1/12
   • Lecture/reading: #includes, #defines, and types. sections 2.2 - 2.7)
   • Some example programs (material to be covered  1/14 & 1/16).
     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 Janunary 19th,  11:59pm, handin cs30b p1

5. 1/14
   • Lecture/reading: Batch mode,  (section 2) also Functions, Chapter 3
   • Example Programs:
     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)
     
   • Reminder: The first midterm is on Jan 28, W. 

6. 1/16
   • Lecture/reading: Selection, the if statement (sections 4.3,4.4 and 4.6)
   • Example Programs:
     quadroots2.c (if statement),
     waterbill.c (if statement),
     tax.c (multi-alternatives),
7. 1/21
   • Lecture/reading: more on conditions and if statement (section 4.2)
   • Example  programs
     danglingelse.c (the ``dangling else'' problem),
     conditioneg.c (conditions)
     logicalassign.c (logical assignment)
     
   • homework 3 due next Monday, Jan 26
   • Homework #3
     handin cs30b p3
   • 1/23
     
     
     
     

8. • 1/23 Lecture/reading: the switch statement (section 4.8)
     Repetition and loop statements (Chapter 5)
     The while statement (section 5.2)
     Example programs
     grade.c (nest-if ==> switch),
     shipclass.c (switch),
     date.c (switch),
     squareroots.c (while loop),
     sum.c (while loop),
     payroll.c (while loop),
   • COMPLICATED  example, (sort 3 numbers in decreasing order)
     to be discussed in discussion next week: big3.c
     
   • Reminder: The first midterm is on Jan 28, W.  Practice Midterm
   • Bilingual Example program: evenbilingual.c
   • Polylingual Example program (swithc): evenpoly.c
     
     
     
     
9. 1/25

• Solutions to assignment Homework 2 (p1 set)  (in tar format,  try "tar xvf p1.tar". Read "man tar" for details)
• Programs used class today: (save the linked file, and try "tar xvf jan25.tar")
• Homework #4. Due tuesday, Feb 3, midnight, submission instructions after the jump.
• Now available : midterm with solutions.
  

10.  2/2
• Examples used in class today: lect11-puzz1.c, lect11-puzz2.c, lect11-swap.c, pexamp1.c, sort.c:  tar file
  
• Another pair of examples: separate.c, sum_n_avg.c,
• And the next homework
• (For Submitting next, handin cs30b p5, due Feb 9th, at 11:59)
  
  
11. 2/4
• MOdular programming, more fancy kinds of subroutines/functions.
  
• Example: main.c and its subprograms scan_fraction.c,  get_operator.c,  add_fractions.c,  multiply_fractions.c, find_gcd..c,  reduce_fraction.c
• How to compile the above mess together: Use a makefile. Makefile
  
• Makefiles willbe covered in discussion section. DO NOT MISS!!!
  
  
12. 2/6
• Types, Type Conversions,
• Examples:  sizeof.c  posnumrange.c  inaccuracy.c
• Solutions to the previous homework (tar file)
• Examples/puzzles from class (tar file)
  
  
13. 2/9
    • Lecture/reading: More on Types (chapter 7)
    • Notes on Types
    • Example programs.
      
    • copyin2out.c
    • char-order.c
      col_seq.c
      length.c (getchar())
      length2.c
      expenses.c (enumerated type)
      
      
    • Homework #6 , due Feb. 16

14. 2/11
    • Lecture/reading: (1) More on types, (2) Function parameters (section 7.4), (3) Arrays (Chapter 8)
    • Notes on Arrays
    • Example programs. 
      week_hours.c (enumerated type)
      eval_fun.c (function parameter)
      bisection.c (application of function parameter)
      array1.c (arrays, basics)
      mean.c (arrays, basics)
      
    • The really big find the bad guy program and the geneg.c program that generates it (compile this, run it and see what happens!) ; and the much better much smarter version using arrays .

15. 2/13
    • Lecture/reading: Arrays (Chapter 8)
    • Notes on Arrays (updated)
    • Example Programs.
      fill_array.c
      fill_array2.c
      maxmin.c
      get_max.c
      add_arrays.c
      
    • More Programs.
      search.c
      select_sort.c
      
      
      
16. 2/18
    • add_matrices.c(multidimensional arrays)
    • Lecture/reading: Strings (Chapter 9)
    • Notes on Strings
    • String examples
      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

17. 2/20
    • Lecture/reading: Strings (Chapter 9) -- scanf vs. gets
    • String Examples
      lineinput_scanf.c (line scanning, ``whitespace'' issue)
      lineinput_gets.c (full line scanning)
    • 
      
      
      
18. 2/23
    
    
    • Answers for previous two homeworks. hw5 hw6
      
    • strings6.c (string comparison, and ordering)
      alphaorder0.c (string comparison and ordering using array of pointers)
      alphaorder.c
      
    • Next homework (Strings)
      
      
    • Midterm 2 Answers
19. 2/25
• Midterm Today.
  
  
20. 2/27
    
    • scanline1.c (getchar, putchar)
      scanline2.c (same function as scanline1.c, but uses char *)
      
    • Notes on Recursion
    • Example programs
      multiply.c (multiply_trace.c)
      factorial_rec.c (factorial_rec_trace.c)
      fibonacci.c
    • Midterm answers
21. 3/2
    • lecture/reading: Recursion (Chapter 10)
    • Notes on Recursion (updated)
    • Example Programs
      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 (on recursion)
      due March 9 23:59 handin cs30b p8

22. 3/4
    • 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
      
    • 
      
    • 
      

23. 3/6
    • 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 (partial).
      array_dyn.c (intro. to dynamic memory allocation, more later)
      
    • Practice final problems on strings, recursion, structure types and dynamic memory allocation.
24. 3/11
• Recursive Lists, example: print_list_rec.c, get_list_rec.c, list_rec_driver.c, find_list_rec.c
  
  
25. 3/13
• A more complete tarball with all the code. With apologies for the confusion about finding the position of an item on the list. The correct implementation is in the tarball (find_nth_rec.c). It's a bit confusing, but if you read it, you'll see what I'm doing; we'll also discuss it in class on Monday. Please look at the material in Chapter 14.4 on linked lists.