CSCI 1320 - Principle of Algorithm Design I

Fall 2009

MWF 8:30-9:20am, 228 HAS
MWF 9:30-10:20am, 228 HAS

Professor: Yu Zhang Office: 201H HAS Phone: 7399 Email: yzhang@cs.trinity.edu Help Session Hours: Tuesday and Thursday 3:45-5:45pm, 200 HAS, or by appointment TA: Xin Ma xma@trinity.edu

Course Pre-requisites

None.

Textbook

Forouzan and Gilberg, Computer Science: A Structured Programming Approach Using C, Third Edition, Thomson Course Technology, 2005.

Supplemental Readings

Schildt, C the Complete Reference, McGraw Hill, 2000, Fourth Edition.

Course URL

http://www.cs.trinity.edu/~yzhang/teaching/fall2009/CSCI1320/.

Goals of This Course

  1. To understand organization and characteristics of computer science.
  2. To learn fundamental problem solving methodology.
  3. To apply problem solving techniques to algorithm design.
  4. To build abstractions with procedures and data.
  5. To develop good programming habits.
  6. To learn programming in the C computer language.

At the end of this course you should

  1. Be able to describe basic concepts, nomenclature, and history of computers and computing.
  2. Be able to solve simple problems with a computer, using math and science skills.
  3. Understand and be able to implement software design principles, including abstraction, modularity, data representation, and portability.
  4. Be able to properly document program code.
  5. Be able to describe and implement software engineering concepts, including requirements definition, analysis, design, implementation, testing, and maintenance considerations.
  6. Be able to development and execute computer programs using structured techniques.

Email and WWW

We will be using an email list this semester to communicate pertinent messages to everyone in the class. I will put together the list of email addresses in the first two weeks of class. It is the student's responsbility to ensure that they watch for and read any messages throughout the semester. In addition, this web page will continually be updated with the class schedule, resources, and other information.

Late Turn-in Policy

The penalty for late assignments will be -10% per day (determined on a 24-hour basis relative the due-time, which is the start of class ), down to a minimum of 50% (you can still get 1/2 credit if you turn it in by the end of the semester).

Exams

There will be 6-7 homeowrk assignments, and several quizzes which will be given randomly in class.
There will be two mid-term exams (approximately in the early week of October and the early week of November) plus a comprehensive final.

Grades will be determined by the percentage of total points earned during the course of the semester. The total points will be computed according to the following approximate weighting scheme, though it is subject to slight adjustment as appropriate:

Homework Assignment 30%
Two Midterm Exams 30%
Final Exam 20%
Quiz 20%

Grade Curving

The top 20% of students will get an A.
The next 10% will get a A- or B+.
The next 30% will get a B or B-.
The next 25% will get a C+, C or C-.
The next 15% will get a D+, D or F.

Attendance Policy

Lecture attendance is encouraged, but will not be used for grades. Unavoidable absences are understood, but each student is responsible for any missed material. For excused absences, an opportunity will be provided to make up any graded work that was missed. For unexcused absences, a grade of zero will be assigned for in-class assignment. Missed exams will be rescheduled without penalty for an excused absence, or with a 25% penalty if the absence is not excused. If you are going to be absent when an assignment is due you should try to turn in the assignment early. If that is not possible, be sure to include a request for an extended turn-in time in your e-mail.

To request approval of an absence or late turn-in, send me an e-mail explaining the reason prior to the class or due date. Tell me if you believe it is a university excused absence. If advance notification is not possible (e.g. unexpected illness) send the e-mail within 48 hours of the absence and be sure to explain why you were not able to notify me in advance. For illness, follow-up the e-mail by submitting a note from a doctor or clinic to my office.

Miscellaneous Notes

All students are covered by Academic Honor Code. Do not copy anybody else's homework assignments, exams, quizes, source codes, and any material used in previous semesters. You are welcome to talk with each other about homework programs unless otherwise specified, but do not turn in syntactically similar work. Cheating will be dealt with according to the university's policies on academic integrity.

If you have a documented disability and will need accomodations in this class, please speak with me privately early in the semester so I may be prepared to meet your needs. If you have not already registered with Disability Services for Students, contact the office at 999-7411. You must be registered with DSS before I can provide accommodations.

Tentative Schedule

The following is a planning schedule. It may be modified as necessary during the semester. Students will be expected to have some familiarity with the material in the schedule at the beginning of the lecture.

Week of Topic Forouzan and Gilberg
8/23 Introduction.
8/30 Basic Unix Commands Handout
9/6 Numeration Systems and Data Representation Appendix D
9/13 Solving Problem by C - An Overview Ch 1, Ch 2
9/20 Operators and Expressions Ch 3.1-3.4, 5.1
9/27 Basic Data Types Ch 2.4, 3.5, 5.4
10/4 Review and Midterm 1.
10/11 Flow of Control Ch 5, 6
10/18 Functions Ch 4
10/25 Pointers Ch 9
11/1 Review and Midterm 2.
11/8 Arrays, Strings, Sorting and Searching Ch 8, 10.1-10.4, 11
11/15 Stuctures Ch 12
11/22 File I/O Ch 13
11/29 Review and Final Exam .

Calendar

Details about lectures, homework assignments, exams etc. are added here.

Monday Tuesday Wednesday Thursday Friday






8/28
Go over syllabus.
8/31
Useful Linux commands.
Basic Computer Skills.
VI Manual.
Pico Manual.
Summary of Linux Commands.
Dr. Massingill's Unix/Linux links.
 9/1
