CSC204: Intro to Computer Science II

• CSC204: Introduction to Computer Science II builds upon CSC203 for students minoring in Computer Science.
• The course continues studying the C programming language and introduces writing reports using word processors.
• Programming is best learned by example, with labs serving as an essential course component.
• Students are strongly advised to actively understand the reason programs work.

Course Structure:

• Lectures are scheduled:
  • Tuesdays, 17:00 – 19:00 at Restau VI
  • Thursdays, 07:00 – 09:00 at CRB I 150 A
• Problem-solving exercises are incorporated into lectures, replacing formal tutorials.
• Students must register for laboratory groups.
• Examinations consist of 30% continuous assessment and 70% end-of-semester examination according to University regulations.
• End-of-semester examinations emphasize laboratory work to reward consistent effort.
• There will be at least one written test, with a possible second programming project or assignment.
• Students receive feedback on tests and can verify continuous assessment marks before final examinations.
• Missing a test requires an official letter to the Vice-Dean of the Faculty of Science within 72 hours, with supporting documents.
• Only medical reports from the University's medical doctor are considered for medical excuses, with final decisions made by the University Senate.
• Students are advised to read the University of Buea Students’ Guide, particularly the section on examination fraud to avoid issues.
• Examination fraud includes all forms of cheating aimed at unfairly influencing the score, not just during examinations.

Recommended Books:

• Computer science: An overview (7th ed.) by Brookshear, J. G. (2003)
• C by Dissection (4th ed.) by Kelley, A., & Pohl, I. (2000)
• The C programming language: ANSI C version by Kernighan, B., & Ritchie, D. (1988)

Course Outline:

• Techniques in program development
• Introductory Notions in Algorithms Design
  • Efficiency
  • Introduction to the analysis of algorithms
  • Correctness
  • Notion of proofs
• Flow of control in C
  • Branch construct revisited
  • Break and continue statements
  • Switch statement
  • The conditional operator
  • Iteration revisited
  • Arrays revisited
• Functions and Structured Programming
  • Use of functions in top-down design
  • Mathematical functions
  • Functions vs Macros
• Data types revisited
  • Fundamental Data Types
  • Conversions and Casts in C
  • Enumerated Types
  • User-defined types
• Character processing.
• Functions and pointers
  • Parameter passing
  • Scope of identifiers
  • Side effects
• Arrays and Pointers
• Strings and pointers
• Structures and Abstract Data Types
• Introduction to Recursion
• Simple Search and Sort Algorithms
• Introduction to File Processing
• Introduction to some major areas of Computer Science
  • Operating systems
  • Databases
  • Artificial intelligence
  • Computer Networks
  • Parallel Distributed Computing
  • Trends in Computer Architecture

Techniques in Program Development:

• Elegant programs are written using techniques to enhance programming style and design, especially useful for large projects.

Top-Down Design:

• Top-down design, or stepwise refinement, involves breaking down a large problem into smaller, manageable parts as part of the evolution of structured programming.
• The original problem is refined into easily coded sub-problems.
• The main program is written first, with complex tasks delegated to functions (procedures).
• Stubs can represent functions, allowing compilation and testing of the main program before functions are fully written.
• Stepwise refinement applies recursively to functions, breaking them into smaller sub-functions.

Advantages of Top-Down Approach:

• Division of a complex problem into smaller, easier sub-problems (divide and conquer).
• Enables independent work on modular parts, even if some parts are initially beyond the programmer's ability.
• Facilitates independent testing of functions, simplifying debugging.
• Allows planning of the program structure extensively before writing code.

Top-Down Design Example: Computing Class Average:

• A program to compute the class average for an exam uses a top-down design.
• Stage I, is the top level, involves determining the class average for the test.
• Stage II, is the first refinement, divides top level into smaller tasks:
  • Initialize variables.
  • Input, sum up, and count the number of grades.
  • Calculate and print the class average.
• Stage III, is the second refinement, breaks down each step from Stage II:
  • Running total and count of grades are needed - variables for average and individual grades are required.
  • Grades uses a loop to input each grade, as the exact number of grades is unknown.
  • A sentinel-controlled loop is suitable, with -1 as the sentinel value.
  • Two possibilities to calculate and print the class average are considered:
  • If at least one grade, computes the average.
  • Informs the user that "no grades were entered", avoiding division by zero.

Simplicity:

• Code should be easy to read and understand.
• Use the simplest possible approach to solve your problem.

Premature Optimization:

• Consider the trade-off between programming costs and program efficiency.
• Optimize when the time saved justifies the programmer's time.

Meaningful Identifier Names:

• Variable names should be informative to enhance understanding (e.g., avg instead of x).
• Function names should describe the function's purpose (e.g., read_data).

Documentation and Comments:

• Comments are key to explaining code statements and function.
• Act as documentation within the code.
• User manuals and technical documents are required for a complete project.

Program Readability:

• Indentation improves code readability and error detection:
  • Indent statements within a block.
  • Similarly indent blocks of code nested in other blocks.

Algorithmic Efficiency:

• An algorithm is a general method, whereas a program is its language-specific implementation.
• Efficiency measures a program's impact on computer resources.
• Time, measured by running time, is influenced by:
  • Computer language with source code.
  • Computer speed.
  • Compiler.
  • Operating system.
  • System load.
• Computer scientists prefer counting the number of steps proportional to running time.
• An algorithm with N/2 steps is twice as fast as one taking N steps.

Efficiency Example: Summing a Sequence of Numbers:

• First algorithm uses a loop.
• Second algorithm uses Gauss's formula i.e. (*sum of the first and last number) * N/2 to sum number series.

Number of Statements:

• The first algorithm involves N + 4 steps, proportional to N (linear).
• The second algorithm uses 4 statements, irrespective of N (constant).
• Gauss's algorithm is preferable for large N values.

Big O Notation:

• It expresses running time in terms of N.
• Constant multiples or smaller terms are ignored.
• Examples include:
  • O(1): Constant time
  • O(log₂N): Logarithmic time
  • O(N): Linear time
  • O(N²): Quadratic time
  • O(N³): Cubic time
  • O(2^N): Exponential time.
• Algorithms with exponential complexity are inefficient except for small N.
• Big O notation extends to the use of memory, i.e., space.

Correctness of Algorithms:

• Testing shows that a program works for a particular data set.
• Testing helps increase confidence that the program works correctly.

Examples of Testing Methods:

• Bench Testing: Programmer walks through their code with a small group.
• Static Analysis: Analyzers spot errors compilers miss.
• Trace Tools: Track variable changes to spot design problems.
• Data Testing: Generate test data automatically.

Notion of Proofs:

• Program proofs verify that a program will always produce correct results with assertions.
• Focus on the implementation through program proof.
• Correctness of machine code may not always obey the rules.