NB. For unanswered questions search for the string: ??? ------------------------------------------------------------------------------- UNIT CODE, NAME, ABBREVIATION FIT2004, Algorithms and Data Structures, ADS REASONS FOR INTRODUCTION Reasons for Introduction Define here the original reasons for the introduction of the unit The unit is part of a sequence of learning and practice about algorithms and data-structures. It is core content for Computer Science and for Software Engineering. It applies and further develops techniques for the design and analysis of algorithms and data-structure begun in level-1. Later core and elective units require its content as a prerequisite. Reasons for Change Define here the reasons for changing the unit Role of Unit Define here the role of the unit in the course(s) for which it is offered The unit is a core unit in Computer Science and Software Engineering. It comes after FIT1008 CSciA or FIT1015 CSciB ??? and before FIT3014 ADA ???. It is also a prequisite for FIT2??? and FIT3??? Relationship of Unit The unit requires prerequisite knowledge of introductory data structures and algorithms including arrays, records (structs, class), pointers (ref), linked lists, iteration, choice (if, case, switch), procedures, parameters, recursion, as found in the prerequisite units. It also requires prerequisite mathematical ability including logic (predicates, and, or, not, implication), proof, proof by contradiction, proof by induction, as indicated by the prerequisite of 12-points of maths. ??? Units FIT2??? and FI3??? require the unit as a prerequisite. The unit covers more advanced data structures and algorithms than its prerequisite and studies algorithms and data structures using techniques of a mathematical nature -- hence the math requirement. The most important part of the unit is the analysis and the problem-solving techniques covered, but in addition the algorithms and data structures introduced in the unit are part of the working computer scientist's of software engineer's toolkit. Relevance of Unit The "algorithm" is the central object of study in computer science. This unit equips people with tools for solving new computing problems -- those without existing text-book solutions. OBJECTIVES Statement of Objectives Those passing the subject will be able to solve new problems (those not having text-book solutions) with a computer, i.e. extract the abstract problem from a brief description of a real-world situation, design an efficient computer algorithm to solve the problem, analyse alternative algorithmic solutions in terms of correctness and best- averge- and worst-case, time- and space-complexity, and implement the selected algorithm as an efficient computer program in the designated computer programming language on the designated platform. Knowledge and Understanding (Cognitive Domain Objectives) Understanding of and the ability to make a 'formal argument' that a new algorithm and/or data-structure is correct or has such and such a complexity or some other property. Knowledge of and ability to use algorithmic paradigms such as divide and conquer, greedy, dynamic programming and so on, and the ability to identify these paradigms in diverse algorithms. Attitudes, Values and Beliefs (Affective Domain Objectives) Practical Skills (Psychomotor Domain Objectives) Ability to identify the key features of a brief informal problem description and abstract the underlying formal problem. Ability to invent a new solution for a new problem. Ability to make a formal argument about desirable properties of the solution. Ability to adapt an existing algorithm and/or data-structure where that is possible and appropriate. Relationships, Communication and TeamWork (Social Domain Objectives) Team work is not involved. The student will be able to make a 'formal argument' that an algorithm and/or data-structure is correct or has such and such a complexity or some other desirable property. UNIT CONTENT Classification Algorithms and Complexity (AL) Summary Handbook Summary Synopsis: Concepts and techniques fundamental to the science of programming. Topics include analysis of best-, average- and worst-case time- and space-complexity; introduction to numerical algorithms; recursion; advanced data structures such as heaps and B-trees; hashing; sorting algorithms; searching algorithms; graph algorithms; and numerical computing. Recommended Reading To be decided, but possibly: M. A. Weiss. Data Structures and Problem Solving Using Java. Addison Wesley, 2001. TEACHING METHODS Mode Lecture, tutorial, practical. Strategies of Teaching Teaching Methods Relationship to Objectives ASSESSMENT Strategies of Assessment Examination (3 hours): 70% (hurdle 1/2 marks) - Tutorial: 5%. Laboratory work: 25% (tute + lab hurdle 1/2 marks). If one or both hurdles are failed, the maximum possible result is 44%N. Assessment Relationship to Objectives Examination (3 hours): 70%. Tutorial + Laboratory work: 30%. The unit has an emphasis on the student 'doing': (i) extracting the abstract problem from a brief informal description, (ii) devising an algorithm and/or data-structure(s) to solve the abstract problem, (iii) analysing the correctness, time- and space-complexity and other properties of algorithms(s) and/or data-structure(s) for the problem, (iv) implementing the algorithm and/or data-structure(s) on a designated platform. All of these stages occur in the practical work. At least one practical will involve a new problem that is easy to state but that has a non-trivial solution. At least one practical will involve a graph problem. Assessment will consider . the elegance of the code, . pre- and post-conditions, invariants, . formal arguments for correctness and for time- and space-complexity, and . the actual time- and space-complexity of the implemented solution. The tutorial work covers the above steps (i) (ii) and particularly (iii). It also covers formal properties of algorithms and data-structures, and further algorithms and data-structures from the "toolkit", including manual simulations and examples, that time does not allow to be covered by practical work. WORKLOADS Credit Points 6 Workload Requirement Lab' week: Lectures: 2 hours, Lab: 3 hours, Tutorial: 1-hour, Private study: 6 hours. Non-lab' week: Lectures: 2 hours, Tutorial: 1 hour, Private study: 9 hours. RESOURCE REQUIREMENTS Lecture Requirements 2 x 1-hour lectures per week. Tutorial Requirements 1 x 1-hour tutorial per week. Laboratory Requirements 1 x 3-hour lab every other week, with extra unsupervised access to computers generally available. (But it might be that 2-hours per week would be better ??? ) It is important that the computers in the laboratories all be able to boot the designated software platform (see software requirements) quickly and reliably (and simultaneously) with no excessive delays. Access to required software (e.g. compilers, editors, etc.) must be fast and reliable. Access to, and saving of, a student's files onto stable long-term storage must be fast, reliable and, where possible, automatic. Sensible user "defaults" (file permissions, editor, shell, window manager, etc.) should be set and checked by the system administrators so as to provide a secure, usable and friendly environment, from the very first login, for even a novice user. The laboratory systems must be checked and stress-tested under realistic loads well before the semester begins. Staff Requirements Software Requirements Operating System: Linux ??? Text-based editors to be available: . vi . emacs Programming Languages, current versions of the following: . Sun Microsystems Java, with a "proper" compiler 'javac'. . Gnu C compiler 'gcc'. . Gnu Pascal compiler 'gpc' http://www.gnu.org/directory/GNU/GNUPascal.html . Glasgow Haskell compiler 'ghc' http://www.haskell.org/ghc/ . All required from week 1 of semester. Note that the unit itself is not about "Java" but it must use some designated computer and software platform. Both from choice and to fit in with other units, the main components of the platform are: Linux, Java. Library Requirements Teaching Responsibility (Callista Entry) Lloyd ALLISON Implications for CASPA Interfaculty Involvement Interschool Involvement Other Resource Requirements PREREQUISITES Prerequisite Units FIT10008 CSciA or FIT1015 CSciB Prerequisite Knowledge As for http://www.csse.monash.edu.au/courseware/cse2304/Open/Prereqs.html COREQUISITES PROHIBITIONS ALIAS TITLES LEVEL level-2 RESEARCH INTEREST This unit has no research component DATE OF INTRODUCTION 2007 FREQUENCY OF OFFERING ENROLMENT 150 (cse2304 had 160 in 2005 but I might guess 120 ???) LOCATION OF OFFERING Clayton 1st semester. (Will there be pressure for both semesters ???) Malaysia 1st semester. ??? ------------------------------------------------------------------------------- L.A., 24 Oct 2005 -------------------------------------------------------------------------------