First help session 3:45-5:45pm at 200. 		9/2
Numeration Systems (Appendix D).
Decimal numbers.
Binary numbers.
Octal numbers.
Hexadecimal numbers.
Conversion Algorithms and Addition Algorithm.
 9/3
Last day for Add/Drop. 		9/4
Addition (Appendix D).
9/7
Labor Day (no class). 		9/8
9/9
Quiz 1 key.
Data Representation (Appendix D).
Notes of 2's Complement.
HW1 Assignment.
 9/10
9/11
Solving Problem on Computers (Ch 1.5).
-Modular Design.
-Algorithm Development.
-Software Life Cycle.
9/14
Quiz 2 key: Calculating Travel Time.
Programming in C - an overview (Ch 1, 2, 3).
Why C?
Lexical elements.
- Keywords
- Identifers
- Constants
- Operators
- Punctuators
 9/15
9/16
HW1 is due.
Compilations.
The Hello World Program.
Preprocessor directives.
Main function.
HW2 Assignment.
travel.c (the initial version).
Homework Instructions.
 9/17
9/18
Quiz 3 key.
Algorithm for Hesperus.
The Hesperus Program.
Declaration, assignment and initialization.

Monday Tuesday Wednesday Thursday Friday
9/21
Formatted I/O (scanf and printf).
 9/22
9/23
Operators and expressions (Ch 3.1-3.4, 5.1).
-Precedence and associativity.
-Increment and decrement operators.
-Relational and logical operators.
-Assignment operator.
-Expression and statement.
9/24
9/25
HW2 is due.
No class.
9/28
Quiz 4 key.
Basic Data Types (Ch 2.4, 3.5, 5.4).
char.
char vs. int.
All data types defined by the C standard.
HW3 Assignment.
 9/29
9/30
int, float, double.
Compile-time operator sizeof.
Coversions.
Cast.
10/1
10/2
Mid-term1 Example Questions.
10/5
Mid-term1 Key.
10/6
10/7
Flow of control (ch 5, 6).
Selection.
-If statement.
An example program of if-else: Calculating Salary.
10/8
10/9
HW3 is due.
HW4 Assignment.
An example program of if-else ladders: Calculating Bonus.
-Switch statement.
An example program of switch: Spelling Checking.
10/12
Quiz 5 key.
How to solve HW4?
Iteration.
-For loop.
 10/13
10/14
-While loop.
-Do-while loop.
An example of nested for: Three-layer Nested For.
 10/15
 10/16
Fall Break (no class).

Monday Tuesday Wednesday Thursday Friday
10/19
Quiz 6 key.
Jump.
Break statement.
An example of break: Break a For Loop.
Another example of break: Break a Nested For Loop.
Continue statement.
An example of continue: Shifting Characters.
Functions (Ch 4).
10/20
10/21
HW4 is due.
HW5 assignment.
Function definition.
Function variables.
An example program of using Local Variables in One Function.
An example program of using Local Variables in Multi-Function.
An example program of using Global Variables in Multi-Function.
Function parameters.
Function scope.
10/22
10/23
HW5 Design.
Function Invocation.
- Call by Value. An example program of Call By Value.
- Call by Reference.
Function prototypes.
Return values.
10/26
Quiz 7 key.
Recursion.
An example program of Factorial Function.
An example program of Recursive Factorial Function.
Pointers (Ch 9).
Why and what?
10/27
10/28
Pointer Operators.
Pointer Assignment.
An example program of Pointer Assignment.
Pointer Initialization.
Pointer Arithmetic.
10/29
Last day for Withdraw.
10/30
HW5 is due.
HW6 Assignment.
HW6 Design.
Call By Reference.
An example program of CBR: Swapping Two Integers.
Sample code of applying CBR in HW6 days.c.
11/2
Quiz 8 key.
Mid-term2 review.
11/3
11/4
Mid-term2.
11/5
11/6
Mid-term2 key.
11/9
Arrays and Strings [Ch 8 (Arrays), Ch 10.1-10.4 (Arrays & Pointers), Ch 11 (Strings)].
Array Definition.
Array Initialization.
Relationship Between Arrays and Pointers.
 11/10
11/11
Passing Arrays to Functions.
An example program of Passing Array to Fucntions (CBR) .
Dynamic Memory Allocation.
An example program of Dynamic Memory Allocation .
 11/12
11/13
HW6 is due.
HW7 assignment.
Strings.
String-Handling Functions.
An example program of using String Handling Functions .

Monday Tuesday Wednesday Thursday Friday
11/16
Quiz 9.
Explain HW7.
11/17
11/18
Structures (Ch. 12).
Structure declaration.
Structure assignment.
An example program of Structure Assignment .
 11/19
11/20
Passing Structures to Fucntions.
An example program of Passing Structures to Functions (CBV) .
Structure pointers.
An example program of Passing Structures to Functions (CBV & CBR) .
Typedef.
11/23
HW7 is due.
Quiz 10.
11/24
11/25
No class.
11/26
11/27
Thanksgiving (no class).
11/30
Final exam review.
12/1
12/2
Q&A (no class).
12/3
Last help session 3:45-5:45pm at 200.
Final due day for all assignments by 5:45pm.
12/4
Final Exam.

Last updated: Tuesday, August 26, 2009 by Yu Zhang.