2CS21 - INTRODUCTION TO PROBLEM SOLVING BY COMPUTER I


1. Overview

Description: 2CS21 is the first year, semester one, programming and problem solving by computer course. The aim is to provide a comprehensive introduction to the software engineering of computer programs which produce solutions to problems. The development process is (ver broadly) divided into a number of steps: requirements, specification, implementation and system testing. Students will learn how to analyse problems and devise algorithms to produce solutions to problems, how to formally specify algorithms, how to implement such specifications and how to test and analyse the quality of the implementations. Problem analysis will concentrate on a top down approach. A number of specification techniques will be considered, but focusing on Nassi-Shneiderman charts and control flow diagrams. Implementations will be in the Ada high level computer programming language; thus the course will also provide a thorough overview of this language. Program quality testing and analysis techniques considered include: limit testing, boundary value analysis, arithmetic testing, path testing and loop testing. Throughout the course students will have the opportunity to design their own programs and to solve a variety of problems. A sophisticated set of web pages have been produced to support the course (http://www.csc.liv.ac.uk/~frans/2CS21/2cs21.html).

Teaching Method: Three lectures are given each week for the 12-week duration of the course. In addition, for one hour each week, students will work in a tutorial/practical setting under staff guidance.

Assessment: Assignments are carried out individually. Each assignment comprises a "stand-alone" problem which is to be addressed, using the software engineering approach taught on the course, to produce a computer generated solution. A grade will be returned for each assignment. The course is 100 % continuously assessed based on practical and attendance. All students will be required to obtain a satisfactory standard in the practical work so as to pass the course.


2. Lectures

The course comprises 36 lectures taught by Dr Frans Coenen (Room G33, ground floor, Chadwick Building) as follows:

WeekLecture topicsPractical
1 Introduction to computers, and the Unix operating system and programming languages.none
2 Software engineering, the mechanics of compilation and the Ada programming language. Tutorial 1: (non-assessed) The Unix operating system, WWW and text editing.
3 Data, introduction to data types, and program composition. Tutorial 2: (non-assessed) More Unix, CSNEWS, e-mail, compiling an Ada program.
4 Scope rules, range and precision, and type attributes and type conversion. Practical 1: (assessed) Giant letters program.
5 type declarations and subtypes, and the character type and Expressions and statements. Practical 2: (assessed) Geographic distance.
6 selection (if-else), top down analysis review and Selection (case). Practical 3: (assessed) Projectile distance.
7 for loop, `reverse' for loop (plus note on efficiency) and while loops and the exit statement. Practical 4: (assessed) Triangle recognition.
8 nested loops, recursion and Enumerated types. Practical 5: (assessed) Geometric progressions.
9 design and style review, parameter passing mechanisms and program errors and testing review. Practical 6: (assessed) Poisson probability.
10 compound data types and arrays, more on arrays and unconstrained arrays. Practical 7: (assessed) Quadratic equations.
11 strings, packages and Some sugested model answers to practical exercises. Practical 8: (assessed) Bubble sort.
12 Slippagenone

Lectures are timetabled as follows:

DAYTIMEROOM
Monday12:00B
Wednesday12:00A
Friday12:00A

and tutorials:

DAYTIMEROOM
Wednesday10:00, 11:00, 12:00, 14:00, 15:00 and 16:00First floor labs
Friday9:00, 10:00 and 11:00First floor labs

All lectures take place in the Science Faculty Lecture Block.


3. Practicals and Course Work

Lectures are supported by 10 x one hour practical sessions (one per week commencing in week 2 and ending in week 11). The first two will take the format of a tutorial. The remaining sessions are official times set aside for students to work on their assignments. There will be 8 assessed assignments. Practical sessions will take place in the Chadwick Building (ground or first floor labs). Practical sessions are timetabled by the course administrator Dr Martyn Amos and will be supervised by various members of the computer science staff.

Each student will be assigned a tutor and will be expected to attend one 1 hour tutorial per week and complete assessments in their own time. Details concerning tutor groups and the tutorials timetable will be made available at the end of week1. Practical sessions commence at the start of week2 (6th October). Each student is expected to spend at least 9 hours per week on 2CS21 related work - 3 hours formal lectures, 1 hour scheduled tutorial, 5 hours private study. To facilitate the latter computer labs are available outside tutorial times between 9:00 and 21:00 during term time. Do not enter a lab if it is being used for a tutorial (timetable outside every lab).


3.1. Presentation of course work

Completed practicals should be submitted to, and marked by, practical tutors.


3.2. Mark scheme

Course work will be marked on the scale of A through to F as follows:

MARKPERCENTAGE RANGE
A>= 85
B>= 70 to <85
C>= 60 to <70
D>= 50 to <60
E>= 35 to <50
F<35 (Fail)

A mark of A or B is commensurate with the standard required for a first class honours degree, C with a 2:1, D with a 2:2 and E with a 3rd. F is equivalent to a fail. In addition marks may be annotated with a `+' or `-'. Thus an A+ will indicate a standard equivalent to a top of the range first class honours degree, while an B- will indicate a bottom of the range first class honours degree. In the absence of such annotation students should assume that the mark indicates a middle of the range mark for the appropriate percentage category.


3.3. Late submission policy

Students who fail to hand in practicals on time will, under normal circumstances, be awarded a mark of 0 for that practical. If there is some extenuating circumstance whereby a student cannot hand in a practical on time than that student should approach his/her tutor. It is then up to the discretion of the tutor whether to mark the course work or not, and whether some penalty should be applied. (see also the departmental policy statement on late submission of Assessed Assignments.)


4. List of Example Problems

  1. Sum and Product - First Ada program, integer declarations, simple I/O, arithmetic expressions.
  2. Circle Calculation - Floating point numbers, constants.
  3. Cylinder Calculation - Templates to create new numeric I/O packages, Functions.
  4. Giant Ada - Strings, procedures.
  5. Pythagoras - Subtypes, using the GENERIC_ELEMENTARY_FUNCTIONS templates to create new mathematics packages (e.g. SQRT).
  6. 2D Geographic Distance - Mathematics packages, functions.
  7. Ada Attributes - Integer and floating point type attributes.
  8. Centigrade to Fahrenheit Conversion Programmer defined types and type conversion.
  9. Vertical Motion Subtypes.
  10. Lower to Upper Case Conversion - The character type (and its attributes).
  11. Sine, Cosine and Tangent - Trigonometric ratios.
  12. Power 4 - Selection, simple if statement.
  13. Linear Equation - Selection, if-else statement.
  14. Temperature Conversion - Nested if-else statements (also if-elsif-else).
  15. Calculator - Use of case statement.
  16. ASCII Code Output - For loop with constant end value
  17. Arithmetic Progression - For loop with variable end value.
  18. Factorial - Reverse For loop.
  19. Euler's number Approximation - While loop.
  20. Multiplication table - Nested for loops.
  21. Random number generator - While loops with and without exit.
  22. Decimal to binary conversion - Recursive procedures.
  23. Fibonacci sequence - Recursive functions.
  24. Temporal Reasoning - Use of enumerated types.
  25. Metres to Yards, Feet and Inches conversion - Simple constrained array.
  26. Set intersection - Comparing arrays.
  27. Pascals triangle - Unconstrained arrays.
  28. Password verification - String handling (character arrays).
  29. Spot the ball - user defined packages.

4.1. Additional example problems not included in the main body of the notes

  1. Temperature Conversion Plus - Use of case statement with selector of type integer.

5. References

  1. Jan Skansholm (1997). Ada 95 From the Beginning, 3rd Edition. Addison-Wesley.
  2. John Barnes (1996). Programming in Ada 95. Addison-Wesley.



Created and maintained by Frans Coenen. Last updated 11 October 1999